matlab - 如何在给定条件的情况下递归地编辑矩阵？

Question

grid = [[5 3 0 0 7 0 0 0 0];[6 0 0 1 9 5 0 0 0];[0 9 8 0 0 0 0 6 0];[8 0 0 0 6 0 0 0 3];[4 0 0 8 0 3 0 0 1];[7 0 0 0 2 0 0 0 6];[0 6 0 0 0 0 2 8 0];[0 0 0 4 1 9 0 0 5];[0 0 0 0 8 0 0 7 9]];

function ov = possibility(grid,x,y,n)
ov = true;
for i = 1:9
    if (grid(x,i) | grid(i,y)) == n
        ov = false;
        return
    end
end

xO = floor((x-1)/3)*3;
yO = floor((y-1)/3)*3;

for m = 1:3
    for k = 1:3
        if grid(xO + m, yO + k) == n
            ov = false;
            return
        end
    end
end
end

function solve(grid)
for x = 1:9
    for y = 1:9
        if grid(x,y) == 0
            for n = 1:9
                if possibility(grid,x,y,n)
                    grid(x,y) = n;
                    solve(grid)
                else
                    grid(x,y) = 0;
                end
            end
        end
    end
end
end

只是一个免责声明，这段代码不是我的原创作品，我只是想弄清楚递归，因为它对我来说一直是一个奇怪的概念。这是来自 youtube 视频https://youtu.be/G_UYXzGuqvM，该程序是用 python 编写的。

我不太明白如何系统地返回求解函数并允许代码决定需要更改哪些“正方形”，因为我看到它的方式：如果grid(x,y)是 0，然后设置为第一个可能选项，但该选项是错误的，代码将永远无法找到难题的解决方案。我不明白它将如何确定返回并将错误的选择更改为下一个可能正确或不正确的可用选择。

标签： matlab

Answer 1

我想通了，这是我的解决方案，感谢所有反馈的家伙:)

function Sudoku_Solver()
clear; close; clc

% manually input sudoku puzzle
gridGrid = [5 3 0 0 7 0 0 0 0;6 0 0 1 9 5 0 0 0;0 9 8 0 0 0 0 6 0;8 0 0 0 6 0 0 0 3;4 0 0 8 0 3 0 0 1;7 0 0 0 2 0 0 0 6;0 6 0 0 0 0 2 8 0;0 0 0 4 1 9 0 0 5;0 0 0 0 8 0 0 7 9];

%{
establishes possibility vector for each index, starts with all possible
solutions 1-9 and removes the non-working ones
%}
gridCell = cellfun(@double, mat2cell(repmat(1:9,9,9),ones(1,9),9*ones(1,9)),'UniformOutput',false);

% used to check common 3x3 grid
squareCheck = repelem(reshape(1:9,3,3)',3,3);

solve()

    function solve()
        % intialize a for loop for indices by row and column
        for x = 1:9
            for y = 1:9
                % Check that the current index is established or not
                if gridGrid(x,y) == 0
                    % if the index is not established check possibilities
                    for n = 1:9
                        possible(x,y,n)
                    end
                    % Check that the possibility is not a singular value
                    if size(gridCell{x,y},2) == 1
                        % if a singular value then establish the index
                        gridGrid(x,y) = gridCell{x,y};
                        % call function with newly established index
                        solve()
                    end
                end
            end
        end
    end

    % establish function to check the integrity of options 1-9 per index
    function possible(deltaX,deltaY,n)
        % initialize a for loop to check row/column
        for deltak = 1:9
            % Check entire row and column of index that we are checking
            if gridGrid(deltaX,deltak) == n || gridGrid(deltak,deltaY) == n
                %{ 
                if any value in the row/column is n that means it is not
                an option and we remove it from the list 
                %}
                gridCell{deltaX,deltaY} = gridCell{deltaX,deltaY}(gridCell{deltaX,deltaY} ~= n);
            end

            %{
            intialize a for loop to check the 3x3 grid that the index
            belongs to
            %}
            for deltai = 1:9
                for deltaj = 1:9
                    % check indices that share a common 3x3 grid
                    if squareCheck(deltai,deltaj) == squareCheck(deltaX,deltaY)
                        if gridGrid(deltai,deltaj) == n
                            % remove any values that are not an option
                            gridCell{deltaX,deltaY} = gridCell{deltaX,deltaY}(gridCell{deltaX,deltaY} ~= n);
                        end
                    end
                end
            end
        end
    end

% print solution to command window
gridGrid

end