Решаем судоку на JavaScript

СудокуСудоку — популярная головоломка, основной задачей которой является размещение цифр в правильном порядке.

Игровое поле представляет собой квадрат 9х9 клеток. Клетки сгруппированы в девять сегментов 3х3. В каждой клетке может быть записана цифра от одного до девяти. Основным правилом судоку является то, что цифра не может повторяться в строке, столбце и сегменте.

Под катом приводится алгоритм решения судоку, реализованный на JavaScript. Рассмотрены только базовые тактики решения головоломки, но этого достаточно для большого числа судоку легкого и среднего уровня.

Основная идея


Ячейка на поле может иметь одно из трех состояний:
  • in — значение определено изначально
  • unknown — значение не определено
  • solved — значение найдено
Для каждой нерешенной ячейки хранится массив предполагаемых значений, которые она может принять (кандидатов). Чтобы решить судоку достаточно поочередно перебирать нерешенные ячейки и уменьшать количество кандидатов в каждой из них. Если количество кандидатов сокращается до одного, то значение ячейки найдено и ей присваивается статус solved.

Поиски решения заканчиваются, если после перебора всех нерешенных ячеек ни для одной из них не удалось найти решение или не было изменено количество кандидатов:
/**
* Решение судоку
*
* Метод в цикле пытается решить судоку, если на текущем этапе не изменилось
* ни одного элемента, то решение прекращается.
*/
function solve() {
  var changed = 0;
  do {
    // сужаем множество значений для всех нерешенных чисел
    changed = updateSuggests();
    steps++;
    if ( 81 < steps ) {
      // Зашита от цикла
      break;
    }
  } while (changed);
}; // end of method solve()
 
/**
* Обновляем множество предположений
*
* Проверяем основные правила -- уникальность в строке, столбце и секции.
*/
function updateSuggests() {
  var changed = 0;
  var buf = arrayDiff(solved[1][3][2], rowContent(1));
  buf = arrayDiff(buf, colContent(3));
  buf = arrayDiff(buf, sectContent(1, 3));
  for ( var i=0; i<9; i++) {
    for ( var j=0; j<9; j++) {
      if ( 'unknown' != solved[i][j][1] ) {
        // Здесь решение либо найдено, либо задано
        continue;
      }
      // "Одиночка"
      changed += solveSingle(i, j);
      // "Скрытый одиночка"
      changed += solveHiddenSingle(i, j);
    }
  }
  return changed;
}; // end of method updateSuggests()

Реализация алгоритма


Есть много способов решения судоку, но в целях демонстрации рассмотрим два наиболее простых метода: «Одиночка» и «Скрытый одиночка». Это базовые методы решения судоку и они отлично подходят для изучения основных принципов.

Метод «Одиночка» основывается непосредственно на правилах судоку: любая цифра может встречаться только один раз в строке колонке и сегменте. С точки зрения алгоритма это означает, что из списка кандидатов ячейки будут вычеркиваться все найденные числа из ее строки, столбца и сегмента.
/**
* Метод "Одиночка"
*/
function solveSingle(i, j) {
  solved[i][j][2] = arrayDiff(solved[i][j][2], rowContent(i));
  solved[i][j][2] = arrayDiff(solved[i][j][2], colContent(j));
  solved[i][j][2] = arrayDiff(solved[i][j][2], sectContent(i, j));
  if ( 1 == solved[i][j][2].length ) {
    // Исключили все варианты кроме одного
    markSolved(i, j, solved[i][j][2][0]);
    return 1;
  }
  return 0;
}; // end of method solveSingle()

Метод «Скрытый одиночка» использует правило: если среди кандидатов в строке/столбце/сегменте отдельная цифра встречается только в одной ячейке, то значение этой ячейки и будет равняться такой цифре.
/**
* Метод "Скрытый одиночка"
*/
function solveHiddenSingle(i, j) {
  var less_suggest = lessRowSuggest(i, j);
  var changed = 0;
  if ( 1 == less_suggest.length ) {
    markSolved(i, j, less_suggest[0]);
    changed++;
  }
  var less_suggest = lessColSuggest(i, j);
  if ( 1 == less_suggest.length ) {
    markSolved(i, j, less_suggest[0]);
    changed++;
  }
  var less_suggest = lessSectSuggest(i, j);
  if ( 1 == less_suggest.length ) {
    markSolved(i, j, less_suggest[0]);
    changed++;
  }
  return changed;
}; // end of method solveHiddenSingle()
 
/**
* Минимизированное множество предположений по строке
*/
function lessRowSuggest(i, j) {
  var less_suggest = solved[i][j][2];
  for ( var k=0; k<9; k++ ) {
    if ( k == j || 'unknown' != solved[i][k][1] ) {
      continue;
    }
    less_suggest = arrayDiff(less_suggest, solved[i][k][2]);
  }
  return less_suggest;
}; // end of method lessRowSuggest()
 
/**
* Минимизированное множество предположений по столбцу
*/
function lessColSuggest(i, j) {
  var less_suggest = solved[i][j][2];
  for ( var k=0; k<9; k++ ) {
    if ( k == i || 'unknown' != solved[k][j][1] ) {
      continue;
    }
    less_suggest = arrayDiff(less_suggest, solved[k][j][2]);
  }
  return less_suggest;
}; // end of method lessColSuggest()
 
/**
* Минимизированное множество предположений по секции
*/
function lessSectSuggest(i, j) {
  var less_suggest = solved[i][j][2];
  var offset = sectOffset(i, j);
  for ( var k=0; k<3; k++ ) {
    for ( var l=0; l<3; l++ ) {
      if ( ((offset.i+k) == i && (offset.j+l) == j)|| 'unknown' != solved[offset.i+k][offset.j+l][1] ) {
        continue;
      }
      less_suggest = arrayDiff(less_suggest, solved[offset.i+k][offset.j+l][2]);
    }
  }
  return less_suggest;
}; // end of method lessSectSuggest()

Использование


Весь код оформлен в виде класса Sudoku. Для решения головоломки необходимо создать экземпляр класса, передать в него условие задачи и вызвать метод solve(). Результат решения выводится методом html(), который возвращает отформатированный таблицу и количество проходов, которое потребовалось для поиска решения. Если решение не может быть найдено, то будет выведена таблица найденных результатов и по наведению курсора на пустые ячейки будет показываться список кандидатов.

Исходные значения задаются целочисленной матрицей 9х9. В ячейках записывается «0», если значение не определено и число иначе.
var in_val = [
  [0, 0, 3, 0, 0, 8, 2, 0, 4],
  [0, 2, 0, 0, 6, 4, 0, 1, 0],
  [9, 0, 0, 0, 0, 0, 0, 0, 8],
  [0, 8, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 6, 9, 8, 0],
  [0, 0, 0, 0, 0, 0, 5, 0, 0],
  [0, 0, 4, 9, 0, 7, 0, 3, 0],
  [8, 0, 0, 0, 0, 1, 0, 0, 0],
  [0, 7, 0, 0, 5, 0, 4, 0, 0]
];
 
var sudoku = new Sudoku(in_val);
document.write(sudoku.html());

Результат работы алгоритма выглядит так:

Результат работы алгоритма

Исходный код класса Sudoku, а также несколько примеров задач доступны по этой ссылке.

Ссылки


Судоку [Википедия]
Как решать судоку: способы, методы и стратегия

UPD Пользователь rozboris любезно создал демку

UPD 2 Реализован обратный поиск. Теперь решает все судоку. И новая демка от rozboris.

UPD3 Так как ссылки в статье умерли, выложил исходники на Google Code.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 28

    +1
    Вместо unknown лучше бы стоило использовать спец значение undefined.
      0
      Да, можно было использовать и unknown, но хотелось однообразия в типах. Т.е. статус — это всегда строка.
      0
      Вот ещё забавная решалка на JS: blgo.ru/games/sudoku/ не всё решает, правда.
        +2
        Сделайте страницу с демкой, если можете.
          0
          Сегодня не обещаю, сейчас реализовано только решение судоку, возможность создания и редактирования отсутствует как класс.
            +4
            Вот, сделал на скорую руку: bit.ly/testSudoku
            Сорри за говнокод, но потестить можно.
            0
            По хорошему, следовало бы добавить ситуации «некоторые K цифр могут встретиться только в K клетках столбца/строки/блока — тогда в этих клетках могут всетретиться только эти цифры, а остальные не могут». При K=1 это дает «скрытого одиночку», а при K=F-1, где F — число неразгаданных клеток блока, — «одиночку». Но, к сожалению, даже этот прием не позволяет решить все. Без перебора не обойтись :(
              0
              По второй ссылке, приведенной в конце статьи, есть еще несколько методов решения судоку, но их реализация раздула бы код и уменьшила его наглядность. Хотя при желании все их можно реализовать ;)
                0
                Да, наверное. Но разве один метод (поиск скрытого блока — перебором всех подмножеств) по сравнению с двумя — это «раздутый код»?
                  0
                  Каждый небазовый метод дает эффект только на ограниченном множестве ситуаций. Использованные «Одиночка» и «Скрытый одиночка» универсальны и решают задачи простого и среднего уровней.

                  Более сложные алгоритмы известны и подробно описаны, поэтому их кодинг не доставит удовольствия создания чего-то нового.
                    0
                    А Вы что, читаете описание алгоритмов??? Тогда, конечно, никакого удовольствия… А если не читать, то всегда есть шанс, что получится что-то новое.
                      0
                      Как там Ньютон говорил? «Если я видел дальше других, то потому, что стоял на плечах гигантов». Всегда полезно знать, до чего додумались коллеги по цеху. Это может натолкнуть и на новые идеи, которые могли бы быть пропущены в попытках решения давно преодоленных задач.

                      Изобретение велосипедов весело и интересно, и даже полезно для самообразования. Показанные алгоритмы я восстановил просто вспоминая, как я решал судоку, но потом решил посмотреть, что же народ напридумывал. И оказалось, что мои «изобретения» даже имя имеют!!! И есть множество других способов решения головоломки, для формализации которых потребуется много задачек перерешать.
              +1
              >Поиски решения заканчиваются, если после перебора всех нерешенных ячеек ни для одной из них не удалось найти решение или не было изменено количество кандидатов

              На этом этапе хорошо было бы не заканчивать поиск, а начинать применять поиск с возвратом.
                0
                А что вы подразумеваете под «поиском с возвратом»?
                  0
                  Поиск с возвратом.

                  Применительно к данной задаче:
                  Когда не осталось явных решений, в каждой ячейке стоит 2 и более вариантов, и «скрытых одиночек» тоже не получается найти, то берётся одна из ячеек, в неё наугад ставится один из возможных вариантов, после чего «заседание продолжается» по приведённым в топике алгоритмам. Если на каком-то этапе приходим к противоречию, то нужно вернуться на шаг выбора варианта и попробовать следующий.
                    0
                    Я думал над этим. Даже пробовал ручной просчет на нерешаемой задаче (в архиве этот вариант помечен как unsolved). Но получалось слишком много уровней ветвлений, т.е. пришлось бы делать многоуровневое сохранение состояний и возможностью отката на каждое из них.

                    Как-то некрасиво это смотрится… не элегантно… Учитывая, что остались еще в запасе нереализованные непрямые алгоритмы.
                      +1
                      >Но получалось слишком много уровней ветвлений, т.е. пришлось бы делать многоуровневое сохранение состояний и возможностью отката на каждое из них.

                      Откатываться нужно не на каждое, а только на предыдущее. И не нужно нигде вручную ветвиться — рекурсия всё сделает за вас. Всё, что вам нужно — «клонировать» текущее состояние, после чего подставить один из возможных вариантов и вызывать вашу основную функцию solve() на этой матрице.
                      Функция завершилась успешно? Всё, вот оно, решение. Завершилась неудачей? Пробуем следующий вариант и снова вызываем.
                      Если подобная «неопределённость» возникнет ещё раз, то она будет разрешена аналогичным образом без какого-либо дополнительного вмешательства.

                      Уж не знаю, каковы у вас критерии «элегантности», но при той реализации, как её вижу я, понадобится добавить строк 20, не больше.
                        0
                        > Всё, что вам нужно — «клонировать» текущее состояние, после чего подставить
                        > один из возможных вариантов и вызывать вашу основную функцию solve() на этой матрице.
                        > Функция завершилась успешно? Всё, вот оно, решение. Завершилась неудачей? Пробуем
                        > следующий вариант и снова вызываем.

                        Не совсем так. Предположим, алгоритм застопорился в бессилии. Находим ячейку с двумя кандидатами. Выбираем первого, прогоняем solve() — решение не найдено. Выбираем второго, и снова решения нет. Переходим ко второму уровню. Берем первого кандидата и снова гоним алгоритм до точки, среди пустых- ячеек снова ищем ячейку с минимальным количеством кандидатов и начинаем их перебирать. И так далее. в ручном режиме я прошел три уровня и так и не добился полного решения. Да все это можно завернуть в рекурсию и гонять ее по всему дереву предположений в надежде найти решение. В худшем случае решение будет мало отличаться от полного перебора.

                        > Уж не знаю, каковы у вас критерии «элегантности»
                        Одним из критериев элегантности я считаю вычислительную сложность алгоритма и полный перебор ну никак этому критерию не соответствует.
                          +1
                          >Предположим, алгоритм застопорился в бессилии. Находим ячейку с двумя кандидатами. Выбираем первого, прогоняем solve() — решение не найдено. Выбираем второго, и снова решения нет.

                          «Решения нет» — это «найдено противоречие» или «снова застопорились»?
                          Если первое — тогда всё, решения действительно нет. Если второе — то алгоритм сделает следующее предположение рекурсивно, никуда «руками» идти не нужно.

                          >Да все это можно завернуть в рекурсию и гонять ее по всему дереву предположений в надежде найти решение. В худшем случае решение будет мало отличаться от полного перебора.

                          Ну, не скажите. После каждого рекурсивного вызова снова гоняются поиски одиночек и скрытых одиночек, что значительно сокращает количество вариантов перебора, так что даже на повышенных уровнях сложности рекурсия не заберётся дальше 2-3-5 уровней. Это я вам говорю как человек, который несколько месяцев подряд развлекался судоку ежевечерне при укладывании дочки спать :)

                          >Одним из критериев элегантности я считаю вычислительную сложность алгоритма и полный перебор ну никак этому критерию не соответствует.

                          Как я уже сказал выше, о полном переборе речи не идёт. На реальных задачах будет не больше полудесятка рекурсивных вызовов. Ну а синтетику, разумеется, можно подогнать какую угодно :)

                          В общем, моё дело предложить, а решать уже вам.
                            0
                            На пустом поле перебор с возвратом (после поиска открытых и скрытых блоков любого размера) потребовал 47 развилок. Точнее, «перебором с возвратом» ее назвать трудно — первая же ветка дала ответ. На первой попавшейся «головоломке для гениев» было достаточно одной развилки.
                            Сам перебор (с поиском оптимальной клетки — где меньше всего возможностей) занял 20 строк, а вся программа меньше 100 (на C#).
                              0
                              Спасибо, ч.т.д.
                              Даже с количеством строк не ошибся :)
                                +1
                                Реализовал обратный поиск. У меня на него ушло 99 строк с комментариями :). Код выложен здесь.
                0
                Именно такая логика была у меня, когда делал AISudokusolver.com. У Кнута есть алгоритм «Dancing Links», реализацию которого для решения судоку не сложно найти. Скорость решения составляет тысячи решений судоку на не самом лучшем компьютере.
                  0
                  Лучше назвать этот метод так, как он всегда назывался, а именно поиск в глубину )
                    0
                    У нас был именно как «поиск с возвратом» :)
                  +3
                  Вам надо бы познакомиться с битовыми масками.
                  Тогда не было бы трехмерных массивов, функции lessRowSuggest и т.п. стали бы гораздо короче,
                  а arrayDiff записалась бы в ОДНУ операцию!
                  Можете сравнить с моим решением на Java.
                    0
                    Когда хотело подружиться с питоном, взялся написать решатель какуро. Там похожие алгоритмы, но почему-то не все какуро решались, но интерес у меня уже пропал и я забросил это дело.
                    Вот что вышло:
                    pastebin.com/DmNBg7pp

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое