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

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

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

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

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

Ячейка на поле может иметь одно из трех состояний:

• in — значение определено изначально
• unknown — значение не определено
• solved — значение найдено

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

Поиски решения заканчиваются, если после перебора всех нерешенных ячеек ни для одной из них не удалось найти решение или не было изменено количество кандидатов:

1. /**
2. * Решение судоку
3. *
4. * Метод в цикле пытается решить судоку, если на текущем этапе не изменилось
5. * ни одного элемента, то решение прекращается.
6. */
7. function solve() {
8.   var changed = 0;
9.   do {
10.     // сужаем множество значений для всех нерешенных чисел
11.     changed = updateSuggests();
12.     steps++;
13.     if ( 81 < steps ) {
14.       // Зашита от цикла
15.       break;
16.     }
17.   } while (changed);
18. }; // end of method solve()
19.  
20. /**
21. * Обновляем множество предположений
22. *
23. * Проверяем основные правила -- уникальность в строке, столбце и секции.
24. */
25. function updateSuggests() {
26.   var changed = 0;
27.   var buf = arrayDiff(solved[1][3][2], rowContent(1));
28.   buf = arrayDiff(buf, colContent(3));
29.   buf = arrayDiff(buf, sectContent(1, 3));
30.   for ( var i=0; i<9; i++) {
31.     for ( var j=0; j<9; j++) {
32.       if ( 'unknown' != solved[i][j][1] ) {
33.         // Здесь решение либо найдено, либо задано
34.         continue;
35.       }
36.       // "Одиночка"
37.       changed += solveSingle(i, j);
38.       // "Скрытый одиночка"
39.       changed += solveHiddenSingle(i, j);
40.     }
41.   }
42.   return changed;
43. }; // end of methos updateSuggests()

* This source code was highlighted with Source Code Highlighter.

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

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

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

1. /**
2. * Метод "Одиночка"
3. */
4. function solveSingle(i, j) {
5.   solved[i][j][2] = arrayDiff(solved[i][j][2], rowContent(i));
6.   solved[i][j][2] = arrayDiff(solved[i][j][2], colContent(j));
7.   solved[i][j][2] = arrayDiff(solved[i][j][2], sectContent(i, j));
8.   if ( 1 == solved[i][j][2].length ) {
9.     // Исключили все варианты кроме одного
10.     markSolved(i, j, solved[i][j][2][0]);
11.     return 1;
12.   }
13.   return 0;
14. }; // end of method solveSingle()

* This source code was highlighted with Source Code Highlighter.

Метод «Скрытый одиночка» использует правило: если среди кандидатов в строке/столбце/сегменте отдельная цифра встречается только в одной ячейке, то значение этой ячейки и будет равняться такой цифре.

1. /**
2. * Метод "Скрытый одиночка"
3. */
4. function solveHiddenSingle(i, j) {
5.   var less_suggest = lessRowSuggest(i, j);
6.   var changed = 0;
7.   if ( 1 == less_suggest.length ) {
8.     markSolved(i, j, less_suggest[0]);
9.     changed++;
10.   }
11.   var less_suggest = lessColSuggest(i, j);
12.   if ( 1 == less_suggest.length ) {
13.     markSolved(i, j, less_suggest[0]);
14.     changed++;
15.   }
16.   var less_suggest = lessSectSuggest(i, j);
17.   if ( 1 == less_suggest.length ) {
18.     markSolved(i, j, less_suggest[0]);
19.     changed++;
20.   }
21.   return changed;
22. }; // end of method solveHiddenSingle()
23.  
24. /**
25. * Минимизированное множество предположений по строке
26. */
27. function lessRowSuggest(i, j) {
28.   var less_suggest = solved[i][j][2];
29.   for ( var k=0; k<9; k++ ) {
30.     if ( k == j || 'unknown' != solved[i][k][1] ) {
31.       continue;
32.     }
33.     less_suggest = arrayDiff(less_suggest, solved[i][k][2]);
34.   }
35.   return less_suggest;
36. }; // end of method lessRowSuggest()
37.  
38. /**
39. * Минимизированное множество предположений по столбцу
40. */
41. function lessColSuggest(i, j) {
42.   var less_suggest = solved[i][j][2];
43.   for ( var k=0; k<9; k++ ) {
44.     if ( k == i || 'unknown' != solved[k][j][1] ) {
45.       continue;
46.     }
47.     less_suggest = arrayDiff(less_suggest, solved[k][j][2]);
48.   }
49.   return less_suggest;
50. }; // end of method lessColSuggest()
51.  
52. /**
53. * Минимизированное множество предположений по секции
54. */
55. function lessSectSuggest(i, j) {
56.   var less_suggest = solved[i][j][2];
57.   var offset = sectOffset(i, j);
58.   for ( var k=0; k<3; k++ ) {
59.     for ( var l=0; l<3; l++ ) {
60.       if ( ((offset.i+k) == i && (offset.j+l) == j)|| 'unknown' != solved[offset.i+k][offset.j+l][1] ) {
61.         continue;
62.       }
63.       less_suggest = arrayDiff(less_suggest, solved[offset.i+k][offset.j+l][2]);
64.     }
65.   }
66.   return less_suggest;
67. }; // end of method lessSectSuggest()

* This source code was highlighted with Source Code Highlighter.

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

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

Исходные значения задаются целочисленной матрицей 9х9. В ячейках записывается "0", если значение не определено и число иначе.

1. var in_val = [
2.   [0, 0, 3, 0, 0, 8, 2, 0, 4],
3.   [0, 2, 0, 0, 6, 4, 0, 1, 0],
4.   [9, 0, 0, 0, 0, 0, 0, 0, 8],
5.   [0, 8, 0, 0, 0, 0, 0, 0, 0],
6.   [0, 0, 0, 0, 0, 6, 9, 8, 0],
7.   [0, 0, 0, 0, 0, 0, 5, 0, 0],
8.   [0, 0, 4, 9, 0, 7, 0, 3, 0],
9.   [8, 0, 0, 0, 0, 1, 0, 0, 0],
10.   [0, 7, 0, 0, 5, 0, 4, 0, 0]
11. ];
12.  
13. var sudoku = new Sudoku(in_val);
14. document.write(sudoku.html());

* This source code was highlighted with Source Code Highlighter.

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

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