The other day I thought about whether it would take a “while” for a computer to solve a sudoku puzzle using a naiive brute-force algorithm. I set out to find out.
In this article I use my bread-and-butter programming language Java to create such a solver in a kind of test driven way and also explore some simple optimizations.
Implementation idea:
- use a backtracking algorithm, that means recursively go from cell to cell on the puzzle board and fill in numbers from 1 to 9 and check if all rules are satisfied. For example:
- It starts with top left, fill in “1”. All rules satisfied – got to the next.
- Fill in “1” – two 1s in a row – try with “2”, all rules satisfied, go to the next. And so on.
- If in a cell no number satisfy the rules, go back to the previous cell and try the next number there.
- The puzzle board is represented as a 2-dimensional array.
- The number “0” represents an empty cell.
Recap of the sudoku rules: In all horizontal and all vertical lines the numbers 1 to 9 are filled in exactly once plus in each 3×3 “subsquare” / “subboard” the numbers 1 to 9 are filled in exactly once.
Step 1: The Solver accepts an already completed board
When the board is already filled out, the Solver returns the board. It does not check if the board is correctly filled out. The following test checks this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
@Test public void fineWithFilledMatrix() { final int[][] matrix = new int[9][9]; for(int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { matrix[i][j] = 1; } } matrix[0][0] = 5; System.out.println(Solver.matrixToString(matrix)); final var result = new Solver().nextField(0, 0, matrix); System.out.println(Solver.matrixToString(matrix)); final int[][] expected = new int[9][9]; for(int i = 0; i < expected.length; i++) { for (int j = 0; j < expected[i].length; j++) { expected[i][j] = 1; } } expected[0][0] = 5; Assert.assertFalse(result.isEmpty()); Assert.assertArrayEquals(expected, result.get()); } |
It creates a board (I call this “matrix” here) and fills it with “ones” except for the very first cell which gets a 5. It feeds it to the solver and checks whether it gets it back as solved.
Here is the code that accomplishes it:
|
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 |
package de.epischel.hello.sudoku; import java.util.Optional; public class Solver { public Optional<int[][]> nextField(int x, int y, int[][] matrix) { if (y==9 && x == 0) { return Optional.of(matrix); } if (matrix[y][x]>0) { int nextX = x<8?x+1:0; int nextY = x<8?y:y+1; return nextField(nextX, nextY, matrix); } return Optional.empty(); } public static String matrixToString(int[][] matrix) { StringBuilder sb = new StringBuilder(); for(int y = 0; y < matrix.length; y++) { for(int x=0; x < matrix[y].length; x++) { sb.append(" ").append(matrix[y][x]).append(" "); } sb.append("\n"); } return sb.toString(); } } |
The method “nextField” takes the current coordinates x and y and the matrix aka the board. It first checks whether it is just outside the board which means the board has been filled out. If so it returns the board. Otherwise if the current cell is already filled in, it recursivly calls the next cell. If the the current cell is not filled in, it returns an empty Optional, indicating it can’t fill in the cell.
Step 2: Adding the “horizontal rule”
Next we want to actually fill in numbers into an empty cell and check against the rule, that each row has pairwise distinct numbers in it.
First, here is the test:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
@Test public void followRuleHorizontal() { final int[][] matrix = new int[9][9]; for(int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { matrix[i][j] = j+1; } } matrix[0][3] = 0; matrix[0][4] = 0; matrix[5][5] = 0; matrix[5][7] = 0; System.out.println(Solver.matrixToString(matrix)); final var result = new Solver().solve(matrix); System.out.println(Solver.matrixToString(matrix)); final int[][] expected = new int[9][9]; for(int i = 0; i < expected.length; i++) { for (int j = 0; j < expected[i].length; j++) { expected[i][j] = j+1; } } Assert.assertFalse(result.isEmpty()); Assert.assertArrayEquals(expected, result.get()); } |
It creates a board with each row numbers incrementally from one to nine and then “blanks” four cells. The solver should fill these cells with the correct numbers. Here is how it’s done (note: I introduce a “solve” method):
|
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 |
public Optional<int[][]> solve(int[][] matrix) { return nextField(0,0,matrix); } public Optional<int[][]> nextField(int x, int y, int[][] matrix) { if (y==9 && x == 0) { return Optional.of(matrix); } if (matrix[y][x]>0) { int nextX = x<8?x+1:0; int nextY = x<8?y:y+1; return nextField(nextX, nextY, matrix); } for(int i = 1; i<=9; i++) { matrix[y][x] = i; // check horizontal rule if (!isPotentialLegal( matrix[y][0],matrix[y][1],matrix[y][2], matrix[y][3],matrix[y][4],matrix[y][5], matrix[y][6],matrix[y][7],matrix[y][8])) { continue; } int nextX = x<8?x+1:0; int nextY = x<8?y:y+1; return nextField(nextX, nextY, matrix); } return Optional.empty(); } private static boolean isPotentialLegal(int... numbers) { final int[] counts = new int[10]; for(int i = 0; i < numbers.length; i++) { counts[numbers[i]]++; } for(int i = 1; i < counts.length; i++) { if (counts[i]>1) return false; } return true; } |
“isPotentialLegal” checks for distinct numbers by counting its occurences. It is called with all numbers of the current row. Zeros are “ignored”. If the rule is not satisfied, the next number is tried.
Step 3: Adding the “vertical rule”
Now I add the rule for columns. To create a test, I use a solved sudoku puzzle and clear some cells:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
final int[][] matrix = new int[][] { {7,9,0,3,5,4,6,0,8}, {8,0,4,1,2,6,3,0,7}, {3,0,1,9,8,7,5,2,4}, // {9,4,5,6,0,8,1,7,2}, {2,7,8,5,4,1,9,3,6}, {6,1,3,0,9,2,8,4,5}, // {4,2,9,8,1,5,7,6,3}, {1,8,7,2,6,3,4,5,9}, {5,3,6,4,7,9,2,0,0}, }; |
and later check for the correct solution.
The implementation is straight forward next to the “horizonal rule”:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
if (!isPotentialLegal( matrix[y][0],matrix[y][1],matrix[y][2], matrix[y][3],matrix[y][4],matrix[y][5], matrix[y][6],matrix[y][7],matrix[y][8]) || !isPotentialLegal( matrix[0][x],matrix[1][x],matrix[2][x], matrix[3][x],matrix[4][x],matrix[5][x], matrix[6][x],matrix[7][x],matrix[8][x]) ) { continue; } |
Step 4: Adding the “subquadrant rule”
I wondered a bit about how to create a puzzle that would not be solvable without the subquadrant rule, but the original puzzle from Step 3 already did that. It has far more empty cells:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
final int[][] matrix = new int[][] { {0,9,0, 0,0,0, 0,1,0}, {8,0,4, 0,2,0, 3,0,7}, {0,6,0, 9,0,7, 0,2,0}, // {0,0,5, 0,3,0, 1,0,0}, {0,7,0, 5,0,1, 0,3,0}, {0,0,3, 0,9,0, 8,0,0}, // {0,2,0, 8,0,5, 0,6,0}, {1,0,7, 0,6,0, 4,0,9}, {0,3,0, 0,0,0, 0,8,0}, }; |
So here is the subquadrant rule. The key is to get the coordinates of the “subquadrant” right: integer division does the job, i.e. “(x/3)*3”. For example x=4 gets us “3” because it is the middle subquadrant starting at x=3. I use an extra method here because of the computation of the subquadrant start:
|
1 2 3 4 5 6 7 8 |
private boolean isSubquadratPotentialLegal(int x, int y, int[][] matrix) { final int xx = (x/3)*3; final int yy = (y/3)*3; return isPotentialLegal( matrix[yy][xx],matrix[yy][xx+1],matrix[yy][xx+2], matrix[yy+1][xx],matrix[yy+1][xx+1],matrix[yy+1][xx+2], matrix[yy+2][xx],matrix[yy+2][xx+1],matrix[yy+2][xx+2]); } |
That did not made the test pass, though! It turned out I missed the backtracking-step, i.e. what happens when the recursion does not return a valid result – try next number (line 29):
|
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 |
public Optional<int[][]> nextField(int x, int y, int[][] matrix) { if (y==9 && x == 0) { return Optional.of(matrix); } if (matrix[y][x]>0) { int nextX = x<8?x+1:0; int nextY = x<8?y:y+1; return nextField(nextX, nextY, matrix); } for(int i = 1; i<=9; i++) { matrix[y][x] = i; // check horizontal rule if (!(isPotentialLegal( matrix[y][0],matrix[y][1],matrix[y][2], matrix[y][3],matrix[y][4],matrix[y][5], matrix[y][6],matrix[y][7],matrix[y][8]) && // check vertical rule isPotentialLegal( matrix[0][x],matrix[1][x],matrix[2][x], matrix[3][x],matrix[4][x],matrix[5][x], matrix[6][x],matrix[7][x],matrix[8][x]) && isSubquadratPotentialLegal(x, y, matrix))) { continue; } int nextX = x<8?x+1:0; int nextY = x<8?y:y+1; final var result = nextField(nextX, nextY, matrix); if (result.isPresent()) return result; } matrix[y][x] = 0; return Optional.empty(); } |
Moreover, line 31 “empties” the cell so that we leave it in the starting state.
Conclusion
That’s it, I implemented a sudoku solver guided by tests. To answer my initial question: it’s fast. Well under one second! I will write a follow-up discussion some optimizations.