Я не знаю, как вы собираетесь решить судоку, но даже если вы используете метод грубой силы (и мне кажется, что вы описываете), вы должны учитывать, что ваша структура данных не подходит.
Под этим я подразумеваю, что каждая ячейка должна быть не просто числом, а набором чисел (которые могут быть там размещены).
Следовательно, данные числа будут представлены в виде одноэлементных наборов, а пустые можно инициализировать с помощью {1,2,3,4,5,6,7,8,9}.
И тогда цель состоит в том, чтобы уменьшить число не-одиночных клеток, пока все клетки не станут синглетонами.
(Обратите внимание, что, решая судоку карандашом и бумагой, часто пишут небольшие числа в пустых ячейках, чтобы отследить, какие числа там возможны, насколько это возможно.)
И затем, при «попытке следующего номера» вы берете следующий номер из набора. Данные ячейки не имеют следующего номера, поэтому вы не можете их изменить. Таким образом, трудности, которые вы описываете, исчезают (по крайней мере, немного).
------ РЕДАКТИРОВАТЬ, ПОСЛЕ УЧЕБЫ, ЧТО ТРЕБУЕТСЯ СИЛЬНАЯ СИЛА.
Ваш учитель, очевидно, хочет научить вас чудесам рекурсии. Очень хорошо!
В этом случае нам просто нужно знать, какие клетки даны, а какие нет.
Конкретный простой способ, который можно использовать здесь, состоит в том, чтобы поместить 0 в любую не заданную ячейку, поскольку данные ячейки по определению являются одной из 1,2,3,4,5,6,7,8,9.
Теперь давайте подумаем, как заставить рекурсивную грубую силу работать.
У нас есть цель решить судоку с n пустыми клетками. Если бы у нас была функция, которая бы решала судоку с n-1 пустыми ячейками (или сигнализировала бы, что она не разрешима), то эта задача была бы простой:
let c be some empty cell.
let f be the function that solves a sudoku with one empty cell less.
for i in 1..9
check if i can be placed in c without conflict
if not continue with next i
place i in c
if f() == SOLVED then return SOLVED
return NOTSOLVABLE
Этот псевдокод выбирает некоторую пустую ячейку, а затем пробует все подходящие числа.
Поскольку судоку по определению имеет только одно решение, возможны только следующие случаи:
- мы выбрали правильный номер. Тогда f () найдет оставшуюся часть решения и вернет решено.
- мы выбрали неправильное число: f () будет сигнализировать, что судоку не разрешимо с этим неправильным числом в нашей ячейке.
- мы проверили все числа, но никто не был прав: тогда мы сами получили неразрешимую судоку, и мы сигнализируем об этом нашему вызывающему.
Излишне говорить, что алгоритм основан на предположении, что мы всегда размещаем только числа, которые не являются
конфликтует с текущим состоянием. Например, мы не размещаем 9 там, где в той же строке, столбце или поле уже есть 9.
Если мы сейчас подумаем о том, как выглядит наша загадочная, но неизвестная функция f(), то окажется, что она будет почти такой же, как у нас!
Единственный случай, который мы еще не рассмотрели, - это судоку с 0 пустыми клетками. Это означает, что если мы обнаружим, что больше нет пустых ячеек, мы знаем, что мы только что решили судоку и вернули просто решено.
Это обычная хитрость при написании рекурсивной функции, которая должна решить проблему. Мы пишем execute (), и мы знаем, что проблема разрешима вообще. Следовательно, мы уже можем использовать функцию, которую мы только что написали, при условии, что с каждой рекурсией проблема каким-то образом приближается к решению. В конце мы достигаем так называемого базового случая, где мы можем дать решение без дальнейшей рекурсии.
В нашем случае мы знаем, что судоку разрешимо, более того, мы знаем, что у него есть ровно одно решение. Поместив кусок в пустую ячейку, мы приближаемся к решению (или к диагнозу, которого такового нет) и рекурсивно передаем новую, меньшую проблему функции, которую мы только что пишем. Базовый случай - «Судоку с 0 пустыми клетками», который на самом деле является решением .
(Все становится немного сложнее, если есть много возможных решений, но мы оставим это для следующего урока.)