- Ensure that each recursive call correctly accumulates solutions and passes them up the call stack.
- Make sure that solutions are added to the cellSolutions array in the correct format and that the recursive function returns this array properly.
Recursive backtracking with cell arrays?
4 次查看(过去 30 天)
显示 更早的评论
I'm working on a function to recursively generate solutions to a given sudoku puzzle represented by a 9x9 array with NaN representing blank spaces utilizing backtracking.
function cellSolutions = solveSudoku(PuzzleA)
cellSolutions = {};
if ~reject(PuzzleA)
if accept(PuzzleA)
disp('solution found')
cellSolutions{end+1} = PuzzleA;
end
[nP, Idx] = firstChild(PuzzleA);
while (~isempty(nP))
possibleSolution = solveSudoku(nP);
if (~isempty(possibleSolution))
cellSolutions{end+1} = possibleSolution{1};
end
nP = nextChild(nP,Idx);
end
end
end
The return cellSolutions is a cell array that contains 0, 1, or more solutions depending on how many exist. The trouble I'm having is actually getting the solutions that are found to appear in the cellSolution returned with the initial call. What I'm hoping for is:
cellSolutions
{[9x9 double] [9x9 double]} or {} or {[9x9 double]}
I can indeed confirm that one or more solutions are found with the disp call, but I'm not sure how to manipulate the cell array. I'm pretty sure the problem lies with:
while (~isempty(nP))
possibleSolution = solveSudoku(nP);
if (~isempty(possibleSolution))
cellSolutions{end+1} = possibleSolution{1};
end
nP = nextChild(nP,Idx);
end
Some other info: reject determines whether the current puzzle satisfies the rules of sudoku; accept checks additionally that there are no empty spaces; firstChild finds and instance of NaN in a given sudoku puzzle, and changes it to 1 and returns linear index it changed and the new puzzle; nextChild takes a sudoku puzzle and index, if the value at that index is not 9, then it increments the value and returns the new puzzle. Thanks!
0 个评论
回答(1 个)
arushi
2024-8-22,5:10
Hi Mason,
Here's a revised version of solveSudoku function with comments explaining each step:
function cellSolutions = solveSudoku(PuzzleA)
cellSolutions = {}; % Initialize the cell array to store solutions
if ~reject(PuzzleA) % Check if the current puzzle configuration is valid
if accept(PuzzleA) % Check if the puzzle is completely solved
disp('solution found');
cellSolutions{end+1} = PuzzleA; % Add the completed puzzle to solutions
return; % Return as we've found a solution
end
[nP, Idx] = firstChild(PuzzleA); % Get the first child puzzle and its index
while ~isempty(nP) % Continue until there are no more children
possibleSolutions = solveSudoku(nP); % Recursively solve the child puzzle
if ~isempty(possibleSolutions)
% Append all solutions found to the current cellSolutions
cellSolutions = [cellSolutions, possibleSolutions];
end
nP = nextChild(nP, Idx); % Move to the next child
end
end
end
Hope this helps.
0 个评论
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!