Loading…
Loading…
Backtracking at its most recognisable: try a digit, recurse, and erase it the moment the branch dies.
73 digits are given and 8 cells are blank. Backtracking fills them in reading order, trying 1 to 9 in each and undoing as soon as a cell has no legal digit left.
1boolean solve(int[][] b) {2 for (int r = 0; r < 9; r++)3 for (int c = 0; c < 9; c++) {4 if (b[r][c] != 0) continue;5 for (int d = 1; d <= 9; d++) {6 if (!legal(b, r, c, d)) continue; // row, column and 3×3 box must all agree7 b[r][c] = d;8 if (solve(b)) return true;9 b[r][c] = 0; // undo — this is the backtrack10 }11 return false;12 }13 return true; // no blanks left → solved14}