I'm having trouble writing a Backtracking algorithm (Sudoku Solver) for my Sudoku project. My idea is to create a 2D array variable "initial" as an initializer array to push into the player's interface and use the "initial" variable to pass in the Backtracking algorithm (sudokuSolver & solver method) and return an array 2D results, then assign it to the variable "solution". Then I want to use the variable "solution" to compare it with the array received from the player's input while playing the game (2D array player) so that know if the player is successful or not. But my current problem is that I have an algorithm that correctly prints the result array, but when I assign it to the "solution" variable for comparison, the return value is just 0 and not the correct result array. I want the "solver" method to be able to return a 2D array, but for now I can only print the results. 

I look forward to the help!

import java.util.Arrays;

public class sudokuSolver {
    private boolean[][] markRow;
    private boolean[][] markCol;
    private boolean[][][] markMatrix;
    private int[][] board;

    // Mark
    public sudokuSolver(int[][] board) {
        this.board = board;
        markRow = new boolean[9][9];
        markCol = new boolean[9][9];
        markMatrix = new boolean[3][3][9];

        for (int row = 0; row < board.length; row  ) {
            for (int col = 0; col < board[row].length; col  ) {
                int currentNumber = board[row][col];
                if (currentNumber != 0) {
                    markRow[row][currentNumber - 1] = true;
                    markCol[col][currentNumber - 1] = true;
                    markMatrix[row / 3][col / 3][currentNumber - 1] = true;
                }
            }
        }
    }
    public int[][] solver(int row, int col) {
        int[][] solution = new int[9][9];
        if (row < 9 && col < 9) {
            if (board[row][col] == 0) {
                for (int i = 1; i <= 9; i  ) {
                    if (!markRow[row][i - 1] && !markCol[col][i - 1] && !markMatrix[row / 3][col / 3][i - 1]) {
                        markRow[row][i - 1] = true;
                        markCol[col][i - 1] = true;
                        markMatrix[row / 3][col / 3][i - 1] = true;
                        board[row][col] = i;
                        solver(row, col   1);
                        markRow[row][i - 1] = false;
                        markCol[col][i - 1] = false;
                        markMatrix[row / 3][col / 3][i - 1] = false;
                        board[row][col] = 0;
                    }
                }
            } else {
                solver(row, col   1);
            }
        } else if (row < 9 && col >= 9) {
            solver(row   1, 0);
        } else {
            for (int i = 0; i < board.length; i  ) {
                System.out.println(Arrays.toString(board[i]));
                solution[i] = board[i];
            }
        }
    return solution;
    }

    public static void main(String[] args) {
        int[][] initial = new int[][]
                {
                        {0, 0, 0, 4, 0, 0, 0, 9, 0},
                        {6, 0, 7, 0, 0, 0, 8, 0, 4},
                        {0, 1, 0, 7, 0, 9, 0, 0, 3},
                        {9, 0, 1, 0, 7, 0, 0, 3, 0},
                        {0, 0, 2, 0, 0, 0, 9, 0, 0},
                        {0, 5, 0, 0, 4, 0, 1, 0, 7},
                        {3, 0, 0, 5, 0, 2, 0, 7, 0},
                        {4, 0, 6, 0, 0, 0, 3, 0, 1},
                        {0, 7, 0, 0, 0, 4, 0, 0, 0}
                };
        sudokuSolver solve = new sudokuSolver(initial);
        int [][] test = solve.solver(0, 0);
        System.out.println("=================");
        System.out.println(test[0][0]);
        }
    }

enter image description here

CodePudding user response：

You've a recursive algorithm. The solution you're printing gets build n-steps deep into your recursion and only lives there. What you're returning as a final result at the top-most level is effectively new int[9][9], which is wrong!

The easiest way around this is to define a special variable in your sudokuSolver class that will hold the final result.

public class sudokuSolver {
    // ...

    private int[][] finalResult = new int[9][9];
    public void clearResult() {
        finalResult = new int[9][9];
    }
    public int[][] getFinalResult() {
        return finalResult;
    }

    public int[][] solver(int row, int col) {
        // ...
        for (int i = 0; i < board.length; i  ) {
            System.out.println(Arrays.toString(board[i]));
            finalResult[i] = board[i].clone();
        }
        // ...
    }

    public static void main(String[] args) {
        // ...
        sudokuSolver solve = new sudokuSolver(initial);
        solve.solver(0, 0);
        System.out.println("=================");
        System.out.println(solve.getFinalResult()[0][0]);
    }
}

Note: You can remove solution variable altogether and change solver's return type to void.

CodePudding user response：

To me, it looks like the issue is that you are doing a recursive solution. This is perfectly fine for this however, the internal calls your method solver makes to itself never get their returned value assigned to the solution array. Thus, the final return which is supposed to return the entire array ends up being empty because all of the work was done deeper in the recursion and that is not being returned.

solution = solver(row   <number>,column <number>)