Sudoku Checker and Solver
Sudoku is a puzzle where we need to fill a 9×9 grid with digits from 1 to 9 such that each column, each row, and each of the nine 3×3 blocks contains all of the 1-9 digits.
Sudoku Checker
The problem is to check whether a given 9×9 array of integers from 1 to 9 is a valid solution to a Sudoku puzzle. For example, the following is a valid solution:
1 2 3 4 5 6 7 8 9 10 11 | 5 3 4 | 6 7 8 | 9 1 26 7 2 | 1 9 5 | 3 4 81 9 8 | 3 4 2 | 5 6 7------+-------+------8 5 9 | 7 6 1 | 4 2 34 2 6 | 8 5 3 | 7 9 17 1 3 | 9 2 4 | 8 5 6------+-------+------9 6 1 | 5 3 7 | 2 8 42 8 7 | 4 1 9 | 6 3 53 4 5 | 2 8 6 | 1 7 9 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | import java.util.Arrays;public class SudokoChecker{ public static boolean check(int[][] arr) { if (arr.length != 9) return false; for (int i = 0; i < 9; i++) { if (arr[i].length != 9) return false; for (int j = 0; j < 9; j++) if (arr[i][j] < 1 || arr[i][j] > 9) return false; } int[] counts = new int[9]; int good_count = 0; Arrays.fill(counts, 0); // rows for (int i = 0; i < 9; i++) { good_count++; for (int j = 0; j < 9; j++) { counts[arr[i][j] - 1]++; if (counts[arr[i][j] - 1] != good_count) return false; } } // columns for (int j = 0; j < 9; j++) { good_count++; for (int i = 0; i < 9; i++) { counts[arr[i][j] - 1]++; if (counts[arr[i][j] - 1] != good_count) return false; } } // blocks for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { good_count++; for (int r = i * 3; r < i * 3 + 3; r++) { for (int c = j * 3; c < j * 3 + 3; c++) { counts[arr[r][c] - 1]++; if (counts[arr[r][c] - 1] != good_count) return false; } } } } return true; } public static void main(String[] args) { int[][] arr = { {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, 9} }; System.out.println(check(arr)); }} |
Sudoku Solver
Given a Sudoku puzzle represented by a 9-by-9 array of integers from 0 to 9, find a solution by replacing all 0’s with a number from 1 to 9: each row, column, and block should contain each integer from 1 to 9 exactly once. The 0’s are placeholders, representing the blank spaces.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | import java.util.Arrays;public class SudokuSolver{ public static boolean isValid(int i, int j, int v, int[][] arr) { for (int k = 0; k < 9; k++) // row if (v == arr[i][k]) return false; for (int k = 0; k < 9; k++) // column if (v == arr[k][j]) return false; int r = (i / 3) * 3; int c = (j / 3) * 3; for (int k = 0; k < 3; ++k) // box for (int m = 0; m < 3; ++m) if (v == arr[r + k][c + m]) return false; return true; // valid } public static boolean solve(int[][] arr) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (arr[i][j] != 0) continue; for (int v = 1; v <= 9; v++) { if (isValid(i, j, v, arr)) { arr[i][j] = v; if (solve(arr)) return true; } } arr[i][j] = 0; // reset backtrack return false; } } return true; } public static void main(String[] args) { int[][] arr = { {0, 0, 0, 6, 7, 8, 9, 1, 2}, {0, 7, 2, 0, 9, 5, 3, 4, 8}, {0, 9, 8, 3, 0, 2, 5, 6, 7}, {8, 0, 9, 7, 6, 0, 4, 2, 3}, {4, 2, 0, 8, 5, 3, 0, 9, 1}, {7, 1, 3, 0, 2, 4, 8, 0, 6}, {9, 6, 1, 5, 0, 7, 2, 8, 0}, {2, 8, 7, 4, 1, 0, 6, 3, 0}, {3, 4, 5, 2, 8, 6, 0, 0, 0} }; if (!solve(arr)) System.out.println("no solution"); else for (int i = 0; i < arr.length; i++) System.out.println(Arrays.toString(arr[i])); }} |
The solve method above can be replaced by the following one, which is more efficient by avoid redundant checks. The method should be called using “solve(0, 0, arr)”.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | public static boolean solve(int i, int j, int[][] arr){ int next_i = i; int next_j = j; if (j == 8) { // next row next_i = i + 1; next_j = 0; } else next_j = j + 1; // skip if (arr[i][j] != 0) { if (next_i == 9) return true; return solve(next_i, next_j, arr); } // fill up for (int v = 1; v <= 9; v++) { if (isValid(i, j, v, arr)) { arr[i][j] = v; if (next_i == 9) return true; if (solve(next_i, next_j, arr)) return true; } } // reset for backtrack arr[i][j] = 0; return false;} |