Судоку — популярная головоломка, основной задачей которой является размещение цифр в правильном порядке.Игровое поле представляет собой квадрат 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.
