ipynb/Sudoku.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:right\"><i>Peter Norvig<br>2006, 2021</i></div>\n",
    "\n",
    "# Solving Any Sudoku Puzzle\n",
    "\n",
    "The rules of <a href=\"https://en.wikipedia.org/wiki/Sudoku\">Sudoku</a> are simple and finite: fill in the empty squares so that each column, row, and 3x3 box contains all the digits from 1 to 9:\n",
    "\n",
    "|Puzzle|Solution|\n",
    "|---|---|\n",
    "|![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg/361px-Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg.png)|![](https://upload.wikimedia.org/wikipedia/commons/thumb/1/12/Sudoku_Puzzle_by_L2G-20050714_solution_standardized_layout.svg/361px-Sudoku_Puzzle_by_L2G-20050714_solution_standardized_layout.svg.png)|\n",
    "\n",
    "This notebook develops a program to solve any Sudoku puzzle, in about 100 lines of Python. You can also see:\n",
    "  - The original 2006 version of this notebook, as a [raw HTML page](https://norvig.com/sudoku.html): \n",
    "    - It uses some outdated Python idioms; the Python code in this notebook is more modern.\n",
    "    - Thus, if you read this notebook, you don't need to see the older version.\n",
    "    - However, the disqus comments might be of some interest.\n",
    "  - [A Java program for Sudoku](SudokuJava.ipynb) that solves over 100,000 puzzles per second.\n",
    "  - [A Python program for Star Battle](StarBattle.ipynb), a related fill-in-the-grid puzzle game.\n",
    "\n",
    "\n",
    "# Sudoku: Implementing Basic Concepts \n",
    "\n",
    "Here are the key concepts and the Python implementation choices I made:\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",
    "- **Boxes**: the 9 boxes are 3×3 squares within the grid (outlined with heavy black lines in the diagram). \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",
    "  - `Fail` represents a grid that has no solution (e.g. if we guess wrong on the filler for some square).\n",
    "- **Picture**: for input and output, a string *picture* of the grid is used (details described below).\n",
    "- **Unit**: a unit is a row, column, or box; each unit is a list of 9 squares. \n",
    "  - `all_units` is a tuple of all 27 units.\n",
    "  - `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[s]` is a set of 20 squares that are in some unit with `s`.\n",
    "- **Solution**: A grid is a valid solution to a puzzle if:\n",
    "  - A square that was filled with a digit in the puzzle has the same digit in the solution.\n",
    "  - Every unit is filled with all nine digits, one to a square, no repeats."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "DigitSet = str  # e.g. '123'\n",
    "Square   = str  # e.g. 'A9'\n",
    "Picture  = str  # e.g. \"53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79\"\n",
    "Grid     = dict # E.g. {'A9': '123', ...}, a dict  of {Square: DigitSet}\n",
    "Fail     = Grid() # The empty Grid is used to indicate failure to find a solution\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",
    "digits    = '123456789'\n",
    "rows      = 'ABCDEFGHI'\n",
    "cols      = digits\n",
    "squares   = cross(rows, cols)\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",
    "\n",
    "def is_solution(solution: Grid, puzzle: Grid) -> bool:\n",
    "    \"Is this proposed solution to the puzzle actually valid?\"\n",
    "    return (solution is not Fail and\n",
    "            all(solution[s] == puzzle[s] for s in squares if len(puzzle[s]) == 1) 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 <b><tt  style=\"color:red\">C2</tt></b>:\n",
    "\n",
    "<pre>\n",
    ".  A2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         A1 A2 A3|.  .  . |.  .  .  \n",
    ".  B2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         B1 B2 B3|.  .  . |.  .  .  \n",
    ".  <b style=\"color:red\">C2</b> . |.  .  . |.  .  .         C1 <b style=\"color:red\">C2</b> C3|C4 C5 C6|C7 C8 C9        C1 <b style=\"color:red\">C2</b> C3|.  .  . |.  .  .  \n",
    "--------+--------+--------        --------+--------+--------        --------+--------+-------- \n",
    ".  D2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  \n",
    ".  E2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  \n",
    ".  F2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  \n",
    "--------+--------+--------        --------+--------+--------        --------+--------+-------- \n",
    ".  G2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  \n",
    ".  H2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .  \n",
    ".  I2 . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  .         .  .  . |.  .  . |.  .  . \n",
    "</pre>\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": [
    "## 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": [
    "# Input and Output: Pictures and Grids\n",
    "\n",
    "We will need to convert between a `Picture` (used for input/output) and a `Grid` (used for computation). 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, and ignored on input.\n",
    "- An uncertain square is represented by a DigitSet in braces, e.g.: `{123}`.\n",
    "  - This `'{123}'` notation never occurs in a standard Sudoku puzzle, but it is what `picture(grid)` produces for a grid that is partially solved, so I thought it was important to be able to read that format back in with `parse(picture)`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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.\"\"\"\n",
    "    if grid is Fail: \n",
    "        return \"Fail\"\n",
    "    def val(d: DigitSet) -> str: return '.' if d == digits else d if len(d) == 1 else '{' + d + '}'\n",
    "    width = max(len(val(grid[s])) for s in grid)\n",
    "    dash = '\\n' + '+'.join(['-' * (width * 3 + 2)] * 3) + ' '\n",
    "    def cell(r, c): return val(grid[r + c]).center(width) + ('|'  if c in '36' else ' ')\n",
    "    def line(r): return ''.join(cell(r, c) for c in cols) + (dash 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": 5,
   "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": [
    "grid1 = parse(\"53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79\")\n",
    "print(picture(grid1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a grid, filled squares have one possible digit, and unfilled squares have all 9 possible digits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'5'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid1['A1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'123456789'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid1['A3']"
   ]
  },
  {
   "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 from 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.</i>\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 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 `Fail` if there is a contradiction.\n",
    "\n",
    "We say that these two strategies constitute [constraint propagation](https://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 `eliminate` in other squares, which can in turn cause a `fill` of yet another square, and so on. \n",
    "\n",
    "Here is the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fill(grid, s, d) -> Grid:\n",
    "    \"\"\"Eliminate all the other 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 Fail\n",
    "\n",
    "def eliminate(grid, s, d) -> 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 Fail        ## Fail: no legal digit left\n",
    "    elif len(grid[s]) == 1:\n",
    "        # 1. If a square has only one possible digit, then eliminate that digit from the square's peers.\n",
    "        d2 = grid[s]\n",
    "        if not all(eliminate(grid, s2, d2) for s2 in peers[s]):\n",
    "            return Fail    ## Fail: 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 Fail    ## Fail: no place in u for d\n",
    "    return grid"
   ]
  },
  {
   "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": [
    "The function `constrain` returns the result of initiating constraint propagation on a grid. So that the original puzzle is not mutated, we create a new `constrained` grid that initially has all possible digits for each square, but then is filled with the known digits from the original grid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def constrain(grid) -> Grid:\n",
    "    \"Propagate constraints on a copy of grid to yield a new constrained Grid.\"\n",
    "    constrained: Grid = {s: digits for s in squares}\n",
    "    for s in grid:\n",
    "        d = grid[s]\n",
    "        if len(d) == 1:\n",
    "            fill(constrained, s, d)\n",
    "    return constrained"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Many puzzles can be solved by `constrain` alone, for example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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": 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": [
    "grid2 = parse(\"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......\")\n",
    "\n",
    "print(picture(constrain(grid2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that some progress has been made: the original 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 10<sup>38</sup>](https://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](https://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",
    "A smarter search strategy is to **interleave** constraint propagation and systematic guessing as follows:\n",
    "  - If the current grid contains a contradiction, don't try more combinations; return failure.\n",
    "  - If there are no unfilled squares in the puzzle, then stop and return the succesful solution.\n",
    "  - Otherwise choose some unfilled square, *s*. \n",
    "  - Guess that some digit *d* fills square *s*. \n",
    "    - Call `fill` on *s* and *d* to initiate constraint propagation.\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, back up and guess a different digit.\n",
    "    - Because we give up as soon as we get a contradiction, we examine far fewer possibilities than brute force search.\n",
    "    \n",
    "Here is the implementation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(grid) -> Grid:\n",
    "    \"Depth-first search with constraint propagation (`fill`) to find a solution.\"\n",
    "    if grid is Fail: \n",
    "        return Fail\n",
    "    unfilled = [s for s in squares if len(grid[s]) > 1]\n",
    "    if not unfilled: \n",
    "        return grid\n",
    "    s = min(unfilled, key=lambda s: len(grid[s]))\n",
    "    for d in grid[s]:\n",
    "        solution = search(fill(grid.copy(), s, d))\n",
    "        if solution:\n",
    "            return solution\n",
    "    return Fail"
   ]
  },
  {
   "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)` 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, verbose=True) -> int:\n",
    "    \"Solve and verify each puzzle, and if `verbose`, print puzzle and solution.\"\n",
    "    sep = '    '\n",
    "    for puzzle in puzzles:\n",
    "        solution = search(constrain(puzzle))\n",
    "        assert is_solution(solution, puzzle)\n",
    "        if verbose:\n",
    "            print('\\nPuzzle            ', sep, 'Solution')\n",
    "            for p, s in zip(picture(puzzle).splitlines(), picture(solution).splitlines()):\n",
    "                print(p, sep, s)\n",
    "    return len(puzzles)"
   ]
  },
  {
   "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([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](https://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([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",
    "  - Assuming no bugs, the program can 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`. There should be more.\n",
    "- How long does it take to solve a puzzle?\n",
    "  - We'll do `%time solve(puzzles)`.\n",
    "  - For a more complete investigation of run times, see the [Java version](SudokuJava.ipynb)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unit_tests():\n",
    "    \"A suite of unit tests.\"\n",
    "    assert len(squares) == 81\n",
    "    assert len(all_units) == 27\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'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'pass'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 27.6 s, sys: 23.5 ms, total: 27.7 s\n",
      "Wall time: 27.7 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10000"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time solve(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",
    "We can inspect the solutions for the ten allegedly hardest puzzles:"
   ]
  },
  {
   "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",
      "CPU times: user 40.6 ms, sys: 3.5 ms, total: 44.1 ms\n",
      "Wall time: 41.5 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time solve(hardest)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Why?\n",
    "\n",
    "Why did I do this? As computer security expert [Ben Laurie](https://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",
   "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}