{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Peter Norvig, Nov. 2016
\n", "\n", "# Solving Any Sudoku Puzzle, Quickly\n", "\n", "Sudoku is a logic puzzle game. Given a grid like the one on below left, fill in the blank squares so that each column, row, and 3x3 box contains all the digits from 1 to 9. The solution is shown below right:\n", "\n", "
\n", "\n", "In this notebook I develop and implement an algorithm to solve any\n", "Sudoku puzzle, quickly. It turns out to be straightforward using two computer science ideas: constraint\n", "satisfaction and search. \n", "This notebook is an expansion of my\n", "previous Sudoku essay; that\n", "one emphasized simplicity; this one emphasizes\n", "efficiency and covers everything in more detail.\n", "\n", "\n", "\n", "We will use these definitions:\n", "\n", "- A **grid** is a 9×9 array of **squares**. We can partition the grid\n", "in three ways: \n", " - as 9 rows (of size 9×1) stacked on top of\n", "each other; \n", " - as 9 columns (of size 1×9) placed left-to-right; \n", " - as 9 boxes (of size 3×3) arranged in a 3×3 array.\n", "- A **unit** is a row,\n", "column, or box: a collection of 9 squares.\n", "- A **puzzle** is a grid in which some squares have been\n", "filled with a **digit** and some are **empty**. \n", "- A **solution** is a grid where every unit contains\n", "all the digits from 1 to 9, and the filled squares of the original puzzle remain unchanged\n", "in the solution. \n", "- A **well-formed puzzle** has exactly one solution.\n", "- A **peer** of a square is any other\n", "square in the same row, column, and box.\n", "\n", "## Sudoku data structures\n", "\n", "Here are the choices I made to implement these concepts. I represent a grid as an 81-element list, with the upper left square being element 0, then going right-to-left and top-to-bottom with the lower-right square being element 80." ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": true }, "outputs": [], "source": [ "Grid = list # an 81-element list, left-to-right, top-to-bottom\n", "Unit = tuple # a 9-element sequence\n", "Square = int # an int from 0 to 80; index into a Grid\n", "Digit = str # a character from '1' to '9'\n", "Digits = str # One or more digits\n", "empty = '.' # a square that has not been filled by a digit\n", "\n", "puzzle0 = Grid('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')\n", "answer0 = Grid('534678912672195348198342567859761423426853791713924856961537284287419635345286179')\n", "\n", "def is_solution(solution: Grid, puzzle: Grid) -> bool: \n", " \"\"\"A solution to a puzzle is a grid where every unit contains all the digits 1 to 9\n", " and the filled squares of the original puzzle remain unchanged in the solution.\"\"\"\n", " def unit_contents(unit): return {solution[s] for s in unit}\n", " return (all(unit_contents(unit) == digits for unit in all_units) and\n", " all(puzzle[s] == solution[s] for s in filled_squares(puzzle)))\n", "\n", "def filled_squares(grid):\n", " \"All the squares in a grid that are already filled with a digit.\"\n", " return (s for s in squares if grid[s] in digits)\n", "\n", "def empty_squares(grid):\n", " \"All the squares in a grid that are not already filled with a digit.\"\n", " return (s for s in squares if grid[s] not in digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Utility Functions and Displaying Grids\n", "\n", "Here is the code to set up all the units and peers and related data structures, alog with the imports and utility functions we will need later on, and code for displaying grids in a pretty fashion. Although we will mostly use 81-square grids, the function `use_grid_size(n)` can be used to work with `n`-square grids, where `n` can be 1, 16, 81, or 256." ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import itertools\n", "import time\n", "from IPython.display import HTML, display\n", "\n", "def use_grid_size(n=81):\n", " global N, D, B, digitstr, digits, squares, all_units, units, peers\n", " N = n # Number of squares in the grid\n", " D = isqrt(N) # Number of different digits\n", " B = isqrt(D) # A boxis of size B x B\n", " rows = range(0, N, D) # Squares at left of each row: (0, 9, 18, ... 72)\n", " cols = range(D) # Squares at top of each column: (0, 1, 2, ... 8)\n", " digitstr = '123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_'[:D] # E.g., '123456789' for D=9\n", " digits = set(digitstr) # E.g., {1, 2, 3, 4, 5, 6, 7, 8, 9} for D=9\n", " squares = range(N) # Al1 the squares\n", " all_rows = [cross(rows, [c]) for c in cols]\n", " all_cols = [cross([r], cols) for r in rows]\n", " all_boxes = [cross(rs, cs) for rs in chunk(rows, B) for cs in chunk(cols, B)]\n", " all_units = all_rows + all_cols + all_boxes\n", " units = [tuple(unit for unit in all_units if s in unit)\n", " for s in squares]\n", " peers = [tuple(union(units[s]) - {s})\n", " for s in squares]\n", "\n", "def cross(rows, cols) -> Unit:\n", " \"A unit of all the ways we can add one of the row numbers to one of the column numbers.\"\n", " return Unit(r + c for r in rows for c in cols)\n", "\n", "def union(collections) -> set: \"Set union\"; return set().union(*collections)\n", "\n", "def isqrt(n) -> int: \"Integer square root.\"; return int(n ** 0.5)\n", "\n", "def chunk(sequence, B) -> list:\n", " \"Chunk sequence into subsequences of length B.\"\n", " return [sequence[i:i+B] for i in range(0, len(sequence), B)]\n", "\n", "def first(iterable) -> object: \n", " \"Return the first item from iterable, or None.\"\n", " return next(iterable, None)\n", "\n", "def show(grid):\n", " \"Display the Sudoku grid.\"\n", " use_grid_size(len(grid))\n", " CSS = ''''''.replace('3', str(B))\n", " table = '' + D * ('' + D * '
{}') + '
'\n", " display(HTML(CSS + table.format(B, *grid)))" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(puzzle0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can how the numbering scheme for squares works; I'll display a grid that is filled, not with digits, but with square numbers. Then I'll show the units and peers for square 20:" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
012345678
91011121314151617
181920212223242526
272829303132333435
363738394041424344
454647484950515253
545556575859606162
636465666768697071
727374757677787980
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(range(81))" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "((2, 11, 20, 29, 38, 47, 56, 65, 74),\n", " (18, 19, 20, 21, 22, 23, 24, 25, 26),\n", " (0, 1, 2, 9, 10, 11, 18, 19, 20))" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "units[20]" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(0, 65, 2, 1, 9, 74, 11, 10, 18, 19, 21, 22, 23, 24, 25, 26, 29, 38, 47, 56)" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "peers[20]" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
BBC......
BBC......
RRXrrrrrr
..c......
..c......
..c......
..c......
..c......
..c......
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# A grid where 'X' marks square 20, 'r' marks squares in same row, 'c' marks squares in same column,\n", "# and capital letters, 'C', 'R', and 'B', mark squares in the same box.\n", "show(Grid('BBC......BBC......RRXrrrrrr..c........c........c........c........c........c......'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We need a test suite:" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'pass'" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "puzzle0 = Grid('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')\n", "answer0 = Grid('534678912672195348198342567859761423426853791713924856961537284287419635345286179')\n", "wrong0 = Grid('532678912672195348198342567859761423426853791713924856961537284287419635345286179')\n", "puzzle1 = Grid('4.7.6.8.5.3....9.....7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......')\n", "answer1 = Grid('417369825632158947958724316825437169791586432346912758289643571573291684164875293')\n", "wrong1 = Grid('427369825632158947958724316825437169791586432346912758289643571573291684164875293')\n", "\n", "def tests():\n", " \"A suite of unit tests.\"\n", " use_grid_size(81)\n", " assert N == 81 and D == 9 and B == 3\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 union(['feed', 'beef', 'cafe', 'face']) == {'a', 'b', 'c', 'd', 'e', 'f'}\n", " assert isqrt(16) == 4 and isqrt(81) == 9 and isqrt(256) == 16\n", " assert cross((0, 9, 18), (0, 1, 2)) == (0, 1, 2, 9, 10, 11, 18, 19, 20)\n", " assert chunk('abcdefghi', 3) == ['abc', 'def', 'ghi']\n", " assert units[20] == ((2, 11, 20, 29, 38, 47, 56, 65, 74),\n", " (18, 19, 20, 21, 22, 23, 24, 25, 26),\n", " (0, 1, 2, 9, 10, 11, 18, 19, 20))\n", " assert set(peers[20]) == {0, 1, 2, 9, 10, 11, 18, 19, 21, 22, \n", " 23, 24, 25, 26, 29, 38, 47, 56, 65, 74}\n", " assert is_solution(answer0, puzzle0)\n", " assert not is_solution(wrong0, puzzle0)\n", " assert is_solution(answer1, puzzle1)\n", " assert not is_solution(wrong1, puzzle1)\n", " return 'pass'\n", "\n", "tests()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solver 1: Generate and Test\n", "\n", "Here is a simple (but very inefficient) algorithm to solve Sudoku puzzles:\n", "\n", "> **Generate and test solver:**\n", "First fill in all the\n", "squares with digits. Then check to see if we have a\n", "solution. If not, then fill the squares with a different\n", "combination of digits. Repeat with different combinations until a solution is found.\n", "\n", "\n", "

Sometimes generate and test is the best you can do. Herb\n", "Simon, in his classic book [The Sciences of\n", "the Artificial](http://books.google.com/books?id=k5Sr0nFw7psC) (page 194), describes the task of opening a\n", "safe that has ten dials, each with 100 numbers on it. If the safe is\n", "well-designed there is no better approach than to generate-and-test\n", "with all\n", "10010 combinations. The generate-and-test solver is simple:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def solve(puzzle): \n", " \"Find a solution to the puzzle.\"\n", " return first(grid for grid in generate_all_grids(puzzle) \n", " if is_solution(grid, puzzle))\n", "\n", "def generate_all_grids(grid):\n", " \"An iterable of all possible ways to fill in grid.\"\n", " values = [(digitstr if d is empty else d) for d in grid]\n", " return itertools.product(*values)" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
...4
4.3.
.4..
.241
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
2314
4132
1423
3241
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "0.210 seconds\n" ] } ], "source": [ "def do1(puzzle):\n", " \"Do one puzzle; showing puzzle and solution and printing elapsed time.\"\n", " show(puzzle)\n", " t0 = time.clock()\n", " solution = solve(Grid(puzzle))\n", " t1 = time.clock()\n", " assert is_solution(solution, puzzle)\n", " show(solution)\n", " print('{:.3f} seconds'.format(t1 - t0))\n", "\n", "use_grid_size(16)\n", "tiny = Grid('...44.3..4...241')\n", "do1(tiny)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "That works fine for a 4x4 array. But on a 9x9, with say, 64 empty squares, there will be 964 combinations of digits.\n", "Suppose we have access to a secret new custom 10 GHz\n", "GPU capable of doing 1024 generate and\n", "test operations in a single clock cycle, and let's say we can fit a million of these units\n", "in a data center, and we could afford a hundred data centers,\n", "and while we're shopping, let's say we also pick up a time\n", "machine and go back 13 billion years to the early days of the universe,\n", "and a fleet of starships with which we visit a trillion galaxies and\n", "in each galaxy convince the inhabitants of a billion planets to each\n", "buy a similar setup, and we all start our programs\n", "running, managing to distribute the cases perfectly so that no\n", "computation is duplicated or wasted. Then we can [estimate](http://www.google.com/search?aq=f&sourceid=chrome&ie=UTF-8&q=10+GHz+*+1024+*+1+million+*+100+*+1+trillion+*+1+billion+*+13+billion+years+%2F+9**64+in+percent)\n", "that we'd be only 3% of the way through with the first puzzle.\n", "\n", "

Generate and test is not the algorithm you're looking for. Move along." ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "# Solver 2: Combinatorial Search\n", "\n", "In Simon's safe example, he next supposes a defective safe, in which a\n", "faint click is heard whenever a dial is set to the right position.\n", "With this safe it only takes 100 × 10 trials to discover the\n", "correct combination, not 10010. The moral is that if we have some selective\n", "knowledge of components of the safe (or puzzle) that tell us if a\n", "partial solution is on track, our search will be\n", "much easier.\n", "\n", "

Fortunately for us, Sudoku is like the defective safe. To be\n", "precise, it is like a safe with 81 dials, each with 9 numbers,\n", "and sometimes if you put one of the dials in the wrong position you hear a sound,\n", "but sometimes not (depending on the positions of the other dials and\n", "on how carefully you listen). For\n", "example, in the lower-left corner of the tiny puzzle above, if we try\n", "1, 2, or 4 we would immediately get feedback that those digits won't\n", "work, because they already appear elsewhere in the bottom row.\n", "Therefore, the lower-left corner must be filled by a 3. There are\n", "262,144 ways to fill in the 9 empty squares, but right away we can eliminate\n", "196,608 of them; we need only consider the ones that have a 3 in that position.\n", "\n", "

Unfortunately for us, Sudoku does not give up all its secrets so\n", "easily. Sometimes, when we consider a square, we can't immediately\n", "tell what digit to put there. For example, in the upper-left of the tiny\n", "puzzle, only 4 can be eliminated as a possibility. That's ok--we're\n", "allowing ourselves the use of an eraser, so just guess one of the\n", "remaining three possibilities; if it doesn't pan out, erase it and try one\n", "of the others. This gives us:\n", "\n", "\n", "

Combinatorial search algorithm: Start filling squares with digits, one at a time, always making sure\n", "that the digit we put in a square is not the same as any peer. If there are several possible digits, pick one, but remember the others. If we\n", "reach a square where every digit conflicts with a peer, back\n", "up and consider a different digit for the previous square. Stop when\n", "we successfully fill every square, or give up if we tried all\n", "possibilities without finding a solution.
\n", "\n", "The progress of this algorithm can be described as a search\n", "tree, where each node represents a partially-filled (incremental) state of the\n", "puzzle, and a branch corresponds to filling in a square with a\n", "digit. (We display the new digits in red.)\n", "Here is a search tree for the tiny puzzle:\n", "\n", "
\n", "\n", "

A few things to note about this particular search tree:\n", "

    \n", "
  • Each successive level fills in one square, so with nine empty\n", " squares, the solution must appear on the ninth level of the tree\n", " (counting the root as the zeroth level).\n", "
  • This is a well-formed puzzle, so there will be exactly one solution,\n", " and thus exactly one node at the ninth level.\n", "
  • A rectangle with a black X indicates an\n", " inconsistency: there is no way to continue because the next\n", " unfilled square\n", " already has all four digits taken by its peers.\n", "
  • When we hit a X we have to pull out our eraser, or in\n", " other words we have to backtrack--go up a level in the tree and\n", " try the next possible digit for the previous square. On the far-left\n", " branch of the tree we have to back up three levels---erasing first the 2, then the 3, then the\n", " 1--before we can pencil in another possible digit \n", " (the 2 in the upper-left corner which we\n", " see in the middle branch of the tree).\n", " \n", "
  • The rightmost branch of the tree remains unexplored--the search\n", " proceeds left-to-right and has not got to that brnach yet. (But since the\n", " puzzle is well-formed and we have found the solution, we know the\n", " unexplored branches cannot contain another solution.)\n", " \n", "
\n", "

The code to implement combinatorial search is straightforward:" ] }, { "cell_type": "code", "execution_count": 99, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def search(grid) -> Grid:\n", " \"\"\"Select an unfilled square, try each possible digit there, recursively searching.\n", " When all squares filled: success; when no more digits to try: return None for failure.\"\"\"\n", " square = select_empty_square(grid)\n", " if square is None: # No empty square means the grid is a solution\n", " return grid\n", " for digit in possible_digits(grid, square):\n", " result = search(assign(Grid(grid), square, digit))\n", " if result: \n", " return result\n", "\n", "solve = search\n", "\n", "def select_empty_square(grid) -> Square:\n", " \"Return the first square that is not filled with a digit; or None if all squares are filled.\"\n", " return (None if grid is None else first(empty_squares(grid)))\n", "\n", "def assign(grid, s, d) -> Grid:\n", " \"For now, simply assign grid[s] = d.\"\n", " grid[s] = d\n", " return grid\n", "\n", "def possible_digits(grid, s):\n", " \"A square can be filled with any digit that is not already taken by a peer.\"\n", " peer_digits = {grid[s] for s in peers[s]}\n", " return digits - peer_digits" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "The key function is search. It obeys the convention that if\n", "it is passed Inconsistent (to indicate an invalid grid) it returns\n", "Inconsistent, meaning that no solution can be found. Otherwise it\n", "selects some unfilled square to work on. If select_square\n", "returns None that is actually good news: it means that all\n", "the squares are already filled, and we are done: we have a solution,\n", "so we just return it. Otherwise, for each possible\n", "digit that could fill square s we try to assign that digit to\n", "s and search for a solution from there. If some call to\n", "search succeeds, return it; but if a digit assignment causes\n", "the search to fail, just keep going with the next digit assignment.\n", "If all digit assignments fail, then the whole call to search\n", "fails, and we back up to the previous recursive call. \n", "\n", "

We call this type of combinatorial search a constraint\n", " satisfaction search: think of each square as being a\n", " variable that can take on a value (a digit), and the\n", " rules of Sudoku as being constraints on the possible values.\n", " A state in the search tree is then an assignment of values to some\n", " subset of variables in a way that does not violate any constraint.\n", "The constraint satisfaction\n", " approach has found many fun applications in puzzles and serious\n", " applications in problem solving.\n", "\n", "

Here we see solve (and therefore search) in action:\n", "\n", "\n", "\n", "That's all there is to it! The only reason we don't stop this article\n", "now is that the program is still too slow for some purposes. We're\n", "not talking billions-of-years slow, but it did take 3 minutes and 45\n", "seconds to solve this puzzle (a rather hard one). On a benchmark of\n", "50 easy puzzles the program was fast enough, taking a total of 9.5\n", "seconds (a rate of 5\n", "puzzles per second, or 5 Hz). \n", "\n" ] }, { "cell_type": "code", "execution_count": 96, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "0.024 seconds\n" ] } ], "source": [ "do1(puzzle0)" ] }, { "cell_type": "code", "execution_count": 97, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
4.7.6.8.5
.3....9..
...7.....
.2.....6.
....8.4..
....1....
...6.3.7.
5..2.....
1.4......
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
417369825
632158947
958724316
825437169
791586432
346912758
289643571
573291684
164875293
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "17.216 seconds\n" ] } ], "source": [ "do1(puzzle1)" ] }, { "cell_type": "code", "execution_count": 98, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 63904089 function calls (62617098 primitive calls) in 30.046 seconds\n", "\n", " Ordered by: standard name\n", "\n", " ncalls tottime percall cumtime percall filename:lineno(function)\n", " 52321162 8.946 0.000 8.946 0.000 :17(is_filled)\n", " 1286992 0.444 0.000 20.602 0.000 :36(first)\n", "1286992/1 3.380 0.000 30.046 30.046 :1(search)\n", " 1286992 1.496 0.000 22.374 0.000 :14(select_empty_square)\n", " 2573983 11.162 0.000 20.108 0.000 :17()\n", " 1286991 0.238 0.000 0.238 0.000 :19(assign)\n", " 1286991 1.272 0.000 4.055 0.000 :24(possible_digits)\n", " 1286991 2.783 0.000 2.783 0.000 :26()\n", " 1 0.000 0.000 30.046 30.046 :1()\n", " 1 0.000 0.000 30.046 30.046 {built-in method builtins.exec}\n", " 1286992 0.326 0.000 20.159 0.000 {built-in method builtins.next}\n", " 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}\n", "\n", "\n" ] } ], "source": [ "import cProfile\n", "cProfile.run(\"solve(puzzle1)\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solver 3. Arc Consistency" ] }, { "cell_type": "code", "execution_count": 93, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def solve(puzzle: Grid) -> Grid:\n", " grid = Grid(digitstr if d is empty else d\n", " for d in puzzle)\n", " return search(grid)\n", "\n", "def possible_digits(grid, s) -> Digits: return grid[s]\n", "\n", "def assign(grid, s, d) -> Grid:\n", " \"\"\"Assign grid[s] = d and eliminate d from the peers of s.\n", " Return the updated grid, or Inconsistent if inconsistency detected.\"\"\"\n", " if d not in grid[s]: return Inconsistent # d is not among the possibilities\n", " grid[s] = d\n", " if not all(eliminate(grid, p, d) for p in peers[s]): \n", " return None\n", " return grid\n", "\n", "def eliminate(grid, s, d) -> bool:\n", " \"Remove d from possibilities for grid[s]. If checking finds an inconsistency return None.\"\n", " if d not in grid[s]: \n", " return True # Already eliminated d\n", " grid[s] = grid[s].replace(d, '')\n", " return all(constraint(grid, s, d) \n", " for constraint in constraints)\n", "\n", "def arc_consistent(grid, s, d):\n", " \"Return true if s has multiple digits left, or one that we can consistently assign.\"\n", " ndigits = len(grid[s])\n", " return ndigits >= 2 or (ndigits == 1 and assign(grid, s, grid[s]))\n", "\n", "constraints = [arc_consistent]" ] }, { "cell_type": "code", "execution_count": 94, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
4.7.6.8.5
.3....9..
...7.....
.2.....6.
....8.4..
....1....
...6.3.7.
5..2.....
1.4......
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "ename": "TypeError", "evalue": "'NoneType' object is not subscriptable", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mdo1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzle1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# Should be 0.2\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m\u001b[0m in \u001b[0;36mdo1\u001b[0;34m(puzzle)\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzle\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0mt0\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mclock\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m \u001b[0msolution\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mGrid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzle\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 6\u001b[0m \u001b[0mt1\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mclock\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mis_solution\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msolution\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpuzzle\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36msolve\u001b[0;34m(puzzle)\u001b[0m\n\u001b[1;32m 2\u001b[0m grid = Grid(digitstr if d is empty else d\n\u001b[1;32m 3\u001b[0m for d in puzzle)\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0msearch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mpossible_digits\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0ms\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mDigits\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36msearch\u001b[0;34m(grid)\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mgrid\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mdigit\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpossible_digits\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msquare\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msearch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0massign\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mGrid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msquare\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 9\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36msearch\u001b[0;34m(grid)\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mgrid\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mdigit\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpossible_digits\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msquare\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msearch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0massign\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mGrid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msquare\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 9\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36msearch\u001b[0;34m(grid)\u001b[0m\n\u001b[1;32m 2\u001b[0m \"\"\"Select an unfilled square, try each possible digit there, recursively searching.\n\u001b[1;32m 3\u001b[0m When all squares filled: success; when no more digits to try: return None for failure.\"\"\"\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0msquare\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mselect_empty_square\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 5\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0msquare\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# No empty square means the grid is a solution\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mgrid\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mselect_empty_square\u001b[0;34m(grid)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mselect_empty_square\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"Return an unfilled square with the fewest possible digits; or None if no unfilled squares.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0munfilled\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0ms\u001b[0m \u001b[0;32min\u001b[0m \u001b[0msquares\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mmin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0munfilled\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mlambda\u001b[0m \u001b[0ms\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0munfilled\u001b[0m \u001b[0;32melse\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mselect_empty_square\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"Return an unfilled square with the fewest possible digits; or None if no unfilled squares.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0munfilled\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0ms\u001b[0m \u001b[0;32min\u001b[0m \u001b[0msquares\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mmin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0munfilled\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mlambda\u001b[0m \u001b[0ms\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0munfilled\u001b[0m \u001b[0;32melse\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mTypeError\u001b[0m: 'NoneType' object is not subscriptable" ] } ], "source": [ "do1(puzzle1) # Should be 0.2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Benchmarking" ] }, { "cell_type": "code", "execution_count": 86, "metadata": { "collapsed": false }, "outputs": [], "source": [ "puzzles = \"\"\"\n", "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......\n", "52...6.........7.13...........4..8..6......5...........418.........3..2...87.....\n", "6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....\n", "48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....\n", "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...\n", "......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.\n", "6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....\n", ".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........\n", "6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....\n", ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....\n", "6..3.2....5.....1..........7.26............543.........8.15........4.2........7..\n", ".6.5.1.9.1...9..539....7....4.8...7.......5.8.817.5.3.....5.2............76..8...\n", "..5...987.4..5...1..7......2...48....9.1.....6..2.....3..6..2.......9.7.......5..\n", "3.6.7...........518.........1.4.5...7.....6.....2......2.....4.....8.3.....5.....\n", "1.....3.8.7.4..............2.3.1...........958.........5.6...7.....8.2...4.......\n", "6..3.2....4.....1..........7.26............543.........8.15........4.2........7..\n", "....3..9....2....1.5.9..............1.2.8.4.6.8.5...2..75......4.1..6..3.....4.6.\n", "45.....3....8.1....9...........5..9.2..7.....8.........1..4..........7.2...6..8..\n", ".237....68...6.59.9.....7......4.97.3.7.96..2.........5..47.........2....8.......\n", "..84...3....3.....9....157479...8........7..514.....2...9.6...2.5....4......9..56\n", "\"\"\".split()[5:6]\n", "\n", "benchmarks = {}\n", "\n", "def benchmark(label, puzzles=puzzles):\n", " \"Run `solve` on these puzzles; record and verify results for this label; print all results.\"\n", " n = len(puzzles)\n", " t0 = time.clock()\n", " results = [solve(Grid(p)) for p in puzzles]\n", " avg = (time.clock() - t0) / len(puzzles)\n", " for (r, p) in zip(results, puzzles):\n", " assert is_solution(r, p) \n", " benchmarks[label] = '{:.3f} sec/puzzle ({:.1f} Hz)'.format(avg, 1/avg)\n", " for L in sorted(benchmarks):\n", " print('{:10s} {}'.format(L, benchmarks[L]))" ] }, { "cell_type": "code", "execution_count": 84, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(puzzles)" ] }, { "cell_type": "code", "execution_count": 87, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3. AC 11.219 sec/puzzle (0.1 Hz)\n" ] } ], "source": [ "benchmark('3. AC')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 4. Dual Consistency" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def dual_consistent(grid, s, d):\n", " \"\"\"After eliminating d from grid[s], check each unit of s and make sure there is some\n", " position in the unit for d. If only one possible place left for d, assign it.\"\"\"\n", " for u in units[s]:\n", " places_for_d = [s2 for s2 in u if d in grid[s2]]\n", " nplaces = len(places_for_d)\n", " if nplaces==0 or (nplaces==1 and not assign(grid, places_for_d[0], d)):\n", " return None\n", " return True" ] }, { "cell_type": "code", "execution_count": 88, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3. AC 11.219 sec/puzzle (0.1 Hz)\n", "4. AC+Dual 26.392 sec/puzzle (0.0 Hz)\n" ] } ], "source": [ "constraints = [arc_consistent, dual_consistent]\n", "benchmark('4. AC+Dual')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# 5. Naked pairs" ] }, { "cell_type": "code", "execution_count": 89, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def naked_pairs(grid, s, ignore):\n", " \"\"\"Look for two squares in a unit with the same two possible digits. \n", " For example, if s and s2 both have the value '35', then we know that 3 and 5\n", " must go in those two squares. We don't know which is which, but we can eliminate \n", " 3 and 5 from any other square s3 that is in the unit.\"\"\"\n", " vals = grid[s]\n", " if len(vals) != 2: return True\n", " for u in units[s]:\n", " for s2 in u:\n", " if s2 != s and grid[s2] == vals:\n", " # Found naked pair: s and s2; remove their two vals from others in unit\n", " for s3 in u:\n", " if s != s3 != s2:\n", " if not all(eliminate(grid, s3, v) for v in vals):\n", " return None\n", " return True" ] }, { "cell_type": "code", "execution_count": 90, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3. AC 11.219 sec/puzzle (0.1 Hz)\n", "4. AC+Dual 26.392 sec/puzzle (0.0 Hz)\n", "5. AC+D+NP 29.821 sec/puzzle (0.0 Hz)\n" ] } ], "source": [ "constraints = [arc_consistent, dual_consistent, naked_pairs]\n", "benchmark('5. AC+D+NP')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 6. Variable Ordering" ] }, { "cell_type": "code", "execution_count": 91, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def select_empty_square(grid):\n", " \"Return an unfilled square with the fewest possible digits; or None if no unfilled squares.\"\n", " unfilled = [s for s in squares if len(grid[s]) > 1]\n", " return min(unfilled, key=lambda s: len(grid[s])) if unfilled else None" ] }, { "cell_type": "code", "execution_count": 92, "metadata": { "collapsed": false }, "outputs": [ { "ename": "TypeError", "evalue": "'NoneType' object is not subscriptable", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mbenchmark\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'6. VarOrd'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m\u001b[0m in \u001b[0;36mbenchmark\u001b[0;34m(label, puzzles)\u001b[0m\n\u001b[1;32m 28\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzles\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 29\u001b[0m \u001b[0mt0\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mclock\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 30\u001b[0;31m \u001b[0mresults\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0msolve\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mGrid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mp\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mp\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpuzzles\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 31\u001b[0m \u001b[0mavg\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mclock\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mt0\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzles\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 32\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mr\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mp\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mzip\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mresults\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpuzzles\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m 28\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzles\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 29\u001b[0m \u001b[0mt0\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mclock\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 30\u001b[0;31m \u001b[0mresults\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0msolve\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mGrid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mp\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mp\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpuzzles\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 31\u001b[0m \u001b[0mavg\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mclock\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mt0\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzles\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 32\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mr\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mp\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mzip\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mresults\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpuzzles\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36msolve\u001b[0;34m(puzzle)\u001b[0m\n\u001b[1;32m 2\u001b[0m grid = Grid(digitstr if d is empty else d\n\u001b[1;32m 3\u001b[0m for d in puzzle)\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0msearch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mpossible_digits\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0ms\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mDigits\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36msearch\u001b[0;34m(grid)\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mgrid\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mdigit\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpossible_digits\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msquare\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msearch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0massign\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mGrid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msquare\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 9\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36msearch\u001b[0;34m(grid)\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mgrid\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mdigit\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpossible_digits\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msquare\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msearch\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0massign\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mGrid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msquare\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 9\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36msearch\u001b[0;34m(grid)\u001b[0m\n\u001b[1;32m 2\u001b[0m \"\"\"Select an unfilled square, try each possible digit there, recursively searching.\n\u001b[1;32m 3\u001b[0m When all squares filled: success; when no more digits to try: return None for failure.\"\"\"\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0msquare\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mselect_empty_square\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 5\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0msquare\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# No empty square means the grid is a solution\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mgrid\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mselect_empty_square\u001b[0;34m(grid)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mselect_empty_square\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"Return an unfilled square with the fewest possible digits; or None if no unfilled squares.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0munfilled\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0ms\u001b[0m \u001b[0;32min\u001b[0m \u001b[0msquares\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mmin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0munfilled\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mlambda\u001b[0m \u001b[0ms\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0munfilled\u001b[0m \u001b[0;32melse\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mselect_empty_square\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"Return an unfilled square with the fewest possible digits; or None if no unfilled squares.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0munfilled\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0ms\u001b[0m \u001b[0;32min\u001b[0m \u001b[0msquares\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mmin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0munfilled\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mlambda\u001b[0m \u001b[0ms\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0munfilled\u001b[0m \u001b[0;32melse\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mTypeError\u001b[0m: 'NoneType' object is not subscriptable" ] } ], "source": [ "benchmark('6. VarOrd')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "

However, if you want to solve a million hard puzzles, you probably\n", "don't want to wait a few years, and you would prefer a\n", "faster algorithm.\n", "Look again at the search tree above, and consider how we can find the\n", "solution faster. Here are four general strategies:\n", "

    \n", "
  1. We could try to move the solution to the left. Since we go top-down,\n", " left-to-right, this means we would find it sooner. This can\n", " potentially be done with better value ordering, the order in\n", " which the function possible_values considers which digit to\n", " try next. If we were able to choose right every time,\n", " there would in effect be no search--the solution would be in the\n", " lower-left corner of the tree and we would arrive at it directly\n", " with no backtracking.\n", "
  2. We could try to move the solution closer to the top. If we only\n", " fill in one square at a time then the solution will always be at the\n", " same level (the number of empty squares in the original puzzle).\n", " But if we could fill in several squares at a time, the solution gets\n", " closer to the top and we can find it faster. Filling in multiple\n", " squares at a time can be accomplished with constraint\n", " propagation--using the constraints imposed by the rules of Sudoku to\n", " conclude that an unfilled square must take on a certain digit,\n", " thus sanctioning us to fill in several squares at once.\n", "
  3. We could prune branches (mark them with an X and backtrack)\n", " earlier. This can also be done with\n", " constraint propagation, but in this case rather than filling in\n", " squares, we would notice that some\n", " square has no possible digit, and thus that we can backtrack immediately.\n", "
  4. We could consider the squares in a better order, a process called\n", " variable ordering, which in our program is implemented by the\n", " function select_square. At each node in\n", " the tree we pick one square to branch on. The current\n", " implementation of select_square just considers the squares\n", " in order from 0 to 80 and chooses the first unfilled one, but it\n", " could be more clever. A\n", " different ordering could be better (or worse) for any of the three reasons above.\n", "
" ] } ], "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.5.1" } }, "nbformat": 4, "nbformat_minor": 0 }