Java Sudoku solver backtracking

Question

I'm trying to build a sudoku solver. I know my code is messy and there will probably be a much simpler way to do it, but I would like finish the algorithm the way I started.

The algorithm starts doing what I want (filling the blank spaces with the first number that could fit), but when it reaches a point with no options, I don't know how to go back and erase the last number I inserted to try with another combination. But I can't just erase the last number from the matrix because it could be a number that wasn't placed by the algorithm.

If someone could help I would really appreciate it.

public class Backtracking{

public static void Sudoku(int[][] sudokuTable){
    if (isAnswer(sudokuTable)){
        printSudoku(sudokuTable);
    }else{
        for (int j = 1; j <=9; j++){
            if (canfit(sudokuTable, j)){
                addToSudoku(sudokuTable, j);
                printSudoku(sudokuTable);
                Sudoku(sudokuTable);
            }
        }
    }
}

public static void addToSudoku(int[][] sudokuTable, int n){
    int i = 0;
    int j = 0;
    boolean done = false;
    while (i < 9 && !done){
        while (j < 9 && !done){
            if (sudokuTable[i][j] == 0){
                sudokuTable[i][j] = n;
                done = true;
            }
            j++;
        }
        i++;
    }
}

public static void printSudoku(int[][] sudokuTable){
    for (int i = 0; i < 9; i++){
        for (int j = 0; j < 9; j++){
            System.out.print(sudokuTable[i][j] + " ");
        }
        System.out.println();
    }
    System.out.println();
}

public static boolean isAnswer(int[][] sudokuTable){
    int sum = 0;
    for (int i = 0; i < 9; i++){
        for (int j = 0 ; j < 9; j++){
            if (sudokuTable[i][j] > 9 || sudokuTable[i][j] < 1)
                return false;
            else
                sum++;
        }
    }
    if (sum != 405)
        return false;
    return true;
}

public static boolean canfit(int[][] sudokuTable, int n){
    int i = 0;
    int j = 0;
    boolean pos = false;
    boolean fit = true;
    while (i < 9 && !pos){
        while (j < 9 && !pos){
            if (sudokuTable[i][j] == 0)
                pos = true;
            else
                j++;
        }
        if (!pos)
            i++;
    }
    for (int k = 0; k < 9; k++){
        if (sudokuTable[i][k] == n && k != j)
            fit = false;
    }
    if (fit){
        for (int l = 0; l < 9; l++){
            if(sudokuTable[l][j] == n && l != i)
                fit = false;
        }
    }
    if (fit){
        if (i >= 0 && i < 3)
            i = 0;
        else if (i >=3 && i < 6)
            i = 3;
        else if (i >=6 && i < 9)
            i = 6;
        if (j >= 0 && j < 3)
            j = 0;
        else if (j >=3 && j < 6)
            j = 3;
        else if (j >=6 && j < 9)
            j = 6;
        for (int m = i; m < i+3; m++){
            for (int o = j; o < j+3; o++){
                if (sudokuTable[m][o] == n)
                    fit = false;
            }
        }
    }
    return fit;
}

Answer 1

Try to return true or false from your Sudoko method.

when isAnswer() method returns true, print table. Then return true from Sudoko() method.

Now inside your for loop, where you are calling Sudoko() method recursively, check if it returns true, or false. If it returns true, that means your choice is correct and it leads to a solution, you need not to do anything else. If it returns false, remove the number you set using addToSudoko() method. Make the table as it was before calling addToSudoko() method and continue iterating.

And if your for loop, loops for 9 times and none of the number has a suitable spot, that means if loop ends, return false.

Hope this helps

Answer 2

Actually you can backtracking moves by using an array, each time a move is wrong you just start to remove some moves and try a different move, however this has a problem:

• the complexity of trying all possible moves is huge (how long does it takes to try all digits on a number with 81 digits? even if you cut computation time here and there , you will need all the time of the universe)
• the main problem in sudoku is that you have no clue which was the wrong move if you move randomly.

Assume the following case sudoky with 2x2 cells:

+----+----++-----+-----+
| 1  |  2 ||  3  |  4  |
+----+----++-----+-----+
| 4  |  3 ||  1  |  2  |
+====+====++=====+=====+
| 2  |  1 ||  4  |  3  |
+----+----++-----+-----+
| 3  |  4 ||  2  |  1  |
+----+----++-----+-----+

If you use your algorithm in the following (unsolved) case:

+----+----++-----+-----+
| 1  |    ||     |  4  |
+----+----++-----+-----+
|    |    ||     |     |
+====+====++=====+=====+
| 2  |    ||     |     |
+----+----++-----+-----+
|    |  4 ||     |  1  |
+----+----++-----+-----+

it is possible he will run into the following sequence

+----+----++-----+-----+
| 1  |    ||  2  |  4  |
+----+----++-----+-----+
|    |    ||  2  |     |
+====+====++=====+=====+
| 2  |    ||     |     |
+----+----++-----+-----+
|    |  4 ||     |  1  |
+----+----++-----+-----+

Actually the added "twos" are both wrong, but when your algorithm find that those are wrong because you have 2 "twos" in the same column, you don't know which one was the wrong one (the first added, the second added, or both?)

A correct backtracking algorithm would works like this:

• You start with a 81 cells arrays, and you start placing numbers (in sequence).

.

 for(int i=0; i<81; i++)
    array[i] = TryNumber();

.

• then you check after each added number if that was correct.

.

if(SomeNumberNotCorrect())
    break;  // you know you can stop "tryingnumbers" so you can save on loop executions

.

• But you don't know which was the wrong number

Now writing a correct algorithm that solves sudokus by attemps and do not run in million of years is pretty long and I cannot write it here but I don't think the way you choosen is the best. The best way is to apply the same strategies used by players. Just keep in mind that if you want an algorithm to resolve sudokus in a similiar way to how Chess is played by computer your algorithm would require much more time than a Chess game (infact a computer cannot analize chess moves more than 5-6 turns). But infact Sudokus can be resolved with much faster algorithms.

Instead I've already done in past a simple solver you could actually try to apply the same strategies a player would use to solve it:

In example:

• For each cell, check if current Sector, Column and Line have already all numbers except 1, then you can add that number. And to check that for each cells you just need 81*81*81 moves.

When your solver do not find anymore solutions on a Sudoku, it is just because you have to develop as player a new strategy and then you need to apply it to your program, in short you will have a program that will be able to solve every sudoku (not very hard, and actually this is the reason that there are a lot of free sudoku solvers out there).