Geek asks and answers

A simple method for solving sudoku

Note: this problem is solved, the actual problem is NOT in this but different, so if you are searching for something about Sudoku and finally go to this page, you can absolutely use my method below, it works.

Well, forget about all the complex algorithms used to solve sudoku. I am writing a simple Java solver to solve simple Sudoku games. The idea of ​​this method is very common, so I think everyone already knows this. I am also surprised that I can not do this.

The method is to go through each cell on the board and fill in all the cells that have only 1 possibility. Repeat until each cell is full. Very simple, and here is my code returned by the int number of fillers can be done:

public int solveGame() {

/*
 variable possible contains 10 elements, the first element is true if there 
 is one or more possible value to fill in, false otherwise. The remaining 
 elements (1-9) are whether true or false depending on their indexes 
 e.g. possible[3] is true if 3 is a possibility.
*/
boolean[] possible; 

int[] save;
int count;
int numresolve = 0;

while (!isFinished()) {

    for (int i = 0; i < GAMESIZE; i++) {
        for (int j = 0; j < GAMESIZE; j++) {
            possible = new boolean[10];
            possible = getPossible(i,j);
            if (possible[0]) {
                count = 0;
                save = new int[9];
                for (int k = 1; k < 10; k++) {
                    if (possible[k]) {
                        count++;
                        save[count] = k;
                    }
                }
                if (count == 1) {
                    setCell(i,j,save[count]);
                    numresolve++;
                }
            }
        }
    }
}

return numresolve;

}

, , , 1 , 1 , .

, -, .

+3
5

, , - :

 while (!isFinished()) {
   int prevResolved = numresolve;

   .... // your loop

   if (numresolve == prevResolved) {
     // did not find anything - out of luck, can't solve this board.
     return ...; // numresolve or something to indicate that it failed
   }
}

, - .

boolean false true . , , - ( , ).

+3

, , . , , getPossible, .
, " " , , , , getPossible, :

1 == {a, b}, 2 = {a, b}, 3 = {a, b, c}

3 , , , , , ..

, , , , - , , , - , .

+3

( setCell), //. , getPossibile .

, . , , , .

+2

, .

It so happens that there is no cell that has only one possibility, so your code should be a fork, calling the function again, flipping each of two (or more) possibilities again until the grid is completely full.

+2
source 
int numresolve = 0;

// this variable will be used to track # of changed cells in each loop
// init to -1 to run loop at least once
// loop can be more elegant if you put the condition at the end
int changed = -1;

// stop loop if no cell changed
while (!isFinished() && changed != 0) {

    // initialize # of changed cells in this loop    
    changed = 0;

    for (int i = 0; i < GAMESIZE; i++) {
        for (int j = 0; j < GAMESIZE; j++) {
            boolean[] possible = getPossible(i,j);
            if (possible[0]) {
                int count = 0;
                int[] save = new int[9];
                for (int k = 1; k < 10; k++) {
                    if (possible[k]) {
                        count++;
                        save[count] = k;
                    }
                }
                if (count == 1) {
                    setCell(i,j,save[count]);
                    numresolve++;
                    changed++;
                }
            }
        }
    }
}
+1
source

More articles:


All Articles