ipynb/CrossProduct.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\" style=\"text-align: right\"><i>Peter Norvig, Feb 2021</i></div>\n",
    "\n",
    "# CrossProduct Puzzle\n",
    "\n",
    "The 538 Riddler [poses a type of puzzle](https://fivethirtyeight.com/features/can-you-cross-like-a-boss/) called ***CrossProduct***, which works like this:\n",
    "\n",
    ">*Replace each \"?\" in the table with a single digit so that the product of the digits in each row equals the number to the right of the row, and the product of the digits in each column equals the number above the column.*\n",
    "\n",
    "\n",
    "Sample puzzle:\n",
    "\n",
    "      \n",
    "|  6615 | 15552 | &nbsp; 420  | [6×3]  |\n",
    "|-------|-------|-------|---|\n",
    "|    ?  |    ?  |    ?  |**210**|\n",
    "|    ?  |    ?  |    ?  |**144**|\n",
    "|    ?  |    ?  |    ?  |**54**|\n",
    "|    ?  |    ?  |    ?  |**135**|\n",
    "|    ?  |    ?  |    ?  |**4**|\n",
    "|    ?  |    ?  |    ?  |**49**|\n",
    "\n",
    "\n",
    "Solution:\n",
    "\n",
    "|6615|15552|&nbsp; 420| [6×3]|\n",
    "|---|---|---|---|\n",
    "|7|6|5|**210**|\n",
    "|9|8|2|**144**|\n",
    "|3|9|2|**54**|\n",
    "|5|9|3|**135**|\n",
    "|1|4|1|**4**|\n",
    "|7|1|7|**49**|\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "We could solve CrossProduct puzzles by hand, but why not write a program to do it?\n",
    "     \n",
    "# Data type definitions\n",
    "     \n",
    "Here are the data types we will use in trying to solve CrossProduct puzzles: \n",
    "- `Digit`: a single digit, from 1 to 9 (but not 0).\n",
    "- `Row`: a tuple of digits that forms a row in the table, e.g. `(7, 6, 5)`.\n",
    "- `Table`: a table of digits that fill in all the \"?\"s; a list of rows, e.g. `[(7, 6, 5), (9, 8, 2), ...]`.\n",
    "- `Products`: a list of the numbers that corresponding digits must multiply to, e.g. in the puzzle above:\n",
    "  - `[6615, 15552, 420]` for the column products;\n",
    "  - `[210, 144, 54, 135, 4, 49]` for the row products.\n",
    "- `Puzzle`: a puzzle to be solved, as defined by the row products and column products."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing      import Tuple, List, Set, Iterable, Optional\n",
    "from numpy       import divide, prod, transpose\n",
    "from collections import namedtuple\n",
    "import random\n",
    "\n",
    "Digit    = int\n",
    "Row      = Tuple[Digit, ...] \n",
    "Table    = List[Row]   \n",
    "Product  = int\n",
    "Products = List[Product] \n",
    "Puzzle   = namedtuple('Puzzle', 'row_prods, col_prods')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The puzzles\n",
    "\n",
    "Here are the puzzles given by 538 Riddler (they promised one a week for four weeks; so far we've seen three):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzles = (\n",
    "    Puzzle([135,  45,  64, 280, 70],             [3000,   3969,    640]),\n",
    "    Puzzle([210, 144,  54, 135,  4,  49],        [6615,  15552,    420]),\n",
    "    Puzzle([280, 168, 162, 360, 60, 256, 126], [183708, 245760, 117600]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Strategy\n",
    "\n",
    "Here's my strategy:\n",
    "- To solve a puzzle, first find all ways to fill the first row, and for each way, solve the rest of the puzzle.\n",
    "- To fill a row, first find all ways to fill the first digit, and for each way, fill the rest of the row.\n",
    "\n",
    "So the first step is to define `fill_one_row(row_prod, col_prods)` to return a set of digit-tuples that can legally fill a row that has the given row product in a puzzle with the given column products. \n",
    "  - If `col_prods` is empty, then there is one solution (the 0-length tuple) if `row_prod` is 1, and no solution otherwise.\n",
    "  - Otherwise, try each digit `d` that divides both the `row_prod` and the first number in `col_prods`, and then try all ways to fill the rest of the row."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fill_one_row(row_prod: Product, col_prods: Products) -> Set[Row]:\n",
    "    \"All permutations of digits that multiply to `row_prod` and evenly divide `col_prods`.\"\n",
    "    if not col_prods:\n",
    "        return {()} if row_prod == 1 else set()\n",
    "    else:\n",
    "        return {(d, *rest) for d in range(1, 10)\n",
    "                if (row_prod / d).is_integer() and (col_prods[0] / d).is_integer()\n",
    "                for rest in fill_one_row(row_prod // d, col_prods[1:])}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(5, 6, 7), (7, 6, 5)}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fill_one_row(210, [6615, 15552, 420]) # There are 2 ways to fill this row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(1, 9, 6),\n",
       " (3, 3, 6),\n",
       " (3, 6, 3),\n",
       " (3, 9, 2),\n",
       " (9, 1, 6),\n",
       " (9, 2, 3),\n",
       " (9, 3, 2),\n",
       " (9, 6, 1)}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fill_one_row(54, [6615, 15552, 420]) # There are 8 ways to fill this row"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can solve the rest of a puzzle:\n",
    "\n",
    "- `solve(puzzle)` finds the first solution. (A well-formed puzzle has exactly one solution, but some might have more, or none.)\n",
    "- `solutions(puzzle)` yields all possible solutions to a puzzle. There are three main cases to consider:\n",
    "  - A puzzle with no rows has the empty table, `[]`, as a solution, as long as the column products are all 1.\n",
    "  - A puzzle with rows might have solutions, as long as the column products are all integers. Call `fill_row` to get all possible ways to fill the first row, and for each one recursively call `solutions` to get all the possible ways of filling the rest of the rows (making sure to pass in an altered `col_prods` where each element is divided by the corresponding element in the first row).\n",
    "  - Otherwise there are no solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(puzzle) -> Optional[Table]: return next(solutions(puzzle), None)\n",
    "\n",
    "def solutions(puzzle) -> Iterable[Table]:\n",
    "    \"\"\"Yield all tables that solve the puzzle.\n",
    "    The product of the digits in row r must equal row_prods[r], for all r.\n",
    "    The product of the digits in column c must equal col_prods[c], for all c.\"\"\"\n",
    "    row_prods, col_prods = puzzle\n",
    "    if not row_prods and all(c == 1 for c in col_prods):\n",
    "        yield []\n",
    "    elif row_prods and all(c == int(c) for c in col_prods):\n",
    "        yield from ([row1, *rows]\n",
    "                    for row1 in fill_one_row(row_prods[0], col_prods)\n",
    "                    for rows in solutions(Puzzle(row_prods[1:], list(divide(col_prods, row1)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solutions\n",
    "\n",
    "Here are  solutions to the three puzzles posed by *The Riddler*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(3, 9, 5), (5, 9, 1), (8, 1, 8), (5, 7, 8), (5, 7, 2)],\n",
       " [(7, 6, 5), (9, 8, 2), (3, 9, 2), (5, 9, 3), (1, 4, 1), (7, 1, 7)],\n",
       " [(7, 8, 5), (3, 8, 7), (9, 6, 3), (9, 8, 5), (3, 5, 4), (4, 8, 8), (9, 2, 7)]]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[solve(p) for p in puzzles]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Those are the correct solutions. However, we could make them look nicer.\n",
    "\n",
    "# Prettier solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import Markdown, display\n",
    "\n",
    "def pretty(puzzle) -> Markdown:\n",
    "    \"\"\"A puzzle and its solution in pretty Markdown format.\"\"\"\n",
    "    row_prods, col_prods = puzzle\n",
    "    head = row(col_prods + [f'[{len(row_prods)}×{len(col_prods)}]'])\n",
    "    dash = row(['---'] * (1 + len(col_prods)))\n",
    "    rest = [row(r + (f'**{rp}**',))\n",
    "            for r, rp in zip(solve(puzzle), row_prods)]\n",
    "    return Markdown('\\n'.join([head, dash, *rest]))\n",
    "\n",
    "def row(items) -> str: \n",
    "    \"\"\"Make a markdown table row.\"\"\"\n",
    "    return '|' + '|'.join(map(str, items)) + '|'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "|3000|3969|640|[5×3]|\n",
       "|---|---|---|---|\n",
       "|3|9|5|**135**|\n",
       "|5|9|1|**45**|\n",
       "|8|1|8|**64**|\n",
       "|5|7|8|**280**|\n",
       "|5|7|2|**70**|"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "|6615|15552|420|[6×3]|\n",
       "|---|---|---|---|\n",
       "|7|6|5|**210**|\n",
       "|9|8|2|**144**|\n",
       "|3|9|2|**54**|\n",
       "|5|9|3|**135**|\n",
       "|1|4|1|**4**|\n",
       "|7|1|7|**49**|"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "|183708|245760|117600|[7×3]|\n",
       "|---|---|---|---|\n",
       "|7|8|5|**280**|\n",
       "|3|8|7|**168**|\n",
       "|9|6|3|**162**|\n",
       "|9|8|5|**360**|\n",
       "|3|5|4|**60**|\n",
       "|4|8|8|**256**|\n",
       "|9|2|7|**126**|"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "for p in puzzles:\n",
    "    display(pretty(p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Making new puzzles\n",
    "\n",
    "Can we make new puzzles? Can we make well-formed ones (those with exactly one solution)? Here is an approach:\n",
    "- Make a table filled with random digits (`random_table`).\n",
    "- Make a puzzle from the row and column products of the table (`table_puzzle`).\n",
    "- Repeat `N` times (`random_puzzles`).\n",
    "- Optionally, check if puzzles are `well-formed`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_table(nrows, ncols) -> Table:\n",
    "    \"Make a table of random digits of the given size.\"\n",
    "    return [tuple(random.randint(1, 9) for c in range(ncols))\n",
    "            for r in range(nrows)]\n",
    "\n",
    "def table_puzzle(table) -> Puzzle:\n",
    "    \"Given a table, compute the puzzle it is a solution for.\"\n",
    "    return Puzzle([prod(row) for row in table], \n",
    "                  [prod(col) for col in transpose(table)])\n",
    "\n",
    "def random_puzzles(N, nrows, ncols, seed=42) -> List[Puzzle]: \n",
    "    \"Return a list of `N` random puzzles.\"\n",
    "    random.seed(seed) # For reproducability\n",
    "    return [table_puzzle(random_table(nrows, ncols)) for _ in range(N)]\n",
    "\n",
    "def well_formed(puzzle) -> bool: \n",
    "    \"Does the puzzle have exactly one solution?\"\n",
    "    S = solutions(puzzle)\n",
    "    first, second = next(S, None), next(S, None)\n",
    "    return first is not None and second is None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(6, 1, 7), (9, 7, 3), (9, 3, 5), (5, 6, 9), (6, 6, 4)]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_table(nrows=5, ncols=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "puz = table_puzzle(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "well_formed(puz)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(list(solutions(puz)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "|14580|756|3780|[5×3]|\n",
       "|---|---|---|---|\n",
       "|6|1|7|**42**|\n",
       "|9|7|3|**189**|\n",
       "|5|3|9|**135**|\n",
       "|9|6|5|**270**|\n",
       "|6|6|4|**144**|"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pretty(puz)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How likely are random puzzles (of various sizes) to be well-formed?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33% of random puzzles with 3 rows and 3 cols ( 9 cells) are well-formed\n",
      "18% of random puzzles with 3 rows and 4 cols (12 cells) are well-formed\n",
      "14% of random puzzles with 4 rows and 3 cols (12 cells) are well-formed\n",
      " 8% of random puzzles with 3 rows and 5 cols (15 cells) are well-formed\n",
      " 2% of random puzzles with 5 rows and 3 cols (15 cells) are well-formed\n",
      " 4% of random puzzles with 4 rows and 4 cols (16 cells) are well-formed\n",
      " 0% of random puzzles with 6 rows and 3 cols (18 cells) are well-formed\n"
     ]
    }
   ],
   "source": [
    "N = 200\n",
    "for r, c in [(3, 3), (3, 4), (4, 3), (3, 5), (5, 3), (4, 4), (6, 3)]:\n",
    "    w = sum(map(well_formed, random_puzzles(N, r, c))) / N\n",
    "    print(f'{w:3.0%} of random puzzles with {r} rows and {c} cols ({r * c:2} cells) are well-formed')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that most puzzles are not well-formed. Smaller sizes are more likely to yield well-formed puzzles.\n",
    "\n",
    "# Speed\n",
    "\n",
    "How long does it take to solve random puzzles? We can do a thousand small (5x3) puzzles in about two seconds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.56 s, sys: 48.6 ms, total: 1.6 s\n",
      "Wall time: 1.56 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time all(solve(p) for p in random_puzzles(1000, 5, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Puzzles that are even a little bit larger can be a lot slower, and there is huge variability in the time to solve. For example, a single 10 x 6 puzzle can take from a few milliseconds to tens of seconds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3.03 s, sys: 10.3 ms, total: 3.04 s\n",
      "Wall time: 3.03 s\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "|24576|979776|274400|2177280|1792000|524880|[10×6]|\n",
       "|---|---|---|---|---|---|---|\n",
       "|4|1|5|6|2|2|**480**|\n",
       "|1|7|1|3|4|3|**252**|\n",
       "|8|9|2|9|2|1|**2592**|\n",
       "|8|3|7|8|5|6|**40320**|\n",
       "|1|6|7|3|5|3|**1890**|\n",
       "|1|8|1|7|4|6|**1344**|\n",
       "|3|9|2|8|5|6|**12960**|\n",
       "|4|6|5|1|7|9|**7560**|\n",
       "|1|1|8|2|4|5|**320**|\n",
       "|8|2|7|5|8|3|**13440**|"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[p10x6] = random_puzzles(1, 10, 6)\n",
    "%time pretty(p10x6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, the time to solve a puzzle can grow exponentially in the number of cells. Consider a row in a six-column puzzle, where the products are all 5040. There are 3,960 ways to fill this row: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3960"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 5040\n",
    "len(fill_one_row(n, [n] * 6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If four rows all had a similar number of possibilities and didn't constrain each other, that would be hundreds of trillions of combinations to try—an infeasible number. We will need a faster algorithm for larger puzzles.\n",
    "\n",
    "# Faster Speed\n",
    "\n",
    "To speed things up, we could encode the puzzle as a constraint satisfaction problem (CSP), and use a highly-optimized [CSP solver](https://developers.google.com/optimization/cp/cp_solver). But even without going to a professional-grade CSP solver, we could borrow the heuristics they use. There are four main considerations in CSP solving:\n",
    "- **Variable definition**: In `solutions`, we are treating each **row** as a variable, and asking \"which of the possible values returned by `fill_one_row` will work as the value of this row? An alternative would be to treat each **cell** as a variable, and fill in the puzzle one cell at a time rather than one row at a time. This has the advantage that each variable has only 9 possible values, not thousands of possibilities.\n",
    "- **Variable ordering**: In `solutions`, we consider the variables (the rows) in strict top-to-bottom order. It is usually more efficient to reorder the variables, filling in first the variable with the minimum number of possible values. The reasoning is that if you have a variable with only 2 possibilities, you have a 50% chance of guessing right the first time, whereas if there were 100 possibilities, you have only a 1% chance of guessing right.\n",
    "- **Value ordering**: The function `fill_one_row` returns values in sorted lexicographic order, lowest first. We could reorder the values to pick the one that imposes the least constraints first (that is, the value that allows the most possibilities for the other variables).\n",
    "- **Domain-specific heuristics**: CSP solvers are general, but sometimes knowledge that is specific to a problem can be helpful. One fact about CrossProduct is that the digits 5 and 7 are special in the sense that if a row (or column) product is divisible by 5 (or 7), then the digit 5 (or 7) must appear in the row (or column). That is not true for the other digits (for example, if a row product is divisible by 8, then an 8 may appear in the row, or it might be a 2 and a 4, or three 6s, etc.).\n",
    "\n",
    "Usually variable ordering is the most productive heuristic. Let's try it. The function `reorder` takes a puzzle and returns a version of the puzzle with the row products permuted so that the rows with the fewest possible fillers come first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reorder(puzzle) -> Puzzle:\n",
    "    \"\"\"Create a version of puzzle with the rows reordered so the rows with the fewest\n",
    "    number of possible fillers come first.\"\"\"\n",
    "    def fillers(r): return len(fill_one_row(r, puzzle.col_prods))\n",
    "    rows = sorted(puzzle.row_prods, key=fillers)\n",
    "    return Puzzle(rows, puzzle.col_prods)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Puzzle(row_prods=[280, 168, 162, 360, 60, 256, 126], col_prods=[183708, 245760, 117600]),\n",
       " Puzzle(row_prods=[256, 280, 162, 360, 126, 168, 60], col_prods=[183708, 245760, 117600]))"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p2 = puzzles[2]\n",
    "p2, reorder(p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{256: 1, 280: 2, 162: 2, 360: 2, 126: 5, 168: 7, 60: 8}"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How many ways are there to fill each row?\n",
    "{r: len(fill_one_row(r, p2.col_prods)) \n",
    " for r in reorder(p2).row_prods}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I'll define a set of test puzzles and see how long it takes to solve them all, and compare that to the time to solve the reordered versions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_puzzles = random_puzzles(20, 10, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 20.6 s, sys: 453 ms, total: 21.1 s\n",
      "Wall time: 20.7 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time all(solve(p) for p in test_puzzles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 134 ms, sys: 3.41 ms, total: 137 ms\n",
      "Wall time: 134 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time all(solve(reorder(p)) for p in test_puzzles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's a nice improvement—150 times faster on this small test set! I'm curious whether we would get even more speedup by treating each cell as a separate variable, or by considering value ordering, but I'll leave that as an exercise for the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tests\n",
    "\n",
    "A suite of unit tests:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def test():\n",
    "    \"Test suite for CrossProduct functions.\"\n",
    "    assert fill_one_row(1, [])  == {()}\n",
    "    assert fill_one_row(2, [])  == set()\n",
    "    assert fill_one_row(9, [9]) == {(9,)}\n",
    "    assert fill_one_row(10, [10])  == set()\n",
    "    assert fill_one_row(73, [360, 360, 360])  == set()\n",
    "    \n",
    "    assert solve(Puzzle([], []))   == []\n",
    "    assert solve(Puzzle([], [1]))  == []\n",
    "    assert solve(Puzzle([], [2]))  == None\n",
    "    assert solve(Puzzle([5], [5])) == [(5,)]\n",
    "    assert solve(Puzzle([0], [0])) == None # Maybe should allow zero as a digit?\n",
    "    assert solve(Puzzle([2, 12], [3, 8])) == [(1, 2), (3, 4)]\n",
    "\n",
    "    assert fill_one_row(729, [90, 126, 81]) == {(9, 9, 9)} # Unique fill\n",
    "    \n",
    "    assert fill_one_row(729, [90, 126, 81, 30]) == {\n",
    "     (3, 9, 9, 3), (9, 3, 9, 3), (9, 9, 3, 3), (9, 9, 9, 1)}\n",
    "    \n",
    "    # 72 has the most ways to fill a 3-digit row\n",
    "    assert max(range(1, 100), key=lambda n: len(fill_one_row(n, [5*7*8*9]*3))) == 72\n",
    "    assert fill_one_row(72, [72, 72, 72])  == { \n",
    "        (1, 8, 9),\n",
    "        (1, 9, 8),\n",
    "        (2, 4, 9),\n",
    "        (2, 6, 6),\n",
    "        (2, 9, 4),\n",
    "        (3, 3, 8),\n",
    "        (3, 4, 6),\n",
    "        (3, 6, 4),\n",
    "        (3, 8, 3),\n",
    "        (4, 2, 9),\n",
    "        (4, 3, 6),\n",
    "        (4, 6, 3),\n",
    "        (4, 9, 2),\n",
    "        (6, 2, 6),\n",
    "        (6, 3, 4),\n",
    "        (6, 4, 3),\n",
    "        (6, 6, 2),\n",
    "        (8, 1, 9),\n",
    "        (8, 3, 3),\n",
    "        (8, 9, 1),\n",
    "        (9, 1, 8),\n",
    "        (9, 2, 4),\n",
    "        (9, 4, 2),\n",
    "        (9, 8, 1)}\n",
    "    \n",
    "    assert fill_one_row(7**8, [7]*9) == {\n",
    "        (1, 7, 7, 7, 7, 7, 7, 7, 7),\n",
    "        (7, 1, 7, 7, 7, 7, 7, 7, 7),\n",
    "        (7, 7, 1, 7, 7, 7, 7, 7, 7),\n",
    "        (7, 7, 7, 1, 7, 7, 7, 7, 7),\n",
    "        (7, 7, 7, 7, 1, 7, 7, 7, 7),\n",
    "        (7, 7, 7, 7, 7, 1, 7, 7, 7),\n",
    "        (7, 7, 7, 7, 7, 7, 1, 7, 7),\n",
    "        (7, 7, 7, 7, 7, 7, 7, 1, 7),\n",
    "        (7, 7, 7, 7, 7, 7, 7, 7, 1)}\n",
    "    \n",
    "    assert solve(Puzzle([210, 144, 54, 135, 4, 49], [6615, 15552, 420])) == [\n",
    "        (7, 6, 5), \n",
    "        (9, 8, 2), \n",
    "        (3, 9, 2), \n",
    "        (5, 9, 3), \n",
    "        (1, 4, 1), \n",
    "        (7, 1, 7)]\n",
    "    \n",
    "    assert sorted(solutions(Puzzle([8, 8, 1], [8, 8, 1]))) == [ # Multi-solution puzzle\n",
    "        [(1, 8, 1), \n",
    "         (8, 1, 1), \n",
    "         (1, 1, 1)],\n",
    "        [(2, 4, 1), \n",
    "         (4, 2, 1), \n",
    "         (1, 1, 1)],\n",
    "        [(4, 2, 1), \n",
    "         (2, 4, 1), \n",
    "         (1, 1, 1)],\n",
    "        [(8, 1, 1), \n",
    "         (1, 8, 1), \n",
    "         (1, 1, 1)]]\n",
    "    \n",
    "    assert not list(solutions(Puzzle([8, 8, 1], [8, 8, 2]))) # Unsolvable puzzle\n",
    "    \n",
    "    assert solve(Puzzle([1470, 720, 270, 945, 12, 343], \n",
    "                        [6615, 15552, 420, 25725])) == [ # 4 column puzzle\n",
    "        (7, 6, 5, 7),\n",
    "        (9, 8, 2, 5),\n",
    "        (3, 9, 2, 5),\n",
    "        (5, 9, 3, 7),\n",
    "        (1, 4, 1, 3),\n",
    "        (7, 1, 7, 7)]\n",
    "    \n",
    "    puzz  = Puzzle([6, 120, 504], [28, 80, 162])\n",
    "    table = [(1, 2, 3), \n",
    "             (4, 5, 6), \n",
    "             (7, 8, 9)]\n",
    "    assert solve(puzz) == table\n",
    "    assert table_puzzle(table) == puzz\n",
    "    assert well_formed(puzz)\n",
    "    \n",
    "    assert not well_formed(Puzzle([7, 7], [7, 7]))\n",
    "    assert well_formed(Puzzle([64, 224, 189, 270, 405, 144, 105], \n",
    "                              [308700, 12960, 1119744]))\n",
    "    \n",
    "    assert row((1, 2, 3)) == '|1|2|3|'\n",
    "    \n",
    "    col_prods = [193536, 155520, 793800]\n",
    "    assert (reorder(Puzzle([10, 48,  36,  7, 32,  81, 252, 160, 21, 90], col_prods)) == \n",
    "                    Puzzle([ 7, 10, 160, 21, 81, 252,  90,  32, 48, 36], col_prods))\n",
    "    return True\n",
    "    \n",
    "test()"
   ]
  }
 ],
 "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
}