Recursive backtracking with cell arrays?

Question

Mason Scott 2015-8-5

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/232404-recursive-backtracking-with-cell-arrays

回答： arushi 2024-8-22，5:10

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

arushi 2024-8-22，5:10

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/232404-recursive-backtracking-with-cell-arrays#answer_1503014

在 MATLAB Online 中打开

Hi Mason,

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.

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