Project Euler Solution 96: Su Doku
In this post we will look at Project Euler Problem 96 which is about solving Su Doku puzzles.
The first riddle is the following:
┌───────┬───────┬───────┐ │ 3 │ 2 │ 6 │ │ 9 │ 3 5 │ 1 │ │ 1 │ 8 6 │ 4 │ ├───────┼───────┼───────┤ │ 8 │ 1 2 │ 9 │ │ 7 │ │ 8 │ │ 6 │ 7 8 │ 2 │ ├───────┼───────┼───────┤ │ 2 │ 6 9 │ 5 │ │ 8 │ 2 3 │ 9 │ │ 5 │ 1 │ 3 │ └───────┴───────┴───────┘
According to the problem statement, there are always unique solutions. This doesn't necessarily mean that we don't have to keep some state while searching. At first I'd like to take a very simple approach without any graph search and rather try whether it is possible to solve them without any temporary state.
The Su Doku rule is that no number must occur another time in the same row, column or sub-square. If we take a look at the number of possibilities that we have for each position, we can see whether there is exactly one possibility (=) or more than one (+):
┌───────┬───────┬───────┐ │ + + │ + + │ + + │ │ + + │ + │ + + │ │ + + │ + │ + + │ ├───────┼───────┼───────┤ │ + + │ + │ + + │ │ + + │ + + = │ = + │ │ + + │ + │ + + │ ├───────┼───────┼───────┤ │ + + │ + │ + + │ │ + + │ + │ + + │ │ + + │ = + │ + + │ └───────┴───────┴───────┘
There are a couple of positions where we have exactly one possibility. We can fill those in. With these positions filled, we then have the following:
┌───────┬───────┬───────┐ │ 3 │ 2 │ 6 │ │ 9 │ 3 5 │ 1 │ │ 1 │ 8 6 │ 4 │ ├───────┼───────┼───────┤ │ 8 │ 1 2 │ 9 │ │ 7 │ 4 │ 1 8 │ │ 6 │ 7 8 │ 2 │ ├───────┼───────┼───────┤ │ 2 │ 6 9 │ 5 │ │ 8 │ 2 3 │ 7 9 │ │ 5 │ 4 1 7 │ 3 │ └───────┴───────┴───────┘
I didn't freeze the grid for this pass, so there are a few positions filled in which only became unique after filling in others. But I've only made one pass through the riddle.
We can then look whether there are more positions ripe for filling in. And indeed, there are a couple of = symbols:
┌───────┬───────┬───────┐ │ + + │ = = │ + + │ │ + + │ + │ = + │ │ + + │ + │ + + │ ├───────┼───────┼───────┤ │ + + │ + │ + + │ │ + = │ + + │ + │ │ + + │ + │ + + │ ├───────┼───────┼───────┤ │ + + │ = │ + = │ │ + = │ = │ + │ │ = + │ │ + + │ └───────┴───────┴───────┘
We can do this again and again until hopefully all fields are filled in. When we do that, we get this:
┌───────┬───────┬───────┐ │ 4 8 3 │ 9 2 1 │ 6 5 7 │ │ 9 6 7 │ 3 4 5 │ 8 2 1 │ │ 2 5 1 │ 8 7 6 │ 4 9 3 │ ├───────┼───────┼───────┤ │ 5 4 8 │ 1 3 2 │ 9 7 6 │ │ 7 2 9 │ 5 6 4 │ 1 3 8 │ │ 1 3 6 │ 7 9 8 │ 2 4 5 │ ├───────┼───────┼───────┤ │ 3 7 2 │ 6 8 9 │ 5 1 4 │ │ 8 1 4 │ 2 5 3 │ 7 6 9 │ │ 6 9 5 │ 4 1 7 │ 3 8 2 │ └───────┴───────┴───────┘
That seems to be the solution for the example given in the problem statement.
Does it hold for all given riddles?
It is not clear whether all the ones that are given are solvable with this approach. And indeed, the very next problem cannot be solved using this approach:
┌───────┬───────┬───────┐ │ 2 │ 8 │ 3 │ │ 6 │ 7 │ 8 4 │ │ 3 │ 5 │ 2 9 │ ├───────┼───────┼───────┤ │ │ 1 5 │ 4 8 │ │ │ │ │ │ 4 2 │ 7 6 │ │ ├───────┼───────┼───────┤ │ 3 1 │ 7 │ 4 │ │ 7 2 │ 4 │ 6 │ │ 4 │ 1 │ 3 │ └───────┴───────┴───────┘
The approach manages to put in the "6" in the upper middle sub-square:
┌───────┬───────┬───────┐ │ 2 │ 8 │ 3 │ │ 6 │ 7 │ 8 4 │ │ 3 │ 5 6 │ 2 9 │ ├───────┼───────┼───────┤ │ │ 1 5 │ 4 8 │ │ │ │ │ │ 4 2 │ 7 6 │ │ ├───────┼───────┼───────┤ │ 3 1 │ 7 │ 4 │ │ 7 2 │ 4 │ 6 │ │ 4 │ 1 │ 3 │ └───────┴───────┴───────┘
But then there is no clear way to fill in more spots. We do need explore possibilities.
Backtracking
A classical approach here is backtracking. We'll just go through the cells one-by-one and see what possibilities we have. We then pick the first option and go to the next cell. There we do the same. We proceed through all the cells until we either have filled all cells (success) or run out of options. In that case we go back to the previous cell (backtracking) and take the second option there. Then we proceed again.
This way we end up trying all possibilities in a systematic fashion. It is a depth-first search approach and commonly used for many things.
Let's go through the code. First I define a Grid type which will be a two-dimensional list of integers that we'll use to store the riddles.
Grid = list[list[int]]
Next is a generator that just reads the riddles from the file:
def iter_problems() -> Iterator[list[list[int]]]: with open("data/p096_sudoku.txt") as f: rows = [] for line in f: if line.startswith("Grid"): rows = [] else: rows.append([int(d) for d in line.strip()]) if len(rows) == 9: yield rows
One convenient helper is one that iterates all the entries within the current sub-square:
def iter_square(grid: Grid, row: int, col: int) -> Iterator[int]: row -= row % 3 col -= col % 3 for i in range(3): for j in range(3): yield grid[row + i][col + j]
To compute the possibilities that we have, we start with a set of all digits and discard the ones that are in the same row, the same column or the same sub-square.
def get_possibilities(grid: Grid, row: int, col: int) -> set[int]: if grid[row][col]: return set() possible = set(range(1, 10)) for c in range(9): possible.discard(grid[row][c]) for r in range(9): possible.discard(grid[r][col]) for elem in iter_square(grid, row, col): possible.discard(elem) return possible
To generate the ASCII-art images for this page, I've also written a function to print. A good visualization always helps.
def print_grid(grid) -> None: print("┌───────┬───────┬───────┐") for rb in range(3): if rb > 0: print("├───────┼───────┼───────┤") for r in range(3): for cb in range(3): print("│", end="") for c in range(3): print(" ", end="") print(grid[rb * 3 + r][cb * 3 + c] or " ", end="") print(" ", end="") print("│") print("└───────┴───────┴───────┘")
The backtracking is implemented as a recursive function. It will fill in the grid and then proceed to the next cell. The return value indicates whether a solution has been found, in that case the search is aborted. The problem statement said that the solution is unique, therefore this is fine. If no solution is found and we need to backtrack, the cell is cleared again with a 0.
def fill_in(grid: Grid, row: int, col: int) -> bool: if row >= 9: return True if grid[row][col]: return fill_in(grid, row + 1 if col == 8 else row, (col + 1) % 9) possibilities = get_possibilities(grid, row, col) for possibility in possibilities: grid[row][col] = possibility if fill_in(grid, row + 1 if col == 8 else row, (col + 1) % 9): return True grid[row][col] = 0 return False
For the end result we need to get the three digit number at the top left of the solved riddle.
def grid_number(grid) -> int: for row in range(9): for col in range(9): assert grid[row][col], grid return int("".join(map(str, grid[0][0:3])))
The solution just iterates over the problems, fills them in, asserts that a solution was found, and then adds the number to the solution.
def solution() -> int: s = 0 for grid in iter_problems(): assert fill_in(grid, 0, 0) s += grid_number(grid) return s
This runs in 6.2 s, which seems reasonably fast. Perhaps there are even more elaborate graph search algorithms for this one, which can make it a bit faster. This approach here seems to be sufficient.