{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Peter Norvig
2006, 2021
\n",
"\n",
"# Solving Any Sudoku Puzzle\n",
"\n",
"The rules of Sudoku are simple and finite: fill in the empty squares in the puzzle so that each column, row, and 3×3 box contains all the digits from 1 to 9 with no repeats. For example:\n",
"\n",
"|Puzzle|-|Solution|\n",
"|---|--|---|\n",
"|| ||\n",
"\n",
"This notebook develops a program to solve any Sudoku puzzle, in about 80 lines of Python. You can also see:\n",
" - The [original 2006 version of this program](http://norvig.com/sudoku.html); it has some obsolete Python idioms.\n",
" - [A Java program for Sudoku](SudokuJava.ipynb) that is less clear but faster, solving over 100,000 puzzles per second.\n",
" - [A Python program for Star Battle](StarBattle.ipynb), a related fill-in-the-grid puzzle.\n",
" - [A Python program for KenKen](KenKen.ipynb), a related fill-in-the-grid puzzle.\n",
"\n",
"\n",
"# Sudoku: Implementing Basic Concepts \n",
"\n",
"Here are the key concepts and the Python implementation choices I made. Types are in Uppercase and constants in lowercase:\n",
"\n",
"- **Digit**: the digits are the characters `'1'` to `'9'`. \n",
"- **Digit set**: when several digits could fill a square, use `'123'` to mean 1, 2, or 3 are possible.\n",
"- **rows**: by convention the 9 rows have labels `'A'` to `'I'` (top to bottom). \n",
"- **columns**: by convention the 9 columns have labels `'1'` to `'9'` (left to right).\n",
"- **Square**: a square is named by the concatenation of its row and column labels, e.g. `'A9'` is the upper-rightmost square.\n",
" - `squares` is a tuple of all 81 squares.\n",
"- **Grid**: a grid of 81 squares is represented as a dict of `{Square: DigitSet}` such as `{'A9': '123', ...}`.\n",
"- **Boxes**: the 9 boxes are 3×3 squares within the grid (outlined with heavy black lines in the diagram). \n",
" - `all_boxes` is a list of all 9 boxes\n",
"- **Unit**: a unit is a row, column, or box; each unit is a tuple of 9 squares. \n",
" - `all_units` is a list of all 27 units.\n",
" - `units` is a dict such that `units[s]` is a tuple of the 3 units that square `s` is a part of.\n",
"- **Peers**: the squares that share a unit are called peers. \n",
" - `peers` is a dict such that `peers[s]` is a set of 20 squares that are in some unit with `s`.\n",
"- **None**: If a puzzle has no solution, we represent that with `None`.\n",
"- **Picture**: for input and output, a string is used to describe the grid (details described below).\n",
"- **Solution**: A grid is a valid solution to a puzzle if every unit is filled with all nine digits, one to a square, with no repeats, and each square that was filled with a digit in the puzzle has the same digit in the solution."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import re\n",
"from typing import Dict, Optional\n",
"\n",
"def cross(A, B) -> tuple:\n",
" \"Cross product of strings in A and strings in B.\"\n",
" return tuple(a + b for a in A for b in B)\n",
"\n",
"Digit = str # e.g. '1'\n",
"digits = '123456789'\n",
"DigitSet = str # e.g. '123'\n",
"rows = 'ABCDEFGHI'\n",
"cols = digits\n",
"Square = str # e.g. 'A9'\n",
"squares = cross(rows, cols)\n",
"Grid = Dict[Square, DigitSet] # E.g. {'A9': '123', ...}\n",
"all_boxes = [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]\n",
"all_units = [cross(rows, c) for c in cols] + [cross(r, cols) for r in rows] + all_boxes\n",
"units = {s: tuple(u for u in all_units if s in u) for s in squares}\n",
"peers = {s: set().union(*units[s]) - {s} for s in squares}\n",
"Picture = str \n",
"\n",
"def is_solution(solution: Grid, puzzle: Grid) -> bool:\n",
" \"Is this proposed solution to the puzzle actually valid?\"\n",
" return (solution is not None and\n",
" all(solution[s] in puzzle[s] for s in squares) and\n",
" all({solution[s] for s in unit} == set(digits) for unit in all_units))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For example,\n",
"here are the three units (and the 20 peers) for the square C2:\n",
"\n",
"\n",
". A2 . |. . . |. . . . . . |. . . |. . . A1 A2 A3|. . . |. . . \n",
". B2 . |. . . |. . . . . . |. . . |. . . B1 B2 B3|. . . |. . . \n",
". C2 . |. . . |. . . C1 C2 C3|C4 C5 C6|C7 C8 C9 C1 C2 C3|. . . |. . . \n",
"--------+--------+-------- --------+--------+-------- --------+--------+-------- \n",
". D2 . |. . . |. . . . . . |. . . |. . . . . . |. . . |. . . \n",
". E2 . |. . . |. . . . . . |. . . |. . . . . . |. . . |. . . \n",
". F2 . |. . . |. . . . . . |. . . |. . . . . . |. . . |. . . \n",
"--------+--------+-------- --------+--------+-------- --------+--------+-------- \n",
". G2 . |. . . |. . . . . . |. . . |. . . . . . |. . . |. . . \n",
". H2 . |. . . |. . . . . . |. . . |. . . . . . |. . . |. . . \n",
". I2 . |. . . |. . . . . . |. . . |. . . . . . |. . . |. . . \n",
"\n",
"\n",
" \n",
"\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(('A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'),\n",
" ('C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'),\n",
" ('A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3'))"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"units['C2']"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'A1',\n",
" 'A2',\n",
" 'A3',\n",
" 'B1',\n",
" 'B2',\n",
" 'B3',\n",
" 'C1',\n",
" 'C3',\n",
" 'C4',\n",
" 'C5',\n",
" 'C6',\n",
" 'C7',\n",
" 'C8',\n",
" 'C9',\n",
" 'D2',\n",
" 'E2',\n",
" 'F2',\n",
" 'G2',\n",
" 'H2',\n",
" 'I2'}"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"peers['C2']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Constraint Propagation\n",
"\n",
"Sudoku players know these two key strategies:\n",
"\n",
"1. If a square has only one possible digit, then **eliminate** that digit as a possibility for each of the square's peers.\n",
"2. If a unit has only one possible square that can hold a digit, then **fill** the square with the digit.\n",
"\n",
"This suggests two functions:\n",
"1. `eliminate(grid, s, d)` to eliminate digit `d` as a possibility for square `s`\n",
"2. `fill(grid, s, d)` to fill square `s` with the digit `d`. \n",
"\n",
"You might think that `fill` is the most fundamental operation, and that it could be implemented with `grid[s] = d`. But it turns out the code is simpler if we think of `eliminate` as the fundamental operation, and implement `fill` as \"eliminate all the digits except for `d` from `s`.\" Both functions mutate the grid they are passed, and return the mutated grid if they can perform the operation, or return `None` if there is a contradiction.\n",
"\n",
"We say that these two strategies constitute [constraint propagation](http://en.wikipedia.org/wiki/Constraint_satisfaction): \"constraint\" because they constrain what values can go in what squares, and \"propagation\" because a `fill` of one square can lead to an `eliminate` in other squares, which can in turn cause a `fill` of yet another square, and so on. \n",
"\n",
"The function `constrain` starts the whole process off. We initialize a new grid, `result`, (so that the original puzzle is not mutated), where `result` is filled with the known digits from the original grid. \n",
"\n",
"Here is the code:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def constrain(grid) -> Grid:\n",
" \"Propagate constraints on a copy of grid to yield a new constrained Grid.\"\n",
" result: Grid = {s: digits for s in squares}\n",
" for s in grid:\n",
" if len(grid[s]) == 1:\n",
" fill(result, s, grid[s])\n",
" return result\n",
"\n",
"def fill(grid: Grid, s: Square, d: Digit) -> Optional[Grid]:\n",
" \"\"\"Eliminate all the digits except d from grid[s].\"\"\"\n",
" if grid[s] == d or all(eliminate(grid, s, d2) for d2 in grid[s] if d2 != d):\n",
" return grid\n",
" else:\n",
" return None\n",
"\n",
"def eliminate(grid: Grid, s: Square, d: Digit) -> Optional[Grid]:\n",
" \"\"\"Eliminate d from grid[s]; implement the two constraint propagation strategies.\"\"\"\n",
" if d not in grid[s]:\n",
" return grid ## Already eliminated\n",
" grid[s] = grid[s].replace(d, '')\n",
" if not grid[s]:\n",
" return None ## None: no legal digit left\n",
" elif len(grid[s]) == 1:\n",
" # 1. If a square has only one possible digit, then eliminate that digit as a possibility for each of the square's peers.\n",
" d2 = grid[s]\n",
" if not all(eliminate(grid, s2, d2) for s2 in peers[s]):\n",
" return None ## None: can't eliminate d2 from some square\n",
" for u in units[s]:\n",
" dplaces = [s for s in u if d in grid[s]]\n",
" # 2. If a unit has only one possible square that can hold a digit, then fill the square with the digit.\n",
" if not dplaces or (len(dplaces) == 1 and not fill(grid, dplaces[0], d)):\n",
" return None ## None: no place in u for d\n",
" return grid"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Input and Output: Pictures and Grids\n",
"\n",
"To show how constraint propagation works, we will need to read in a string representing a puzzle (what we call a `Picture`), convert that picture to a `Grid`, apply constraint propagation, convert the solution back to a picture, and display the picture. Conventions for `Picture`:\n",
"- A filled square is represented by a single digit, e.g.: `5`.\n",
"- A blank square is represented by a period: `.`.\n",
"- Spaces, newlines, and dashes/bars to separate boxes are included on output, but are optional (and ignored) on input.\n",
"- An uncertain square is represented by a DigitSet in braces, e.g.: `{123}`."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"def parse(picture) -> Grid:\n",
" \"\"\"Convert a Picture to a Grid.\"\"\"\n",
" vals = re.findall(r\"[.1-9]|[{][1-9]+[}]\", picture)\n",
" assert len(vals) == 81\n",
" return {s: digits if v == '.' else re.sub(r\"[{}]\", '', v) \n",
" for s, v in zip(squares, vals)}\n",
"\n",
"def picture(grid) -> Picture:\n",
" \"\"\"Convert a Grid to a Picture string, one line at a time.\"\"\"\n",
" if grid is None: \n",
" return \"None\"\n",
" def val(d: DigitSet) -> str: return '.' if d == digits else d if len(d) == 1 else '{' + d + '}'\n",
" maxwidth = max(len(val(grid[s])) for s in grid)\n",
" dash1 = '-' * (maxwidth * 3 + 2)\n",
" dash3 = '\\n' + '+'.join(3 * [dash1])\n",
" def cell(r, c): return val(grid[r + c]).center(maxwidth) + ('|' if c in '36' else ' ')\n",
" def line(r): return ''.join(cell(r, c) for c in cols) + (dash3 if r in 'CF' else '')\n",
" return '\\n'.join(map(line, rows))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here we parse a picture string into a grid, and then print the grid's picture:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5 3 .|. 7 .|. . . \n",
"6 . .|1 9 5|. . . \n",
". 9 8|. . .|. 6 . \n",
"-----+-----+-----\n",
"8 . .|. 6 .|. . 3 \n",
"4 . .|8 . 3|. . 1 \n",
"7 . .|. 2 .|. . 6 \n",
"-----+-----+-----\n",
". 6 .|. . .|2 8 . \n",
". . .|4 1 9|. . 5 \n",
". . .|. 8 .|. 7 9 \n"
]
}
],
"source": [
"pic1 = \"53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79\"\n",
"grid1 = parse(pic1)\n",
"print(picture(grid1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In a grid, filled squares (like `A1`, the upper left corner of `grid1`) have one possible digit, and unfilled squares (like `A9`, the upper right corner of `grid1`) have all 9 possible digits:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'5'"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grid1['A1']"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'123456789'"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grid1['A9']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To see how this all works, let's look again at `grid1`:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5 3 .|. 7 .|. . . \n",
"6 . .|1 9 5|. . . \n",
". 9 8|. . .|. 6 . \n",
"-----+-----+-----\n",
"8 . .|. 6 .|. . 3 \n",
"4 . .|8 . 3|. . 1 \n",
"7 . .|. 2 .|. . 6 \n",
"-----+-----+-----\n",
". 6 .|. . .|2 8 . \n",
". . .|4 1 9|. . 5 \n",
". . .|. 8 .|. 7 9 \n"
]
}
],
"source": [
"print(picture(grid1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Constraint propagation will at some point consider the square `E5`, in the center of the center box. It is in a row with the digits 4, 8, 3, 1, and in a column with the digits 7, 9, 6, 2, 1, 8. If according to strategy 1 we call `eliminate(grid1, 'E5', d)` for each of these digits, then we're left with only one possible digit, `5`, for `E5`. Thus, we would next call `eliminate(grid1, s2, '5')` for each peer `s2` of 'E5'. This would lead to the square three columns to the left, `E2`, only having one remaining possible digit, `2`. Constraint propagation continues in this fashion.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Many puzzles can be completely solved by `constrain` alone, for example:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5 3 4|6 7 8|9 1 2 \n",
"6 7 2|1 9 5|3 4 8 \n",
"1 9 8|3 4 2|5 6 7 \n",
"-----+-----+-----\n",
"8 5 9|7 6 1|4 2 3 \n",
"4 2 6|8 5 3|7 9 1 \n",
"7 1 3|9 2 4|8 5 6 \n",
"-----+-----+-----\n",
"9 6 1|5 3 7|2 8 4 \n",
"2 8 7|4 1 9|6 3 5 \n",
"3 4 5|2 8 6|1 7 9 \n"
]
}
],
"source": [
"print(picture(constrain(grid1)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"But for other puzzles, `constrain` is not enough:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4 . .|. . .|8 . 5 \n",
". 3 .|. . .|. . . \n",
". . .|7 . .|. . . \n",
"-----+-----+-----\n",
". 2 .|. . .|. 6 . \n",
". . .|. 8 .|4 . . \n",
". . .|. 1 .|. . . \n",
"-----+-----+-----\n",
". . .|6 . 3|. 7 . \n",
"5 . .|2 . .|. . . \n",
"1 . 4|. . .|. . . \n"
]
}
],
"source": [
"grid2 = parse(\"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......\")\n",
"print(picture(grid2))"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 4 {1679} {12679} | {139} {2369} {269} | 8 {1239} 5 \n",
" {26789} 3 {1256789}| {14589} {24569} {245689}| {12679} {1249} {124679} \n",
" {2689} {15689} {125689}| 7 {234569} {245689}| {12369} {12349} {123469} \n",
"-----------------------------+-----------------------------+-----------------------------\n",
" {3789} 2 {15789} | {3459} {34579} {4579} | {13579} 6 {13789} \n",
" {3679} {15679} {15679} | {359} 8 {25679} | 4 {12359} {12379} \n",
" {36789} 4 {56789} | {359} 1 {25679} | {23579} {23589} {23789} \n",
"-----------------------------+-----------------------------+-----------------------------\n",
" {289} {89} {289} | 6 {459} 3 | {1259} 7 {12489} \n",
" 5 {6789} 3 | 2 {479} 1 | {69} {489} {4689} \n",
" 1 {6789} 4 | {589} {579} {5789} | {23569} {23589} {23689} \n"
]
}
],
"source": [
"print(picture(constrain(grid2)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that some progress has been made: the `grid2` puzzle has 17 squares filled in, and after constraint propagation, 20 are filled in. But that leaves 61 squares to go. We could try to add [additional constraint propagation strategies](https://bestofsudoku.com/sudoku-strategy), but there are many strategies, each one complicates the code, and even if we implemented them all, we wouldn't be *guaranteed* they could solve *any* puzzle. \n",
"\n",
"\n",
"# Search Strategy\n",
"\n",
"We need a strategy that will **search** through all possibile solutions, systematically and efficiently, until the solution is found. (A well-formed Sudoku puzzle has exactly one solution). \n",
"\n",
"A naive search can be slow. Consider a brute force search that tries every possible combination of digits. In the constrained `grid2` above, `A2` has 4 possibilities, `{1679}`, `A3` has 5, `{12679}`, and if we keep going and multiply all the choices together, [we get over 1038](http://www.google.com/search?hl=en&q=4*5*3*4*3*4*5*7*5*5*6*5*4*6*4*5*6*6*6*5*5*6*4*5*4*5*4*5*5*4*5*5*3*5*5*5*5*5*3*5*5*5*5*3*2*3*3*4*5*4*3*2*3*4*4*3*3*4*5*5*5) possibilities for the whole\n",
"puzzle. Suppose we have a\n",
"very efficient implementation that takes only ten CPU instructions to evaluate a\n",
"position, and that we have access to next-generation computers\n",
"with 1024–core CPUs running at 100 GHz, and let's say\n",
"we could afford a million of them, and while we're shopping, let's also pick up a time machine and go back 13 billion years to the origin of the universe and start our program running. We can then [estimate](http://www.google.com/search?&q=100+GHz/10+*+1024+*+1+million+*+13+billion+years+%2F+4.6e38+in+percent)\n",
"that we'd be almost 1% done with this one puzzle by now! Brute force is not the search you're looking for.\n",
"\n",
"It is too slow to do constraint propagation first and then search. A smarter strategy is to **interleave** constraint propagation and search as follows:\n",
" - If a previous step of the search on this branch returned `None`, then pass the `None` along.\n",
" - If there are no squares with multiple possibilities in the puzzle, then return the completed grid.\n",
" - Otherwise choose one of the not-yet-determined squares, *s*. \n",
" - For each digit *d* that could possibly fill square *s*:\n",
" - Initiate constraint propagation by calling `fill` on *s* and *d* and a copy of the grid.\n",
" - Recursively search for a solution to the puzzle from there.\n",
" - If the guess was right, we will get a solution.\n",
" - If the guess was wrong, continue on to the next digit *d*.\n",
"\n",
"Because we give up as soon as we get a contradiction, we examine far fewer possibilities than brute force search. Here is the implementation:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"def search(grid) -> Grid:\n",
" \"Depth-first search with constraint propagation to find a solution.\"\n",
" if grid is None: \n",
" return None\n",
" s = min((s for s in squares if len(grid[s]) > 1), \n",
" default=None, key=lambda s: len(grid[s]))\n",
" if s is None: # No squares with multiple possibilities; the search has succeeded\n",
" return grid\n",
" for d in grid[s]:\n",
" solution = search(fill(grid.copy(), s, d))\n",
" if solution:\n",
" return solution\n",
" return None"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are two choices we have to make in implementing the search:\n",
"**variable ordering** (which square do we try first?) and **value\n",
"ordering** (which digit do we try first for the square?). For\n",
"variable ordering, I used a common heuristic called **minimum\n",
"remaining values**, which means that we choose a \n",
"square with the minimum number of possible values. Why? Consider \n",
"`grid2` above. Suppose we chose `B3` first. It has 7\n",
"possibilities, `{1256789}`, so we'd expect to guess wrong with\n",
"probability 6/7. If instead we chose `G2`, which only has 2\n",
"possibilities, `{89}`, we'd expect to be wrong with probability\n",
"only 1/2. Thus we choose the square with the fewest possibilities and\n",
"the best chance of guessing right. For value ordering we won't do\n",
"anything special; we'll consider the digits in numeric order.\n",
"\n",
"Note we create a new **copy** of `grid` for each recursive call to `search`. This way\n",
"each branch of the search tree is independent, and mutations to `grid` done by constraint propagation in one branch do not confuse other branches. When it is time to back up and try a different digit, we have the original unaltered `grid` ready to go.\n",
"\n",
"We could call `search` directly, but I'll define the helper function `solve_puzzles(puzzles)` to call `constrain` and then `search` on each puzzle, and then verify that the solution is correct with `is_solution`, and finally print the puzzle and the solution side by side:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"def solve_puzzles(puzzles, verbose=True) -> int:\n",
" \"Solve and verify each puzzle, and if `verbose`, print puzzle and solution.\"\n",
" for puzzle in puzzles:\n",
" solution = search(constrain(puzzle))\n",
" assert is_solution(solution, puzzle)\n",
" if verbose:\n",
" print_side_by_side('\\nPuzzle:\\n' + picture(puzzle), \n",
" '\\nSolution:\\n' + picture(solution))\n",
" return len(puzzles)\n",
"\n",
"def print_side_by_side(left, right, width=20):\n",
" \"\"\"Print two strings side-by-side, line-by-line, each side `width` wide.\"\"\"\n",
" for L, R in zip(left.splitlines(), right.splitlines()):\n",
" print(L.ljust(width), R.ljust(width)) "
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" \n",
"Puzzle: Solution: \n",
"5 3 .|. 7 .|. . . 5 3 4|6 7 8|9 1 2 \n",
"6 . .|1 9 5|. . . 6 7 2|1 9 5|3 4 8 \n",
". 9 8|. . .|. 6 . 1 9 8|3 4 2|5 6 7 \n",
"-----+-----+----- -----+-----+----- \n",
"8 . .|. 6 .|. . 3 8 5 9|7 6 1|4 2 3 \n",
"4 . .|8 . 3|. . 1 4 2 6|8 5 3|7 9 1 \n",
"7 . .|. 2 .|. . 6 7 1 3|9 2 4|8 5 6 \n",
"-----+-----+----- -----+-----+----- \n",
". 6 .|. . .|2 8 . 9 6 1|5 3 7|2 8 4 \n",
". . .|4 1 9|. . 5 2 8 7|4 1 9|6 3 5 \n",
". . .|. 8 .|. 7 9 3 4 5|2 8 6|1 7 9 \n",
" \n",
"Puzzle: Solution: \n",
"4 . .|. . .|8 . 5 4 1 7|3 6 9|8 2 5 \n",
". 3 .|. . .|. . . 6 3 2|1 5 8|9 4 7 \n",
". . .|7 . .|. . . 9 5 8|7 2 4|3 1 6 \n",
"-----+-----+----- -----+-----+----- \n",
". 2 .|. . .|. 6 . 8 2 5|4 3 7|1 6 9 \n",
". . .|. 8 .|4 . . 7 9 1|5 8 6|4 3 2 \n",
". . .|. 1 .|. . . 3 4 6|9 1 2|7 5 8 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|6 . 3|. 7 . 2 8 9|6 4 3|5 7 1 \n",
"5 . .|2 . .|. . . 5 7 3|2 9 1|6 8 4 \n",
"1 . 4|. . .|. . . 1 6 4|8 7 5|2 9 3 \n"
]
},
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solve_puzzles([grid1, grid2])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that `search` is effective at solving the previously-unsolved `grid2`.\n",
"\n",
"Computer scientists call this a [depth-first search](http://en.wikipedia.org/wiki/Depth-first_search) because it (recursively) considers all possible continuations from the grid with *d* in square *s* before it backs up and considers a different digit in *s*. Sudoku players call this the [Nishio strategy](https://www.sudokuonline.io/tips/advanced-sudoku-strategies), after professional puzzle player Tetsuya Nishio, although Nishio only applied it when there were just two remaining possibilities for a square. We can apply it with any number of possibilities; we can even find a solution for the completely empty puzzle where every square has 9 possibilities:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" \n",
"Puzzle: Solution: \n",
". . .|. . .|. . . 1 2 3|4 5 6|7 8 9 \n",
". . .|. . .|. . . 4 5 6|7 8 9|1 2 3 \n",
". . .|. . .|. . . 7 8 9|1 2 3|4 5 6 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|. . .|. . . 2 3 1|6 7 4|8 9 5 \n",
". . .|. . .|. . . 8 7 5|9 1 2|3 6 4 \n",
". . .|. . .|. . . 6 9 4|5 3 8|2 1 7 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|. . .|. . . 3 1 7|2 6 5|9 4 8 \n",
". . .|. . .|. . . 5 4 2|8 9 7|6 3 1 \n",
". . .|. . .|. . . 9 6 8|3 4 1|5 7 2 \n"
]
},
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"empty = parse('.' * 81)\n",
" \n",
"solve_puzzles([empty])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Verifying the Program\n",
"\n",
"We had success in solving `grid1`, `grid2`, and `empty`, but we are left with some questions:\n",
"- Can the program solve *any* puzzle? \n",
" - We'll test it on some more `puzzles`, taken from some files. The more we test, the more confidence we have.\n",
" - Theoretically, the program should be able to solve any puzzle, but we haven't determined a bound on how long it would take.\n",
"- Are the components of the program correct? \n",
" - We'll run some `unit_tests` to give us some confidence/ There should be more tests.\n",
"- How long does it take to solve a puzzle?\n",
" - We can measure that with the `%time` magic command.\n",
" - For a more complete investigation of run times, see the [Java version](SudokuJava.ipynb)."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'pass'"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def unit_tests():\n",
" \"A suite of unit tests.\"\n",
" assert len(squares) == 81\n",
" assert len(all_units) == 27\n",
" assert cross('AB', '12') == ('A1', 'A2', 'B1', 'B2')\n",
" for s in squares:\n",
" assert len(units[s]) == 3\n",
" assert len(peers[s]) == 20\n",
" assert units['C2'] == (('A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'),\n",
" ('C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'),\n",
" ('A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3'))\n",
" assert peers['C2'] == {'A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',\n",
" 'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',\n",
" 'A1', 'A3', 'B1', 'B3'}\n",
" return 'pass'\n",
"\n",
"def parse_grids(pictures):\n",
" \"\"\"Parse an iterable of picture lines into a list of grids.\"\"\"\n",
" return [parse(p) for p in pictures if p]\n",
"\n",
"hardest = parse_grids(open('hardest.txt'))\n",
"grids10k = parse_grids(open('sudoku10k.txt'))\n",
"\n",
"unit_tests()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can solve 10,000 puzzles, verifying that each solution is correct (but not printing them):"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 27.2 s, sys: 17.1 ms, total: 27.2 s\n",
"Wall time: 27.4 s\n"
]
},
{
"data": {
"text/plain": [
"10000"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%time solve_puzzles(grids10k, verbose=False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That took less than 3 milliseconds per puzzle, or over 350 puzzles per second. (The [Java version](SudokuJava.ipynb) does over 100,000 puzzles per second. It benefits from being able to run 20 threads in parallel, from using more efficient data structures, and from the Java JVM being more efficient than Python's bytecode interpreter.)\n",
"\n",
"The ten allegedly hardest puzzles also take about 3 milliseconds per puzzle on average:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 33.8 ms, sys: 1.08 ms, total: 34.9 ms\n",
"Wall time: 34.3 ms\n"
]
},
{
"data": {
"text/plain": [
"10"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%time solve_puzzles(hardest, verbose=False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can see the puzzles and their solutions:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" \n",
"Puzzle: Solution: \n",
"8 5 .|. . 2|4 . . 8 5 9|6 1 2|4 3 7 \n",
"7 2 .|. . .|. . 9 7 2 3|8 5 4|1 6 9 \n",
". . 4|. . .|. . . 1 6 4|3 7 9|5 2 8 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|1 . 7|. . 2 9 8 6|1 4 7|3 5 2 \n",
"3 . 5|. . .|9 . . 3 7 5|2 6 8|9 1 4 \n",
". 4 .|. . .|. . . 2 4 1|5 9 3|7 8 6 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|. 8 .|. 7 . 4 3 2|9 8 1|6 7 5 \n",
". 1 7|. . .|. . . 6 1 7|4 2 5|8 9 3 \n",
". . .|. 3 6|. 4 . 5 9 8|7 3 6|2 4 1 \n",
" \n",
"Puzzle: Solution: \n",
". . 5|3 . .|. . . 1 4 5|3 2 7|6 9 8 \n",
"8 . .|. . .|. 2 . 8 3 9|6 5 4|1 2 7 \n",
". 7 .|. 1 .|5 . . 6 7 2|9 1 8|5 4 3 \n",
"-----+-----+----- -----+-----+----- \n",
"4 . .|. . 5|3 . . 4 9 6|1 8 5|3 7 2 \n",
". 1 .|. 7 .|. . 6 2 1 8|4 7 3|9 5 6 \n",
". . 3|2 . .|. 8 . 7 5 3|2 9 6|4 8 1 \n",
"-----+-----+----- -----+-----+----- \n",
". 6 .|5 . .|. . 9 3 6 7|5 4 2|8 1 9 \n",
". . 4|. . .|. 3 . 9 8 4|7 6 1|2 3 5 \n",
". . .|. . 9|7 . . 5 2 1|8 3 9|7 6 4 \n",
" \n",
"Puzzle: Solution: \n",
"1 2 .|. 4 .|. . . 1 2 8|5 4 7|6 3 9 \n",
". . 5|. 6 9|. 1 . 3 4 5|8 6 9|2 1 7 \n",
". . 9|. . .|5 . . 6 7 9|2 1 3|5 4 8 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|. . .|. 7 . 9 1 2|4 8 6|3 7 5 \n",
"7 . .|. 5 2|. 9 . 7 8 4|3 5 2|1 9 6 \n",
". 3 .|. . .|. . 2 5 3 6|7 9 1|4 8 2 \n",
"-----+-----+----- -----+-----+----- \n",
". 9 .|6 . .|. 5 . 8 9 1|6 2 4|7 5 3 \n",
"4 . .|9 . .|8 . 1 4 6 7|9 3 5|8 2 1 \n",
". . 3|. . .|9 . 4 2 5 3|1 7 8|9 6 4 \n",
" \n",
"Puzzle: Solution: \n",
". . .|5 7 .|. 3 . 6 2 4|5 7 8|1 3 9 \n",
"1 . .|. . .|. 2 . 1 3 5|4 9 6|8 2 7 \n",
"7 . .|. 2 3|4 . . 7 8 9|1 2 3|4 5 6 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|. 8 .|. . 4 2 1 6|3 8 5|7 9 4 \n",
". . 7|. . 4|. . . 8 5 7|9 6 4|2 1 3 \n",
"4 9 .|. . .|6 . 5 4 9 3|2 1 7|6 8 5 \n",
"-----+-----+----- -----+-----+----- \n",
". 4 2|. . .|3 . . 9 4 2|6 5 1|3 7 8 \n",
". . .|7 . .|9 . . 5 6 8|7 3 2|9 4 1 \n",
". . 1|8 . .|. . . 3 7 1|8 4 9|5 6 2 \n",
" \n",
"Puzzle: Solution: \n",
"1 . .|. . 7|. 9 . 1 6 2|8 5 7|4 9 3 \n",
". 3 .|. 2 .|. . 8 5 3 4|1 2 9|6 7 8 \n",
". . 9|6 . .|5 . . 7 8 9|6 4 3|5 2 1 \n",
"-----+-----+----- -----+-----+----- \n",
". . 5|3 . .|9 . . 4 7 5|3 1 2|9 8 6 \n",
". 1 .|. 8 .|. . 2 9 1 3|5 8 6|7 4 2 \n",
"6 . .|. . 4|. . . 6 2 8|7 9 4|1 3 5 \n",
"-----+-----+----- -----+-----+----- \n",
"3 . .|. . .|. 1 . 3 5 6|4 7 8|2 1 9 \n",
". 4 .|. . .|. . 7 2 4 1|9 3 5|8 6 7 \n",
". . 7|. . .|3 . . 8 9 7|2 6 1|3 5 4 \n",
" \n",
"Puzzle: Solution: \n",
"1 . .|. 3 4|. 8 . 1 5 2|9 3 4|6 8 7 \n",
". . .|8 . .|5 . . 7 6 3|8 2 1|5 4 9 \n",
". . 4|. 6 .|. 2 1 9 8 4|5 6 7|3 2 1 \n",
"-----+-----+----- -----+-----+----- \n",
". 1 8|. . .|. . . 6 1 8|4 9 3|2 7 5 \n",
"3 . .|1 . 2|. . 6 3 7 5|1 8 2|4 9 6 \n",
". . .|. . .|8 1 . 2 4 9|7 5 6|8 1 3 \n",
"-----+-----+----- -----+-----+----- \n",
"5 2 .|. 7 .|9 . . 5 2 1|3 7 8|9 6 4 \n",
". . 6|. . 9|. . . 4 3 6|2 1 9|7 5 8 \n",
". 9 .|6 4 .|. . 2 8 9 7|6 4 5|1 3 2 \n",
" \n",
"Puzzle: Solution: \n",
". . .|9 2 .|. . . 3 8 7|9 2 6|4 1 5 \n",
". . 6|8 . 3|. . . 5 4 6|8 1 3|9 7 2 \n",
"1 9 .|. 7 .|. . 6 1 9 2|4 7 5|8 3 6 \n",
"-----+-----+----- -----+-----+----- \n",
"2 3 .|. 4 .|1 . . 2 3 5|7 4 9|1 6 8 \n",
". . 1|. . .|7 . . 9 6 1|2 5 8|7 4 3 \n",
". . 8|. 3 .|. 2 9 4 7 8|6 3 1|5 2 9 \n",
"-----+-----+----- -----+-----+----- \n",
"7 . .|. 8 .|. 9 1 7 5 4|3 8 2|6 9 1 \n",
". . .|5 . 7|2 . . 6 1 3|5 9 7|2 8 4 \n",
". . .|. 6 4|. . . 8 2 9|1 6 4|3 5 7 \n",
" \n",
"Puzzle: Solution: \n",
". 6 .|5 . 4|. 3 . 8 6 9|5 7 4|1 3 2 \n",
"1 . .|. 9 .|. . 8 1 2 4|3 9 6|7 5 8 \n",
". . .|. . .|. . . 3 7 5|1 2 8|6 9 4 \n",
"-----+-----+----- -----+-----+----- \n",
"9 . .|. 5 .|. . 6 9 3 2|8 5 7|4 1 6 \n",
". 4 .|6 . 2|. 7 . 5 4 1|6 3 2|8 7 9 \n",
"7 . .|. 4 .|. . 5 7 8 6|9 4 1|3 2 5 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|. . .|. . . 2 1 7|4 6 9|5 8 3 \n",
"4 . .|. 8 .|. . 1 4 9 3|7 8 5|2 6 1 \n",
". 5 .|2 . 3|. 4 . 6 5 8|2 1 3|9 4 7 \n",
" \n",
"Puzzle: Solution: \n",
"7 . .|. . .|4 . . 7 9 8|6 3 5|4 2 1 \n",
". 2 .|. 7 .|. 8 . 1 2 6|9 7 4|5 8 3 \n",
". . 3|. . 8|. 7 9 4 5 3|2 1 8|6 7 9 \n",
"-----+-----+----- -----+-----+----- \n",
"9 . .|5 . .|3 . . 9 7 2|5 8 6|3 1 4 \n",
". 6 .|. 2 .|. 9 . 5 6 4|1 2 3|8 9 7 \n",
". . 1|. 9 7|. . 6 3 8 1|4 9 7|2 5 6 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|3 . .|9 . . 6 1 7|3 5 2|9 4 8 \n",
". 3 .|. 4 .|. 6 . 8 3 5|7 4 9|1 6 2 \n",
". . 9|. . 1|. 3 5 2 4 9|8 6 1|7 3 5 \n",
" \n",
"Puzzle: Solution: \n",
". . .|. 7 .|. 2 . 5 9 4|8 7 6|1 2 3 \n",
"8 . .|. . .|. . 6 8 2 3|9 1 4|7 5 6 \n",
". 1 .|2 . 5|. . . 6 1 7|2 3 5|8 9 4 \n",
"-----+-----+----- -----+-----+----- \n",
"9 . 5|4 . .|. . 8 9 6 5|4 2 1|3 7 8 \n",
". . .|. . .|. . . 7 8 1|6 5 3|9 4 2 \n",
"3 . .|. . 8|5 . 1 3 4 2|7 9 8|5 6 1 \n",
"-----+-----+----- -----+-----+----- \n",
". . .|3 . 2|. 8 . 1 5 9|3 4 2|6 8 7 \n",
"4 . .|. . .|. . 9 4 3 6|5 8 7|2 1 9 \n",
". 7 .|. 6 .|. . . 2 7 8|1 6 9|4 3 5 \n"
]
},
{
"data": {
"text/plain": [
"10"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solve_puzzles(hardest)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Roads not taken\n",
"\n",
"I made my implementation choices for clarity and ease of debugging. There are alternative choices I could have made:\n",
"- **Digit**: could have been an `int`, but:\n",
" - There is no need to do arithmetic on digits (all that matters is that they are unique).\n",
" - I wanted the compact DigitSet representation.\n",
"- **Digit set**: I considered two other options:\n",
" - `set` of digits: a good choice, but:\n",
" - I would then need to do a `deepcopy` of each grid, not just a copy.\n",
" - The printed representation `'123'` is shorter and easier to read than `{'1', '2', '3'}` when debugging.\n",
" - `int` bitset: each digit is represented by a bit; a DigitSet is a 9-bit binary int.\n",
" - Efficient, but obfuscating. Used in the [Java version](SudokuJava.ipynb) for efficiency.\n",
"- **Grid**: I considered three other options: \n",
" - `defaultdict`: the default is the DigitSet `'123456789'`.\n",
" - I thought that the top levels in the search tree would have only a few entries, so this would save space. \n",
" - But the first round of constraint propagation touches almost all the squares anyway.\n",
" - `list` of 9 rows, each a `list` of 9 squares (or a numpy 2D array):\n",
" - Then a `Square` is a pair of coordinates, like `(1, 2)` rather than the simpler string `C2`.\n",
" - Copying a grid would again require a `deepcopy`. \n",
" - `list` of 81 squares: \n",
" - Then a `Square` is an integer from 0 to 81.\n",
" - Efficient, but for debugging it is clear that `C2` is in the third row and second column; it is not obvious that `19` is.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Why?\n",
"\n",
"Why did I do this? As computer security expert [Ben Laurie](http://en.wikipedia.org/wiki/Ben_Laurie) has\n",
"stated, Sudoku is \"a denial of service attack on human intellect.\" \n",
"Several people I know (including my\n",
"wife) were victims of the attack, and I thought maybe this would\n",
"demonstrate that they didn't need to spend any more time on Sudoku. It\n",
"didn't work for my friends (although my wife has since independently\n",
"kicked the habit without my help), but at least one stranger wrote\n",
"and said this page worked for them, so I've made the world more\n",
"productive. And perhaps along the way I've taught something about\n",
"Python, constraint propagation, search, problem solving, and Sudoku."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.12"
}
},
"nbformat": 4,
"nbformat_minor": 4
}