ipython/sudoku_revised.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sudoku Solver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Taro Kuriyama. January 2016, Revised August 2020.\n",
    "  \n",
    "Functionally inspired by Richard Bird's solution in *Pearls of Functional Algorithm Design*.\n",
    "\n",
    "<hr>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Define and Show Board\n",
    "\n",
    "The Sudoku board is provided as a string of digits, where either '0' or '.' defines a blank cell. \n",
    "\n",
    "This string is parsed into a list of 9 rows referred to throughout as `board`. Each row is a list comprised of 9 cells, where each cell is a set reflecting possible integer values. A pre-defined cell will be parsed into a singleton set, whereas an empty cell will be parsed into a set of all possible values {1, 2, 3, 4, 5, 6, 7, 8, 9}."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def group(items, n):\n",
    "    \"\"\"Group sequence into n-tuples.\"\"\"\n",
    "    return list(zip(*[items[i::n] for i in range(n)]))\n",
    "\n",
    "def parse(board_str):\n",
    "    \"\"\"Parse puzzle input string into board object.\"\"\"\n",
    "    assert len(board_str) == 81\n",
    "    digits = {1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
    "    board = group(board_str, 9)\n",
    "    return [[digits if n in ('0', '.') else set([int(n)]) for n in row]\n",
    "            for row in board]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "**Sample Boards**\n",
    "\n",
    "Some sample boards are borrowed from http://www.7sudoku.com/instructions/loading-puzzles.\n",
    "\n",
    "`Show` returns a string representation of the board that can be printed for visualization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "easy = parse('..6...94.9.....3....4.92...6.7.1..2.5.23.64.9.3..4.7.5...68.5....5.....4.98...1..')\n",
    "medium = parse('...28.94.1.4...7......156.....8..57.4.......8.68..9.....196......5...8.3.43.28...')\n",
    "hard = parse('...16..2...2...8.5..5..36.9....5.18...........96.7....1.89..3..4.9...7...5..16...')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "nefarious = parse('000060080020000000001000000070000102500030000000000400004201000300700600000000050')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def to_str(sets):\n",
    "    \"\"\"Convert sequence of integer sets to string.\"\"\"\n",
    "    return ' '.join(['.' if len(s) > 1 else str(tuple(s)[0])\n",
    "                     for s in sets])\n",
    "    \n",
    "def show(board):\n",
    "    \"\"\"Convert board object to string representation.\"\"\"\n",
    "    bars = '-' * 21 + '\\n'\n",
    "    output = bars\n",
    "    row_group = group(board, 3)\n",
    "    for rows in row_group:\n",
    "        for row in rows:\n",
    "            output += ' | '.join([to_str(cols) for cols in group(row, 3)])\n",
    "            output += '\\n'\n",
    "        output += bars\n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------------------\n",
      ". . 6 | . . . | 9 4 .\n",
      "9 . . | . . . | 3 . .\n",
      ". . 4 | . 9 2 | . . .\n",
      "---------------------\n",
      "6 . 7 | . 1 . | . 2 .\n",
      "5 . 2 | 3 . 6 | 4 . 9\n",
      ". 3 . | . 4 . | 7 . 5\n",
      "---------------------\n",
      ". . . | 6 8 . | 5 . .\n",
      ". . 5 | . . . | . . 4\n",
      ". 9 8 | . . . | 1 . .\n",
      "---------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(show(easy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Board Validation\n",
    "\n",
    "A board is valid if there are no duplicate numbers in any rows, columns, or boxes. \n",
    "\n",
    "A board is complete if **(a)** it is valid and **(b)** the sum of each row, column, or box is 45 (assuming only digits 0 - 9 are ever used in the board). Note that given (a), only one of rows, columns, or boxes need to be checked for (b).\n",
    "\n",
    "The validation functions always iterate over board transformations, which are generated by the functions `rows` (identity function), `cols` (matrix transposition), and `boxs` (grouping into boxes). This keeps the validation logic simple.\n",
    "\n",
    "Note that `rows`, `cols`, and `boxs` are all involutions for a 9 x 9 Sudoku board as defined here, so `cols(cols(board))` is equivalent to just `board`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def rows(board):\n",
    "    \"\"\"Return board.\"\"\"\n",
    "    return board\n",
    "\n",
    "def cols(board):\n",
    "    \"\"\"Return transposed board.\"\"\"\n",
    "    return list(zip(*board))\n",
    "\n",
    "def flatten(nested):\n",
    "    \"\"\"Flatten nested sequence of sequences.\"\"\"\n",
    "    return list(n for sublist in nested for n in sublist)\n",
    "\n",
    "def boxs(board):\n",
    "    \"\"\"Group board by its boxes.\n",
    "    For each triple of rows, group each row into 3 digits and \n",
    "    zip up the rows; the resulting lists are the board boxes.\n",
    "    \"\"\"\n",
    "    boxes = []\n",
    "    for grouped in group(board, 3):\n",
    "        triple = [group(row, 3) for row in grouped]\n",
    "        zipped = list(zip(*triple))\n",
    "        rows = [flatten(row) for row in zipped]\n",
    "        boxes.extend(rows)\n",
    "    return boxes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def singletons(row):\n",
    "    \"\"\"Return all singleton values from list of sets.\"\"\"\n",
    "    return [tuple(ns)[0] for ns in row if len(ns) == 1]\n",
    "\n",
    "def singleton_nums(row):\n",
    "    \"\"\"Return all singleton numbers from list of sets, excluding singleton sets.\n",
    "    singletons() only finds singleton sets like {1} in [{1}, {2,3,4}, {3,4}];\n",
    "    this function would find [2], since 2 only appears once in all non-singleton sets.\n",
    "    \"\"\"\n",
    "    exclude = singletons(row)\n",
    "    ns = [n for nums in row for n in nums \n",
    "          if len(nums) > 1 and n not in exclude]\n",
    "    digits = defaultdict(int)    \n",
    "    for n in ns:\n",
    "        digits[n] += 1 \n",
    "    return [k for k in digits if digits[k] == 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def noempties(board):\n",
    "    \"\"\"Iterate through board; return True if there are no\n",
    "    empty cells in any row.\"\"\"\n",
    "    return all(ns for ns in flatten(board))\n",
    "\n",
    "def nodups(board):\n",
    "    \"\"\"Iterate through board; return True if there are no \n",
    "    duplicate singleton numbers in any row.\n",
    "    \"\"\"\n",
    "    checks = []\n",
    "    for row in board:\n",
    "        singles = singletons(row)\n",
    "        checks.append(len(singles) == len(set(singles)))\n",
    "    return all(checks)\n",
    "\n",
    "def valid(board):\n",
    "    \"\"\"Return True if board is valid.\"\"\"\n",
    "    return (noempties(board) and \n",
    "            all(nodups(f(board)) for f in (rows, cols, boxs)))\n",
    "    \n",
    "def complete(board):\n",
    "    \"\"\"Return True if board is complete.\"\"\"\n",
    "    return (valid(board) and \n",
    "            all([sum(singletons(row)) == 45 for row in board]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "**Test Singletones and Singleton_Nums**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(sorted(singletons([{1}, {1,2}, {}])) == [1])\n",
    "print(sorted(singletons([{1}, {1,2}, {3}, {4,5,6}])) == [1,3])\n",
    "\n",
    "# 4, 6, 9 are not singleton sets and appear only once in all sets\n",
    "print(singleton_nums([{1}, {2}, {3,4,5}, {3}, {5,6,7}, {5,7,9}]) == [4,6, 9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "**Validate Sample Boards**\n",
    "\n",
    "We can run some trivial unit tests to verify the input boards are as expected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def verify_board(board):\n",
    "    \"\"\"Some basic unit tests\"\"\"\n",
    "    assert valid(board) is True\n",
    "    assert complete(board) is False\n",
    "    assert len(board) == 9\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(verify_board(easy))\n",
    "print(verify_board(medium))\n",
    "print(verify_board(hard))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "**Validate Transformations**\n",
    "\n",
    "Validate the rows, cols, and boxs transformations don't mutate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hard == boxs(boxs(cols(cols(rows(rows(hard))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Tracker\n",
    "\n",
    "A global variable tracker is introduced to profile the solver's progress and debug issues (e.g. interminable loops!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "TRACKER = {'iters': 0,\n",
    "           'stack': 0,\n",
    "           'candidates': 9*9*9}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def update_tracker(board, stack, suppress=False):\n",
    "    \"\"\"Update global TRACEKRS dict\"\"\"\n",
    "    TRACKER['iters'] += 1\n",
    "    TRACKER['candidates'] = score_progress(board)\n",
    "    TRACKER['stack'] = stack\n",
    "    \n",
    "    iters = TRACKER['iters']\n",
    "    if not suppress:\n",
    "        if iters < 1000 and iters % 100 == 0:\n",
    "            print_tracker(board)\n",
    "        elif iters < 5000 and iters % 500 == 0:\n",
    "            print_tracker(board)\n",
    "        elif iters % 1000 == 0:\n",
    "            print_tracker(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def score_progress(board):\n",
    "    \"\"\"Return # of candidates remaining in board.\"\"\"\n",
    "    return sum(sum(len(cell) for cell in row) for row in board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def clear_tracker():\n",
    "    \"\"\"Reset all valeus to 0\"\"\"\n",
    "    for k in TRACKER:\n",
    "        TRACKER[k] = 0\n",
    "    TRACKER['candidates'] = 9*9*9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def print_tracker(board=[]):\n",
    "    \"\"\"Pirnt tracker under certain conditions\"\"\"\n",
    "    print(TRACKER)\n",
    "    if valid(board): \n",
    "        print(show(board))\n",
    "    else:\n",
    "        print('Invalid board')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solver: Prune, Fill, Search\n",
    "\n",
    "The solver works on a stack of boards and operates in a pipeline of three steps:\n",
    "1. prune\n",
    "2. fill\n",
    "3. search\n",
    "\n",
    "**Prune**\n",
    "\n",
    "For each unit of row, column, or box, any cell values that are also singletons in the unit can be removed as possibilities.\n",
    "\n",
    "**Fill**\n",
    "\n",
    "For each unit of row, column, or box, if a value can only appear in one cell, fill that cell with the value.\n",
    "\n",
    "**Search**\n",
    "\n",
    "Find possible next boards by trying possible values for cells. It makes sense to work with cells that have the smallest number of possibilities. DFS is much faster than BFS for this solving model; invalid boards are pruned after search iteration.\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prune(board):\n",
    "    \"\"\"Remove known choices from the board.\"\"\"\n",
    "    rows = []\n",
    "    for row in board:\n",
    "        singles = singletons(row)\n",
    "        new = [ns - set(singles) if len(ns) > 1 else ns\n",
    "               for ns in row]\n",
    "        rows.append(new)\n",
    "    return rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fill(board):\n",
    "    \"\"\"Fill cells where only a single value is possible.\"\"\"\n",
    "    new_board = []\n",
    "    for row in board:\n",
    "        singles = singleton_nums(row)\n",
    "        new_row = []\n",
    "        for nums in row:\n",
    "            intersect = set(singles) & set(nums)\n",
    "            if intersect:\n",
    "                new_row.append(intersect)\n",
    "            else:\n",
    "                new_row.append(nums)\n",
    "        new_board.append(new_row)\n",
    "    return new_board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def next_boards(board):\n",
    "    \"\"\"Generate list of some possible next boards.\"\"\"\n",
    "    flat = flatten(board)\n",
    "    len_choices = [len(ns) for ns in flat if len(ns) > 1]\n",
    "    \n",
    "    if not len_choices: return []\n",
    "    target_len = min(len_choices)\n",
    "\n",
    "    boards = []\n",
    "    for ind, ns in enumerate(flat):\n",
    "        if len(ns) == target_len:\n",
    "            flats = [flat[:ind] + [set([n])] + flat[ind+1:] for n in ns]\n",
    "            boards.extend([group(b, 9) for b in flats])\n",
    "            break\n",
    "    \n",
    "    return [b for b in boards if valid(b)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solver itself is straightforward because `rows`, `cols`, `boxs` are involutions and allow `prune` and `fill` to iterate over board transformations. For each board transformation, the board is first pruned, then filled, then inverted back to its original arrangement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(board, suppress=False, max_iters=10000):\n",
    "    \"\"\"Solver: prune, fill, and search in order.\"\"\"\n",
    "    clear_tracker()\n",
    "    \n",
    "    boards = [board]\n",
    "    while boards:\n",
    "        board = boards.pop()    \n",
    "        for f in (rows, cols, boxs):\n",
    "            board = prune(f(board))\n",
    "            board = f(fill(board))\n",
    "            \n",
    "        if complete(board): return show(board)\n",
    "        if valid(board):\n",
    "            boards.extend(next_boards(board))\n",
    "            boards = sorted(boards, key=score_progress, reverse=True)\n",
    "        \n",
    "        update_tracker(board, len(boards), suppress)\n",
    "        if TRACKER['iters'] > max_iters: break\n",
    "            \n",
    "    return []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solver is designed with simplicity over performance in mind, but appears to work reasonably well. It can solve 17-hint puzzles (minimum uniquely completable) but may take longer (e.g. 1 second)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------------------\n",
      ". . . | . 6 . | . 8 .\n",
      ". 2 . | . . . | . . .\n",
      ". . 1 | . . . | . . .\n",
      "---------------------\n",
      ". 7 . | . . . | 1 . 2\n",
      "5 . . | . 3 . | . . .\n",
      ". . . | . . . | 4 . .\n",
      "---------------------\n",
      ". . 4 | 2 . 1 | . . .\n",
      "3 . . | 7 . . | 6 . .\n",
      ". . . | . . . | . 5 .\n",
      "---------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(show(nefarious))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'iters': 100, 'stack': 8, 'candidates': 182}\n",
      "---------------------\n",
      "4 5 7 | 3 6 9 | 2 8 1\n",
      ". 2 . | . 1 . | . . .\n",
      ". . 1 | . . . | . . .\n",
      "---------------------\n",
      ". 7 . | . . . | 1 . 2\n",
      "5 4 . | 1 3 . | . . .\n",
      "1 . . | 9 . . | 4 . 5\n",
      "---------------------\n",
      "7 6 4 | 2 5 1 | . . .\n",
      "3 1 5 | 7 . . | 6 2 .\n",
      "2 . . | 6 . 3 | . 5 .\n",
      "---------------------\n",
      "\n",
      "{'iters': 200, 'stack': 9, 'candidates': 107}\n",
      "Invalid board\n",
      "{'iters': 300, 'stack': 11, 'candidates': 113}\n",
      "---------------------\n",
      "4 5 9 | 3 6 7 | 2 8 1\n",
      "8 2 7 | 4 1 9 | 5 . .\n",
      "6 3 1 | 8 2 5 | . 4 .\n",
      "---------------------\n",
      "9 7 . | 5 4 . | 1 . 2\n",
      "5 4 . | 1 3 . | . . .\n",
      "1 8 . | 9 7 . | 4 . 5\n",
      "---------------------\n",
      "7 6 4 | 2 5 1 | 3 . .\n",
      "3 1 5 | 7 . 4 | 6 2 .\n",
      "2 9 8 | 6 . 3 | . 5 4\n",
      "---------------------\n",
      "\n",
      "{'iters': 400, 'stack': 9, 'candidates': 103}\n",
      "---------------------\n",
      "4 5 9 | 3 6 7 | 2 8 1\n",
      "6 2 3 | 4 1 8 | 5 . .\n",
      "7 8 1 | 5 2 9 | 3 4 6\n",
      "---------------------\n",
      "9 7 6 | 8 4 5 | 1 . 2\n",
      "5 4 . | 1 3 . | . . .\n",
      "1 3 . | 9 7 . | 4 . 5\n",
      "---------------------\n",
      "8 6 4 | 2 5 1 | . . 3\n",
      "3 1 5 | 7 . 4 | 6 2 .\n",
      "2 9 7 | 6 . 3 | . 5 4\n",
      "---------------------\n",
      "\n",
      "{'iters': 500, 'stack': 7, 'candidates': 84}\n",
      "Invalid board\n",
      "{'iters': 600, 'stack': 9, 'candidates': 144}\n",
      "---------------------\n",
      "4 5 9 | 3 6 7 | 2 8 1\n",
      ". 2 . | 9 1 8 | 5 4 .\n",
      ". . 1 | 4 2 5 | . . .\n",
      "---------------------\n",
      ". 7 . | 5 4 . | 1 . 2\n",
      "5 4 . | 1 3 . | . . .\n",
      "1 . . | 8 7 . | 4 . 5\n",
      "---------------------\n",
      ". . 4 | 2 5 1 | . . .\n",
      "3 1 5 | 7 . 4 | 6 2 .\n",
      "2 . . | 6 . 3 | . 5 4\n",
      "---------------------\n",
      "\n",
      "{'iters': 700, 'stack': 7, 'candidates': 108}\n",
      "---------------------\n",
      "4 5 7 | 9 6 3 | 2 8 1\n",
      "9 2 3 | 4 1 8 | 5 . .\n",
      "6 8 1 | 5 2 7 | . 4 .\n",
      "---------------------\n",
      "8 7 9 | 6 4 5 | 1 . 2\n",
      "5 4 . | 1 3 . | . . .\n",
      "1 3 . | 8 7 . | 4 . 5\n",
      "---------------------\n",
      "7 6 4 | 2 5 1 | . . .\n",
      "3 1 5 | 7 . 4 | 6 2 .\n",
      "2 9 8 | 3 . 6 | 7 5 4\n",
      "---------------------\n",
      "\n",
      "{'iters': 800, 'stack': 12, 'candidates': 103}\n",
      "---------------------\n",
      "4 5 3 | 9 6 7 | 2 8 1\n",
      "7 2 8 | 4 1 5 | 3 . .\n",
      "9 6 1 | 3 2 8 | 5 4 7\n",
      "---------------------\n",
      "8 7 9 | 5 4 6 | 1 3 2\n",
      "5 4 . | 1 3 . | . . .\n",
      "1 3 . | 8 7 . | 4 . 5\n",
      "---------------------\n",
      "6 . 4 | 2 5 1 | . . 3\n",
      "3 1 5 | 7 . 4 | 6 2 .\n",
      "2 . 7 | 6 . 3 | . 5 4\n",
      "---------------------\n",
      "\n",
      "{'iters': 900, 'stack': 6, 'candidates': 93}\n",
      "Invalid board\n",
      "{'iters': 1000, 'stack': 6, 'candidates': 116}\n",
      "Invalid board\n",
      "---------------------\n",
      "9 4 7 | 1 6 5 | 2 8 3\n",
      "8 2 3 | 9 7 4 | 5 1 6\n",
      "6 5 1 | 3 2 8 | 9 4 7\n",
      "---------------------\n",
      "4 7 8 | 5 9 6 | 1 3 2\n",
      "5 1 6 | 4 3 2 | 8 7 9\n",
      "2 3 9 | 8 1 7 | 4 6 5\n",
      "---------------------\n",
      "7 6 4 | 2 5 1 | 3 9 8\n",
      "3 8 5 | 7 4 9 | 6 2 1\n",
      "1 9 2 | 6 8 3 | 7 5 4\n",
      "---------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(solve(nefarious, False, 5000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Time some puzzles of varying degrees of supposed difficulty..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.74 ms ± 729 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "solve(easy, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.67 ms ± 607 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "solve(hard, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.3 s ± 118 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "solve(nefarious, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  More Puzzles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some more puzzles from a massive repository of 17-hint puzzles collected here: http://staffhome.ecm.uwa.edu.au/~00013890/sudoku17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('puzzles.txt', 'r') as f:\n",
    "    puzzles = [line.strip() for line in f.readlines()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 of 100 samples solved\n"
     ]
    }
   ],
   "source": [
    "sample = 100\n",
    "solved = [p for p in puzzles[:sample] \n",
    "          if solve(parse(p), True, 5000)]\n",
    "print('{} of {} samples solved'.format(len(solved), sample))"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}