Determine whether a Sudoku has a unique solution

Question

I'm struggling with a backtracking algorithm to determine wether a Sudoku has a unique solution or if it has multiple Solutions. Here's the backtracking code i use:

    static boolean solve(int i, int j, int[][] cells) {
    if (i == 9) {
        i = 0;
        if (++j == 9)
            return true;
    }
    if (cells[i][j] != 0)  // skip filled cells
        return solve(i+1,j,cells);

    for (int val = 1; val <= 9; ++val) {
        if (legal(i,j,val,cells)) {
            cells[i][j] = val;
            if (solve(i+1,j,cells))
                return true;
        }
    }
    cells[i][j] = 0; // reset on backtrack
    return false;
}

First approach: If i change

for (int val = 1; val <= 9; ++val) {
for (int val = 9; val >= 1; val--) {

i get two different solving-algorithmns which should find different solutions (if different solutions exist). The problem with this approach is, that the algorithm doesn't terminate even though its just a slight change and i don't know why.

Second approach: Reset to backtrack and continue searching for a solution. If i try this, it doesn't work either.

I tried to find a Java example, but i can only find information like "reset on backtrack and continue searching for a second solution".

Could someone please provide a example how to change the algorithm so it tells me if multiple solutions exists (the exact number is not needed)

OR

Could someone please explain to me why my first approach doesn't terminate?

Thanks!

Scirrhous

What does "legal()' mean ? I am trying to translate this code into C.. – Alexandrina

It returns true if val is allowed at position i, j and false if the same value is present in the corresponding row, column or 3x3 grid – Scirrhous

Answer 1

If you return a number instead of a boolean, you can distinguish between cases where there are 0, 1, or more than 1 solution(s).

// returns 0, 1 or more than 1 depending on whether 0, 1 or more than 1 solutions are found
static byte solve(int i, int j, int[][] cells, byte count /*initailly called with 0*/) {
    if (i == 9) {
        i = 0;
        if (++j == 9)
            return 1+count;
    }
    if (cells[i][j] != 0)  // skip filled cells
        return solve(i+1,j,cells, count);
    // search for 2 solutions instead of 1
    // break, if 2 solutions are found
    for (int val = 1; val <= 9 && count < 2; ++val) {
        if (legal(i,j,val,cells)) {
            cells[i][j] = val;
            // add additional solutions
            count = solve(i+1,j,cells, count));
        }
    }
    cells[i][j] = 0; // reset on backtrack
    return count;
}

Hohenstaufen

Why use byte? You expect maximally 127 solutions? Also AFAIK byte takes same memory as int, so there isn't really a difference. – Scoville

@kajacx: Only 2 solutions need to be found to tell, if the solution is unique, so why not? – Hohenstaufen

But I can't see anywhere that number of solutions would be checked, so if the sudoku would have 256 solution, then your method would return 0. – Scoville

@kajacx: Look at the condition in the for loop. Did you think I'm doing a DFS for all solutions? – Hohenstaufen

@kajacx: BTW: even an int would overflow, if none of the fields are filled, since there are over (9!)^3 > 2^55 solutions (filling the 3x3 fields on one diagonal independently should be possible). – Hohenstaufen

Thank you, this is exactly what i tried to do. I've never used Backtracking before so i had quite a hard time understanding and modifying the algorithm. – Scirrhous

Aaa, count < 2, I'm sorry, didn't see that. I meant no flame, i just really didnt see how it would work. All right then. – Scoville

Answer 2

The reset must be inside the for loop and after the if solve condition

 for (int val = 1; val <= 9; ++val) {
        if (legal(i,j,val,cells)) {
            cells[i][j] = val;
            if (solve(i+1,j,cells))
                return true;
            cells[i][j] = 0; // reset on backtrack
        }
    }

Meisel

Thank you, now the algorithm terminates even if the for-loop counts down instead of up. – Scirrhous

Both answers are correct, unfortunately i can only accept one. – Scirrhous

@user3158988 thank you, it's up to you to vote for the correct answer :) I only wanted to know why a person downvoted my answer. but anw hope he/she will post a comment – Meisel