Судоку — популярная головоломка, основной задачей которой является размещение цифр в правильном порядке.Игровое поле представляет собой квадрат 9х9 клеток. Клетки сгруппированы в девять сегментов 3х3. В каждой клетке может быть записана цифра от одного до девяти. Основным правилом судоку является то, что цифра не может повторяться в строке, столбце и сегменте.
Под катом приводится алгоритм решения судоку, реализованный на JavaScript. Рассмотрены только базовые тактики решения головоломки, но этого достаточно для большого числа судоку легкого и среднего уровня.
Основная идея
Ячейка на поле может иметь одно из трех состояний:
- in — значение определено изначально
- unknown — значение не определено
- 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.
