Рекурсивные функции бывает сложно абстрагировать даже в простых случаях. В вашем случае есть дополнительный уровень сложности, так как помимо необходимости вычислять вещи на основе предыдущих итераций, алгоритм также должен иметь возможность вернуться определенное количество итераций, прежде чем продолжить путь вперед.
Я сделал рабочий пример, но это не единственный способ добиться результата. Я предлагаю использовать два флага , чтобы помочь рекурсивной функции знать, в каком направлении она движется. Вы можете обойтись без флагов, но это потребует дополнительных проверок во время функции для оценки состояния платы. Поскольку есть возможность использовать флаги, я использовал ее для упрощения.
Я настоятельно рекомендую вам прочитать документацию по return, так как это полезный инструмент для этих типов функций.
Теперь к ответу:
Стартовая доска:
Во-первых, для всеобщего блага представляю начальную неразрешенную доска. Это матрица 9x9, содержащая начальные числа и NaN везде.
unsolvedBoard = [
5 3 NaN NaN 7 NaN NaN NaN NaN
6 NaN NaN 1 9 5 NaN NaN NaN
NaN 9 8 NaN NaN NaN NaN 6 NaN
8 NaN NaN NaN 6 NaN NaN NaN 3
4 NaN NaN 8 NaN 3 NaN NaN 1
7 NaN NaN NaN 2 NaN NaN NaN 6
NaN 6 NaN NaN NaN NaN 2 8 NaN
NaN NaN NaN 4 1 9 NaN NaN 5
NaN NaN NaN NaN 8 NaN NaN 7 9 ] ;
Начальные условия: Ваш алгоритм вслепую перебирал все 99 возможных блоков сетки. В формулировке задачи рекомендовалось идентифицировать пустые индексы в сетке (которые должны быть помещены в переменную emptyInd и выполнять итерацию только по этим пустым индексам благодаря переменной ind. Чтобы включить это, я изменил начало основного решателя:
function solvedBoard = solveSudoku(board)
emptyInd = find(isnan(board)) ; % find the empty indices in the grid
% this will solve the board recursively
solvedBoard = solverec( board, emptyInd, 1 );
end
Теперь emptyInd содержит только 51 индекс, который нужно найти. Мы будем выполнять итерацию только по ним, а не по 99 ячейкам сетки.
Возможные числа для данного поля:
Ваша функция checkSudoku(board, row, col, num) работала отлично, но ее можно упростить. Вы уже конвертировали индексы строк и столбцов в линейные индексы. в своей функции h вы можете повторно использовать тот же тип вычислений в этой функции, чтобы узнать индексы subrow/subcol/subBoard. Также обратите внимание, что вы можете объединить условия if с логическими or для проверки всех условий сразу. Функция может выглядеть так:
function safe = checkSudoku(board, row, col, num)
subrow = board(row, :);
subcol = board(:, col);
subSquareRow = (1:3) + 3*(ceil(row/3)-1) ;
subSquareCol = (1:3) + 3*(ceil(col/3)-1) ;
subBoard = board( subSquareRow , subSquareCol );
subBoard = subBoard(:) ; % Reshape into column vector (easier comparison)
% This whole block can be replaced with the line described below
if any(subrow == num) || any(subcol == num) || any(any(subBoard == num))
safe = false;
else
safe = true;
end
% Note that since we are dealing with boolean, the "IF" check above could
% be avoided and simply written as :
% safe = ~( any(subrow == num) || any(subcol == num) || any(any(subBoard == num)) ) ;
end
Теперь эта функция позже используется в рекурсивном l oop, чтобы проверять, соответствует ли число от 1 до 9 действительно в данной позиции. Вы использовали while l oop для бега от 1 до 9. Я считаю бесполезным проверять девять чисел, когда мы могли с самого начала знать несколько возможных кандидатов для данного ящика. Итак, я написал функцию, которая возвращает список единственно возможных действительных номеров для коробки. Если он вернет только 3 возможных числа, мне нужно будет перебрать только эти 3 числа, вместо того, чтобы делать это вслепую более 9 из них.
function candidates = getCandidates(board, row, col)
subrow = board(row, :);
subcol = board(:, col);
subSquareRow = (1:3) + 3*(ceil(row/3)-1) ;
subSquareCol = (1:3) + 3*(ceil(col/3)-1) ;
subBoard = board( subSquareRow , subSquareCol );
subBoard = subBoard(:) ; % Reshape into column vector (easier comparison)
% Get the difference of each array compared to a reference line
refval = 1:9 ;
cdrow = setdiff(refval,subrow) ;
cdcol = setdiff(refval,subcol) ;
cdsqr = setdiff(refval,subBoard) ;
% intersection of the three arrays
candidates = intersect( intersect(cdrow,cdcol) , cdsqr ) ;
end
Вы можете прочитать setdiff и intersect, чтобы понять, как это работает.
Теперь рекурсивный решатель:
Эта функция выполняет работа вашей h() функции. В вашей реализации были две основные проблемы:
- Слишком много условных ветвей: в потоке программы было слишком много
if ветвей, и некоторые пути фактически никогда не использовались. Даже когда это работает, это сбивает с толку, но часто путаница также приводит к ошибкам. - Нет надежного условия для проверки, когда доска была полностью решена: у вас была проверка, но она не фиксировала завершение доски (частично из-за проблемы, описанной выше).
То, что произошло, - это когда ваша плата была полностью решена, алгоритм не имеет возможности обнаружить это и вернуться к вызову итеративной функции с конечным результатом. Ваш алгоритм находил решение, но из-за отсутствия выходной двери для этого случая (полностью решенного) он по умолчанию работал с другими ветвями и в конечном итоге последовательно возвращал последние несколько итераций, даже если они были правильными.
Следующая реализация работает нормально для нашего тестового примера и нескольких других. Вы можете попробовать это в других случаях, если хотите, но помните, что сетка должна быть разрешимой. Я не ставил никаких проверок или инструкций о том, что делать, если сетка неразрешима, поэтому я не знаю, что произойдет, если вы запустите ее на такой сетке.
Код для solverec.m:
function [res, solved, noSolutionFound] = solverec(board,emptyInd,ind,solved)
%% initialise the return flag for first function call
if nargin < 4 ; solved = false ; end
noSolutionFound = false ; % initialise second flag
% check if we are done with all the EmptyInd
if ind>numel(emptyInd) ;
solved = true ;
end
%% Return quickly if the board is already solved
if solved
res = board ;
return ;
end
%% If we are here, we still have to find new emptyInd
% prepare useful indices (row, column & linear index)
num = emptyInd(ind) ;
col = ceil(num / 9);
row = num - ((col - 1) * 9);
% get possible candidates for this box
cd = getCandidates(board, row, col) ;
ncd = numel(cd) ; % number of candidates
if ncd == 0
% no candidate for this box => back track
noSolutionFound = true ;
else
% Try the possible candidates one by one
for k=1:ncd ;
board(num) = cd(k) ; % try one candidate
% move on to next emptyInd
[res, solved, noSolutionFound] = solverec(board,emptyInd,ind+1,solved) ;
% bail out if solved
if solved ; return ; end
% otherwise, reset this emptyInd before trying next candidate
if noSolutionFound
board(num) = NaN ;
end
end
end
if noSolutionFound
% We have exhausted all possible candidates for this emptyInd
% We have to back track further
board(num) = NaN ;
res = board ;
return % this one is actually optional, the function will "return"
% anyway at the end of the "if" block.
end
end
Тестирование:
>> solvedBoard = solveSudoku(unsolvedBoard)
solvedBoard =
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
Я позволю вам написать необязательную функцию displaySudoku(board) в качестве упражнения;)