I've this Sudoku code that's done using backtracking and I understand everything, except few lines of code which I ask to be explained. This is the whole code.
public class Sudoku {
static int N = 9;
static int grid[][] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 },
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 },
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };
static class Cell {
int row, col;
public Cell(int row, int col) {
super();
this.row = row;
this.col = col;
}
@Override
public String toString() {
return "Cell [row=" + row + ", col=" + col + "]";
}
};
static boolean isValid(Cell cell, int value) {
if (grid[cell.row][cell.col] != 0) {
throw new RuntimeException("Cannot call for cell which already has a value");
}
for (int c = 0; c < 9; c++) {
if (grid[cell.row][c] == value)
return false;
}
for (int r = 0; r < 9; r++) {
if (grid[r][cell.col] == value)
return false;
}
int x1 = 3 * (cell.row / 3);
int y1 = 3 * (cell.col / 3);
int x2 = x1 + 2;
int y2 = y1 + 2;
for (int x = x1; x <= x2; x++)
for (int y = y1; y <= y2; y++)
if (grid[x][y] == value)
return false;
return true;
}
static Cell getNextCell(Cell cur) {
int row = cur.row;
int col = cur.col;
col++;
if (col > 8) {
col = 0;
row++;
}
if (row > 8)
return null;
Cell next = new Cell(row, col);
return next;
}
static boolean solve(Cell cur) {
if (cur == null)
return true;
if (grid[cur.row][cur.col] != 0) {
return solve(getNextCell(cur));
}
for (int i = 1; i <= 9; i++) {
boolean valid = isValid(cur, i);
if (!valid)
continue;
grid[cur.row][cur.col] = i;
boolean solved = solve(getNextCell(cur));
if (solved)
return true;
else
grid[cur.row][cur.col] = 0;
}
return false;
}
public static void main(String[] args) {
boolean solved = solve(new Cell(0, 0));
if (!solved) {
System.out.println("SUDOKU cannot be solved.");
return;
}
System.out.println("SOLUTION\n");
printGrid(grid);
}
static void printGrid(int grid[][]) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++)
System.out.print(grid[row][col]);
System.out.println();
}
}
}
However, if you go to isValid method I can't really understand this part. If someone can explain this part in detail and what exactly it does, that would be great. I saw this in many codes, but I still can not comprehend it.
int x1 = 3 * (cell.row / 3);
int y1 = 3 * (cell.col / 3);
int x2 = x1 + 2;
int y2 = y1 + 2;
for (int x = x1; x <= x2; x++)
for (int y = y1; y <= y2; y++)
if (grid[x][y] == value)
return false;
return true;
int x1 = 3 * (cell.row / 3);
int y1 = 3 * (cell.col / 3);
int x2 = x1 + 2;
int y2 = y1 + 2;
for (int x = x1; x <= x2; x++)
for (int y = y1; y <= y2; y++)
if (grid[x][y] == value)
return false;
return true;
This block of code locates the 3x3 box containing your current number. The nested loops checks that the given number does not exist in the 3x3 box.
If you are wondering why the formula (divide by 3 then multiply by 3) followed by adding of 2. Take a look:
If current row is 0..8:
3 * (0 / 3) + 2 = 2 (read 3x3 box starting from pos 0 to 2)
3 * (1 / 3) + 2 = 2 (read 3x3 box starting from pos 0 to 2)
3 * (2 / 3) + 2 = 2 (read 3x3 box starting from pos 0 to 2)
3 * (3 / 3) + 2 = 5 (read 3x3 box starting from pos 3 to 5)
3 * (4 / 3) + 2 = 5 (read 3x3 box starting from pos 3 to 5)
3 * (5 / 3) + 2 = 5 (read 3x3 box starting from pos 3 to 5)
3 * (6 / 3) + 2 = 8 (read 3x3 box starting from pos 6 to 8)
3 * (7 / 3) + 2 = 8 (read 3x3 box starting from pos 6 to 8)
3 * (8 / 3) + 2 = 8 (read 3x3 box starting from pos 6 to 8)