Как я могу рекурсивно редактировать матрицу при определенных условиях?

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.

Я не совсем понимаю, как систематически go возвращаться через функцию решения и разрешать код, чтобы решить, какие `` квадраты '' ему нужно изменить, потому что я это вижу: если бы grid(x,y) должен был быть равен 0, а затем установить первый возможный вариант, но этот вариант был неправильным, код никогда не смог бы найти решение загадки. Я не понимаю, как он определил бы go назад и изменил неправильный выбор на следующий доступный вариант, который также может быть правильным, а может и нет.

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