I want help for 16 by 16 sudoku solver!

Question

Hubaib Ahsan 2024-4-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2112481-i-want-help-for-16-by-16-sudoku-solver

评论： Hubaib Ahsan 2024-5-2

I've been working on this code for solving a 16 by 16 sudoku. It solves the first 8 columns and leaves the rest of 8 as it is. I don't know where the problem is. Can anybody help?

function sudokuSolver(inputFile, outputFile)
    % Read the puzzle from the input file
    puzzle = readPuzzle(inputFile);
    
    % Solve the puzzle
    solution = solveSudoku(puzzle);
    
    % Write the solution to the output file
    writeSolution(outputFile, solution);
end
function puzzle = readPuzzle(inputFile)
    fid = fopen(inputFile, 'r');
    if fid == -1
        error('Error: Unable to open input file');
    end
    puzzle = textscan(fid, '%s', 'Delimiter', '\n');
    puzzle = puzzle{1}; % Extract the puzzle as a cell array of strings
    fclose(fid);
end
function writeSolution(outputFile, solution)
    fid = fopen(outputFile, 'w');
    if fid == -1
        error('Error: Unable to open output file');
    end
    for i = 1:numel(solution)
        fprintf(fid, '%s\n', solution{i}); % Write each row of the solution to the file
    end
    fclose(fid);
end
function solution = solveSudoku(puzzle)
    solution = puzzle; % Initialize solution with the input puzzle
    
    % Call the recursive backtracking solver
    [foundSolution, solution] = backtrackSolver(puzzle, 1, 1);
    
    % If a solution is not found, keep searching for empty cells and fill them
    while ~foundSolution
        % Find the indices of empty cells ('#')
        [row, col] = findEmptyCell(solution);
        
        % If there are no empty cells, break the loop
        if isempty(row) || isempty(col)
            break;
        end
        
        % Attempt to fill the empty cell with a valid value
        for val = '0123456789ABCDEF'
            if isValidMove(solution, row, col, val)
                solution{row}(col) = val;
                break;
            end
        end
        
        % Re-run the solver to check if the puzzle is solved
        [foundSolution, solution] = backtrackSolver(solution, 1, 1);
    end
    
    if ~foundSolution
        error('Error: No solution found for the given puzzle');
    end
end
function [row, col] = findEmptyCell(puzzle)
    n = 16; % Size of the Sudoku grid
    for i = 1:n
        for j = 1:n
            if puzzle{i}(j) == '#'
                row = i;
                col = j;
                return;
            end
        end
    end
    % If no empty cell is found, return empty indices
    row = [];
    col = [];
end
function [foundSolution, solution] = backtrackSolver(puzzle, row, col)
    n = 16; % Size of the Sudoku grid
    foundSolution = false;
    solution = puzzle; % Initialize solution with the input puzzle
    
    % Base case: If we have reached the end of the puzzle, return true
    if row > n
        foundSolution = true;
        return;
    end
    
    if col > n
        foundSolution = true;
        return;
    end
    
    % If the current cell is already filled, move to the next cell
    if ~isequal(puzzle{row}(col), '#')
        [foundSolution, solution] = backtrackSolver(puzzle, row + (col == n), mod(col, n) + 1);
        return;
    end
    
    % Try placing each possible value in the current cell
    for val = '0123456789ABCDEF'
        % Check if the current value is valid in the current cell
        if isValidMove(solution, row, col, val)
            solution{row}(col) = val; % Place the value in the cell
            
            % Move to the next cell recursively
            [foundSolution, solution] = backtrackSolver(solution, row + ((col+1) > n), mod(col, n) + 1);
            
            % If a solution is found, return
            if foundSolution
                return;
            end
            
            % Backtrack: If no solution is found, reset the current cell
            solution{row}(col) = '#';
        end
    end
end
function isValid = isValidMove(puzzle, row, col, val)
    n = 16; % Size of the Sudoku grid
    
    % Check if the value already exists in the same row or column
    for i = 1:n
        if puzzle{row}(i) == val || puzzle{i}(col) == val
            isValid = false;
            return;
        end
    end
    
    % Check if the value already exists in the same subgrid
    subgridRow = 1 + 4 * floor((row - 1) / 4);
    subgridCol = 1 + 4 * floor((col - 1) / 4);
    for i = subgridRow:subgridRow + 3
        for j = subgridCol:subgridCol + 3
            if puzzle{i}(j) == val
                isValid = false;
                return;
            end
        end
    end
    
    % Check if the value already exists in the remaining columns (9 to 16)
    for i = 9:n
        if puzzle{row}(i) == val
            isValid = false;
            return;
        end
    end
    
    % If the value doesn't violate any Sudoku rules, it's a valid move
    isValid = true;
end

5 个评论
显示 3更早的评论隐藏 3更早的评论

Voss 2024-4-29

编辑：Voss 2024-4-29

在 MATLAB Online 中打开

Please upload (using the paperclip button) an input file that exhibits the problem behavior you are seeing.

The code runs and seems to provide a solution for the input sudoku.txt file I've attached here. I didn't exhaustively check whether the solution is correct, but it doesn't leave columns 9-16 as they were.

Also, this part is redundant and can be removed (it doesn't affect the result):

    % Check if the value already exists in the remaining columns (9 to 16)
    for i = 9:n
        if puzzle{row}(i) == val
            isValid = false;
            return;
        end
    end    

because the same checks were already done earlier in the same function as part of:

    % Check if the value already exists in the same row or column
    for i = 1:n
        if puzzle{row}(i) == val || puzzle{i}(col) == val
            isValid = false;
            return;
        end
    end