The aim of my code, similar to the backtracking algorithm for labyrinths, is to calculate solutions for a 9 × 9 sudoku.
and The Sudoku and its solution are stored like the labyrinth in a two-dimensional int array.
I know that :The backtracking algorithm tries to enter a value of 1 ... 9 from cell [0.0] starting in a free field (value is then 0), starting with paragraph 1. Testing whether this is a valid value is a little more complicated than the maze, where it only had to be checked whether the cell is free. I think it is a good idea to use the methods
isRowOk ,
isColOk ,
isBlockOk
To take advantage of the check whether value is allowed at all, i.e. not already contained in the block.
and then These three functions must all give their OK before the backtracking algorithm tries recursively to enter a value of 1 ... 9 in the next free cell. Otherwise-if all digits 1 ... 9 have been tried-the search will be canceled (backtracking) and the next possible number will be tried in the calling search.
Do anyone have a better idea, because my code doesn't work correctly?
What I have tried:
package test;
public class Sudoku {
private final int BLOCK_SIZE = 3;
private final int ROW_SIZE = BLOCK_SIZE * BLOCK_SIZE;
private int nrOfSolutions, nrOfTests;
private int[][] board;
private int[][][] testBoard = {
{ { 5, 3, 0, 0, 7, 0, 0, 0, 0 }, { 6, 0, 0, 1, 9, 5, 0, 0, 0 }, { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
{ 8, 0, 0, 0, 6, 0, 0, 0, 3 }, { 4, 0, 0, 8, 0, 3, 0, 0, 1 }, { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
{ 0, 6, 0, 0, 0, 0, 2, 8, 0 }, { 0, 0, 0, 4, 1, 9, 0, 0, 5 }, { 0, 0, 0, 0, 8, 0, 0, 7, 9 } },
{ { 5, 3, 4, 6, 7, 8, 9, 1, 2 }, { 6, 7, 2, 1, 9, 5, 3, 4, 8 }, { 1, 9, 8, 3, 4, 2, 5, 6, 7 },
{ 8, 5, 9, 7, 6, 1, 4, 2, 3 }, { 4, 2, 6, 8, 5, 3, 7, 9, 1 }, { 7, 1, 3, 9, 2, 4, 8, 5, 6 },
{ 9, 6, 1, 5, 3, 7, 2, 8, 4 }, { 2, 8, 7, 4, 1, 9, 6, 3, 5 }, { 3, 4, 5, 2, 8, 6, 1, 7, 0 } },
{ { 0, 0, 0, 5, 4, 2, 0, 0, 0 }, { 9, 6, 7, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 3, 1, 8 },
{ 0, 0, 0, 0, 7, 0, 8, 6, 4 }, { 0, 2, 0, 6, 0, 4, 0, 9, 0 }, { 6, 4, 5, 0, 1, 0, 0, 0, 0 },
{ 8, 9, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 5, 4, 7 }, { 0, 0, 0, 3, 2, 6, 0, 0, 0 } },
};
public void testSudokuSolver() {
for (int[][] s : this.testBoard) {
this.board = s;
this.print();
nrOfSolutions = 0;
nrOfTests = 0;
this.solve(0, 0);
}
}
private boolean isBlockOk(int row, int col, int num) {
int iRowStart = (row / BLOCK_SIZE) * BLOCK_SIZE;
int iColStart = (col / BLOCK_SIZE) * BLOCK_SIZE;
for ( int irow = iRowStart; irow < iRowStart + BLOCK_SIZE; irow++) {
for ( int icol = iColStart; icol < iColStart + BLOCK_SIZE; icol++) {
if (num == board[irow][icol]) {
return false;
}
}
}
return true;
}
private boolean isRowOk(int row, int num) {
for (int i = 0; i < ROW_SIZE; i++) {
if (num == board[row][i]) {
return false;
}
}
return true;
}
private boolean isColOK(int col, int num) {
for (int i = 0; i < ROW_SIZE; i++) {
if (num == board[i][col]) {
return false;
}
}
return true;
}
public void print() {
final String horizBorder = " ┼────────┼────────┼────────┼";
System.out.println();
for (int i = 0; i < ROW_SIZE; i++) {
if (0 == i % 3) {
System.out.println(horizBorder);
}
for (int j = 0; j < ROW_SIZE; j++) {
if (0 == j % 3) {
System.out.print(" │ ");
}
int num = board[i][j];
if (num == 0) {
System.out.print("_ ");
} else {
System.out.print(num + " ");
}
}
System.out.println(" │");
}
System.out.println(horizBorder);
}
private boolean isValid(int num, int row, int col) {
return (isBlockOk(row, col, num) && isColOK(col, num) && isRowOk(row, num));
}
public boolean solve(int row, int col) {
for (int i = 1; i < BLOCK_SIZE; i++) {
for (int j = 1; j < BLOCK_SIZE; j++) {
if (board[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
board[i][j] = k;
if (isValid(i, j, k) && solve(i, col)) {
return true;
}
board[i][j] = 0;
}
return false;
}
}
}
return true;
}
public static void main(String[] args) {
new Sudoku().testSudokuSolver();
}
}