ipynb/SudokuJava.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:right\" align=\"right\"><i>Peter Norvig<br>Oct. 2021</i></div>\n",
    "\n",
    "# Solving Sudoku at 100,000 puzzles per second\n",
    "\n",
    "The rules of [**Sudoku**](http://en.wikipedia.org/wiki/Sudoku) are simple and finite:  fill in the empty squares so that each column, row, and 3x3 box contains all the digits from 1 to 9.\n",
    "\n",
    "|Puzzle|Solution|\n",
    "|---|---|\n",
    "|![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg/361px-Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg.png)|![](https://upload.wikimedia.org/wikipedia/commons/thumb/1/12/Sudoku_Puzzle_by_L2G-20050714_solution_standardized_layout.svg/361px-Sudoku_Puzzle_by_L2G-20050714_solution_standardized_layout.svg.png)|\n",
    "\n",
    "\n",
    "In 2006, I wrote a [Python program](http://norvig.com/sudoku.html) to solve [**Sudoku**](http://en.wikipedia.org/wiki/Sudoku). Soon after that,  [Peter Seibel](https://gigamonkeys.com/) invited me to publish an article  in [*Code Quarterly*](https://gigamonkeys.com/code-quarterly/) magazine which would go into more detail about backtracking search and constraint propagation in general, and would feature a  more efficient  program. Unfortunately, the magazine [folded](https://gigamonkeys.wordpress.com/2011/10/17/end-of-the-line-for-code-quarterly/) before I could finish the article. In 2021 I [updated the Python Sudoku program](Sudoku.ipynb) to Jupyter notebook form, with modern coding idioms, and now I do the same for the [more efficient Java Sudoku program](Sudoku.java). (I apologize for some remaining legacy Java idioms from decades ago).\n",
    "\n",
    "The [Java program](Sudoku.java) is similar to the [Python program](Sudoku.ipynb) in many ways:\n",
    "\n",
    "- They both represent a puzzle as a **grid** of 81 squares, with 27 **units** (9 rows, 9 columns, 9 boxes).\n",
    "- They both represent uncertainty about a square's contents with a **set** of the possible digits from 1 to 9.\n",
    "- They both do a depth-first [search](http://en.wikipedia.org/wiki/Search_algorithm) for a solution.\n",
    "  - They find an unfilled square with the fewest remaining possible digits, guess a digit to fill the square, and try to solve the rest of the puzzle from there. If that fails, back up and try a different guess for the square.\n",
    "  - Each guess is placed on a new *copy* of the board. If the guess turns out to be wrong, revert to the old board.\n",
    "- They both use [constraint propagation](http://en.wikipedia.org/wiki/Constraint_satisfaction) to limit the search:\n",
    "  - *The one rule:* After filling a square with a digit, eliminate the digit from all of the square's [peers](https://www.sudocue.net/guide.php#peers).\n",
    "  - *Arc consistency:* after eliminating a possible digit from a square, check that it still has some other possible digit.\n",
    "  - *Dual consistency:* after eliminating a possible digit from a square, check that another square in each of the square's 3 units could hold that digit.\n",
    "  - These changes do not require a new copy of the board, because they are logical consequences, not guesses.\n",
    "  - If a check fails, back up a level in the search.\n",
    "\n",
    "\n",
    "The [Python program](http://norvig.com/sudoku.html) was written for clarity and brevity; the [Java program](Sudoku.java) for efficiency. In particular:\n",
    "- Primitive Java data types are used:\n",
    "  - A grid is an `int[81]` array, not a hash table (dict). \n",
    "  - A square is an int (like `8`), not a string (like `'A9'`).\n",
    "  - A set of possible digits  is an int bitset (like `0b110010100`) not a string of digits (like `'9853'`). \n",
    "- Multiple puzzles are solved in parallel, in different threads.\n",
    "- Rather than allocating (and then garbage collecting) a new copy of the grid at each step in the depth-first search, instead  we pre-allocate a `gridpool` array of grids once and for all (at the start of each thread), and then every recursive call to `search` re-uses `gridpool[level]`. \n",
    "- The specific Sudoku strategy of [naked pairs](https://www.learn-sudoku.com/naked-pairs.html) is implemented.\n",
    "- Java is inherently faster than Python.\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Command Line Options\n",
    "\n",
    "Here are the options for the `java Sudoku` command:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "usage: java Sudoku -(no)[fghnprstuv] | -[RT]<number> | <filename> ...\n",
      "E.g., -v turns verify flag on, -nov turns it off. -R and -T require a number. The options:\n",
      "\n",
      "  -f(ile)    Print summary stats for each file (default on)\n",
      "  -g(rid)    Print each puzzle grid and solution grid (default off)\n",
      "  -h(elp)    Print this usage message\n",
      "  -n(aked)   Run naked pairs (default on)\n",
      "  -p(uzzle)  Print summary stats for each puzzle (default off)\n",
      "  -r(everse) Solve the reverse of each puzzle as well as each puzzle itself (default off)\n",
      "  -s(earch)  Run search (default on, but some puzzles can be solved with CSP methods alone)\n",
      "  -t(hread)  Print summary stats for each thread (default off)\n",
      "  -u(nitTest)Run a suite of unit tests (default off)\n",
      "  -v(erify)  Verify each solution is valid (default on)\n",
      "  -T<number> Concurrently run <number> threads (default 26)\n",
      "  -R<number> Repeat each puzzle <number> times (default 1)\n",
      "  <filename> Solve all puzzles in filename, which has one puzzle per line\n"
     ]
    }
   ],
   "source": [
    "!java Sudoku -help"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Benchmark Puzzles\n",
    "\n",
    "I gathered a collection of puzzles from various sources. I then added variants by permuting digits or rows of a puzzle (e.g. given a valid puzzle, if you swap the first and second row, or swap each 3 with each 7, you still have a valid puzzle). I ended up with exactly 250,000 puzzles:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  250000  250000 20500000 sudoku.txt\n"
     ]
    }
   ],
   "source": [
    "!wc sudoku.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below are the first 10  (the 9 rows of a puzzle are all run together on a line; a dot represents an empty square):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "..7........1....3..5..4.6...4....7...6...3........1..2.....7.......6..8...2.....1\n",
      "..3..2.8.14......9.68.593.7..24.5...............2.85..9.457.86.6......75.8.6..4..\n",
      ".....4.....5.....3...8.1.6.......81..73........2..6.......2....14...........5...7\n",
      "......8..3...6.9.71.8.9..6..673...2....2.6....2...938..3..8.1.25.267...8..9......\n",
      "......7.4.1.5......6..........15.9..8.....3.....6.....4...97.....7..8..........1.\n",
      "..2..6..7......8.9.8..4..6.85.2..93.....3.....93..1.25.1..9..5.5.4......2..3..6..\n",
      ".....8......6.4.........1.7....9......5.....36......84..7.......4.....6.....269..\n",
      "....1......4....6....85............289............7.34.........15....8....3..4..7\n",
      "...9.........1..7..9...4.2..4.16.....5.3......1...7.533......1....58..4.8.....2..\n",
      ".......8...4....15..23.7........3...8.......1.....2..6........4....1.....26...7..\n"
     ]
    }
   ],
   "source": [
    "!head sudoku.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sample Puzzle Solution\n",
    "\n",
    "Here is one puzzle and its solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Puzzle 1:                   Solution:\n",
      ". . 7 | . . . | . . .       6 9 7 | 5 3 8 | 1 2 4 \n",
      ". . 1 | . . . | . 3 .       4 2 1 | 7 9 6 | 8 3 5 \n",
      ". 5 . | . 4 . | 6 . .       3 5 8 | 1 4 2 | 6 7 9 \n",
      "------+-------+------       ------+-------+------\n",
      ". 4 . | . . . | 7 . .       1 4 3 | 8 2 9 | 7 5 6 \n",
      ". 6 . | . . 3 | . . .       2 6 5 | 4 7 3 | 9 1 8 \n",
      ". . . | . . 1 | . . 2       8 7 9 | 6 5 1 | 3 4 2 \n",
      "------+-------+------       ------+-------+------\n",
      ". . . | . . 7 | . . .       5 8 6 | 2 1 7 | 4 9 3 \n",
      ". . . | . 6 . | . 8 .       9 1 4 | 3 6 5 | 2 8 7 \n",
      ". . 2 | . . . | . . 1       7 3 2 | 9 8 4 | 5 6 1 \n"
     ]
    }
   ],
   "source": [
    "!java Sudoku -grid -nofile one.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Latency versus Throughput\n",
    "\n",
    "There are two measures of the efficiency of a program:\n",
    "1. **Latency** is the time it takes to solve a single puzzle.\n",
    "2. **Throughput** is the number of puzzles that can be solved in a given amount of time.\n",
    "\n",
    "These measures would amount to the same thing if there were only one processor available, but if, say, there are 10 processors working in parallel with no overhead and each puzzle takes 1 second to solve, then latency would be 1 second but throughput would be 10 puzzles per second.\n",
    "\n",
    "# Benchmark Timing Statistics\n",
    "\n",
    "Let's run the program and print two lines of summary timing statistics: one line for the 250,000 puzzles in `sudoku.txt`, and one line where the  `-r` option specifies that the reverse of each puzzle is also solved (the last square becomes the first, etc.), and the  `-R2` option specifies that each puzzle is repeated twice, for a total of  2 × 2 × 250,000 = a million puzzles.  (The idea is that there will be less variance if there are more puzzles to solve, and also that the effect of any JIT cache warmup period will be lessened.) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Puzzles   μsec     KHz Threads Backtracks Name\n",
      "======= ====== ======= ======= ========== ====\n",
      " 250000   10.7  93.400      26       30.3 sudoku.txt\n",
      "1000000    8.5 117.781      26       31.4 sudoku.txt\n"
     ]
    }
   ],
   "source": [
    "!java Sudoku sudoku.txt -r -R2 sudoku.txt "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We solved a million puzzles with a throughput of **over 100,000 puzzles per second**. Not too shabby! \n",
    "\n",
    "The columns of the output are:\n",
    "\n",
    "- `Puzzles`: the total number of puzzles solved.\n",
    "- `μsec`: the throughput expressed as average time to solve a puzzle in microseconds (millionths of a second).\n",
    "- `KHz`: the throughput expressed as thousands of puzzles solved per second.\n",
    "- `Threads`: the number of concurrent threads.\n",
    "- `Backtracks`: the average number of times per puzzle that the search guessed wrong and had to back up.\n",
    "- `Name`: here the name of the file; could also be the name of a thread or puzzle.\n",
    "\n",
    "To determine the latency, use the `-T1` option to request a single thread:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Puzzles   μsec     KHz Threads Backtracks Name\n",
      "======= ====== ======= ======= ========== ====\n",
      " 250000   98.5  10.148       1       34.2 sudoku.txt\n"
     ]
    }
   ],
   "source": [
    "!java Sudoku -T1 sudoku.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The average latency is about 100 μsec (or 1/10,000th of a second)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Effect of Number of Threads\n",
    "\n",
    "I'm running these benchmarks on a [10-core Intel Comet Lake core i9 processor](https://everymac.com/systems/apple/imac/specs/imac-core-i9-3.6-10-core-27-inch-retina-5k-2020-20-2-specs.html) with [hyperthreading](https://www.intel.com/content/www/us/en/gaming/resources/hyper-threading.html) that allows 20 threads to run at once. So I expected that peak throughput would be at 20 threads–any more than that, and there would be overhead of swapping threads in and out. Let's look at this plot of throughput  versus number of threads:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEGCAYAAACKB4k+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3de3xU5Z3H8c8vFyCQQLhGCCiiiEW8YPBSr6BSrGuVWu+2q62tva1ldWuVtlu73W2L0nqr3bq2dr3UilZdtFqlikHEispFBS8oCioBAYEAgdzz2z/OSRjCJBmSzJyZ5Pt+vebFnOfMzPlyxPnNeZ5znmPujoiICEBW1AFERCR9qCiIiEgTFQUREWmioiAiIk1UFEREpElO1AE6YtCgQT5y5Mg92nfs2EGfPn1SH6gDlDk1lDn5Mi0vdL/Mixcv/tTdB8dd6e4Z+ygpKfF4SktL47anM2VODWVOvkzL6979MgOLvIXvVXUfiYhIExUFERFpkrSiYGZ/NLMNZrY8pm2mmb1jZm+Y2f+ZWWHMuulmttLMVpjZlGTlEhGRliXzSOFu4PRmbc8A49z9MOBdYDqAmY0FLgQOCd/z32aWncRsIiISR9KKgrvPBzY3a/u7u9eFiwuB4eHzs4FZ7l7t7quAlcDRycomIiLxRXlK6teAB8PnxQRFotGasE1EupDZS8uYOWcFa8srGVaYxzVTxjB1fPFev0aSxzyJs6Sa2UjgCXcf16z9R8AE4Bx3dzP7LfCSu/8pXH8X8Dd3fyTOZ14BXAFQVFRUMmvWrD22W1FRQX5+fif/bZJLmVNDmZOvpbz/WFvL3ctrqGnY1dYjCy4b14PjhuUm/JpUZk5nHck8adKkxe4+Id66lB8pmNmlwJnAqb6rIq0BRsS8bDiwNt773f1O4E6ACRMm+MSJE/d4zbx584jXns6UOTWUOflayvujGc/t9mUPUNMAT36UzQ8vnshdC1bxyPsrW31NqjOns2RlTukpqWZ2OnAtcJa774xZ9ThwoZn1NLP9gdHAK6nMJiLJVVZeGbd9bdj+u3kr2bSjpsXX1NU3xF0nnSuZp6Q+ALwEjDGzNWZ2OXA7UAA8Y2avmdkdAO7+JvAQ8BbwNPBdd69PVjYRSY3Y7unePeKfUDisMA+Al6afyrDCXnFfM7igJ0f9/FleXPkpEIw7HD/jOfa/7kmOn/Ecs5eWdXLy7itp3UfuflGc5rtaef3PgZ8nK4+IJFfjAHFZeSXFC5/jwqNH8OQb67j94iM5cEg+Pz7zM/zsr29RVbvrF39ebjbXTBkDQG52Fj+YcjDTH11GZW39bq+5/ISRLCvbxugh+cxeWsYPHnmDmrrgc8rKK5n+6DKA3QakNWDdPhk9IZ5IV9b8SzYdv9R2VNfR4M7ctzfs9mVeVl7Jb0tXMrigJ1srgy6hi4/ej965Oa1+UTc+b+01M+esaCoIjSpr67nukTeaXvc/89/npr+/S3WChSOd93GqqSiIpKHZS8v2+JKd/ugy6hsamDJuKPk9g/91N26vZltVLQcMDs5CeW/9dj6tqOGzBwwE4OUPNrFhezVfOHwYAH9bto6N26u59LiRANzzj9Vs3lHDVZMPAuBXc1awvaqW/zg7OGHw+395ndr6Bm69cDwAX/7Dy/TIyeKPlx0FwAV3vsSQgl6s+GT7br/uAapqG2hogJL9BjS1TR1f3OaXbluvWdvC2ERVTKG4+ZldBaFRZW09M+esYOr4Yl77uJyX3v+U2+au3GMfN2borjT3kUgamjlnxR5fspW19fzk8Tf57C/mNrXdNvc9zrvjpabluxasYtqspU3LD776MTc8/U7T8t+WreOel1Y3Lb+5ditLPtrStFxVW79b986I/r3Zb0DvpuXJY4s45eAhTcvfOHEUFx41osUv6pbaO6JxDKK54pj26tr4g9KNeX7y2HJuefa9uPt45pwV3PTMuzy8eE1Te+mKDby9blvTckV1HQ0NyTudP0o6UhBJMxXVdS1+me6sruffzxzbtHz+hBGcMHpQ0/I3Tz6Ai4/Zt2n5x2eOpa5h1xfkrReOJ8t2fd6N5x6+2+f/OOazAaadNnq35cYjjEZnHxH8oh5WmBf37KKWvsA74popY+KOOzSOTSSSZ8Y5h/FPt70Q9/PXlldS+s4GDh/Rj3NLgkkXrvnLG0weO4RfnnMYACfe8BxnHjaM/5waHFFddOdCzjhsKF85dj8Abnn2XY4dNZBjRwVHbK+u3sx+A3ozpG/8gfS9kewuLx0piKSRqtp6zrp9AXmtnKnztRP2b1o+dHg/phyyT9Py/oP6cNjwpnkmGdCnB0MKdn0RZWcZZjFVoZNcM2UMebm7Z27+Rd1Zpo4v5pfnHEpxYR5GcITwy3MO3e2Lsa08Y4f1bbFgDSvM469XnsB/TT20qe2BbxzDdyYe2LT8vVNHN+13d6dnbha5YbWtqWvgtrnv8eqqYJafqtp6zrvjJR5ZEpwhVVFdx5gfP8V9L60GYFtVLV+/ZxHz390IBOM09760mg82VjR93qpPd1BZU9/UrdhY8Bq7vDrz7CsdKYikkV652VxyzH5s2VHNXQtWt/prOJ3EDhCXlVdSnOSzfdoad0hkwDqRI45Go4sKdlv+6vG7CrOZcfdXd03V1iMni5U/P4P68HTc7CzjT5cfw75hN5y7c+lxIxmzT18AKmvqKSuvZEd1MC3cJ9uq+Mljb3LrhUcwanA+qzft4HM3z+f2i8e32K3YOFbSGVQURCK2eUcNP3x0Gf9yyoGMK+7H5eGRwIFDClL2JdsZGr+o0+Xq4L0pHJ29j7OyjCyCI4fc7KzduvgKeuXywzM+07Rc1LcXT007sWl55MA+vPqj0+jTMzjSGVLQk5svOJzx+/ZPydiNioJIxNydN9dtZeWGCsYV92tqT7cv2a4oHfdxdpYxuKBn03Jh7x58cXwwtpGKsRuNKYhEoK6+gf9bugZ3Z2B+T569+uS0PgqQ9JCKsRsVBZEIPLlsHVc9+DoLwmkbeubonlLStthBdog/yN5R6j4SSaGtO2vp1zuXsw4fxqD8nhx/4KC23yQSI9ldXjpSEEmR35au5PRb57NlRw1mpoIgaUlHCiIpcvJBg9lWVUufnvrfTtKX/nWKJIm78+CrH7NpRw3fnRScbhp7dpFIOlL3kUiSmBmvrN7My6s2U99F58mRrkdHCiKdbMlHW9inby+GFebxiy8eSo/sLLKyOn9qCZFk0JGCSCeqqK7jq//7atPMpL1ys1UQJKPoSEGkE1RU15HfM4f8njnc+ZUSDh7aN+pIIu2iIwWRDnp3/XYmzixlzpufAHDMqIH0y8uNOJVI+6goiHTQyIF9OGn0YEYN6hN1FJEOU1EQaYcPN+3g3x56naraenrkZHHTBUfsMb2ySCZSURBphw827uDZt9ezckNF1FFEOpWKgkiCdtbU8fIHmwCYdPAQXrh2ki5Gky5HRUEkQT/761t87e5XKd9ZA0DfXhpMlq5Hp6SKtMLdqa5roFduNldNPoizjyimsHePqGOJJI2KgkgL3J1v/2kJOdnGby4aT1HfXhT17RV1LJGkUlEQaYGZceR+heRkqZdVug8VBZEYdfUN3F66kpMPGsz4fftzxUkHRB1JJKWS9hPIzP5oZhvMbHlM2wAze8bM3gv/7B+2m5ndZmYrzewNMzsyWblEWrOztp6/LFrDs2+vjzqKSCSSeVx8N3B6s7brgLnuPhqYGy4DfB4YHT6uAH6XxFwie3j5g000NDh9e+XyxJUncM2Ug6OOJBKJpBUFd58PbG7WfDZwT/j8HmBqTPu9HlgIFJrZ0GRlE4n16urNXHDnQv6y+GMA+vfR2UXSfZl7/Jt/mNl2oMU7g7h7m9NAmtlI4Al3Hxcul7t7Ycz6Le7e38yeAGa4+4KwfS5wrbsvivOZVxAcTVBUVFQya9asPbZbUVFBfn5+W/HSijKnRmzmugYnJ8twd15cW8exQ3PIScNprjNtP2daXuh+mSdNmrTY3SfEXenurT6AnwHfAQqAvsC3gR+09b7wvSOB5THL5c3Wbwn/fBI4IaZ9LlDS1ueXlJR4PKWlpXHb05kyp0Zj5qeWrfMTbpjr67dVRhsoAZm2nzMtr3v3ywws8ha+VxM5+2iKux8Ts/w7M3sZuHHvahMA681sqLuvC7uHNoTta4ARMa8bDqxtx+eLxDV7aRkz56ygrLyS4oXP8eVj92X0kIJWjoVFuqdExhTqzewSM8s2sywzuwSob+f2HgcuDZ9fCjwW0/7P4VlIxwJb3X1dO7chspvZS8uY/ugyysorASgrr+S2uSs56/BhDNHFaCK7SaQoXAycD6wPH+eFba0ysweAl4AxZrbGzC4HZgCTzew9YHK4DPA34ANgJfB7gu4qkU4xc84KKmt3/x1TWVvPzDkrIkokkr7a7D5y99UEZwftFXe/qIVVp8Z5rQPf3dttiLTlHys/ZW14hNBcS+0i3VmbRcHMBgPfIBg0bnq9u38tebFEOm5HdR3f+fMSeuVm73GkADCsMC+CVCLpLZGB5seAF4Bnaf9YgkhKuDuvrNrM0fsPoE/PHO756tG8u347P3nszd0KQ15uNtdMGRNhUpH0lEhR6O3u1yY9iUgneHr5J3z7/iX872VHMengIRw+opDDRxSSm5216+yjwjyumTKGqeOLo44rknYSKQpPmNkZ7v63pKcRaYeGBmf99iqG9stj8tgibvzSYZw4etBur5k6vpip44uZN28eEydOjCaoSAZI5OyjaQSFocrMtoePbckOJpKo7z/8OhfeuZCq2npysrM4/6gR5GRrumuR9kjk7KOCVAQR2Rs1dQ1kGUERmDCC4w4YRM8cFQKRjkrofgpmdhZwUrg4z92fSF4kkdZt3VnL+f/zEueWDOcbJ43i2FEDo44k0mW0+dPKzGYQdCG9FT6mhW0iKeXh5I1983I4av/+HDgksyYwE8kEiRxvnwFMdvc/uvsfCe6RcEZyY4nsbtHqzZz5mwVs3F6NmfFfUw9l0sFDoo4l0uUk2glbGPO8XzKCiLSmsHcuAFt21kScRKRrS2RM4ZfAUjMrBYxgbGF6UlOJEExk98HGCq7+3BgOHFLAE1eegFn63e9ApCtJ5OyjB8xsHnAUQVG41t0/SXYwkdc+Lmd52VaurG8gNztLBUEkBRKZ++iLwHPu/ni4XGhmU919dtLTSbdSV9/A3f9YzckHDWZ0UQHXff5gemRnkZWGd0MT6aoSGVO43t23Ni64ezlwffIiSXe1tbKW20tXMvu1MgB65WarIIikWCJjCvEKR0LXN4i0paq2nifeWMeXjixmYH5PnrjyBIo1e6lIZBI5UlhkZjeZ2QFmNsrMbgYWJzuYdA+PLFnD9//yOq+vCQ5Gh/fvrbEDkQgl8ov/SuDfgQfD5b8DP05aIunytlbW8snWKsbsU8AFE0ZwUFEBR4wobPuNIpJ0iZx9tAO4zszy3b0iBZmki/vGvYv4dHs1z1x9MjnZWRw1ckDUkUQklMjZR8cBfwDygX3N7HDgm+6u+yhLwjZsr2JA7x7kZGdx3ecPJjcri2wNIouknUTGFG4GpgCbANz9dXZNjifSpjVbdnLqr5/nrgWrADhy3/4cOlwXxouko4SmuXD3j5s16bac0qaq8PaXxYV5fP2EUUw5ZJ+IE4lIWxIpCh+HXUhuZj3M7PvA20nOJRnusdfKOHlmadMEdtNOG83IQX2ijiUibUikKHwL+C5QDKwBjgiXRfbQOL31IcP6ccz+A9HZpSKZJZGzjz4FLklBFslg7s4vn3qH2voGrv/CIRw4JJ/bLhofdSwR2UuJ3GTnRjPra2a5ZjbXzD41sy+nIpykp9lLyzh+xnNc9vQOjp/xHLOXlmFm1NY3UFfvTUcLIpJ5Erl47XPu/oNwYrw1wHlAKfCnpCaTtDR7aRnTH11GZTiIXFZeybWPvAHAT84cq6uRRTJcImMKueGfZwAPuPvmJOaRNDdzzoqmgtCouq6BmXNWqCCIdAGJFIW/mtk7wARgrpkNBqo6slEzu8rM3jSz5Wb2gJn1MrP9zexlM3vPzB40sx4d2YYkx9ryyr1qF5HM0mZRcPfrgM8CE9y9FtgJnN3eDZpZMfC98PPGAdnAhcANwM3uPhrYAlze3m1I8gzt1ytu+zDNbCrSJSR68doWd68Pn+/ohDuv5QB5ZpYD9AbWAacAD4fr7wGmdnAbkgRXTz6InGbTU+TlZnPNlDERJRKRzmRRnCliZtOAnwOVBLOuTgMWuvuB4foRwFPhkUTz914BXAFQVFRUMmvWrD0+v6Kigvz8/OT9BZIgkzL/Y20tj7xby6aqBgb2yuJLB+Vy3LDctt+YBjJpPzfKtMyZlhe6X+ZJkyYtdvcJcVe6e9wHkNPSuo48gP7Ac8BggkHs2cBXgJUxrxkBLGvrs0pKSjye0tLSuO3pLN0zb6+q9cvvfsXfWru1qS3dM8ejzMmXaXndu19mYJG38L3a2impC81sDfA08LS7r25XSdrTacAqd98IYGaPAscBhWaW4+51wHBgbSdtTzrBh5t2sLxsG9ur6qKOIiJJ1GJRcPcJZrYf8HnglnCAeAHwFPC8u1e3c5sfAceaWW+C7qNTgUUE1z6cC8wCLgUea+fnSxIcMqwfz/9gIj1zsqOOIiJJ1OpAs7t/6O53uPtUgl/zfyX4pf+CmT3Zng26+8sEA8pLgGVhhjuBa4GrzWwlMBC4qz2fL51r4/ZqZr3yEe6ugiDSDSRyRTMAHpyO+lz4aDy1tF3c/Xrg+mbNHwBHt/czJTn+/PJH/HbeSo4/cBAjBvSOOo6IJFnCRaE5dy/rzCCSnq485UAmjy1SQRDpJhK6TkG6n7LySrburCUryxg7rG/UcUQkRfaqKJhZlpnpG6KLc3eumvUaF9z5Eg0NmvFUpDtps/vIzP5McKOdemAx0M/MbnL3mckOJ9EwM3585mf4tKKarCxNcifSnSRypDDW3bcRTDvxN2BfgovNpAuqrgtmQD1seCGnHFwUcRoRSbWEps42s1yCovBYeBaS+hS6oMqaer7wmwXc/eKqqKOISEQSKQr/A6wG+gDzwwvatiUzlESj3p1xxf04qKgg6igiEpFE7tF8G3BbTNOHZjYpeZEkKvk9c7jp/COijiEiEUrkHs1FZnaXmT0VLo8lmIZCuogtO2q48oGlulGOiCTUfXQ3MAcYFi6/C/xrsgJJ6r21bhsL3ttI+c7aqKOISMQSKQqD3P0hoAEgnMW0vvW3SCY5/sBBvHjdKbpITUQSKgo7zGwg4RlHZnYssDWpqSQlPt68k2ffWg9A7x7tnvFERLqQRIrC1cDjwAFm9iJwL3BlUlNJSvz3vPe56sHXKN9ZE3UUEUkTiZx9tMTMTgbGAAasCK9VkAz307PGctHRIyjs3SPqKCKSJlosCmZ2TgurDjIz3P3RJGWSJFuzZSeDC3rSMyebw4YXRh1HRNJIa0cKX2hlnQMqChmorr6Br939Kvv0y+Per+n2FSKyu9Zux/nVVAaR1MjJzuK6zx9Mj2zdRU1E9pTIxWv1ZjbDzCymbUlyY0ky1NU3AHDKwUWcMHpQxGlEJB0lcvbRm+Hr/m5mA8I2zaecYbburGXKLfN58o11UUcRkTSWSFGoc/cfAL8HXjCzEjRLasaprq9neP/ejBiQF3UUEUljiVyxZADu/pCZvQk8QHBPBckgQwp6cY8GlkWkDYkcKVze+MTd3wROAL6XtETSqdZtrWT6o8vYWqlLS0SkbYkUhb+Y2bcaF8K7sJ2fvEjSmV5ZtZkn3ljLlh26allE2pZI91EtMMnMjgG+6e41QHFyY0lnOfuIYiaOGUK/vNyoo4hIBkjkSGGnu18AvE0w0LwfGmhOeys3bOf1j8sBVBBEJGGJFIXGgeYbgR8S3FtheDJDScfNeOodrrhvEdV1muVcRBKXSPfRTxqfuPtcM/sccFnSEkmn+PX5R7Dq0x30zNGVyyKSuESKwlYzO6lZ27yObNTMCoE/AOMIuqK+BqwAHgRGAquB8919S0e20x2t21pJUUEv+uXlcsQITXYnInsnkaJwTczzXsDRwGLglA5s91bgaXc/18x6AL0JuqbmuvsMM7sOuA64tgPb6HZ21tRx3h0vccKBg5jxpcOijiMiGSiR+ynsNluqmY0AbmzvBs2sL3ASYRdUeDZTjZmdDUwMX3YPwdGIisJeyMvN5ruTDuSgooKoo4hIhmrPPRjXEHT7tNcoYCPwv2Z2OMFRxzSgyN3XAbj7OjMb0oFtdDsNDU5WlnHR0brYXETaz9xbP7vUzH7DrlNQs4AjgNXu/uV2bdBsArAQON7dXzazW4FtwJXuXhjzui3u3j/O+68ArgAoKioqmTVr1h7bqKioID8/vz3xItORzOVVDfxqURVfGduTMQNSN7Dc3fZzVDItc6blhe6XedKkSYvdfULcle7e6gO4NOZxCcGXeZvva+Xz9iEoKo3LJwJPEgw0Dw3bhhLc9rPVzyopKfF4SktL47ans45kfn/Ddj/79gX+3vrtnRcoAd1tP0cl0zJnWl737pcZWOQtfK+22n1kZuOBHcCb7v52u0rSnkXoEzP72MzGuPsK4FTgrfBxKTAj/POxzthedzBqcD7/953jiLnlhYhIu7R48ZqZ/YTgFNEvAU+a2Tc6cbtXAveb2RsE3VG/ICgGk83sPWByuCyteH9jBTPnvENNXYMKgoh0itaOFC4AjnD3nWY2EHia4J4KHeburwHx+rNO7YzP7y7mvr2e+1/+iEs/O5IhfXtFHUdEuoDWikKVu+8EcPdNZpbIlBiSQlecdADnHDmcQfk9o44iIl1Ea0XhADN7PHxuzZZx97OSmkxa9ObarRT0zGXfgb1VEESkU7VWFM5utvyrZAaRxLg70x9dRnVtA09NO5GsLI0liEjnabEouPvzqQwiiTEzfvflEjZX1KggiEin0zhBBtm4vRqA4sI8Dh3eL+I0ItIVqShkiE0V1Xz+1vnc+ux7UUcRkS5MRSFD9M3L5ZJj9uP0cftEHUVEurAWxxTMrB8wHZgKDA6bNxBcaTzD3cuTH08gGFzOzc7iqskHRR1FRLq41o4UHgK2ABPdfaC7DwQmhW1/SUU4gQ837WDqb19kxSfbo44iIt1Aa0VhpLvf4O6fNDa4+yfufgOg+ZlTZNOOGqpqGyjo1Z5ZzkVE9k5rReFDM/uBmRU1NphZkZldC3yc/GgCcOS+/Xlq2okMK8yLOoqIdAOtFYULgIHA82a2xcy2ENwNbQBwfgqydWvL1mzl7hdXNd08R0QkFVq7eG0Lwe0wdUvMCDyyZA1PL/+Ec0qG07dXbtRxRKSbaOt+ClMIzj4qJrj72lrgMXd/OgXZurXrvzCWb548SgVBRFKqtVNSbwEOAu4luC8zwHDge2b2eXefloJ83c6yNVsZ3j+P/n16MLSfxhFEJLVaO1I4w933ODHezB4E3gVUFDpZXX0D375/MfsN7M39Xz826jgi0g21ej8FMzva3V9p1n4UUJXETN3K7KVlzJyzgrLySooXzuOiY0Zw6sFFbb9RRCQJWisKlwG/M7MCdnUfjQC2heukg2YvLWP6o8uorK0HoKy8kt8+9z7DC3vzmaF9I04nIt1Ra2cfLQGOMbN9CAaaDVgTezGbdMzMOSuaCkKjytp6Zs5ZwdTxxRGlEpHurK2zj/oBJxNz9pGZzdG8R51jbXnlXrWLiCRbixevmdk/A0uAiUBvoA/B3EeLw3XSQS1dpayrl0UkKq0dKfwIKGl+VGBm/YGXCU5VlQ74/ucO4pqH36CuwZva8nKzuWbKmAhTiUh31to0F0bQZdRcQ7hOOmjCyAFkZ0G/vOACteLCPH55zqEaTxCRyLR2pPBzYImZ/Z1dE+DtC0wG/jPZwbqDEQN6s3D6aeT3yuHFF+YzceLEqCOJSDfX4pGCu98DTACeB6qBGoIJ8Sa4+92pCNeVbaoI7rfcv08PcrN1AzwRSQ+tnn0UToo3K0VZuo2q2nrOuv1FTh+3D/9+5tio44iINGnXT1QzW9bZQbqTLDO+evxIJo/Vlcsikl5amxDvnJZWAbp7fAf0yMni6yeOijqGiMgeWus+ehC4n/hnIPXq6IbNLBtYBJS5+5lmtj9BV9UAgusjvuLuNR3dTrq5b+GHDO+fx6QxQ6KOIiKyh9aKwhvAr9x9efMVZnZaJ2x7GvA20DjJzw3Aze4+y8zuAC4HftcJ20kb9Q3O/Qs/5OB9ClQURCQttTam8K8Ek9/F88WObNTMhgP/BPwhXDbgFODh8CX3ENzcp0vJzjIe/5cT+OlZh0QdRUQkLnOP1zuU5I2aPQz8EigAvk8w6+pCdz8wXD8CeMrdx8V57xXAFQBFRUUls2bteXJURUUF+fn5ScvfHhU1Tl5OUBjirk/DzG1R5tTItMyZlhe6X+ZJkyYtdvcJcVe6e0ofwJnAf4fPJwJPAIOBlTGvGQEsa+uzSkpKPJ7S0tK47VH65r2L/OzbF3hDQ0Pc9emYuS3KnBqZljnT8rp3v8zAIm/he7XV6xSS5HjgLDM7g2DAui9wC1BoZjnuXkdw28+1EWRLmqnji9mys4agp0xEJD2l/FJad5/u7sPdfSRwIfCcu18ClALnhi+7FHgs1dmS6fRx+3DR0ftGHUNEpFUJFQUzO7K15U5yLXC1ma0EBgJ3JWEbKbfgvU+5b+GH1NU3RB1FRKRNiR4pfLuN5XZx93nufmb4/AN3P9rdD3T389y9ujO2EbUnl63lrhc+iHuxh4hIukloTMHdv9HasrTsF188lE8rajTpnYhkhDa/qcxsbjgoHNt2Z/IidQ3VdfVsr6rFzBhc0DPqOCIiCUnk5+v+wLVmdn1MW/zzW6XJfS99yMkz57FhW1XUUUREEpZIUSgHTgWKzOyvZtYvyZm6hGNHDeTio/dlSN8OTxMlIpIyiYwpWHjtwHfM7DJgAdA/qam6gHHF/RhXrPopIpklkSOFOxqfeHDHtcuAvycpT8Zbv62KG55+h62VtVFHERHZay0WBTMbYGYDgL80Pg+XVxHMVyRxzH93I3ctWMXWnSoKIpJ5Wus+WkxwLwUDhhJMO9E4R4MDuktMHOdNGMHEMUN0xpGIZKQWi4K778HdTvkAAA0jSURBVN/43MyWuvv41ETKXJsqqhmY31MFQUQyVqJXVOmC3DYs+WgLn53xHPPf3Rh1FBGRdtNltp1kWL88Lj56X0r204lZIpK5Wuw+MrOrYxaHNFvG3W9KWqoMtE+/XrqjmohkvNaOFApiHr9vtpxZtyhKovoG5xd/e5vVn+6IOoqISIe1dvbRXe6+Jt4KM/tCkvJknBWfbOdPCz/ksOH9GDmoT9RxREQ6pLUjhblmNrJ5o5l9leBOaQKMHdaX+T+YxBnjhkYdRUSkw1orClcBz5jZ6MYGM5sOXA2cnOxgmWBTRXDLh0H5PcnK0m02RSTztVgU3P1vwLeAp8xsnJndApwJnNRSt1J3sq2qltNuep7fzH0v6igiIp2m1VNS3X0uwVxH8wiuYD7V3bckP1b6y83K4vIT9mfSwUOijiIi0mlaOyV1O7umuehJMH32BjMzwN29b2oipqe8Htn8yymj236hiEgGaW2ai4JUBskkv5//AYcN78cxowZGHUVEpFPpiua9VFVbz93/WM1Tyz+JOoqISKdL5CY7EqNXbjZz/+1kauoboo4iItLpdKSwFzbvqKGhwemVm03fXrlRxxER6XQqCglyd771p8V87Z5Xo44iIpI06j7aCxcdPYIs00VqItJ1qSgkyMz44vjhUccQEUkqdR8l4Onln/Dw4jU0NOheQyLStaW8KJjZCDMrNbO3zexNM5sWtg8ws2fM7L3wz7S5W83spWXc84/VUccQEUm6KLqP6oB/c/clZlYALDazZwim05jr7jPM7DrgOuDaCPLt4b8vOZLNO2s06Z2IdHkpP1Jw93XuviR8vh14GygGzgbuCV92DzA11dma21FdR2VNPVlZxqD8nlHHERFJOnOPrp88vF/DfGAc8JG7F8as2+Lue3QhmdkVwBUARUVFJbNmzdrjcysqKsjP7/jN4R5+t4YXy+r4xYl55OUk9yihszKnkjKnRqZlzrS80P0yT5o0abG7T4i70t0jeRDc0nMxcE64XN5s/Za2PqOkpMTjKS0tjdu+t15Ztcl/M/fdTvmstnRW5lRS5tTItMyZlte9+2UGFnkL36uRnJJqZrnAI8D97v5o2LzezIa6+zozGwpsiCJbrKNGDuCokQOijiEikjJRnH1kwF3A2+5+U8yqx4FLw+eXAo+lOluj9zdWcPMz77Kjui6qCCIikYjiOoXjga8Ap5jZa+HjDGAGMNnM3gMmh8uRKH1nA3ctWEVlbX1UEUREIpHy7iN3X0Bw4554Tk1llpZ8/cRRnH1Esc44EpFuR1c0x3B3NlVUAzC4QAVBRLofFYUY81Zs5PgbnmPpR7oNtYh0TyoKMQ4YnM9FR+/LuOJ+UUcREYmEZkmNse/A3lz/hUOijiEiEhkdKRDcd/k/n3iLteWVUUcREYmUigLw+sfl3LfwQ1Z9uiPqKCIikVL3EXDMqIG8eO0pOuNIRLq9bn+koFNQRUR26dZFYf22Kk68sZT7XloddRQRkbTQrYtCXo9sLjtuJCcdNDjqKCIiaaHbjSnMXlrGzDkrWFteybDCPK6ZMob9BvaJOpaISFroVkVh9tIypj+6rGmiu7LySqY/ugyAqeOLo4wmIpIWulX30cw5K/aY+bSytp6Zc1ZElEhEJL10q6LQ0sVpumhNRCTQrYrCsMK8vWoXEeluulVRuGbKGPJys3dry8vN5popYyJKJCKSXrrVQHPjYHLzs480yCwiEuhWRQGCwqAiICISX7fqPhIRkdapKIiISBMVBRERaaKiICIiTVQURESkibl71Bnazcw2Ah/GWTUI+DTFcTpKmVNDmZMv0/JC98u8n7vHnR46o4tCS8xskbtPiDrH3lDm1FDm5Mu0vKDMsdR9JCIiTVQURESkSVctCndGHaAdlDk1lDn5Mi0vKHOTLjmmICIi7dNVjxRERKQdVBRERKRJlysKZna6ma0ws5Vmdl3UeRJhZqvNbJmZvWZmi6LOE4+Z/dHMNpjZ8pi2AWb2jJm9F/7ZP8qMsVrI+1MzKwv382tmdkaUGZszsxFmVmpmb5vZm2Y2LWxP5/3cUua03ddm1svMXjGz18PM/xG2729mL4f7+UEz6xF1Vmg1791mtipmHx/RKdvrSmMKZpYNvAtMBtYArwIXuftbkQZrg5mtBia4e9pePGNmJwEVwL3uPi5suxHY7O4zwgLc392vjTJnoxby/hSocPdfRZmtJWY2FBjq7kvMrABYDEwFLiN993NLmc8nTfe1mRnQx90rzCwXWABMA64GHnX3WWZ2B/C6u/8uyqzQat5vAU+4+8Odub2udqRwNLDS3T9w9xpgFnB2xJm6BHefD2xu1nw2cE/4/B6CL4O00ELetObu69x9Sfh8O/A2UEx67+eWMqctD1SEi7nhw4FTgMYv2LTZz63kTYquVhSKgY9jlteQ5v9AQw783cwWm9kVUYfZC0Xuvg6CLwdgSMR5EvEvZvZG2L2UNt0wzZnZSGA88DIZsp+bZYY03tdmlm1mrwEbgGeA94Fyd68LX5JW3x3N87p74z7+ebiPbzaznp2xra5WFCxOWyb0jx3v7kcCnwe+G3Z9SOf7HXAAcASwDvh1tHHiM7N84BHgX919W9R5EhEnc1rva3evd/cjgOEEPQyfifey1KZqWfO8ZjYOmA4cDBwFDAA6pUuxqxWFNcCImOXhwNqIsiTM3deGf24A/o/gH2kmWB/2KTf2LW+IOE+r3H19+D9XA/B70nA/h33GjwD3u/ujYXNa7+d4mTNhXwO4ezkwDzgWKDSzxlsUp+V3R0ze08OuO3f3auB/6aR93NWKwqvA6PAsgh7AhcDjEWdqlZn1CQfoMLM+wOeA5a2/K208DlwaPr8UeCzCLG1q/GINfZE028/hgOJdwNvuflPMqrTdzy1lTud9bWaDzawwfJ4HnEYwFlIKnBu+LG32cwt534n5oWAE4x+dso+71NlHAOGpb7cA2cAf3f3nEUdqlZmNIjg6AMgB/pyOmc3sAWAiwXS964HrgdnAQ8C+wEfAee6eFoO7LeSdSNCd4cBq4JuNffXpwMxOAF4AlgENYfMPCfro03U/t5T5ItJ0X5vZYQQDydkEP4wfcvefhf8vziLoilkKfDn8FR6pVvI+Bwwm6DZ/DfhWzIB0+7fX1YqCiIi0X1frPhIRkQ5QURARkSYqCiIi0kRFQUREmqgoiIhIExUFSXtm5mb265jl74eT23XGZ99tZue2/coOb+e8cCbR0mbtI83s4pjly8zs9mTnCbfV4dMXpetRUZBMUA2cY2aDog4SK5yVN1GXA99x90nN2kcCF+/58k7dtkjCVBQkE9QR3I/2quYrmv/Sb/z1a2YTzex5M3vIzN41sxlmdkk4L/0yMzsg5mNOM7MXwtedGb4/28xmmtmr4YRj34z53FIz+zPBBVvN81wUfv5yM7shbPsJcAJwh5nNbPaWGcCJ4Xz4jX+/YWb2tAXz+t8Y+3czs5+Z2cvAZ82sJPw7LjazOTFXuH4jzP26mT1iZr3D9v3N7KVw3X/GfO5QM5sfZlhuZicm9p9FuiR310OPtH4Q3BehL8GVsf2A7wM/DdfdDZwb+9rwz4lAOTAU6AmUAf8RrpsG3BLz/qcJfiCNJpg/qxdwBfDj8DU9gUXA/uHn7gD2j5NzGMEVx4MJrk5/DpgarptHcM+M5u+ZSDAnfuPyZcAH4d+zF/AhMCJc58D54fNc4B/A4HD5AoIr+AEGxnzefwFXhs8fB/45fP7dmH31b8CPwufZQEHU/831iO7ROPmTSFpz921mdi/wPaAywbe96uHUCmb2PvD3sH0ZENuN85AHE7e9Z2YfEMw8+TngsJijkH4ERaMGeMXdV8XZ3lHAPHffGG7zfuAkgulA9sZcd98afsZbwH4EU8LXE0w8BzAGGAc8E0x9QzbBbKQA48zsv4BCIB+YE7YfD3wpfH4fcEP4/FXgj+HEdrPd/bW9zCtdiIqCZJJbgCUEM0I2qiPsBg0nBou9hWLsvDUNMcsN7P5vv/lcL04wn8yV7j4ndoWZTSQ4Uogn3tTt7RGbu55dWavcvT5mW2+6+2fjvP9ugiOU183sMoKjkUZ7zGvj7vMtmK79n4D7zGymu9/bsb+CZCqNKUjG8GASuIcIBm0brQZKwudnE3Sr7K3zzCwrHGcYBawg+HX97fDXM2Z2UDiLbWteBk42s0HhQPBFwPNtvGc7UNCOzCuAwWb22TBfrpkdEq4rANaF2S+Jec+LBDMHE9tuZvsBG9z99wQznh7ZjjzSRagoSKb5NcHMp41+T/BF/ApwDC3/im/NCoIv76cIZpqsAv4AvAUsMbPlwP/QxpF12FU1nWAK5teBJe7e1vTLbwB14aDwHgPprWyrhmCa5xvM7HWCWTKPC1f/O0GBegZ4J+Zt0whu4vQqQXdYo4nAa2a2lKB76dZEc0jXo1lSRUSkiY4URESkiYqCiIg0UVEQEZEmKgoiItJERUFERJqoKIiISBMVBRERafL/+FYOVDKrcbMAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Previously-collected {number_of_threads: KHz} data\n",
    "T = {1:    9.760,  5:  46.362, 10:  81.680, 15:   97.457, 20: 115.467, 25: 116.169, \n",
    "     26: 118.546, 27: 118.524, 28: 116.736, 29: 116.013, 30: 115.467, 35: 113.780}\n",
    "\n",
    "plt.plot(list(T), list(T.values()), 'o:'); plt.grid()\n",
    "plt.xlabel('Number of threads'); plt.ylabel('KHz: 1000 Puzzles / second');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It looks like there is a plateau between 20 and 30 threads: they all have about the same throughput, with  a slight peak at 26 or 27 threads. Why doesn't throughput start to go down after 20 threads? The program works by dividing up the puzzles into fixed-size shards and handing a shard to each thread. If it happens that one thread gets a particularly easy shard of puzzles, then it will terminate early. With 20 threads, that would mean that part of the CPU would become idle with no more work to do. With a few more than 20 threads, there would be an extra thread ready to be swapped in when the easy thread(s) terminate early. Apparently the advantage of that outweights the disadvantage of having to swap some threads in and out. Of course, the computer is also running a few threads to keep the Jupyter notebook, the browser, the display, the network, and other things up and running."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Effect of Naked Pairs Strategy\n",
    "\n",
    "The Java program explicitly uses the [naked pairs strategy](https://www.learn-sudoku.com/naked-pairs.html) to eliminate some possible digits, whereas the Python program would have to make guesses to get the same solution. We can check how much the naked pairs strategy helps by disabling it with the `-nonaked` option:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Puzzles   μsec     KHz Threads Backtracks Name\n",
      "======= ====== ======= ======= ========== ====\n",
      "1000000    9.1 109.824      26       30.7 sudoku.txt\n",
      "1000000   14.3  70.025      26       94.9 sudoku.txt\n"
     ]
    }
   ],
   "source": [
    "!java Sudoku -r -R2 sudoku.txt -nonaked sudoku.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It makes a noticable difference: throughput decreases from 110 KHz to 70 KHz without it. Perhaps implementing [other strategies](https://bestofsudoku.com/sudoku-strategy) could give similar speedups. However, my feeling is that the program is already fast enough, and there would probably be diminishing returns from further strategies."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hardest(?) Puzzles\n",
    "\n",
    "Here is a collection of 10 puzzles that have been nominated as \"hardest\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.\n",
      "..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..\n",
      "12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4\n",
      "...57..3.1......2.7...234......8...4..7..4...49....6.5.42...3.....7..9....18.....\n",
      "1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..\n",
      "1...34.8....8..5....4.6..21.18......3..1.2..6......81.52..7.9....6..9....9.64...2\n",
      "...92......68.3...19..7...623..4.1....1...7....8.3..297...8..91...5.72......64...\n",
      ".6.5.4.3.1...9...8.........9...5...6.4.6.2.7.7...4...5.........4...8...1.5.2.3.4.\n",
      "7.....4...2..7..8...3..8.799..5..3...6..2..9...1.97..6...3..9...3..4..6...9..1.35\n",
      "....7..2.8.......6.1.2.5...9.54....8.........3....85.1...3.2.8.4.......9.7..6....\n"
     ]
    }
   ],
   "source": [
    "!cat hardest.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can compare performance of these puzzles with the benchmark puzzles. To keep things fair, use 20 threads for both (with reversed puzzles included, that's 20 \"hardest\" puzzles, so 1 per thread) and 500,000 total puzzles for both:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Puzzles   μsec     KHz Threads Backtracks Name\n",
      "======= ====== ======= ======= ========== ====\n",
      " 500000   14.0  71.562      20       10.4 hardest.txt\n",
      " 500000    9.0 111.215      20       31.4 sudoku.txt\n"
     ]
    }
   ],
   "source": [
    "!java Sudoku -r -T20 -R25000 hardest.txt -R1 sudoku.txt "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This suggests these puzzles are indeed harder than average, by roughly 50%. One interesting point  is that the number of backtracks is below average for the \"hardest\" puzzles. \n",
    "\n",
    "I can get timing and backtrack data for individual puzzles with the `-p` option:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Puzzles   μsec     KHz Threads Backtracks Name\n",
      "======= ====== ======= ======= ========== ====\n",
      "      1  598.9   1.670       1        1.0 Puzzle 1\n",
      "      1  172.2   5.807       1        6.0 Puzzle 2\n",
      "      1  212.7   4.702       1       13.0 Puzzle 3\n",
      "      1  182.9   5.467       1       12.0 Puzzle 4\n",
      "      1  109.1   9.170       1        0.0 Puzzle 5\n",
      "      1  172.3   5.803       1        8.0 Puzzle 6\n",
      "      1  194.5   5.142       1        6.0 Puzzle 7\n",
      "      1  213.2   4.690       1        9.0 Puzzle 8\n",
      "      1  265.2   3.771       1       11.0 Puzzle 9\n",
      "      1  631.3   1.584       1       79.0 Puzzle 10\n",
      "      1  147.9   6.763       1        1.0 Puzzle 11\n",
      "      1  110.4   9.057       1        0.0 Puzzle 12\n",
      "      1  113.8   8.788       1        0.0 Puzzle 13\n",
      "      1  125.1   7.996       1        3.0 Puzzle 14\n",
      "      1  125.2   7.987       1        1.0 Puzzle 15\n",
      "      1  120.3   8.309       1        0.0 Puzzle 16\n",
      "      1  126.0   7.938       1        2.0 Puzzle 17\n",
      "      1  104.1   9.609       1        0.0 Puzzle 18\n",
      "      1  201.5   4.963       1       10.0 Puzzle 19\n",
      "      1  425.1   2.352       1       48.0 Puzzle 20\n",
      "     20  559.5   1.787       1        0.0 hardest.txt\n"
     ]
    }
   ],
   "source": [
    "!java Sudoku -r -T1 -p hardest.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A few puzzles take about half a millisecond each; the other puzzles are faster. Overall, I think the claim of \"hardest\" is overblown."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Distribution of Puzzle Difficulty\n",
    "\n",
    "What's the distribution of puzzle run times across the benchmark puzzles? Of number of backtracks?\n",
    "\n",
    "I can get data  for individual puzzles with the `-p` option, then eliminate the header lines with `fgrep \".\"`, then [cut](https://linuxize.com/post/linux-cut-command/) out just the characters of each line that denote the μsec and Backtracks columns. The following line does that, but it is commented out for now because the output is already captured in `sudata.txt` and does not need to be generated again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!java Sudoku -T1 -r -nofile hardest.txt -p Sudoku.txt | fgrep \".\" | cut -c8-15 -c31-39 > sudata.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, load the data into a pandas dataframe and describe it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>μsec</th>\n",
       "      <th>backtracks</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>count</th>\n",
       "      <td>500000.000000</td>\n",
       "      <td>500000.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>mean</th>\n",
       "      <td>94.786948</td>\n",
       "      <td>32.050252</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>std</th>\n",
       "      <td>226.471924</td>\n",
       "      <td>152.089871</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>min</th>\n",
       "      <td>34.500000</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25%</th>\n",
       "      <td>43.500000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>50%</th>\n",
       "      <td>53.100000</td>\n",
       "      <td>4.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>75%</th>\n",
       "      <td>81.500000</td>\n",
       "      <td>18.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>max</th>\n",
       "      <td>22856.310000</td>\n",
       "      <td>8145.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                μsec     backtracks\n",
       "count  500000.000000  500000.000000\n",
       "mean       94.786948      32.050252\n",
       "std       226.471924     152.089871\n",
       "min        34.500000       0.000000\n",
       "25%        43.500000       1.000000\n",
       "50%        53.100000       4.000000\n",
       "75%        81.500000      18.000000\n",
       "max     22856.310000    8145.000000"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "sudata = pd.read_csv('sudata.txt', delim_whitespace=True, names=['μsec', 'backtracks'])\n",
    "sudata.describe()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The mean latency is a bit under 100 microseconds, the median is 53.1 microseconds, and the maximum is about 23,000 microseconds, or 1/40th of a second. For backtracks, the mean is 32, the median is only 4, and the maximum is over 8,000. \n",
    "\n",
    "It may help to look at a scatterplot:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYsAAAEGCAYAAACUzrmNAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deXxcZ3no8d8zo83aJVt2HNuyQrPVgdiWFW8BGhIIIaGYW+LghBYXnDhJs9De9kIClFBCIeltm0uWhogkbUITC2KgcSkFjJNASbxJ3rKR2BBZlm1s2VqsxdpmnvvHeWc8MxppRvKMNj/fz0efmXnnnDNnRtJ55n2fdxFVxRhjjBmKb6xPwBhjzPhnwcIYY0xCFiyMMcYkZMHCGGNMQhYsjDHGJJQx1ieQDtOmTdOKioqxPg1jjJlQ6urqjqlqWbznJmWwqKiooLa2dqxPwxhjJhQR2T/Yc9YMZYwxJiELFsYYYxKyYGGMMSYhCxbGGGMSsmBhjDEmIQsWxhhjErJgYSa9YFBpau/BZlg2ZuQm5TgLY0KCQeX672yhbn8Li+aWsO6mpfh8MtanZcyEYzULM6kd7+ylbn8L/UGlbn8Lxzt7x/qUjJmQ0hosROSvROR1EXlNRNaJSI6InCMiW0Vkr4h8T0Sy3LbZ7vE+93xFxHHuduVviciH03nOZnKZlp/ForklZPiERXNLmJafNdanZMyElLZmKBGZBdwJzFPVkyLyfWAVcDXwgKrWiMi3gTXAo+62RVXPFZFVwP3AJ0VkntvvIuBs4Bcicr6qBtJ17mbyEBHW3bSU4529TMvPQsSaoIwZiXQ3Q2UAU0QkA8gFDgOXA+vd808BH3f3V7jHuOevEO8/ewVQo6o9qvoOsA9YnObzNpOIzyeUFWRboDDmNKQtWKjqQeAfgQa8INEG1AGtqtrvNmsEZrn7s4ADbt9+t/3UyPI4+4SJyFoRqRWR2qamptS/IWOMOYOlLViISAlereAcvOajPOAjcTYN9WeM97VPhyiPLlCtVtUqVa0qK4s7w64xxpgRSmcz1AeBd1S1SVX7gB8Cy4Fi1ywFMBs45O43AnMA3PNFQHNkeZx9jDHGjIJ0BosGYKmI5LrcwxXAG8CLwLVum9XA8+7+BvcY9/wL6o2i2gCscr2lzgHOA7al8byNMcbESFtvKFXdKiLrgR1AP7ATqAb+C6gRka+7sifcLk8A3xWRfXg1ilXuOK+7nlRvuOPcZj2hjDFmdMlknAKhqqpKbaU8Y4wZHhGpU9WqeM/ZCG5jjDEJWbAw41IwqBxp6+boie7TngDQJhI05vTZRIJm3AkGlVXVW9hW3wzA4ooSatYuG9EEgDaRoDGpYTULM+4c7+ylrqEl/Ph0JgC0iQSNSQ0LFmbcCU3+F3I6EwDaRILGpIb1hjLjUijPIMJpz+sUDKpNJGhMEobqDWU5CzMu+XzCjKKclB2rrCA7Jccy5kxlzVBmUrGeT8akh9UszKRhPZ+MSR+rWZhJw3o+GZM+FizMuDPSpiTr+WRM+lgzlBlXTqcpaaRLqFpvKWMSs2BhxpV4TUnD6ck03J5PlucwJjnWDGXGldFuSrI8hzHJsZqFGVdG2pQ0UqHgFKpZWJ7DmPjSFixE5ALgexFF7wK+AjztyiuAeuA6VW1xq+l9C7ga6AL+XFV3uGOtBr7sjvN1VX0qXedtxkZk3mCopqRU5xdGOzgZM1GlrRlKVd9S1QWqugBYhBcAfgTcBWxS1fOATe4xwEfwlkw9D1gLPAogIqXAPcASYDFwj4iUYCaNUN5g2Tc3sap6C8Fg/F5Q/f1BPvHtV1iaYLtErxXb0yoUnCxQGDO40cpZXAH8VlX3AyuAUM3gKeDj7v4K4Gn1bAGKRWQm8GFgo6o2q2oLsBG4apTO24yCZPIGwaByXfVmdja0EggqtSPILyQblIwxA41WsFgFrHP3Z6jqYQB3O92VzwIOROzT6MoGK48iImtFpFZEapuamlJ8+iadkklqH+/sZfeB1vDji2cXDTu/EBmUauubeftIu00LYkyS0h4sRCQL+BjwXKJN45TpEOXRBarVqlqlqlVlZWXDP1EzZkJ5g813X0HN2qVxm4Om5WdRVVGKX6CyvJjn1i7lWEfvsC72oaDkF8jNzuCah35tNQxjkjQavaE+AuxQ1SPu8RERmamqh10z01FX3gjMidhvNnDIlV8WU/5SWs/YjLpE4yMiE9GluZlRYyOevXEpLSf7EiaoQ8d4+0g71zz0awIjHMthzJloNJqhrudUExTABmC1u78aeD6i/NPiWQq0uWaqnwFXikiJS2xf6crMGSYUUI519rKtvoWAwrb6Fq597JW4eYjBktkXnFVAlU0LYsywpLVmISK5wIeAmyOK7wO+LyJrgAZgpSv/CV632X14Pac+A6CqzSJyL7Ddbfc1VW1O53mb8S227rCnsY2gElVL6O8Pcl31ZnY1tLKgvJjnbl6G3+99N4rtLqsKxzp6rOusMUNIa7BQ1S5gakzZcbzeUbHbKnDbIMd5EngyHedoJp6ygmwWV5RS19DCovJiAHY0tIZrCcGgstL1nAo9d+1jm3lu7bJwc1WolmLTfRiTHBvBbSYcEaFmbXTNIHJQ3bGOHvY0tkXts/tAKyurN7OnsY2LZxex3tU0TncuKmPOFDY3lJmQIgfSxQ6qm5afRdXcEvw+IS/bj09gwZxi9jS2EQgqOxtaWfnYZoJBtWnNjUmS1SzMpBPbc6q5q4+peZl84tunmqZ2H2gN1yJsug9jErOahRnXklkIaagpPPx+H2UF2fh8PtbfvIzK8mL8AlUVpeFahE33YUxiVrMw41YyyefhJKj9fh/rb1lutQhjRsBqFmbcSmbOqOGuR2G1CGNGxoKFGbeSST6PNEE90nW+jTlTyWT8Z6mqqtLa2tqxPg0zhGTXpUhmu+GucWFjK4yJT0TqVLUq3nOWszCjbjgX62TW1B7uuts2tsKY4bNmKDPqmtp7qB3Dda9tbIUxw2c1CzOqgkHljnU7CLgJ/yrLE1+sR9pkFQwqTR09CEQltW0pVWOGz4KFGVXHO3vZ4QbG+QUevmFhwgAwVJNVKECU5mZyw+Nbw9s9s2YJNzy+hW31LQAsriilZu2pfYfbdGXMmc6ChRlVoSag0EU90QV7qPxCKJDU1jcz7+xC3jjcHl6jYl9TB3X7W8LHqWuw3IQxp8OChRlVw50ePBRcauubuXh2EVPzMsPPHe/spba+mYDCqwdPkJftp7svyKK5JZw/I59Fc0vCNQvLTRhzeqzrrBkz/f3B8EywVUP0ihpsO1XlE4++Em7W8gn85M73ccFZBUPmLIwx8Q3VdTatvaFEpFhE1ovIb0TkTRFZJiKlIrJRRPa62xK3rYjIgyKyT0T2iEhlxHFWu+33isjqwV/RTBTBoHKdW3MiEFRqh+gV1XKyj1fdjLGRvadEhOduXsbC8mL8PuGSitJwoAAvLzGjMIfphTkWKIw5TeluhvoW8FNVvVZEsoBc4IvAJlW9T0TuAu4CvoC3Vvd57mcJ8CiwRERKgXuAKkCBOhHZoKotA1/OTBTHO3vZfaA1/Pji2UWDNhPF5jkit/P7ffzA5nsyJu3SFixEpBB4P/DnAKraC/SKyArgMrfZU8BLeMFiBfC0WzFvi6uVzHTbbgwtpSoiG4GriF7X20ww0/KzqKoopba+mflzill/y7JBL/SJurpazyZj0i+dNYt3AU3Av4rIfKAO+BwwQ1UPA6jqYRGZ7rafBRyI2L/RlQ1WHkVE1gJrAcrLy1P7TkzKDXesQ+QyqLZetjGjL505iwygEnhUVRcCnXhNToOJ95+vQ5RHF6hWq2qVqlaVlZWN5HzNKBvuDLChrrLLvrmJVdVbCAYnX+cMY8ardAaLRqBRVbe6x+vxgscR17yEuz0asf2ciP1nA4eGKDcTXGjm10AgmNQMsMOdjtwYkzppa4ZS1d+LyAERuUBV3wKuAN5wP6uB+9zt826XDcDtIlKDl+Buc81UPwO+Eeo1BVwJ3J2u8zapkWiKjvCAuv0t5Gb56erpp6qidMhJBYdKdBtj0ivdvaHuAJ5xPaF+B3wGrzbzfRFZAzQAK922PwGuBvYBXW5bVLVZRO4FtrvtvhZKdpvxKZlZZUO1hEBQae/uB6B2fwvHOnqYXpgT97g2p5MxYyetwUJVd+F1eY11RZxtFbhtkOM8CTyZ2rMz6RI5srq2vjnuNBvhkdn7W8jN9NPe008gqKz9bi3PrV1Ga3e/9XwyZhyx6T5MypXmZpKbnUF7dz+52RmU5mYO2CaylhAIBll+3wsEFXYdaGP+vT+nuzdIVUUJNWuX2cJExowDtp6FSbnmrj66egMAdPUGaO7qi7tdqJYwozCH+XOKw+VdvUGCwLb6Fpo6ekbjlI0xCViwMCk3LT+LKre4UNXcEkpzM4fs7SQirL95GZXlxQP6SVudwpjxwZqhTMpFNjHFrjMxWG8nv9/H+luWc6yjh9uf3UFdQ2tSU5gbY0aHBQuTcv39QfY1dXD+jHyOd/YlXO86spvt9MIcatYuO+0eT8murmeMSY4FC5NS/f1BFn59I+3d/RTkZLDjSx8ccmzEYN1sT6dGkUzXXWPM8FiwMCm1r6kjPG6ivbuf3x7rHHJsxFAr4Y1UOo5pzJnOEtwmpc6fkU9BjvcdpCAng/Nn5EfNARUMKkdOdHP0RDeBQBBVpdIlw2NrHqHpQIa7QFdoDEe8YxpjRsZWyjMpF5mz8PlOfR8JBpVV1ZvDS50WZGfQ1dvPorklPHR9JdPys2ju6gsvt3o6TUmWszBm+IZaKc+aoUzKZWT4uHBm4YDyUPNQSHuP11wVWhY1stfUg6sWnlZTko30Nia1rBnKjJpQ81BIfpYfH3jjK4RwcKitbwbUmpKMGUesZmFGjYjw7I1LWfnYK+w60AYC4hMQYWpeFpXlxWyrbyGgcEfNLp5ds4SWk33WlGTMOGA1CzOqWk728erBEyjQ0RMgEFR27G+huauPh66vxO/yEjv2t9Bysm9YiyMZY9LHgoVJm8jeTKH7U/MyWTS3BL94vaX8Ec1M0wuzw9OEWNOTMeOLNUOZlAr1Qoqc5qOyvARQdrgpPJ5xzUuluZnh3k+h2oOtV2HM+JTWYCEi9UA7EAD6VbVKREqB7wEVQD1wnaq2iHdl+BbeAkhdwJ+r6g53nNXAl91hv66qT6XzvM3IRI6cfs+sQnY3thFUqGtoAVUC6iWxQ81LwIAeS5G9mIbb/dW6yxqTPqPRDPUBVV0Q0Xf3LmCTqp4HbHKPAT4CnOd+1gKPArjgcg/eUquLgXsillg140jkyOmdB7xAAV5vp+H2bAoFnmXf3MSq6i0Eg0OPBxru9saY4UmqZiEiK4Gfqmq7iHwZqMT7hr9jBK+5ArjM3X8KeAn4git/2q2Yt0VEikVkptt2Y2gpVRHZCFwFrBvBa5s0mpZ/qkdTiN8nPHJDJdPys4f1rf94Zy/b65sJKmwfZLW92O1tig9j0ifZmsXfukDxXuDDeBf5R5PYT4Gfi0idiKx1ZTNU9TCAu53uymcBByL2bXRlg5WbcUZEeOj6SiIHWl88u4iyguyoKT9C4iXAQzMKFOdkhNeyEPd4KDbFhzHplWzOIuBurwEeVdXnReSrSex3qaoeEpHpwEYR+c0Q28b7uqlDlEfv7AWjtQDl5eVJnJpJh+mF2VxSUUptfTPz5xSz/pZlcWsSkfmN2AT4upuW8vbRDgLutxxQ2NvUwbyziwZ93cg1NCxnYUzqJRssDorIY8AHgftFJJskaiWqesjdHhWRH+HlHI6IyExVPeyamY66zRuBORG7zwYOufLLYspfivNa1UA1eHNDJfm+TIole9GOajaKSYA3dfTwxR/ujtq+JM463rFsig9j0ifZZqjrgJ8BV6lqK1AK/J+hdhCRPBEpCN0HrgReAzYAq91mq4Hn3f0NwKfFsxRoc81UPwOuFJESl9i+0pWZMZJoNth4TU6xYpuNIu8L8OrB9qjt/T4bEmTMWEq2ZnG9qj4ReuBqBZ8Dfj7EPjOAH7kLRgbwrKr+VES2A98XkTVAA7DSbf8TvG6z+/C6zn7GvVaziNwLbHfbfS2U7Dajb6iFhYbTdTW2BqJK+D5AVUVJOFG+uMKWVzVmrCUbLK4VkW5VfQZARP4FGPK/V1V/B8yPU34cuCJOuQK3DXKsJ4EnkzxXk0aD9Toayep0kc1GItFjLmrWLqOpoweBqFqKjaUwZmwkGyz+BNggIkG88RDNqvoX6TstM16Fmo9il0lNdddVn0+YUZgTVWbLpRozdoYMFm5AXMiNwH8ALwNfE5FSaw46M8R+m4+XwI4NIqW5mTS196S0BmBjKYwZO4lqFnWc6r4aur3G/SjwrrSenRlzg32bj71IRwaRyHmhBqsBRAagyHxFMknx2FqNMSb9hgwWqnrOaJ2IGZ+G820+FESa2nuorW8moFAbZ/R1ojEWgzUt2VgKY8ZOUv0RReQ2ESmOeFwiIpazOAMMZ2R0qEttyZQMcrO97yFTsvwEg8GobraxYyxig9FQkumWa4xJvWQT3Dep6iOhB26W2JuAf0nPaZmxEpufSPbbfGRt4eLZRXT1eoP+O3oCLL//Raoiag2RzUmVc0tAT9Us0pHrMMacvmSDhU9ExHVvRUT8gDUYTyKhWsEd63YMaBIaamR0KLioariGsPtAKxfPKWZ3QytBIODW1X77SDsXnFUQd4xFU3sPinL941vZ4ZqnHrphIdOtFmHMuCCDjcKN2kjk/+KtP/FtvMT2LcABVf3rtJ7dCFVVVWltbe1Yn8aEEaoV1O5vIeCm9s7wCZvvvmLItSWicg8xNYR//+xirqvews4DrQAUZGfQ1ReIqmEMeH2X5wjxC1RVlFoXWWNGiYjURSwnESXZmsUXgJuBW/F6RP0ceDw1p2fGWiiHEAoUfiEqP9HfH+S66s3sPtAadfGOzD3s2N/Cy1+4PNzMdKyjl1cPtgHgE+jq89bbjpckD7++CxR+EQIRc0VZF1ljxl5SCW5VDarqo6p6rap+QlUfU9VA4j3NRBCZxF5cUcrmu6+gZu1SRIRgUFlZvZkdDa3h3k1NHT1R62mHkt/TC7PDyefQMf0+4eLZRSwqLx40SR79+iW8ctcHWFxh040bM54k2wx1HvBNYB4QHlarquNynIU1Qw3fYNNoNLX3sOQbvwiverdwThGZGX52uLEOofW0Y5unjnf2UpyTwSe/s4XdB7ymqYeur2R6YXbccRWxr2/Tehgz+lLRDPWveEubPgB8AG+SP/sPnkQGS2KX5maSl51Be3c/edl+Hv1UJe/9h5fCXV0j19Pu7w/y9tF27tnwOjsbWnnP7CL2HPBqJDsaWvH5BFUGDPIDopLdxzq83lDW9GTM+JFssJiiqptcj6j9wFdF5H/wAoiZxJq7+sLdYLv7gvh8vgGjqINB5fCJk1z5wK/o7DnVOrmnsY0LZxbw5uF2Fs4pQlU51tETNa6iqaOHO9ftHPYAPWPM6Eo2WHSLiA/YKyK3Awc5tRyqmcSm5WdRFREcygqyB3R7XVW9OWrdbfCS2lMyfbx+yFuX4je/72DZNzdRWV7Ce2YVsedgW3jtisEWQbLEtjHjR7LB4i+BXOBO4F68pqjVQ+5hJpTBcgTxBuVFTiceqilEysvy89zNS7nmoZfDZe09/QBs39+CD1hQXsyzNy7B55LY8brfWmLbmPEjYbBwA/CuU9X/A3TgFiUyk0eiqb+HGpQX6skUqlm8++xCnr9tOT6fj/lzith1oO3UcYCg+9nT2EZzV1/cmoolto0Zf5JZRzsALJIR/ueKiF9EdorIj93jc0Rkq4jsFZHviUiWK892j/e55ysijnG3K39LRD48kvMwnnhLosabLDDZ/UWEmrXL2PrFK9j2xSv4zzvei9/vR0T4wS3LWTinCB9wydxiNt99edwusZHzPdncT8aMT8k2Q+0EnheR54DOUKGq/jCJfT8HvAkUusf3Aw+oao2IfBtYAzzqbltU9VwRWeW2+6SIzANWARcBZwO/EJHzbZzH4AZrUgoGlVXVW6hraKGyvJiHXVfWqLmayktQVVR1wAV7sBpIvIWKAPx+Hz+49dKoc6lZu8xqDsZMQEkNygNKgePA5cAfu5+PJtpJRGbjrX3xuHss7hjr3SZPAR9391e4x7jnr3DbrwBqVLVHVd/BW6N7cZLnfcYJXdCXfXMTq6q30N8fDNcEmtp72FbfTCCobK9vYfn9L/DJxzbz5uETfPczl7Dh9ktRDbL8vhcG7AvDq4GExNYUrOZgzMSUbM3icVV9ObJARC5NYr//B3weKHCPpwKtqtrvHjcCs9z9WcABAFXtF5E2t/0sYEvEMSP3iTyftcBagPLy8iRObXKKvKDX1jezsnozrza2UVlezFc+Oi9q20BQ2VbfwtUP/hqfeE1KoSk/auubWfnY5nCvpZqbloZrILX1zVw8u4ipeZles1TMWtmhpqpQItwCgzETX7LB4iGgMomyMBH5KHBUVetE5LJQcZxNNcFzQ+1zqkC1GqgGbwT3YOc12UU2KV08u4jdjW3hoPCxR14edL+gAhF5jHln5YcnAdz2TjNN7d3MKJrCM2uWsLJ6M7sb21hVvRXVINv3e9strijl2RuXcMPjW9lW3+zKSqhZu8zGSxgzwSVag3sZsBwoE5H/HfFUIeBPcOxLgY+JyNV4U4QU4tU0ikUkw9UuZgOH3PaNwBygUUQygCKgOaI8JHIfEyOyq+vUvExWVW9he30LCuEpOwBy/NA9RNZnb1Nn1OO1T9dS/elLEIFXXQCqa2hBIw5au7+Z7fXN3niJcFkLxzp6mB4np2GMmTgS5SyygHy8oFIQ8XMCuHaoHVX1blWdraoVeAnqF1T1U8CLEfuuBp539zdwauzGtW57deWrXG+pc4DzgG1Jv8Mz0KmurgLIgKqZED9QRG7X3R9dOdt98ATL73+Bm79bx7vPLgjPTLtobngBRfKyM/jUE1vJzTr1PSKosPa7tQQCwdN9W8aYMZRoDe5fAr8UkaddcjlMRC4Z4Wt+AagRka/j9bJ6wpU/AXxXRPbh1ShWuXN4XUS+D7wB9AO3WU+owUX2hDre2cuOhhZiL9Px2uh8wP98/jJufmYHrx08QW6mj66+6D0DQQ03Tc2fXci6G5cgIjR19NDc0cNHH36ZoEJXTz/P3LiYP318GwrsOtDGysc2s/6W5dYcZcwElWxvqPUiEk4qi8j7gSeTfRFVfUlVP+ru/05VF6vquaq6UlV7XHm3e3yue/53Efv/var+gapeoKr/nezrnmlie0KV5mZGTf29YE4RPvHWqwBvSo6QqooSzi7J5T9uvZSF5cV09wfJy/LjHyQ5vbvxBG8daUcEZhTmcOHMQqrca1VVlLLsXVNZUH6q1rH7QGtSvaeMMeNTsgnuW4D/EJE/xktqfwO4Om1nZYY0WG+j2K6tzV19PLNmCfuaOjh/Rj7gLVhUmOXnE9Wbef3gCd59diGP/WklmRn+8DF2H2glqHCyN8B/3fle7tnwOrX1LeTE1DY++tCvuSRiMaTYaUHW37yMlY+dWjTJpu8wZuJKKlio6nYRuRNvhbxu4EOq2pTWMzNxhQbWxettFNkTatHcEkpzM7nh8a3hx8+sWQJAS3cfbxw8gQKvHTrBh7/1P5zsDVBZXkJvfyCcCM/LzuD8GQXhgXQlUzJY+dgW9jS2EVAlqF4C20umZw0YbOf3+1h/y3IbhGfMJJCoN9R/Et3EnQu0AU+ICKr6sXSenBnoeGdvVG+jyNlZYyf9O9YRMeZifwvXVW9mV0MrOZm+qDxGh5tWfHvMhIBdvQGOdfTg8/kozc2kuauP9bcs4+iJbq544Jd09QaZkumjINPHtd9+ZcCyqzD0vFLGmIkjUc3iH0flLEzSwhP3vePVLGJnZ428OJfmZnpjLQ60cvHsInY1tBKEqKYkAfKy/XT2BAYkvgOqXPHPv+RkX5DcLD9dPf0smltCX0Dp6vWO0dEToPIbm8JrXtTWN9vU4sZMQsn0hsJ1WT2sqt3u8RRgRvpPz8QSEWpuWppwhLSX7N7K7sY2Lp5dzHNrl3Jd9RZ2NLRGbTdvZj5TsjLZ0dBCbqafzt7ojmahWkd7tzfovtaN2YjUFbHP/DnFlpswZhJKtjfUcxDVchFwZWYM+HzCjKIcphfmxJ3sr6m9h6b27vA8UDsPtHK8s4/nbl7GgjlFUdu/friD2v0tBBU6ewNcMCMPn0BBTkb41u8T8tzYidzsjHCwyMvy4/dJeNuF5cWsv2WZ5SaMmYSS7Q2Voarhfo+q2huaWtyMH17yezN1+1t4z6zCmGcVv9/HD2+9lKPt3dz673XsaWzjD2cW8JpbzQ7grSOdVJYX872bltLa3U9xTgbXVW9mp1uXosMtYuT3CZv++o/wR+QzLIltzOSVbM2iSUTCyWwRWQEcS88pmZFq6uhhW30LAYVdjSeYHxEwbn92J0dOdKOq+H1eL6UtX/wgP7p1OXlZ0X8GexrbaD7ZB3gJ9Z0RCxiBFyiq5pYwozCHsoJs/H6fTRhozCQ3nHEWz4jIw3g50QPAp9N2VmZEYi/V3/iT9/Cxh18moF5Pp2Xf2EReTgZdvQGqXFfaTz2xlZN9QS6aWUCGD1471E5leTF3rNvJjv0tvPvs6BrKe2bm8cRnllpwMOYMk1TNQlV/q6pLgXnAPFVdrqr70ntqZrjKCrJZXFESfvzV/3yDRXNL8LturEG8RHUgqGx/p5m9R9upc/mK1w+389qhDi6eXcw9H7so3OV2z8HoWsVd11wUN1dijJncJHJ5zSE3FLkGb7W68PShqvq1NJ3XaamqqtLa2tqxPo0xceREN8u/uYmAQoZPePkLl6Mot3y3jl2N0Rf+S+aWIOL1cIrsvSBAvquBLCovDj/vF3j761fh9yeacNgYMxGJSJ2qVsV7LqlmKLf8aS7wAbxV767FZn4dE/39wfD0HT6fVzGMnDywdEomf3h2IW8ebqfSjcG44fGtvHroxIBjbd/fwiuf/wBt3X185MFfh8sVbzLA/7rzfVxwVgF9fUHqGlqomltMc1c/pbkyIKEdOgdLdhszOSWbs1iuqheLyB5V/V6TMWoAAB0PSURBVDsR+ScgmfW3TQr19wdZ+PWNtHf3U5CTwc4vfwifT8LrYi+cU8ybv28P91jq7+vjaHsPtfXNBAapQDZ39TKtIJv8bH94TAV4g/0uOKsAESEry8+Sd03l+u9soba+mdzsU3mPdTctBRj0OZtl1pjJIdlgcdLddonI2XjrcZ+TnlMy8QSDyvb65vDguPbufvY1dTA1P/vU5IENLVELHO1obGfNU9vCgWJKhnAyZp2Kv6rZwb5jJ6MG2vkEHr6hMqpm0NRxKuiEB+i5hY1EhLr9LVHPRU5DYoyZ+JLtOvtjESkG/gGoA+qBmnSdlIkWmnr8U49vDU8vXpCTwblleagqleXFZPiERXNLohYeAnjjcEf4/qzigavV7Y0JFABVc0soK8imvz/Ibw6foLu7jzX/tj0cdPKzve8YgaBy+7M7wlOh+yMG8cVOQ2KMmdiSrVn8I3Ar8D5gM/A/wKND7SAiOcCvgGz3OutV9R43dUgNUArsAP7MDfLLBp4GFuHVXD6pqvXuWHcDa/BGjt+pqj8bzpucyIJB5e0j7dTWNxMEfArrblzCovJibwbYg20sKi/m5bsuZ3pBNn19AeZ/7ecDahAA+46dHPgCzkVnF/Dk6ksQ8eaWCgQ03OQVa92Ni/n4v7xCQGFHQyvNXX3hCQwtZ2HM5JRszeIpvJ5QDwIPAX+Id2EfSg9wuarOBxYAV4nIUuB+4AFVPQ9owQsCuNsWVT0XeMBth4jMw1s17yLgKuBfROSM6I4TqlFc89Cvyc3OwC9wyTmlLD6nlE9+Zws7D7QSCCrb6lsIBoIc6+glM9PPi3/zgaR/seBNJLjhtkuZUTQl3C12X1NH3EAB8LfPvx5eVCk0FXoowW4D9IyZnJKtWVzgLvohL4rI7qF2cOtnh9pAMt2PApcDN7jyp4Cv4tVSVrj7AOuBh8W74qwAatyKeu+4ZVcX49VwJrXQYkaBoNLVGwj3TjrW0cvumFHVH3zAmx12/uxiHr5hAfNmFfLawYE9oCI9veYSpuVmceHMwnDPqpDzZ+STm+ULzy4b6dVDJ3jlC5fj88mANTMsqW3M5JTsF9CdrlYAgIgsAV5OtJOI+EVkF3AU2Aj8FmhV1dBX1kYgtFzrLLyR4bjn24CpkeVx9ol8rbUiUisitU1NE29dptAEgJHjXkpzM3nP7KLw9Bqh3knT8rOoihh8B9DZGySosPNAK5fe/9KAQJEdUxfzC/z5k9v5ux+/ycCx3+Dz+dj15Q+FcyC5WX4WzC4Mn8v0wmzKCrJp7uqLWp3Plk41ZnJKtPjRq3i1gUzg0yLS4B7PBd5IdHBVDQALXHL8R3jNVwM2C73cIM8NVh77WtVANXiD8hKd23gSWv2ursH7dl7juqPe8PhW9hxoZf6cYp69cUm4aUdEqFm7jKPt3dzy73XsOtBGbsySp7FiZh4PJ6uH6rWUlZXBnq9cOWBZ1sh8ROzqfJbUNmZyStQM9dFUvIiqtorIS8BSoFhEMlztYTZwyG3WCMwBGkUkAygCmiPKQyL3mRSa2nvCy6Rue6eZpvYefL5T3VH3NLbR3NUXdUH3+YTpBTlk+b3KYVdfcMiAERs9c7N8dPcGE17gMzJ8XDjz1PxQsUEldnU+y1UYMzkN2QylqvuH+hlqXxEpczWK0GJJHwTeBF7EGwEOsBp43t3f4B7jnn/B5T02AKtEJNv1pDqPSTZ6PPb6KnLqG3tkEvnIiW4Ot3Tx+sFWjrSd5FhHD7URS6EOVbOI5BPo6Vfmlxfz9J9fwlu/bycYTG7fuMdzq/NZoDBm8ko2wT0SM4GnXM8lH/B9Vf2xiLwB1IjI14GdwBNu+yeA77oEdjNeDyhU9XUR+T5es1c/cJtr3po0QhMAhppyQhfeZ9Ys4e2j7ZTmZrKqejPb90evcnfJ3GJvudSYZHciQQVU2dPYRuU3fkFnTyA8IjwjYzj9qIwxZ4qkJxKcSCbiRIKR8zuJSHgho231LYPuI8CP77iUL/3otfAkgT7xgkGWQO8gv9q8LD/d/UHmzSzg1YhE+E8/976oJidjzJllqIkE7WvkOBHblHO8s5faIQIFeBf9jz3yCoqS7X6Toek+YgPFRTML+PXnL2PhnCJO9gaYP7uIH96yjHzXTSovy0dJbma4N1a83lnGmDNXOpuhzGkozc0kLzuD9p5TA+MumJ7L439WxYneAEFV/vjhVwDY3Tj0eArATTAYYE9jG0Fg94FWmk/2M29mIbX1LfjEx/L7X4xaFMnGThhjQqxmMU41d/XR1RedmnnraBdXPfwy55UV8JXnE/ZcjjJ/dhGFOX5yMt24iewMUGVHQ6u3KFLPqUWR9jV12NgJY0wUCxbjTKj5Z2peJlVulbvIL/WdPQHqGloGrGAXEu/7/7tnFeIXYfn9L9HpBlx09QYQ8XpaRe4jAu+amhvVE8vGThhjrBlqHAnNBVVb38z8OcWsW7OET1RvjhqN7ROYVZI9aC4htvTCs/J54tNVLL//xajyi2cXUVaQzTNrlrDxjSPc+uwOwBus97vjXTZ2whgTxYLFOOIltZvDs7l+onozb8SscBdUeP///VVSx8vxwz+tnB8es7HtHW/g38I5RfzglmWowqee2Mq2d5rDvagKcjLcKnxia1EYY8IsWIyB2G6yoTJVZd5Z+bzq1qB47eAJFs4pYs/BE+Rk+MJNSMmYd1Y++493cc1DL5Of7WfHlz5Ec1cvLV29nDc9n+OdfagqtfXNuGEXXHhWPj++/b0DJhU0xhgLFqMs1NQU2dMoGFRWVm9mT2MbgWB0Q1JPXz/BoHJWYTa/PdaV9Ov0B4N0uhHdHT0B3m5q594fvxm19Omi8mIunl3MzgPeYL+9RztpOdlPWcEZMQO8MWYY7CvkKAtNOx7qadTU3sN11ZvZ2dA6IFAAvPH7ThSGFSgA3j4avX3byT62RyyLGgh6PaEe/dNKFpYXh2eTtWS2MSYeq1mMsthZWkW8MQ/p5BP49JPbB/SUqiwvYUZhDj+4Zbkls40xQ7JgMcpiZ2kFqKoopba+mXlnF/L6oRPEqWCcltBcUJF8Ag/fsBARQWTgbLLGGBPJgsUYiO1pFAoeU/My+ZNHXxn2xIDxXDh9Cr85emrNbb9PyM30h0eEV1WUWoAwxiTNgsU44PMJU/OyaOrowT9wXafhHw94as0y7li3i7qGFirLi3nkhkqm5mVxrLMXAZtS3BgzLBYsxlAwqDR19IAqd6zbGV7s6HTNm1XI9MIcatYOHFg3ozCHYFA51mE5CmNM8ixYpEG8cRTxtkk0BflI5Pjh+b9YPmguIl7XXZsk0BiTSNq6zorIHBF5UUTeFJHXReRzrrxURDaKyF53W+LKRUQeFJF9IrJHRCojjrXabb9XRFYP9prjQehivOybm1hVvYXgINnqUBfaSH6BqvIi3n22N5fTSJw7owBVoam9h0AgOGCa8diuuzZJoDEmGekcZ9EP/LWq/iHe2tu3icg84C5gk6qeB2xyjwE+grdk6nnAWuBR8IILcA+wBFgM3BMKMOPRUBfj0CSBgUAQVWX+rFMLDeVl+fnBrUvpDyqvHzrBuWW5I3r91w+1s7J6M0u/uYkF925k6Td+ERW0YpdrtXEVxphkpK0ZSlUPA4fd/XYReROYBawALnObPQW8BHzBlT/t1t3eIiLFIjLTbbtRVZsBRGQjcBWwLl3nfjpix1GELsb9/cHw4LspmT5O9gWjUtmdvQE+/i9bwo/fOto5rNedkiF09ysLy4vZ7UaCt3d7PZ9q65s51tHD9MKcAV13LWdhzOSRTBP4SI1KzkJEKoCFwFZghgskqOphEZnuNpsFHIjYrdGVDVYe+xpr8WoklJeXp/YNDEPsxVgVjrZ3c8t368LTanS5aThO+7WAlz//R2RkZDA1L4vmrj6m5mVy/Xe2Uru/JdxVNqBw+7qd1Lj8hE0SaMzkk+58ZNqDhYjkAz8A/lJVTwwR7eI9oUOURxeoVgPV4K3BPbKzTY3Qxbi/P8jKx7xxE+k4oXs/diEzinJp7uoLl0UGq0AgyKX/8KI3tYdrErMgYczkFK8JPJX/72kNFiKSiRconlHVH7riIyIy09UqZgJHXXkjMCdi99nAIVd+WUz5S+k871QIBpVrH0vNALvB/O2G33DfT/fS0RtgSobQE1AWzS3he2uXUVbgrXlRFadJzBgz+QzWBJ4qaQsW4lUhngDeVNV/jnhqA7AauM/dPh9RfruI1OAls9tcQPkZ8I2IpPaVwN3pOu/TEWovLM3N5De/b09roACvetXhpi0/2e/VXbbXt3DkRDczi6dYfsKYM0i6/9/TWbO4FPgz4FUR2eXKvogXJL4vImuABmCle+4nwNXAPqAL+AyAqjaLyL3Adrfd10LJ7vEkcpW73KwMOty0GiGhpPZoaO3qZWbxFGDg1CLGmMkrnf/v6ewN9Wvi5xsAroizvQK3DXKsJ4EnU3d2qRdqLwwo4fmXQnKzfDx8/Xw++9TOtJ9HfnYGF5xVkPbXMcacWWwEd4qE2gu3v9NMZP3h/113MWWFOeSleT2hBz85n/NmFHDBWQW20p0xJuUsWKRIqL2wqb2by//pJTp7g0zJgL9+bk9K5nsail/gmotn4vfbCnfGmPSwYJFCPp8wo2gKu7/yYfY1dXC8s4dPPb4tra/5yA0LWFReYrUJY0xa2RUmDTIyfFw4s5Cl55QOmrQ5Hdl+b/GihXOK+LeX63nvP7w05DxUxpjkhKbkUbX/pVgWLNJIVcjJTH242PXlDzF/TjF7Dp5g+/5WmxTQmBRIdhLQM5UFizT6zZETnOxL/R/czoNt7DnQSsD9MfsFG3RnzGmyGZmHZjmLNAkGlb/9j9fScuwbHt9GXpafk30BquaW8uCqBbYmhTFxDGdivXSPgJ7oLFikSH9/kH1NHZw/Ix+fz8fxzl72NJ5I2+t19gZ499kFPLNmMX/65DZbzMiYGMOdWM9mPBiaBYsU6O8PsvDrG2nv7qcgO4Of/tX7OHmyl0CKk2QLZhexq/HUFCKvHWpnb1NHWicPM2a8SlRrGMnEejbjweAsZ5ECb/7+RHjtiPaefi6970U++K2XU/oaeVl+am5cwkUz86PKp+bZYkbmzJNMMtoW+kotq1mMUOhbTWGWnxWPpDYwxNPZG+Da6i28ebgjXLZwTjHTC3Os6mwmlWTyDMnUGqxZKbUsWIxAZFvoudPzGK0edq8dOsHCOUXsaWxj/pxi1t+yDBFBBKs6m0kh2TxDssloa1ZKHQsWIxD5rebtIx34hLQFjNg8xaOfWoTf77NvSmZSSjbPYLWG0Wc5ixGIbAu9pKKU7Xd9IOWvsWB2IVvvvpwf/sVyFleU4MMbsT29MJuygmz75zCT0nDyDKFag/0vjA6ZjMPaq6qqtLa2Nq2vEZmzuOCen6X8+AvmFPHDWy/F5xNvedbqzexpbKPKuseaSW44YyNMaolInapWxXsubTULEXlSRI6KyGsRZaUislFE9rrbElcuIvKgiOwTkT0iUhmxz2q3/V4RWZ2u801WaO6YUJ5gx4HWtLzOqwdPhEeQtpzs49XGNgI2svSMcKbPT2Q1hvEpnc1Q/wZcFVN2F7BJVc8DNrnHAB8BznM/a4FHwQsuwD14y6wuBu6JWF511MXrrlc5pyilr5GTIfh9QlVEFdy6AE5ukcHB5icy41U6V8r7lYhUxBSvAC5z958CXgK+4MqfdqvlbRGRYhGZ6bbdGFpGVUQ24gWgdek676EcPdFNbX0LAVVq97fw6sFWVlVvTtnxczN97P7Kh2jtDkRVwS2ZN3nF9v558PqFwxpIFjtzgDHpMtq9oWao6mEAVT0sItNd+SzgQMR2ja5ssPJR198f5IMP/DI8KjvLByseeSVlx39o1Xyufo+3gFFZ5sBfi3UBnJxie/8IJD0/UeTMAXnZfnZ9+UNkZtoCWCY9xstXkXhflXWI8oEHEFkrIrUiUtvU1JTSkwPY19RBR08g/Phkf2qbB+6s2c0Nj2+zZocJJBW5hdgmxrKCbNbdtJTNd19BzdqlQ9Yi9zV1hGcO6OwJ8CfffsX+fkzajHbN4oiIzHS1ipnAUVfeCMyJ2G42cMiVXxZT/lK8A6tqNVANXm+o1J42nFuWl9bxFArU1jfz9pF2LjirwJqaxrnI5qPK8mIeur6S6YXDT8rGa2JMdpDl+TPyycv20+m+xLxxuN3mBjNpM9o1iw1AqEfTauD5iPJPu15RS4E211z1M+BKESlxie0rXdmoaznZn/ILeG6WD78I+dkZ+IDc7AyueejXlticACKbj7bVt7D8/heifm/DqXUM1vsnNvEdezyfz8euL3+I98wqHNApwphUS1vNQkTW4dUKpolII16vpvuA74vIGqABWOk2/wlwNbAP6AI+A6CqzSJyL7Ddbfe1ULJ7tE3Lz6KyvJjt9S0pOd6/f7aKZX9QRnNXH6W5mew92sE1D/06qnusfUMcf0JjAKbmZbJobgm19c0EFAJBr9PDsY4epuVnD2tq7Nju2CISU3MpAZQdDa0DjpeZ6ef5295rnR9M2qWzN9T1gzx1RZxtFbhtkOM8CTyZwlMbEVXo7knN+IbcTB/nTi+ISlpfcFYBVbbwyrgWDCqrqrdQ1+D9jp5ds4Tmrl5uf3YH2+pbCASV25/dwUPXV1K7vyUqgEwvzBnymNvqve9AiytKqFm7LDrx3dACqgSUuF8krPODGQ3jJcE97jU2d/Lq4c7TPk5OhtDVF2TpfS/yycc2h5stQm3XySQ2zdhoau9hW30zgaCy7Z1mjnf2Mr0wh4duqMTvfl11Da0ENUiu65UUCCq3PbNj0GbF4529XjBwQsEgNvFt42zMWLOJBJPQ1dXH+//xl6d9nAvKcth3vCf8OPZbon1DHN9i47eq13xUlp/Forml4UDyF8/soKOnP7zdjgOtgzYrhoLCtne8mkUoGMQmvlWxpiYzpixYJBAMKh995H9O+zg+gadvXM4dNbsGXBjMxFBWkM3iipJwHuHOmp3hPMK3rl/Ae+97gYDippAvYtcBb7bgoX7PIkLNTUsH5Cwg+suDTUNvxpoFiwQOnzjJ746fPO3jzJ9dxPTCnEEvDGb8E5FwPkFVWX7fC+HBdH4RqipKwzmnZ29cwrHOXoTEv2efT5hRFD+nYcx4YcFiCP39QT5w/4unfZyLZuTyg1uXh/vQ24Vh4gp921fVqJHWocF0kU1FMwZJahszEVmwGMJrh1vpTcFwh39ds8zm7ZlkTmcwnTETkQWLIew/fvq9n5acU2oXkEnKOiSYM4kFiyH4CCTeaAibv3AZZxXnWl7CGDPhWbAYRG9vgDtqXh/x/m/93QfJzrZvncaYycEa0uMIBpVrvvXCiPd/+f+8zwKFMWZSsWARx8G2LvYeH9nUHgtmF3J2aUGKz8gYY8aWBYs4frp7/4j2u3BGHj/8i0stR2GMmXQsWMQIBpW//+k7w94vN9PHf935Pusia4yZlOzKFmPv79tGtN8Lf/1H+P22pKUxZnKyYBHjww++POx9Ljq7gBlFU9JwNsYYMz5YsIjQ2zv8cRV5WX423GZ5CmPM5DZhxlmIyFXAtwA/8Liq3pfq1zj/Kz8d1vY/vn05884usjyFMWbSmxDBQkT8wCPAh4BGYLuIbFDVN8bqnPbeeyWZmZlj9fLGGDOqJspX4sXAPlX9nar2AjXAirE4kQun5/Lbv7/KAoUx5owyIWoWwCzgQMTjRmBJ5AYishZYC1BeXp6Wk/jV/17OnLJiy08YY844E6VmEe/qHDV5uKpWq2qVqlaVlZWl9MX/19les1P59BILFMaYM9JECRaNwJyIx7OBQ6l+kfr7rhlQ9tItF/HAnddYs5Mx5ow2UZqhtgPnicg5wEFgFXBDOl4oXsAwxpgz3YQIFqraLyK3Az/D6zr7pKqOfP5wY4wxwzIhggWAqv4E+MlYn4cxxpyJJkrOwhhjzBiyYGGMMSYhCxbGGGMSsmBhjDEmIVHVxFtNMCLSBIxsuTuYBhxL4elMZPZZeOxzOMU+i1Mm42cxV1XjjmqelMHidIhIrapWjfV5jAf2WXjsczjFPotTzrTPwpqhjDHGJGTBwhhjTEIWLAaqHusTGEfss/DY53CKfRannFGfheUsjDHGJGQ1C2OMMQlZsDDGGJOQBYsIInKViLwlIvtE5K6xPp90EJF6EXlVRHaJSK0rKxWRjSKy192WuHIRkQfd57FHRCojjrPabb9XRFaP1fsZDhF5UkSOishrEWUpe+8issh9tvvcvuN2paxBPouvishB97exS0Sujnjubve+3hKRD0eUx/2fEZFzRGSr+4y+JyJZo/fukicic0TkRRF5U0ReF5HPufIz8u9iSKpqP17exg/8FngXkAXsBuaN9Xml4X3WA9Niyv4BuMvdvwu4392/GvhvvJUKlwJbXXkp8Dt3W+Lul4z1e0vivb8fqAReS8d7B7YBy9w+/w18ZKzf8zA/i68CfxNn23nu/yEbOMf9n/iH+p8Bvg+scve/Ddw61u95kM9hJlDp7hcAb7v3e0b+XQz1YzWLUxYD+1T1d6raC9QAK8b4nEbLCuApd/8p4OMR5U+rZwtQLCIzgQ8DG1W1WVVbgI3AVaN90sOlqr8CmmOKU/Le3XOFqrpZvSvE0xHHGncG+SwGswKoUdUeVX0H2If3/xL3f8Z9c74cWO/2j/xcxxVVPayqO9z9duBNYBZn6N/FUCxYnDILOBDxuNGVTTYK/FxE6kRkrSuboaqHwfvnAaa78sE+k8n0WaXqvc9y92PLJ5rbXfPKk6GmF4b/WUwFWlW1P6Z8XBORCmAhsBX7uxjAgsUp8doRJ2O/4ktVtRL4CHCbiLx/iG0H+0zOhM9quO99MnwmjwJ/ACwADgP/5Mon/WchIvnAD4C/VNUTQ20ap2xSfRaDsWBxSiMwJ+LxbODQGJ1L2qjqIXd7FPgRXlPCEVddxt0edZsP9plMps8qVe+90d2PLZ8wVPWIqgZUNQh8B+9vA4b/WRzDa57JiCkfl0QkEy9QPKOqP3TF9ncRw4LFKduB81wvjixgFbBhjM8ppUQkT0QKQveBK4HX8N5nqPfGauB5d38D8GnXA2Qp0Oaq5D8DrhSREtdUcaUrm4hS8t7dc+0istS12X864lgTQuji6PwvvL8N8D6LVSKSLSLnAOfhJW3j/s+4tvkXgWvd/pGf67jifldPAG+q6j9HPGV/F7HGOsM+nn7wejq8jdfD40tjfT5peH/vwuuxsht4PfQe8dqYNwF73W2pKxfgEfd5vApURRzrs3iJzn3AZ8b6vSX5/tfhNa/04X3jW5PK9w5U4V1gfws8jJshYTz+DPJZfNe91z14F8WZEdt/yb2vt4jozTPY/4z7W9vmPqPngOyxfs+DfA7vxWsW2gPscj9Xn6l/F0P92HQfxhhjErJmKGOMMQlZsDDGGJOQBQtjjDEJWbAwxhiTkAULY4wxCVmwMMYYk5AFC2OMMQlZsDAmBUSkImZtiL9x60PcKSJvuMn5atxzeW6ivu0islNEVrhyv4j8o1v7YI+I3DFW78eYWBmJNzHGnIa7gHNUtUdEil3Zl4AXVPWzrmybiPwCbyqIc4CFqtovIqVjdM7GDGA1C2PSaw/wjIj8KRCasvtK4C4R2QW8BOQA5cAHgW+rm9pbVZNdb8KYtLOahTGpEzkddaa7vQZvVbqPAX8rIhe57T6hqm9F7exNNGfz75hxyWoWxqTOXBEpExEfXoDwA3NU9UXg80AxkI83Q+kdobWYRWSh2//nwC2hqb2tGcqMJxYsjEmd43jLZtbhzTL6WWCziLwK7AQeUNVW4F68mscelxS/1+3/ONDgyncDN4zy+RszKJt11pgUcEty/lhV3z3Gp2JMWljNwhhjTEJWszDGGJOQ1SyMMcYkZMHCGGNMQhYsjDHGJGTBwhhjTEIWLIwxxiT0/wE2NQt1+mEujgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "sudata.plot.scatter(y='backtracks', x='μsec', marker='.');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Wow! That's unusual!** I expected the comet-tail-shaped cluster to the left, but I did ***not*** expect the small cluster of outlier points in the lower right corner (all with 10000+ μsec and 500—2000 backtracks).  \n",
    "\n",
    "Let's look at the outliers more closely:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYsAAAEHCAYAAABfkmooAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAeJ0lEQVR4nO3df5xddX3n8dd7kskQDJjJDxSSYLBE9yE+AuII1NhWoUJAl7jLj8XWEoGagqirXQUsbelCH/uQQOvCanFTSCVdFgRCm2xXixFUtj7kxwSS8MNiRkQyCZWQhB+RZJjJfPaP8x25mdy5507mnnvn5r6fj8d9zLmfc869n7nkzofv+f44igjMzMwqaWt0AmZmNv65WJiZWS4XCzMzy+ViYWZmuVwszMwsl4uFmZnlmljUC0uaA6wA3goMAssi4gZJ04BvAXOBZ4FzI2KHJAE3AGcArwGfjIhH02stBv40vfRfRsStld57xowZMXfu3Jr/TmZmB7K1a9e+GBEzy+1TUfMsJB0OHB4Rj0o6BFgLfAz4JLA9Ir4i6QqgMyIul3QG8FmyYnEicENEnJiKSzfQBUR6nfdGxI6R3rurqyu6u7sL+b3MzA5UktZGRFe5fYVdhoqI54daBhHxKvATYBawCBhqGdxKVkBI8RWReRCYmgrOacCaiNieCsQaYGFReZuZ2b7q0mchaS7wHuAh4C0R8TxkBQU4LB02C9hUclpvio0UNzOzOim8WEiaAqwEPh8Rr1Q6tEwsKsSHv88SSd2Surdu3bp/yZqZWVmFFgtJ7WSF4raIuCeFf5kuLw31a7yQ4r3AnJLTZwNbKsT3EhHLIqIrIrpmzizbP2NmZvupsGKRRjfdAvwkIv66ZNdqYHHaXgysKomfr8xJwMvpMtW9wKmSOiV1AqemmJmZ1UlhQ2eBBcAfAI9LWpdifwJ8BbhT0kXAc8A5ad+3yUZC9ZANnb0AICK2S7oGeCQdd3VEbC8wbzOzprRtZx+9O3Yxu3My06d01PS1Cxs620geOmtmrWbVus1cvnID7W1t9A8OsvSs+Zx53OjGAjVk6KyZmdXHtp19XL5yA7v7B3m1b4Dd/YNctnID23b21ew9XCzMzJpc745dtLft/ee8va2N3h27avYeLhZmZk1ududk+gcH94r1Dw4yu3Nyzd7DxcLMrMlNn9LB0rPmc1B7G4d0TOSg9jaWnjW/pp3cRY6GMjOzOjnzuFksOHpGYaOhXCzMzA4Q06d01LxIDPFlKDMzy+ViYWZmuVwszMwsl4uFmZnlcrEwM7NcLhZmZpbLxcLMzHK5WJiZWS4XCzMzy+ViYWZmuVwszMwsl4uFmZnlcrEwM7NcLhZmZpbLxcLMzHIVViwkLZf0gqQnSmLHSXpQ0jpJ3ZJOSHFJulFSj6QNko4vOWexpI3psbiofM3MbGRFtiy+CSwcFlsK/NeIOA748/Qc4HRgXnosAW4CkDQNuAo4ETgBuEpSZ4E5m5lZGYUVi4h4ANg+PAwcmrbfDGxJ24uAFZF5EJgq6XDgNGBNRGyPiB3AGvYtQGZmVrB631b188C9kq4nK1TvT/FZwKaS43pTbKS4mZnVUb07uC8BvhARc4AvALekuMocGxXi+5C0JPWDdG/durUmyZqZWabexWIxcE/avousHwKyFsOckuNmk12iGim+j4hYFhFdEdE1c+bMmiZtZtbq6l0stgC/k7ZPBjam7dXA+WlU1EnAyxHxPHAvcKqkztSxfWqKmZlZHRXWZyHpduCDwAxJvWSjmj4F3CBpIrCbbOQTwLeBM4Ae4DXgAoCI2C7pGuCRdNzVETG809zMzAqmiLJdAE2tq6sruru7G52GmVlTkbQ2IrrK7fMMbjMzy+ViYWZmuVwszMwsl4uFmZnlcrEwM7NcLhZmZpbLxcLMzHK5WJiZWS4XCzMzy+ViYWZmuVwszMwsl4uFmZnlcrEwM7NcLhZmZpbLxcLMzHK5WJiZWS4XCzMzy+ViYWZmuVwszMwsl4uFmZnlcrEwM7NchRULScslvSDpiWHxz0p6WtKTkpaWxL8sqSftO60kvjDFeiRdUVS+ZmY2sokFvvY3ga8BK4YCkj4ELALmR0SfpMNS/F3AecAxwBHA9yS9I532deDDQC/wiKTVEfFUgXmbmdkwhRWLiHhA0txh4UuAr0REXzrmhRRfBNyR4j+X1AOckPb1RMQzAJLuSMe6WJiZ1VG9+yzeAfyWpIck/VDS+1J8FrCp5LjeFBspbmZmdVTkZaiR3q8TOAl4H3CnpLcDKnNsUL6YRbkXlrQEWAJw5JFH1iRZMzPL1Ltl0QvcE5mHgUFgRorPKTluNrClQnwfEbEsIroiomvmzJmFJG9m1qrqXSz+ETgZIHVgTwJeBFYD50nqkHQUMA94GHgEmCfpKEmTyDrBV9c5ZzOzllfYZShJtwMfBGZI6gWuApYDy9Nw2teBxRERwJOS7iTruB4ALo2IPel1PgPcC0wAlkfEk0XlbGZm5Sn7W31g6erqiu7u7kanYWZlbNvZR++OXczunMz0KR2NTsdKSFobEV3l9tW7g9vMWtiqdZu5fOUG2tva6B8cZOlZ8znzOA9wbAZe7sPM6mLbzj4uX7mB3f2DvNo3wO7+QS5buYFtO/sanZpVwcXCzOqid8cu2tv2/pPT3tZG745dDcrIRsPFwszqYnbnZPoHB/eK9Q8OMrtzcoMystFwsTCzupg+pYOlZ83noPY2DumYyEHtbSw9a747uZuEO7jNrG7OPG4WC46e4dFQTcjFwszqavqUDheJJuTLUGZmlsvFwszMcrlYmJlZLhcLMzPL5WJhZma5XCzMzCyXi4WZmeVysTCzsrbt7GP9ppe80J8BnpRnZmV4KXEbrqqWhaRzJB2Stv9U0j2Sji82NTNrBC8lbuVUexnqzyLiVUkfAE4DbgVuKi4tM2sULyVu5VRbLPaknx8BboqIVcCkYlIys0byUuJWTrXFYrOk/wmcC3xbUscozjWzJuKlxK2caju4zwUWAtdHxEuSDge+VFxaZtZIXkrchqu2dfDxiLgnIjYCRMTzwMnFpWVmjTZ9SgfHzpnqQmFA9cXibEm/P/RE0t8AMyudIGm5pBckPVFm3xclhaQZ6bkk3SipR9KG0pFWkhZL2pgei6vM18zMaqjay1D/EVgtaRA4HdgeEZ/OOeebwNeAFaVBSXOADwPPlYRPB+alx4lkI61OlDQNuAroAgJYK2l1ROyoMm8zM6uBii0LSdPSH+zJwB8ClwGvAFen+Igi4gFge5ldX02vEyWxRcCKyDwITE39IqcBayJieyoQa8j6TszMrI7yWhZryf6oq+TnR9IjgLeP5s0knQlsjoj1kkp3zQI2lTzvTbGR4uVeewmwBODII48cTVpmZpajYrGIiKNq9UaSDgauBE4tt7vc21eI7xuMWAYsA+jq6ip7jJmZ7Z9ql/u4VNLUkuedkvL6LIb7DeAoYL2kZ4HZwKOS3krWYphTcuxsYEuFuJmZ1VG1o6E+FREvDT1J/QefGs0bRcTjEXFYRMyNiLlkheD4iPg3YDVwfhoVdRLwchqeey9waipOnWStkntH875mZjZ21RaLNpV0MkiaQM5yH5JuB34MvFNSr6SLKhz+beAZoAf4W+DTABGxHbgGeCQ9rk4xMzOro2qHzt4L3CnpG2R9BhcD/1zphIj4eM7+uSXbAVw6wnHLgeVV5mlmZgWotlhcDvwRcAlZp/N3gZuLSsrMxm7bzj4v12E1U1WxiIhBsolyXpbcrAn45kVWa9WOhpon6W5JT0l6ZuhRdHJmNnq+eZEVodoO7r8ja1UMAB8iW8Lj74tKysz2n29eZEWotlhMjoj7AEXELyLiL/Cqs2bjkm9eZEWotljsltQGbJT0GUn/ATiswLzMbD/55kVWhGpHQ30eOBj4HNm8hw8BXi7cbJzyzYus1nKLRZqAd25EfAnYCVxQeFZmNmbTp3S4SFjN5F6Giog9wHtLZ3CbmVlrqfYy1GPAKkl3Ab8aCkbEPYVkZWZm40q1xWIasI29R0AF4GJhZtYCqi0WN0fEj0oDkhYUkI9Zy/MyHTYeVVss/gdwfBUxMxsDL9Nh41XFYiHpN4H3AzMl/XHJrkOBCUUmZtZqSpfp2E02qe6ylRtYcPQMtzCs4fJGQ00CppAVlUNKHq8AZxebmllr8TIdNp7l3YP7h8APJa2IiJ+X7pP0vkIzM2sxXqbDxrNql/u4W9KvL5xK+m18QyKzmvIyHTaeVdvBfTHwj5L+PVmn9n8DzigsK7MW5WU6bLyq9uZHj0j6HNkd8nYDH46IrYVmZtaivEyHjUd5o6H+D9nkuyEHAy8Dt0giIs4sMjkzMxsf8loW19clCzMzG9cqdnBHxA/TiKjngIdKnj8M/KLSuZKWS3pB0hMlsesk/aukDZL+QdLUkn1fltQj6WlJp5XEF6ZYj6Qr9vcXNTOz/VftaKi7gNIxfXtSrJJvAguHxdYA746I+cBPgS8DSHoXcB5wTDrnbyRNSMujfx04HXgX8PF0rJmZ1VG1xWJiRLw+9CRtT6p0QkQ8AGwfFvtuRAykpw8Cs9P2IuCOiOhL8zl6gBPSoycinknveUc61szM6qjaYrFV0q87syUtAl4c43tfCHwnbc8CNpXs602xkeL7kLREUrek7q1bPVDLzKyWqi0WFwN/Iuk5SZuAy4E/2t83lXQlMADcNhQqc1hUiO8bjFgWEV0R0TVz5sz9Tc3MzMqodp7Fz4CTJE0BFBGv7u8bSloMfBQ4JSKG/vD3AnNKDpsNbEnbI8XNzKxOqp3BjaSPkHVAHzR0h9WIuHo0byZpIVmr5Hci4rWSXauB/y3pr4EjgHlkI64EzJN0FLCZrBP890bznmZmNnZVFQtJ3yCbkPch4GayFWcfzjnnduCDwAxJvcBVZKOfOoA1qeA8GBEXR8STku4EniK7PHVpuvc3kj4D3Eu2JPryiHhytL+kmZmNjd64ElThIGlDRMwv+TkFuCciTi0+xdHr6uqK7u7uRqdhZtZUJK2NiK5y+6rt4B5aUP81SUcA/cBRtUjOzMzGv2r7LP4pzbZeCqxNsZuLScnMzMabaovF9cAlwG8BPwb+H3BTUUmZmdn4Um2xuBV4FbgxPf84sAI4t4ikzMxsfKm2WLwzIo4tef59SeuLSMjMzMafaju4H5N00tATSScCPyomJTMzG2/ybn70ONnyGu3A+ZKeS8/fRjYnwszMWkDeZaiP1iULMzMb1yoWi4ioeIMjMzNrDdX2WZiZWQtzsTAzs1wuFmZmlsvFwszMcrlYmJlZLheLA8S2nX2s3/QS23b2NToVMzsAVX2nPBu/Vq3bzOUrN9De1kb/4CBLz5rPmcfNanRaZnYAccuiyW3b2cflKzewu3+QV/sG2N0/yGUrN7iFYWY15WLR5Hp37KK9be//jO1tbfTu2DXCGWZmo+di0eRmd06mf3Bwr1j/4CCzOyc3KCMzOxC5WDS56VM6WHrWfA5qb+OQjokc1N7G0rPmM31KR6NTM7MDiDu4m8i2nX307tjF7M7JexWDM4+bxYKjZ5TdZ2ZWC4W1LCQtl/SCpCdKYtMkrZG0Mf3sTHFJulFSj6QNko4vOWdxOn6jpMVF5TverVq3mQXX3s8nbn6IBdfez+p1m/faP31KB8fOmepCYWaFKPIy1DeBhcNiVwD3RcQ84L70HOB0YF56LCHd31vSNOAq4ETgBOCqoQLTSjziycwarbBiEREPANuHhReR3c+b9PNjJfEVkXkQmCrpcOA0YE1EbI+IHcAa9i1ABzyPeDKzRqt3B/dbIuJ5gPTzsBSfBWwqOa43xUaK70PSEkndkrq3bt1a88QbySOezKzRxstoKJWJRYX4vsGIZRHRFRFdM2fOrGlyjdaIEU9ePsTMStV7NNQvJR0eEc+ny0wvpHgvMKfkuNnAlhT/4LD4D+qQ57hTzxFPq9Zt5rK71zNBbeyJQa47+1gvH2LW4urdslgNDI1oWgysKomfn0ZFnQS8nC5T3QucKqkzdWyfmmItqR4jnrbt7OO/3LmOvoHgtf499A0Ef3znOrcwzFpckUNnbwd+DLxTUq+ki4CvAB+WtBH4cHoO8G3gGaAH+Fvg0wARsR24BngkPa5OMSvIk1teYWDv7hEGBrO4mbWuwi5DRcTHR9h1SpljA7h0hNdZDiyvYWpWUdkuoQpxM2sF46WD28aJY454M+0T9h5X0D5BHHPEmxuUkZmNBy4WtpfpUzr4q3OOpWNiGwdPmkDHxDb+6pxjPTPcrMV5bSjbR+nIqzdNmsCvXt/Dtp19LhhmLczFwsqaPqWDf+l50XfgMzPAl6FsBF6PysxKuVhYWV6PysxKuVhYWV6PysxKuVhUoRXXSfId+MyslDu4c6xat7llO3l9Bz4zG+JiUUFpJ+9usksyl63cwIKjZ7TMH87pUzpa5nc1s5H5MlQFI3XyPrnllZa7LGVmrc0tiwrKdfLu6h/gUyu6mTSh9S5LmVnrcsuiguGdvB0ThST6Bjz3wMxai1sWOUo7eV/e9TqX3vYY/XsGfr1/aO6Br+ub2YHMxaIKQ52823b2ee6BmbUkX4YaBc89MLNW5ZbFKHnugZm1IheL/eC5B2bWanwZyszMcrlYHIDKrWXViutbmVnt+DJUgbbt7Kt730a5tawCWnZ9KzOrjYYUC0lfAP4QCOBx4ALgcOAOYBrwKPAHEfG6pA5gBfBeYBvwnyLi2UbkPRqNWICw3FpWX7p7AxD0DUTLrm9lZmNX98tQkmYBnwO6IuLdwATgPOBa4KsRMQ/YAVyUTrkI2BERRwNfTccVphaXaxp1l7lya1lNaBMT5JsYmdnYNKrPYiIwWdJE4GDgeeBk4O60/1bgY2l7UXpO2n+KJBWR1Kp1m1lw7f184uaHWHDt/axet3m/XqdRd5krt5bVnsFgT3gioZmNTd2LRURsBq4HniMrEi8Da4GXImJoHY1eYOiazSxgUzp3IB0/vdZ57U9rYKRWSKPuMldu0uB1Z8/nurOP9URCMxuTuvdZSOokay0cBbwE3AWcXubQGDqlwr7S110CLAE48sgjR53XUGtg6Lo+VF73qVKfxNAf7cuG7a/HH+iRJg16IqGZjUUjOrh/F/h5RGwFkHQP8H5gqqSJqfUwG9iSju8F5gC96bLVm4Htw180IpYBywC6urr2KSZ5RtMaqOamSI2c6V1u0qAnEprZWDSiz+I54CRJB6e+h1OAp4DvA2enYxYDq9L26vSctP/+iBh1McgzmnWfqu2TmD6lg2PnTPUfaTNrenVvWUTEQ5LuJhseOwA8RtYi+L/AHZL+MsVuSafcAvy9pB6yFsV5ReU21Bp4csvLgDjmiEPLHteoPomheRtvmjSBX72+x5eUzKxuGjLPIiKuAq4aFn4GOKHMsbuBc+qRF8C/9LyYOz+iEX0SQ30kALv7B+mYINQmT7Azs7pQAVd0Gq6rqyu6u7tHfd62nX0suPZ+dve/0Wo4qL2NH11+ctlCUGmGduk+YEx9F+XyqiY/M7PRkLQ2IrrK7fNyHyVGOyJqpE7j0pFSu/oHkMRBEyfs90zucnlVk5+ZWa14IcESteiLGD5fY2AQ+vfEmGZyl8trf/MzM9sfLhYlanEnvHIjpUrtz0zu0rwOas9eu2OCPMHOzOrGl6GGGev8iEqtANj/lkBpXh4NZWb15mJRxlgmsA0fKVWuz2Isr+3iYGaN4GJRgOGtExjbaCgzs0ZzsaiR4cNoh7cCXCTMrJm5WNRAI250ZGZWTx4NNUaNutGRmVk9uViMUaNudGRmVk8uFmPUqEUFzczqycVijGoxkc/MbLxzB3cNNPJGR2Zm9eBiUSOeMGdmBzJfhqrStp19rN/0kkc5mVlLcsuiCp5HYWatzi2LHJ5HYWbmYpHL8yjMzFwscnkehZmZi0Uuz6MwM2tQB7ekqcDNwLuBAC4Enga+BcwFngXOjYgdkgTcAJwBvAZ8MiIerWe+nkdhZq2uUS2LG4B/joh/BxwL/AS4ArgvIuYB96XnAKcD89JjCXBT/dPNWhjHzpnqQmFmLanuxULSocBvA7cARMTrEfESsAi4NR12K/CxtL0IWBGZB4Gpkg6vc9pmZi2tES2LtwNbgb+T9JikmyW9CXhLRDwPkH4elo6fBWwqOb83xczMrE4aUSwmAscDN0XEe4Bf8cYlp3JUJhb7HCQtkdQtqXvr1q21ydTMzIDGFIteoDciHkrP7yYrHr8curyUfr5QcvyckvNnA1uGv2hELIuIrojomjlzZmHJm5m1oroXi4j4N2CTpHem0CnAU8BqYHGKLQZWpe3VwPnKnAS8PHS5yszM6kMR+1zRKf5NpePIhs5OAp4BLiArXHcCRwLPAedExPY0dPZrwEKyobMXRER3zutvBX5RRSozgBf39/cYB5o9f2j+38H5N5bzr623RUTZSzMNKRbjhaTuiOhqdB77q9nzh+b/HZx/Yzn/+vEMbjMzy+ViYWZmuVq9WCxrdAJj1Oz5Q/P/Ds6/sZx/nbR0n4WZmVWn1VsWZmZWhQOiWEhaLukFSU+UxKZJWiNpY/rZmeKSdKOkHkkbJB1fcs7idPxGSYtL4u+V9Hg658Y0nLfo/K+T9K8px39IK/UO7ftyyuVpSaeVxBemWI+kK0riR0l6KP1e35I0qej8S/Z9UVJImpGeN8Xnn+KfTZ/nk5KWlsTH/ecv6ThJD0pal1Y2OCHFx+PnP0fS9yX9JH3W/znFm+I7XCH/pvkOVyUimv5BtjDh8cATJbGlwBVp+wrg2rR9BvAdsmVETgIeSvFpZHM+pgGdabsz7XsY+M10zneA0+uQ/6nAxLR9bUn+7wLWAx3AUcDPgAnp8TOytbcmpWPelc65EzgvbX8DuKTo/FN8DnAv2ZyXGU32+X8I+B7QkZ4f1kyfP/Ddoc8pfeY/GMef/+HA8Wn7EOCn6XNuiu9whfyb5jtczeOAaFlExAPA9mHh0a5iexqwJiK2R8QOYA2wMO07NCJ+HNl/qRUlr1VY/hHx3YgYSE8fJFvmZCj/OyKiLyJ+DvQAJ6RHT0Q8ExGvA3cAi9L/QZ1MtqzK8M+isPyTrwKXsfdaXk3x+QOXAF+JiL50zNDyM83y+QdwaNp+M28skTMeP//nI92jJiJeJbtlwSya5Ds8Uv7N9B2uxgFRLEYw2lVsK8V7y8Tr6UKy/xuC0ec/HXip5B9tXfKXdCawOSLWD9vVLJ//O4DfSk3/H0p6X4o3xecPfB64TtIm4Hrgyyk+rj9/SXOB9wAP0YTf4WH5l2q67/BwB3KxGMlIq9iONl4Xkq4EBoDbhkIj5DNu8pd0MHAl8Ofldo+Qz7jJP5lIdinjJOBLwJ3p//CaJf9LgC9ExBzgC6T7x1TIp+H5S5oCrAQ+HxGvVDp0hJwa+juMlH8zfofLOZCLxWhXsa0Un10mXrjUQfdR4PdT85mcPMvFXyRrpk8cFi/Sb5Bdi10v6dn0no9KemuFPMfb598L3JMudTwMDJKt49MMnz9ki3Hek7bvIrvEQYU8G/r5S2on+0N7W0QM5d003+ER8m/m7/C+6t1JUtSD7N7dpR1817F359jStP0R9u4cezje6Bz7Odn/TXam7Wlp3yPp2KHOsTPqkP9CstV4Zw477hj27hx7hqxjbGLaPoo3OseOSefcxd6dY58uOv9h+57ljQ7uZvn8LwauTtvvILs8oGb5/Mmum38wbZ8CrB2vn3963RXAfx8Wb4rvcIX8m+o7nPt71vsNC/kl4HbgeaCfrDpfRHad7z5gY/o59I9GwNfJRh08DnSVvM6FZJ1NPWSr2w7Fu4An0jlfI01mLDj/HrI/UOvS4xslx1+ZcnmaklEdZKNEfpr2XVkSfzvZaJCe9I+uo+j8h+1/ljeKRbN8/pOA/5Xe91Hg5Gb6/IEPAGvTH5yHgPeO48//A2SXVTaU/Hs/gyb5DlfIv2m+w9U8PIPbzMxyHch9FmZmViMuFmZmlsvFwszMcrlYmJlZLhcLMzPL5WJhZma5XCzMzCyXi4VZDUiaO+x+El+U9BeSPifpqXRPgzvSvjcpuwfFI5Iek7QoxSdIuj7dd2GDpM826vcxG25i/iFmNgZXAEdFRF/JzW+uBO6PiAtT7GFJ3wPOJ1vq4T0RMSBpWoNyNtuHWxZmxdoA3CbpE2Qrj0J2U5wrJK0DfgAcBBwJ/C7ZkhADABFR7h4hZg3hloVZ7ZQuJd2efn6E7E52ZwJ/JumYdNxZEfH0XidnS6B7/R0bl9yyMKudt0maKamNrEBMAOZExPfJ7hg4FZhCdqvZzw7dB1rSe9L53wUuHlqK2pehbDxxsTCrnW1kS1WvJVvh9ELgx5IeBx4DvhoRLwHXkLU8NqRO8WvS+TcDz6X4euD36py/2Yi86qxZDaTbaf5TRLy7wamYFcItCzMzy+WWhZmZ5XLLwszMcrlYmJlZLhcLMzPL5WJhZma5XCzMzCyXi4WZmeX6/3ovQXjBQFkEAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "outliers = sudata[sudata['μsec'] > 10_000]\n",
    "\n",
    "outliers.plot.scatter(y='backtracks', x='μsec', marker='o');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>μsec</th>\n",
       "      <th>backtracks</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>count</th>\n",
       "      <td>24.000000</td>\n",
       "      <td>24.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>mean</th>\n",
       "      <td>13059.210000</td>\n",
       "      <td>976.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>std</th>\n",
       "      <td>3374.607334</td>\n",
       "      <td>319.690339</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>min</th>\n",
       "      <td>10230.310000</td>\n",
       "      <td>645.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25%</th>\n",
       "      <td>10789.560000</td>\n",
       "      <td>760.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>50%</th>\n",
       "      <td>11910.210000</td>\n",
       "      <td>849.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>75%</th>\n",
       "      <td>12998.510000</td>\n",
       "      <td>1021.250000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>max</th>\n",
       "      <td>22856.310000</td>\n",
       "      <td>1957.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "               μsec   backtracks\n",
       "count     24.000000    24.000000\n",
       "mean   13059.210000   976.000000\n",
       "std     3374.607334   319.690339\n",
       "min    10230.310000   645.000000\n",
       "25%    10789.560000   760.000000\n",
       "50%    11910.210000   849.000000\n",
       "75%    12998.510000  1021.250000\n",
       "max    22856.310000  1957.000000"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "outliers.describe()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only 24 puzzles in total take more than 10 milliseconds; only 5 are over 14 milliseconds; only 1 is over 20 milliseconds. I was worried there was going to be a long tail of times, and clearly this is not a normal distribution, but neither does it seem to be a distribution where the long tail just keeps on going forever. If I solved another million random puzzles I would not be surprised to find a puzzle that doubles the maximum run time, but I would be surprised to find one that increases the run time by a factor of 10.\n",
    "\n",
    "Within the outliers, backtracks correlate very highly with run time (just as with the non-outliers). But as a whole, the outliers take more run time than any of the other 500,000 puzzles and have far fewer backtracks than any other puzzles with comparable run times. \n",
    "\n",
    "I'm imaging that when solving the outliers, the solution takes a step, then has a long chain of constraint propagation only to find a contradiction at the very end, then backs up and takes another step. But I don't really understand the mystery of these outliers. \n",
    "\n",
    "Here are all of them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>μsec</th>\n",
       "      <th>backtracks</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>7803</th>\n",
       "      <td>16931.41</td>\n",
       "      <td>1269</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8828</th>\n",
       "      <td>10820.31</td>\n",
       "      <td>700</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13143</th>\n",
       "      <td>12979.51</td>\n",
       "      <td>973</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>78290</th>\n",
       "      <td>12495.71</td>\n",
       "      <td>819</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>106137</th>\n",
       "      <td>10697.31</td>\n",
       "      <td>785</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>121433</th>\n",
       "      <td>10497.51</td>\n",
       "      <td>645</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>129467</th>\n",
       "      <td>10274.61</td>\n",
       "      <td>756</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>145734</th>\n",
       "      <td>11011.01</td>\n",
       "      <td>746</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>174777</th>\n",
       "      <td>12974.81</td>\n",
       "      <td>972</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>183889</th>\n",
       "      <td>22856.31</td>\n",
       "      <td>1957</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>185319</th>\n",
       "      <td>12170.31</td>\n",
       "      <td>1049</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>191476</th>\n",
       "      <td>12289.61</td>\n",
       "      <td>814</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>210897</th>\n",
       "      <td>11945.81</td>\n",
       "      <td>760</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>286509</th>\n",
       "      <td>10230.31</td>\n",
       "      <td>796</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>300232</th>\n",
       "      <td>10466.41</td>\n",
       "      <td>899</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>323446</th>\n",
       "      <td>11095.31</td>\n",
       "      <td>747</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>349262</th>\n",
       "      <td>11023.11</td>\n",
       "      <td>808</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>356953</th>\n",
       "      <td>11874.61</td>\n",
       "      <td>1012</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>363304</th>\n",
       "      <td>10611.71</td>\n",
       "      <td>879</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>397206</th>\n",
       "      <td>18339.81</td>\n",
       "      <td>1454</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>410566</th>\n",
       "      <td>19241.21</td>\n",
       "      <td>1554</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>461841</th>\n",
       "      <td>11869.61</td>\n",
       "      <td>760</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>473968</th>\n",
       "      <td>13055.51</td>\n",
       "      <td>927</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>485668</th>\n",
       "      <td>17669.21</td>\n",
       "      <td>1343</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            μsec  backtracks\n",
       "7803    16931.41        1269\n",
       "8828    10820.31         700\n",
       "13143   12979.51         973\n",
       "78290   12495.71         819\n",
       "106137  10697.31         785\n",
       "121433  10497.51         645\n",
       "129467  10274.61         756\n",
       "145734  11011.01         746\n",
       "174777  12974.81         972\n",
       "183889  22856.31        1957\n",
       "185319  12170.31        1049\n",
       "191476  12289.61         814\n",
       "210897  11945.81         760\n",
       "286509  10230.31         796\n",
       "300232  10466.41         899\n",
       "323446  11095.31         747\n",
       "349262  11023.11         808\n",
       "356953  11874.61        1012\n",
       "363304  10611.71         879\n",
       "397206  18339.81        1454\n",
       "410566  19241.21        1554\n",
       "461841  11869.61         760\n",
       "473968  13055.51         927\n",
       "485668  17669.21        1343"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "outliers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One weakness of a scatter plot as a visualization tool is that there can be lots of points plotted on top of each other, and you can't tell the density of such points. A histogram portrays density better (but on only one attribute at a time):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEICAYAAACktLTqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAZ6UlEQVR4nO3df5AcZ33n8fcnMgajFf6BnD1bUizBKr4TVorgBePKFVkFcpIMwjkqlZPwpZCjWEUuvpwTpwoZuDvfJTkIKeUSYhMickYhcbTxGQL+IWIcijlwnQBbFEQWQmdZEuW1hAXYlj2KCUh874/uDbO7s6v50fNMT+/nVTWl6We6n36eme9+9czTPd2KCMzMrFp+rN8NMDOz4jm5m5lVkJO7mVkFObmbmVWQk7uZWQU5uZuZVZCTe4skHZX0pgLrG5M0UVR9be77Vkl/1Y99m1kaTu4l1M/Eb2bV4OQ+oCSd0+82mFl5Obm357WSvi7pGUkflfQSSRdKuk/St/Py+yQtndxA0kX5usfy1z/ZrGJJv5HXfRnwaeBSSfX8cWk+lXK3pL+S9BywWdLrJO2R9Kyk45Juk3RuQ52vkvSgpKclPSXp3U32+yJJuyR9XNK5eZ2PSHou3+YPe/A+2jwjKSSNNCzvlPS7+fPF+d/Ns3msfkHSj+WvXZrH5rclHZH0Gw11LJD0bkmPS3pe0l5Jy9L3rpyc3NtzHbAWeCXwk8B7yd7DjwKXAT8BvADc1rDNXwIvBV4F/DjwP6dXKuk/A5uBn42IbwLrgWMRMZQ/juWrXgvcDVwA3AmcAX4TWAxcDbwR+A95nYuAvwf+DrgUGAE+O22/5wGfBP4J+KWI+D7wx8AfR8TL8n7e1f7bZNaWm4EJ4GJgGHg3EHmCvxf4GrCELL5vkrQ23+63gE3ANcDLgF8B/jFt08vLyb09t0XEExHxNPB7wKaI+G5EfDwi/jEins/LfxZA0iVkifqdEfFMRPwgIv5PQ33KR8ZrgTUR8e2z7H9PRHwyIn4YES9ExN6I+GJEnI6Io8CfTe4beAvwrYjYHhHfi4jnI+JLDXW9jCzxPw5cHxFn8vIfACOSFkdEPSK+2OF7ZdaqHwCXAJflfyNfiOyiV68FLo6I/x4R34+Iw8BHgI35dr8KvDciDkbmaxHx3f50oXyc3NvzRMPzb5JNnbxU0p9J+mY+XfJ54AJJC4BlwNMR8cws9V0AbAXeFxEn29w/kn4y/zr7rXzf/4NsFE++78fnqOv1wE8B74+pV4/bQvat5BuSHpb0lhbaZdaNPwAOAZ+RdFjStrz8MrK/sWcnH2Sj+uH89bPF+Lzm5N6exvm8nwCOkX2lvBy4Kp/KeEP+usiS8UWSLpilvmfIRtgflfQzDeWzXapzevmfAt8AVub7fne+X/J9v3KOvnwGeB/wWUmTfyxExGMRsYlsCun3gbslLZyjHrNWvaTh+T//TeTfKm+OiFcAG4DfkvRGshg+EhEXNDwWRcQ1+aZni/F5zcm9Pb8uaamki8gS6d8Ai8jm2Z/Ny//r5MoRcZzs4OiH8gOvL5L0hsYKI6JGNpf/t5KuyoufAl4u6fyztGcR8BxQl/QvgV9reO0+4F9IuknSiyUtaqh/ct8fAP6aLMEvBpD07yVdHBE/BJ7NVz2DWfeuzw+Cvpps/nxR/jfxFkkjkkQWz2fyx5eB5yS9S9J5+bZXSHptXt+fA78jaaUyPyXp5X3pWQk5ubfnr8lGvIfzx+8CfwScB3wH+CLZPHajXyabU/wGcAK4aXqlEfEgcD1wj6QrI+IbwC7gcP519NJZ2vPbwNuB58nmIv+moc7ngZ8nGwl9C3gMWNNk379DdlD17/P/nNYB+yXVyQ6uboyI7839tpi15KXAcbJY/S/AO4CfA1aSHfyvA3uAD0VELT8OtAF4NXCE7G/sz4HJQc8fkh3w/wzZfwr/i+xv0QD5Zh1m1muSgmz68FC/2zJfeORuZlZBTu5mZhXkaRkzswryyN3MrIJKcfGpxYsXx/Lly2eUnzp1ioULy32KtdtYjCLauHfv3u9ExMUFNamnBjnmizJf+trLfs4Z8xHRtwfZaU47RkZGopnPfe5zTcvLxG0sRhFtBB6JPsZzK48qxHxR5ktfe9nPuWK+r9MyEXFvRGw9//yz/VbHrBoc85ZKX5O7pA2Sdpw82cplVcwGn2PeUvHI3Swhx7yl4pG7WUKOeUvFI3ezhBzzlopH7mYJOeYtFY/czRJyzFsq/oWqmVkF9fUXqpI2ABtGRkZmXWf5tvunLB99/5t73Cqz3ukk5sFxb+3ztIxZQo55S8XTMmZmFeSzZczMKsjTMmYJeUBjqXhaxiwhD2gsFSd3M7MKcnI3M6sgH1A1S8gxb6n4gKpZQo55S8XTMmZmFeTkbmZWQU7uZmYV5ORuZlZBPlvGLCHHvKXis2XMEnLMWyqeljEzqyAndzOzCnJyNzOrICd3M7MKcnI3M6ugwpO7pDFJX5D0YUljRddvVkaOeyublpK7pDsknZD06LTydZIOSjokaVteHEAdeAkwUWxzzdJx3Nsga3XkvhNY11ggaQFwO7AeWAVskrQK+EJErAfeBfy34ppqltxOHPc2oM5pZaWI+Lyk5dOKXwcciojDAJLGgWsj4uv5688AL56tTklbga0Aw8PD1Gq1GevU63VuXn1mSlmz9fqpXq+Xrk3TuY2dKTruO415KF/cF6GMn3kv9KufLSX3WSwBnmhYngCukvQ2YC1wAXDbbBtHxA5gB8Do6GiMjY3NWKdWq7H9oVNTyo5eN3O9fqrVajRre5m4jYXqOO47jXkoX9wXYYA+8670q5/dJHc1KYuI+ATwiZYqkDYAG0ZGRrpohllSXcW9Y95S6eZsmQlgWcPyUuBYOxX4Ohs2gLqKe8e8pdJNcn8YWClphaRzgY3APe1U4Cvk2QDqKu4d85ZKq6dC7gL2AJdLmpC0JSJOAzcCDwAHgLsiYn87O/coxsqsF3HvmLdUWj1bZtMs5buB3Z3u3POPVma9iHvHvKXi67mbJeSYt1R8JyazhBzzlopH7mYJOeYtFV8V0sysgjwtY5aQY95S8bSMWUKOeUvF0zJmZhXkaRmzhBzzloqnZcwScsxbKp6WMTOrICd3M7MK8py7mVkFec7dLCEPaCwVT8uYJeQBjaXi5G5mVkFO7mZmFeTkbmZWQU7uZmYV5FMhzRJyzFsqPhXSLCHHvKXiaRkzswpycjczqyAndzOzCnJyNzOrICd3M7MK6klyl7RQ0l5Jb+lF/WZl45i3smkpuUu6Q9IJSY9OK18n6aCkQ5K2Nbz0LuCuIhtqlpJj3gZdqyP3ncC6xgJJC4DbgfXAKmCTpFWS3gR8HXiqwHaapbYTx7wNMEVEaytKy4H7IuKKfPlq4NaIWJsv35KvOgQsJAv+F4B/GxE/bFLfVmArwPDw8JXj4+Mz9lmv1zly8syUstVLyvXjj3q9ztDQUL+bMaf50sY1a9bsjYjRgppUmpiH8sV9EQYhLovQy37OFfPndFHvEuCJhuUJ4KqIuBFA0mbgO82CHCAidgA7AEZHR2NsbGzGOrVaje0PnZpSdvS6mev1U61Wo1nby8RtLExfYh7KF/dFGJDPvGv96mc3yV1Nyv75a0BE7DxrBdIGYMPIyEgXzTBLxjFvA6Obs2UmgGUNy0uBY901x6zUHPM2MLpJ7g8DKyWtkHQusBG4p50KfBElGzCOeRsYrZ4KuQvYA1wuaULSlog4DdwIPAAcAO6KiP3t7NyXP7WycszboGtpzj0iNs1SvhvY3enOI+Je4N7R0dEbOq3DrBcc8zbofPkBM7MK8p2YzBJyzFsqvhOTWUKOeUvFI3czswryyN0sIQ9oLBUfUDVLyAMaS8XJ3cysgjznbpaQY95S6ebCYV3r5gcdy7fdP6Ps6PvfXESzzHrGP2KyVDwtY2ZWQU7uZmYV5Dl3s4Qc85aKz3M3S8gxb6l4WsbMrIKc3M3MKsjJ3cysgpzczcwqyGfLmCXkmLdUfLaMWUKOeUvF0zJmZhXk5G5mVkF9vXCYmbVn+gXzfLE8m41H7mZmFeTkbmZWQU7uZmYVVHhyl/SvJH1Y0t2Sfq3o+s3KyHFvZdNScpd0h6QTkh6dVr5O0kFJhyRtA4iIAxHxTuCXgNHim2yWhuPeBlmrI/edwLrGAkkLgNuB9cAqYJOkVflrbwUeAj5bWEvN0tuJ494GlCKitRWl5cB9EXFFvnw1cGtErM2XbwGIiPc1bHN/RDQ9V0vSVmArwPDw8JXj4+Mz1qnX6xw5eWZK2eol2S/79j058+fbrbxWtHq9ztDQUE/qLsp8aeOaNWv2RkSho+Yi477TmIfZY7tXcZ3CIMRlEXrZz7livpvz3JcATzQsTwBXSRoD3ga8GNg928YRsUPScWDDokWLrhwbG5uxTq1WY/tDp6aUHb0uW29zsxtkt/Ba0Wq1Gs3aXiZuY6E6jvtOYx5mj+1exXUKA/SZd6Vf/ewmuatJWUREDai1UoHvBG8DqKu4d8xbKt2cLTMBLGtYXgoca6cCXyHPBlBXce+Yt1S6Se4PAyslrZB0LrARuKedCnyFPBtAXcW9Y95SafVUyF3AHuBySROStkTEaeBG4AHgAHBXROxvZ+cexViZ9SLuHfOWSktz7hGxaZby3cxx0LSFej3/aKXVi7h3zFsqvhOTmVkF+U5MZgl5QGOp+MJhZgl5QGOpeFrGLCHHvKXS1zsx9ePg0vQ72YDvZmPp+ICqpeJpGTOzCvI9VM0qwN9IbTrPuZsl5Ji3VHwqpFlCjnlLxXPuZmYV5ORuZlZBnnM3S8gxb6nMu/Pc5zL9jAOfbWBFK1vMW3V5WsbMrIKc3M3MKsjJ3cysgpzczcwqyGfLmCXkmLdU/AtVs4Qc85aKp2XMzCrIV4U0qzhfMXJ+cnJvgf84zGzQeFrGzKyCnNzNzCqoJ8ld0i9I+oikT0n6N73Yh1mZOOatbFpO7pLukHRC0qPTytdJOijpkKRtABHxyYi4AdgM/LtCW2yWiGPeBlk7I/edwLrGAkkLgNuB9cAqYJOkVQ2rvDd/3WwQ7cQxbwOq5bNlIuLzkpZPK34dcCgiDgNIGgeulXQAeD/w6Yj4SrP6JG0FtgIMDw9Tq9VmrFOv17l59ZkpZZPr3bz69Iz1i36tlW3q9XrTtpeJ29iZomPeLKVuT4VcAjzRsDwBXAX8R+BNwPmSRiLiw9M3jIgdwA6A0dHRGBsbm1F5rVZj+0OnppQdvS5bb3Oz0xMLfq2VbWq1Gs3aXiZuY6E6jvlOBzTQ3QBkrtf6qYz/ofdCv/rZbXJXk7KIiA8CHzzrxtIGYMPIyEiXzTBLpuOYj4gdko4DGxYtWnRlqwMa6G4AMtdr/TRA/6F3pV/97PZsmQlgWcPyUuBYqxv7Ohs2gBzzNhC6Hbk/DKyUtAJ4EtgIvL3Vjaswct/35MmZo6n816u+bV8lVSrmHaPV1c6pkLuAPcDlkiYkbYmI08CNwAPAAeCuiNjfap0exViZOeZtkLVztsymWcp3A7s72XnZRjFmjRzzNsh8PXezhBzzlorvxGSWkGPeUvHI3Swhx7yl4uu5l4yvHW9mRfC0jFlCjnlLpa8j94i4F7h3dHT0hn62IzWPzuevQYl5x+jg8806zMwqyNMyZgk55i0VT8uYJVSFmPeUzWDwtIyZWQU5uZuZVZCTu5lZBfmAqllCjnlLxZcfMEvIMW+p+PIDA8RnKZhZqzznbmZWQU7uZmYV5ORuZlZBfZ1z9y3HbL6pesz7uFB5+GwZs4Qc85aKz5apuOXb7ufm1afZ3DCi8kjKrPo8525mVkFO7mZmFeTkbmZWQU7uZmYVVPgBVUmvAN4DnB8Rv1h0/dbc9FPQenXQ1Ke6Nee4t7JpaeQu6Q5JJyQ9Oq18naSDkg5J2gYQEYcjYksvGmuWkuPeBlmrI/edwG3AxyYLJC0Abgd+HpgAHpZ0T0R8vehGWm8UPQqv4Kh+J457G1CKiNZWlJYD90XEFfny1cCtEbE2X74FICLely/fPdfXU0lbga0Aw8PDV46Pj89Yp16vc+TkmSllq5dkP/7Y9+TM62EX/Vor25x4+iRPvVBcfb1o+/B5TGljK/XNptP2nU29XmdoaKildWezZs2avREx2lUl0xQZ953GPKSLqV7G6HRFfOaDoJf9nCvmu5lzXwI80bA8AVwl6eXA7wE/LemWyaCfLiJ2ADsARkdHY2xsbMY6tVqN7Q+dmlJ29Lpsvc3NRokFv9bKNn9y56fYvu+cpq91Ul8v2n7z6tNT2thKfbPptH1nU6vVaBYDJdRx3Hca85AupnoZo9MN0GfelX71s5vkriZlERHfBd7ZUgUVv86GVVJXce+Yt1S6ORVyAljWsLwUONZOBb7Ohg2gruLeMW+pdDNyfxhYKWkF8CSwEXh7OxV4FFNeqU6tHEBdxb1jfqYKHogvhVZPhdwF7AEulzQhaUtEnAZuBB4ADgB3RcT+dnbuUYyVWS/i3jFvqbQ0co+ITbOU7wZ2d7pzj2Lmj0EcnfUi7h3zloqv526WkGPeUvGdmMwSms8xP/3b2851C9veBsr/ja8sPHI3S8gxb6n4qpBmZhXU1+QuaYOkHSdPzvzJslkVOeYtFU/LmCXkmLdUPC1jZlZBnpaxvlu+7X72PXmS5dvub3p2RJU45i0VT8uYJeSYt1Q8LWNmVkFO7mZmFeRfqJol5Jgvjq9cOjfPuZsl5Ji3VDwtY2ZWQU7uZmYV5ORuZlZBTu5mZhXks2XMEnLMV0uZrzfvs2XMEnLMWyqeljEzqyAndzOzCnJyNzOrICd3M7MKcnI3M6sgJ3czswoq/Dx3SQuBDwHfB2oRcWfR+zArE8e8lVFLI3dJd0g6IenRaeXrJB2UdEjStrz4bcDdEXED8NaC22uWhGPeBl2r0zI7gXWNBZIWALcD64FVwCZJq4ClwBP5ameKaaZZcjtxzNsAU0S0tqK0HLgvIq7Il68Gbo2ItfnyLfmqE8AzEXGfpPGI2DhLfVuBrQDDw8NXjo+Pz1inXq9z5OTUv5XVS7Jf9u17cuYNhot+rZVtTjx9kqdeKK6+XrR9+DymtLFX70U3rzW2sZVtmlmzZs3eiBiddYU2lSXmId3nkjJGV5y/gKGhocLb3qmi36dJ9XqdoaGhjtvRacx3k9x/EVgXEb+aL/8ycBXwLuA24HvAQ63MP46OjsYjjzwyo7xWq7H5705NKZu8bsNc13Qo6rVWtvmTOz/F9n3ntLRdv9p+8+rTU9rYq/eim9ca29jKNs1I6nVy70vMQ7rPJWWM7ly3kLGxscLb3qmi36dJtVqNsbGxjtvRacx3c0BVTcoiIk4B17dUgS+iZIPFMW8Do5tTISeAZQ3LS4Fj3TXHrNQc8zYwuknuDwMrJa2QdC6wEbinnQp8hTwbMI55Gxitngq5C9gDXC5pQtKWiDgN3Ag8ABwA7oqI/e3sXNIGSTtOnpx5UMKsnxzzNuhamnOPiE2zlO8Gdne684i4F7h3dHT0hk7rMOsFx7wNOl9+wMysgvqa3P0V1eYbx7yl4tvsmSXkmLdUWv4RU08bIX0b+GaTlxYD30ncnHa5jcUooo2XRcTFRTSm1wY85osyX/ray37OGvOlSO6zkfRIkb847AW3sRiD0MYU5tP7MF/62q9++oCqmVkFObmbmVVQ2ZP7jn43oAVuYzEGoY0pzKf3Yb70tS/9LPWcu5mZdabsI3czM+uAk7uZWQWVMrnPcp/KVPteJulzkg5I2i/pP+Xlt0p6UtJX88c1Ddvckrf1oKS1Kfoh6aikfXlbHsnLLpL0oKTH8n8vzMsl6YN5O/5B0msa6nlHvv5jkt5RcBsvb3i/virpOUk3le29LINB7V+ze80WGYeSrszj/FC+bbNr6vfcHHmhvH2NiFI9gAXA48ArgHOBrwGrEu7/EuA1+fNFwP8ju1/mrcBvN1l/Vd7GFwMr8rYv6HU/gKPA4mllHwC25c+3Ab+fP78G+DTZzSZeD3wpL78IOJz/e2H+/MIefq7fAi4r23vZ78cg9w94A/Aa4NFexCHwZeDqfJtPA+v71M/Z8kJp+1rGkfvrgEMRcTgivg+MA9em2nlEHI+Ir+TPnye7tOuSOTa5FhiPiH+KiCPAIbI+9KMf1wJ/kT//C+AXGso/FpkvAhdIugRYCzwYEU9HxDPAg0y7KXSB3gg8HhHNfpU5qUzvZUoD27+I+Dzw9LTiQuIwf+1lEbEnsuz3sYa6kpojL5S2r2VM7kv40Z3kIbv7zVzJtWeU3UPzp4Ev5UU35l+x7pj8+sXs7e11PwL4jKS9ym68DDAcEcchC0bgx/vcxkYbgV0Ny2V6L/utav0rKg6X5M+nl/fVtLxQ2r6WMbk3vU9l8kZIQ8DHgZsi4jngT4FXAq8GjgPbJ1dtsnnMUV6Un4mI1wDrgV+X9IY51u1XG7OdZ3cteivwv/Oisr2X/Vb1/k1q9/Mt3fvSJC/MumqTsqR9LWNy7/t9KiW9iOwDvDMiPgEQEU9FxJmI+CHwEbKv0nO1t6f9iIhj+b8ngL/N2/NU/vWO/N8T/Wxjg/XAVyLiqbzNpXovS6Bq/SsqDify59PL+6JZXqDMfe3HwYmzHLg4h+wgwwp+dHDpVQn3L7L5rj+aVn5Jw/PfJJsbBngVUw8CHiY7QNazfgALgUUNz/8v2Vz5HzD14M4H8udvZurBnS/Hjw7uHCE7sHNh/vyiHryn48D1ZXwvy/AY9P4By5l6QLWwOCS7b+3r+dFBxmv61MfZ8kJp+9r3wJjljbyG7Gj048B7Eu/7X5N9HfoH4Kv54xrgL4F9efk90xLUe/K2HqThCHev+kF2VsXX8sf+ybqBlwOfBR7L/50MGgG35+3YB4w21PUrZAcuD9GQgAts60uB7wLnN5SV5r0sy2NQ+0d2HOU48AOy0eeWIuMQGAUezbe5jfxX9X3o52x5obR99eUHzMwqqIxz7mZm1iUndzOzCnJyNzOrICd3M7MKcnI3M6sgJ3czswpycjczq6D/D7PMJbAlZR4wAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "sudata.hist(rwidth=0.7, log=True, bins=20);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For both attributes, almost all the puzzles are in the leftmost bin (the first bar goes almost up to the 5 × 10<sup>5</sup> line; the second bar is more than two horizontal lines down on the log scale, thus more than 100 times smaller). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below we zoom in on the puzzles that take 10 backtracks or less. 330,000 out of 500,000 have 10 or less; 189,000 have zero or one backtrack. They all take less than 1/4 millisecond:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>μsec</th>\n",
       "      <th>backtracks</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>count</th>\n",
       "      <td>330155.000000</td>\n",
       "      <td>330155.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>mean</th>\n",
       "      <td>48.805696</td>\n",
       "      <td>2.312011</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>std</th>\n",
       "      <td>10.164409</td>\n",
       "      <td>2.795918</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>min</th>\n",
       "      <td>34.500000</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25%</th>\n",
       "      <td>42.100000</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>50%</th>\n",
       "      <td>45.300000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>75%</th>\n",
       "      <td>52.900000</td>\n",
       "      <td>4.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>max</th>\n",
       "      <td>245.100000</td>\n",
       "      <td>10.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                μsec     backtracks\n",
       "count  330155.000000  330155.000000\n",
       "mean       48.805696       2.312011\n",
       "std        10.164409       2.795918\n",
       "min        34.500000       0.000000\n",
       "25%        42.100000       0.000000\n",
       "50%        45.300000       1.000000\n",
       "75%        52.900000       4.000000\n",
       "max       245.100000      10.000000"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick = sudata[sudata['backtracks'] <= 10]\n",
    "quick.describe()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYkAAAEICAYAAACqMQjAAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAfUUlEQVR4nO3df5RdZX3v8feniSgimEBkbiBIsARbJBZxJOmVZUfSQgDb0LWgDXIlYLrSeqFKm7sugdt74xJp8VZAWWJqlEiwSOACSqpoGKPnKiwSSZQCIXAzhkjGxERMgAxUMfF7/9jPITsne8+c+XXOnJnPa62z5pzvfvazf2SffGc/+5nnUURgZmZW5HeavQNmZjZyOUmYmVkpJwkzMyvlJGFmZqWcJMzMrJSThJmZlXKSaAJJWyT98RDW1yGpe6jq6+e2Py7pX5uxbTMbfk4So1wzE4iZtT4nCUPS+Gbvg5mNTE4SzfMeSU9J2i3py5LeIGmipG9I+kWKf0PSlOoKko5MZbel5V8vqljSR1PdxwPfAo6R1JNex6Qmonsk/aukl4BLJZ0u6RFJL0jaLulzkg7J1fkOSZ2SdknaIemagu2+TtKdku6VdEiqc52kl9I6Nw7DebQxRlJIOjH3+TZJn0zvJ6XvzQvpWv2BpN9Jy45J1+YvJD0r6aO5OsZJukbSTyTtkbRe0nGNP7qRx0mieS4GzgZ+FzgJ+Aeyf48vA8cDbwX+A/hcbp2vAG8E3gEcDdxUW6mk/wlcCvxRRPwUOAfYFhFvSq9tqegc4B5gAnAHsA/4O2AS8IfALOC/pjoPB74DfBs4BjgRWF2z3UOBrwO/Bv4iIl4FPgt8NiKOSMd5d/9Pk1m/LAS6gbcAbcA1QKRE8W/AvwPHkl3fV0o6O63398BFwLnAEcCHgVcau+sjk5NE83wuIrZGxC7gOuCiiPhlRNwbEa9ExJ4U/yMASZPJ/sP/m4jYHRG/iYj/m6tP6Tf1s4H3R8Qv+tj+IxHx9Yj4bUT8R0Ssj4g1EbE3IrYAX6huG/gA8POIuCEifhUReyJiba6uI8gSyE+AyyJiX4r/BjhR0qSI6ImINQM8V2b1+g0wGTg+fUd+ENkAde8B3hIRn4iIVyNiM/BFYG5a76+Af4iIZyLz7xHxy+YcwsjiJNE8W3Pvf0rWJPRGSV+Q9NPUDPR9YIKkccBxwK6I2F1S3wRgAfBPEfFiP7ePpJPSbfrP07b/keyugrTtn/RS10zgncD1ceCIkfPJ7pKelvSopA/UsV9mg/HPQBfwoKTNkhal+PFk37EXqi+yu4y2tLyva3zMcpJonnx751uBbWS3ym8HZqQmmvel5SL7T/1ISRNK6ttN9hv/lyW9NxcvG+a3Nr4EeBqYlrZ9Tdouadu/28uxPAj8E7BaUvVLR0RsioiLyJrGPgXcI+mwXuoxq9cbcu9f+06ku9yFEfE24E+Bv5c0i+wafjYiJuReh0fEuWnVvq7xMctJonkulzRF0pFk/yHfBRxO9hzihRRfXC0cEdvJHkJ/Pj3gfp2k9+UrjIgK2bOOr0makcI7gKMkvbmP/TkceAnokfR7wEdyy74B/CdJV0p6vaTDc/VXt/2/ga+SJYpJAJL+i6S3RMRvgRdS0X2YDd5l6WHzqWTPFw5P34kPSDpRksiu533p9UPgJUlXSTo0rXuKpPek+r4EXCtpmjLvlHRUU45shHGSaJ6vkv0Gvjm9Pgl8BjgUeB5YQ9bOn/chsjbXp4GdwJW1lUZEJ3AZsFLSuyPiaeBOYHO6zT6mZH/+G/BBYA9ZW+1duTr3AH9C9pvZz4FNwPsLtn0t2cPr76QkNxvYIKmH7CH23Ij4Ve+nxawubwS2k12r/wuYB5wJTCPrZNEDPAJ8PiIq6TnZnwKnAs+Sfce+BFR/ebqRrGPFg2TJ5Vay7+KYJ086ZGatRFKQNYt2NXtfxgLfSZiZWSknCTMzK+XmJjMzK+U7CTMzKzXqBnabNGlSTJ069aD4yy+/zGGHuYs++FzklZ2L9evXPx8Rb2nCLvVb2TXfKsby9TiSjr3smh91SWLq1KmsW7fuoHilUqGjo6PxOzQC+VzsV3YuJP208XszMGXXfKsYy9fjSDr2smvezU1mZlbKScLMzEr1mSQkLZO0U9KTudg/S3pa0uOSvpYfT0jS1ZK6JD2TG4YXSbNTrCs36BaSTpC0VtImSXcpzWGQhn+4K5VfK2nqUB20mZnVp547idvIhlfI6wROiYh3Av8PuBpA0slkQ+++I63z+TRGyjjgFrKhrk8GLkplIRv47aaImEY2SN38FJ8P7I6IE8nmTfjUgI7QzMwGrM8kERHfB3bVxB6MiL3p4xqgOnvaHGBFRPw6Ip4lG7L39PTqiojNaTKaFcCcNAjXmWST3wAsB87P1bU8vb8HmJXKm5lZgwzFM4kPk41OCtmMT/l5CrpTrCx+FPBCLuFU4wfUlZa/mMqbmVmDDKoLrKT/Aewlm/4S9s8/kBcUJ6PopXxvdRXtxwKyCXdoa2ujUqkcVKanp6cwPhb5XOznc2HWuwEnCUnzyCa5mZWbjaybAyfTmUI2mQ4l8efJZl4bn+4W8uWrdXVLGk82pO8BzV5VEbEUWArQ3t4eRf2OR1J/5GbzudjP58KsdwNqbpI0G7gK+LOIyE8WvhKYm3omnUA2tvsPgUeBaakn0yFkD7dXpuTyPeCCtP484P5cXfPS+wuA74YHmrIG2Lp1K8BJkjZK2iDpYwCSPi7pZ5IeS6/qrGbu1WejVp93EpLuBDqASZK6yWZLuxp4PdCZniWviYi/iYgNku4GniJrhro8TfaBpCuAVcA4YFlEbEibuApYIemTwI/JJvsg/fyKpC6yO4jqhOUDNnXRN+sqt+X68wa7KWth48ePB+iOiJMlHQ6sl9SZFt8UEZ/Ol6/p1XcM2aRLJ6XFt5BN2NQNPCppZUQ8xf5efSsk/QtZb74l5Hr1SZqbyv3lQI+l3msefN1bsT6TRJqjuNatBbFq+euA6wriDwAPFMQ3k/V+qo3/Criwr/0zG2qTJ08GeAWyWfkkbWR/h4oir/XqA55Nv9hUr+mudI0jqdqrbyNZr74PpjLLgY+TJYk56T1kvfo+J0m+i7Zm8V9cm/UiNfe8C1ibQlekPyJdJmliirlXn41ao26AP7OhIulNwL3AlRHxkqQlwLVkveyuBW4g6wLe8F599fToA1g4fW9hvEizenmN5R5mrXDsThJmxUSWIO6IiPsAImLHawulLwLfSB8b3quvnh59AJf255nExcV1DLex3MOsFY7dzU1mNVLz//HAxoi4sRqXNDlX7M+B6nhm7tVno5bvJMxqPPzww5A9BzhT0mMpfA3ZmGOnkjX/bAH+GmCk9+ozGwwnCbMaZ5xxBsD6iGivWXRQ77wq9+qz0crNTWZmVspJwszMSjlJmJlZKScJMzMr5SRhZmalnCTMzKyUk4SZmZVykjAzs1JOEmZmVspJwszMSjlJmJlZKScJMzMr5SRhZmalnCTMzKyUk4SZmZVykjAzs1JOEmZmVspJwszMSjlJmJlZKScJMzMr1WeSkLRM0k5JT+ZiR0rqlLQp/ZyY4pJ0s6QuSY9LOi23zrxUfpOkebn4uyU9kda5WZJ624aZmTVOPXcStwGza2KLgNURMQ1YnT4DnANMS68FwBLI/sMHFgMzgNOBxbn/9JekstX1ZvexDTMza5A+k0REfB/YVROeAyxP75cD5+fit0dmDTBB0mTgbKAzInZFxG6gE5idlh0REY9ERAC319RVtA0zM2uQgT6TaIuI7QDp59EpfiywNVeuO8V6i3cXxHvbhpmZNcj4Ia5PBbEYQLx/G5UWkDVZ0dbWRqVSOahMT08PC6fvq6u+ovVHk56enlF/jPXyuTDr3UCTxA5JkyNie2oy2pni3cBxuXJTgG0p3lETr6T4lILyvW3jIBGxFFgK0N7eHh0dHQeVqVQq3PDQy3Ud3JaLD15/NKlUKhSdo7HI58KsdwNtbloJVHsozQPuz8UvSb2cZgIvpqaiVcBZkiamB9ZnAavSsj2SZqZeTZfU1FW0DTMza5A+7yQk3Ul2FzBJUjdZL6XrgbslzQeeAy5MxR8AzgW6gFeAywAiYpeka4FHU7lPRET1YfhHyHpQHQp8K73oZRtmZtYgfSaJiLioZNGsgrIBXF5SzzJgWUF8HXBKQfyXRdswM7PG8V9cm5lZKScJMzMr5SRhZmalnCTMamzduhXgJEkbJW2Q9DHwmGU2NjlJmNUYP348QHdE/D4wE7hc0sl4zDIbg5wkzGpMnjwZsi7cRMQeYCPZcDEes8zGnKEelsNsVJE0FXgXsJaa8cQkDfuYZblt1O5Xn0PRACycvreOo8w0a3iSsTw0Siscu5OEWQlJbwLuBa6MiJfSY4PCogWxYR2zrJ6haAAuXfTNuuts1nA0Y3lolFY4djc3mRUTWYK4IyLuS7EdqamIfoxZVhbvdcyygm2YNYWThFmN7DEBxwMbI+LG3CKPWWZjjpubzGo8/PDDAEcBZ0p6LIWvwWOW2RjkJGFW44wzzgBYHxHtBYs9ZpmNKW5uMjOzUk4SZmZWyknCzMxKOUmYmVkpJwkzMyvlJGFmZqWcJMzMrJSThJmZlXKSMDOzUk4SZmZWyknCzMxKOUmYmVkpJwkzMyvlJGFmZqUGlSQk/Z2kDZKelHSnpDdIOkHSWkmbJN0l6ZBU9vXpc1daPjVXz9Up/oyks3Px2SnWJWnRYPbVzMz6b8BJQtKxwEeB9og4BRgHzAU+BdwUEdOA3cD8tMp8YHdEnAjclMoh6eS03juA2cDnJY2TNA64BTgHOBm4KJU1M7MGGWxz03jgUEnjgTcC24EzgXvS8uXA+en9nPSZtHxWmrpxDrAiIn4dEc+Sze51enp1RcTmiHgVWJHKmplZgww4SUTEz4BPk02xuB14EVgPvBARe1OxbuDY9P5YYGtad28qf1Q+XrNOWdzMzBpkwNOXpond5wAnAC8A/4esaahWVFcpWVYWL0pgURBD0gJgAUBbWxuVSuWgMj09PSycvq9o9YMUrT+a9PT0jPpjrJfPhVnvBjPH9R8Dz0bELwAk3Qf8Z2CCpPHpbmEKsC2V7waOA7pT89SbgV25eFV+nbL4ASJiKbAUoL29PTo6Og4qU6lUuOGhl+s6sC0XH7z+aFKpVCg6R2ORz4VZ7wbzTOI5YKakN6ZnC7OAp4DvARekMvOA+9P7lekzafl30wTyK4G5qffTCcA04IfAo8C01FvqELKH2ysHsb9mZtZPA76TiIi1ku4BfgTsBX5M9tv8N4EVkj6ZYremVW4FviKpi+wOYm6qZ4Oku8kSzF7g8ojYByDpCmAVWc+pZRGxYaD7a2Zm/TeY5iYiYjGwuCa8maxnUm3ZXwEXltRzHXBdQfwB4IHB7KOZmQ2c/+LazMxKOUmYmVkpJwkzMyvlJGFmZqWcJMzMrJSThJmZlXKSMDOzUk4SZmZWyknCzMxKOUmYFZsqaaekJ6sBSR+X9DNJj6XXubll/ZpdcSAzOJo1w6CG5Rjtpi76Zt1lt1x/3jDuiTXB88AHgdtr4jdFxKfzgZrZFY8BviPppLT4FuBPyEY7flTSyoh4iv0zOK6Q9C9kMzcuITeDo6TqTI9/OSxHaFYH30mYFeshG4iyHv2aXTGNmtzfGRzNmsJ3Emb9c4WkS4B1wMKI2E02Y+KaXJn8LIq1syvOIJuRsa4ZHCVVZ3B8Pr8T9Uy0BbBw+t7CeJFmTb40lid+aoVjd5Iwq98S4FqyGRKvBW4APkz/Z1csK08fy/YH6phoC+DS/jSZNmmyrbE88VMrHLubm8zqFBE7ImJfRPwW+CL7h8Qvm12xLP48aQbHmvgBddXM4GjWFE4SZnWSNDn38c+Bas+nfs2umGZk7O8MjmZN4eYms2InAI8AkyR1k02u1SHpVLLmny3AX8OAZ1e8in7M4GjWLE4SZsWejYj2mtithSXp/+yKEdHvGRzNmsHNTWZmVspJwszMSjlJmJlZKScJMzMr5SRhZmalnCTMzKyUk4SZmZVykjAzs1KDShKSJki6R9LTkjZK+kNJR0rqTJOpdEqamMpK0s1pMpXHJZ2Wq2deKr9J0rxc/N2Snkjr3Owhk83MGmuwdxKfBb4dEb8H/AGwEVgErI6IacDq9BngHLIxbaaRDXG8BEDSkWRDHswg+wvUxdXEksosyK03e5D7a2Zm/TDgJCHpCOB9pKEKIuLViHiBAydNqZ1M5fbIrCEbBXMycDbQGRG70tj8ncDstOyIiHgkDXB2e64uMzNrgMHcSbwN+AXwZUk/lvQlSYcBbRGxHSD9PDqVf20ylaQ60Upv8e6CuJmZNchgBvgbD5wG/G1ErJX0WfY3LRUpm0ylv/GDK65jlq6enh4WTt/Xy+7tV12/FWb1GohWmA2rUXwuzHo3mCTRDXRHxNr0+R6yJLFD0uSI2J6ajHbmypdNzNJRE6+k+JSC8gepZ5auSqXCDQ+9XNeBVWfoaoVZvQaiFWbDahSfC7PeDbi5KSJ+DmyV9PYUmkU2nn5+0pTayVQuSb2cZgIvpuaoVcBZkiamB9ZnAavSsj2SZqZeTZfk6jIzswYY7HwSfwvckWbd2gxcRpZ47pY0H3iO/WPjPwCcC3QBr6SyRMQuSdeSzeIF8ImIqE7X+BHgNuBQ4FvpZWZmDTKoJBERjwG1E7NAdldRWzaAy0vqWQYsK4ivA04ZzD6amdnA+S+uzcyslJOEmZmVcpIwM7NSThJmZlbKScLMzEo5SZiZWSknCTMzK+UkYWZmpZwkzMyslJOEmZmVcpIwM7NSThJmZlbKScLMzEo5SZiZWSknCTMzK+UkYVZsqqSdkp6sBiQdKalT0qb0c2KKS9LNkrokPS7ptNw681L5TZLm5eLvlvREWufmNPti6TbMmsVJwqzY88DsmtgiYHVETANWp88A5wDT0msBsASy//CBxcAM4HRgce4//SWpbHW92X1sw6wpnCTMivUAu2pic4Dl6f1y4Pxc/PbIrAEmSJoMnA10RsSuiNgNdAKz07IjIuKRNGPj7TV1FW3DrCkGO8e12VjSFhHbASJiu6SjU/xYYGuuXHeK9RbvLoj3to0DSFpAdidCW1sblUqlcIcXTt9b77GV1jHcenp6mrbtZmuFY3eSMBs8FcRiAPG6RcRSYClAe3t7dHR0FJa7dNE3665zy8XFdQy3SqVC2f6Pdq1w7G5uMqvfjtRURPq5M8W7geNy5aYA2/qITymI97YNs6ZwkjCr30qg2kNpHnB/Ln5J6uU0E3gxNRmtAs6SNDE9sD4LWJWW7ZE0M/VquqSmrqJtmDWFm5vMip0APAJMktRN1kvpeuBuSfOB54ALU9kHgHOBLuAV4DKAiNgl6Vrg0VTuExFRfRj+EeA24FDgW+lFL9swawonCbNiz0ZEe0F8Vm0g9VC6vKiSiFgGLCuIrwNOKYj/smgbZs3i5iYzMyvlJGFmZqWcJMzMrNSgk4SkcZJ+LOkb6fMJktamsWfuknRIir8+fe5Ky6fm6rg6xZ+RdHYuPjvFuiR5eAIzswYbijuJjwEbc58/BdyUxp7ZDcxP8fnA7og4EbgplUPSycBc4B1k49d8PiWeccAtZOPinAxclMqamVmDDCpJSJoCnAd8KX0WcCZwTypSO75NdUyae4BZqfwcYEVE/DoiniXrRnh6enVFxOaIeBVYkcqamVmDDLYL7GeA/w4cnj4fBbwQEdUBY/Jj0rw2jk1E7JX0Yip/LLAmV2d+ndpxb2YU7UQ949j09PSwcPq+ug6qun4rjHszEK0wXkyj+FyY9W7ASULSB4CdEbFeUkc1XFA0+lhWFi+6yykc36aecWwqlQo3PPRy0eoHqY5h0wrj3gxEK4wX0yg+F2a9G8ydxHuBP5N0LvAG4AiyO4sJksanu4n8mDTVcWy6JY0H3kw2FHPZ+Db0EjczswYY8DOJiLg6IqZExFSyB8/fjYiLge8BF6RitePbVMekuSCVjxSfm3o/nUA2AcsPyYYymJZ6Sx2StrFyoPtrZmb9NxzDclwFrJD0SeDHwK0pfivwFUldZHcQcwEiYoOku4GngL3A5RGxD0DSFWSDpI0DlkXEhmHYXzMzKzEkSSIiKkAlvd9M1jOptsyvKBmsLCKuA64riD9ANniamZk1gf/i2szMSjlJmJlZKScJMzMr5SRhZmalnCTMzKyUk4SZmZVykjAzs1JOEmZmVspJwszMSg3HsBxm1qKm9mfk4+vPG8Y9sZHCdxJmZlbKScLMzEo5SZiZWSknCTMzK+UkYWZmpZwkzMyslLvADiF3HzSz0cZ3EmZmVsp3Ek3kOw8zG+l8J2FmZqWcJMz6SdIWSU9IekzSuhQ7UlKnpE3p58QUl6SbJXVJelzSabl65qXymyTNy8XfnervSuuq8UdplnGSMBuY90fEqRHRnj4vAlZHxDRgdfoMcA4wLb0WAEsgSyrAYmAGcDqwuJpYUpkFufVmD//hmBVzkjAbGnOA5en9cuD8XPz2yKwBJkiaDJwNdEbErojYDXQCs9OyIyLikYgI4PZcXWYN5wfXZv0XwIOSAvhCRCwF2iJiO0BEbJd0dCp7LLA1t253ivUW7y6IH0DSArK7Ddra2qhUKoU7unD63roPqlKp9Lv8UOjp6RmyulpNKxy7k4RZ/703IralRNAp6eleyhY9T4gBxA8MZIlpKUB7e3t0dHQUbvzS/vSgu7ij3+WHQqVSoWz/R7tWOHY3N5n1U0RsSz93Al8je6awIzUVkX7uTMW7geNyq08BtvURn1IQN2uKAScJScdJ+p6kjZI2SPpYiruXh41akg6TdHj1PXAW8CSwEqheu/OA+9P7lcAl6fqfCbyYmqVWAWdJmpi+I2cBq9KyPZJmpuv9klxdZg03mOamvcDCiPhR+tKsl9QJXErWy+N6SYvIenlcxYG9PGaQ9eCYkevl0U52W71e0sr0MK/ay2MN8ABZL49vDWKfW5r/+G5EaAO+ln5fGQ98NSK+LelR4G5J84HngAtT+QeAc4Eu4BXgMoCI2CXpWuDRVO4TEbErvf8IcBtwKNn1PmaveWu+ASeJ9BtP9UHdHkkbyR6wzQE6UrHlQIUsSbzWywNYI6nay6OD1MsDICWa2ZIqpF4eKV7t5eEvjDVNRGwG/qAg/ktgVkE8gMtL6loGLCuIrwNOGfTOmg2BIXlwLWkq8C5gLQ3u5ZG232dPj56eHhZO31fX8VTXH+6eIc3qedIKPSoaxefCrHeDThKS3gTcC1wZES/18thgWHp5QH09PSqVCjc89HLZvh2g2mtjuHuGNKvnSSv0qGgUnwuz3g2qd5Ok15EliDsi4r4Udi8PM7NRYjC9mwTcCmyMiBtzi9zLw8xslBhMc9N7gQ8BT0h6LMWuAa7HvTzMzEaFwfRueoji5wbgXh5mZqOC/+LazMxKOUmYmVkpJwkzMyvlUWBHsbJhPBZO33vQ31x4GA8zK+I7CTMzK+UkYWZmpZwkzMyslJ9J2Gs8FLmZ1XKSsEGpN7E4qZi1Jjc3mZlZKScJMzMr5eYmayg/9zBrLb6TMDOzUr6TsBHNdx5mzeUkYaOKk4rZ0HJzk5mZlXKSMDOzUk4SZmZWyknCzMxKOUmYmVkpJwkzMyvlJGFmZqWcJMzMrJT/mM7MBsx/vDj6+U7CzMxKOUmYmVmpEZ8kJM2W9IykLkmLmr0/Zo3g695GihGdJCSNA24BzgFOBi6SdHJz98psePm6t5FkpD+4Ph3oiojNAJJWAHOAp5q6V2bDa9Re90UPuhdO38ulBfEt15/nB+MjgCKi2ftQStIFwOyI+Kv0+UPAjIi4oqbcAmBB+vh24JmC6iYBzw/j7rYSn4v9ys7F8RHxlkbvDNR33dd5zbeKsXw9jqRjL7zmR/qdhApiB2W1iFgKLO21ImldRLQP1Y61Mp+L/Ubouejzuq/nmm8VI/TfoCFa4dhH9DMJoBs4Lvd5CrCtSfti1ii+7m3EGOlJ4lFgmqQTJB0CzAVWNnmfzIabr3sbMUZ0c1NE7JV0BbAKGAcsi4gNA6xuVNyaDxGfi/1G3LkY4uu+FYy4f4MGGvHHPqIfXJuZWXON9OYmMzNrIicJMzMrNeqThIc32E/SFklPSHpM0rpm708jSVomaaekJ3OxIyV1StqUfk5s5j6ORv0578rcnL6rj0s6rXl7PniSjpP0PUkbJW2Q9LEUb6njH9VJwsMbFHp/RJw60vtmD4PbgNk1sUXA6oiYBqxOn21o3Ub95/0cYFp6LQCWNGgfh8teYGFE/D4wE7g8/f/TUsc/qpMEueENIuJVoDq8gY0xEfF9YFdNeA6wPL1fDpzf0J0aA/p53ucAt0dmDTBB0uTG7OnQi4jtEfGj9H4PsBE4lhY7/tGeJI4FtuY+d6fYWBXAg5LWp2Edxrq2iNgO2RcaOLrJ+zNWlJ33Uft9lTQVeBewlhY7/hH9dxJDoK5hPcaQ90bENklHA52Snk6/6ZmNBKPy+yrpTcC9wJUR8ZJUdJhZ0YJY049/tN9JeHiDnIjYln7uBL5G1hw3lu2o3s6nnzubvD9jRdl5H3XfV0mvI0sQd0TEfSncUsc/2pOEhzdIJB0m6fDqe+As4Mne1xr1VgLz0vt5wP1N3JexpOy8rwQuSb18ZgIvVptlWpGyW4ZbgY0RcWNuUUsd/6j/i2tJ5wKfYf/wBtc1eZeaQtLbyO4eIGtm/OpYOheS7gQ6yIZm3gEsBr4O3A28FXgOuDAiah+y2iD057yn/1Q/R9Yb6hXgsoho2a7aks4AfgA8Afw2ha8hey7RMsc/6pOEmZkN3GhvbjIzs0FwkjAzs1JOEmZmVspJwszMSjlJmJlZKScJMzMr5SRhZmal/j84bQeaLxjjPAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "quick.hist(rwidth=.9, bins=11);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Verifying Correctness\n",
    "\n",
    "How do we know this program (or any program) is correct? Traditionally, there are four kinds of evidence:\n",
    "- A large number of example input/output pairs that give the right answer.\n",
    "- Manual inspection of a smaller number of example input/output pairs.\n",
    "- A suite of unit tests to verify that components function properly (at least on some inputs).\n",
    "- A formal roof that the code is correct (or at least an outline of an argument for a partial proof).\n",
    "\n",
    "For this program:\n",
    "- Unless `-noverify` is given, every puzzle/solution pair is verified with the `verify` method to make sure:\n",
    "  - Each square in the solution contains a single digit. \n",
    "  - Each unit in the solution contains all nine digits.\n",
    "  - Squares in the puzzle that are filled with a digit keep that same digit in the solution.\n",
    "- I have looked at some example solutions and double-checked some with an [online Sudoku](https://sudokuspoiler.azurewebsites.net/) program. [LGTM](https://www.dictionary.com/e/acronyms/lgtm/).\n",
    "- The `-u` option runs a suite of unit tests.\n",
    "- I have looked at the code carefully, but I am nowhere near a proof of correctness.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unit tests pass.\n"
     ]
    }
   ],
   "source": [
    "!java Sudoku -u  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can manually inspect these puzzle/solution pairs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Puzzle 1:                   Solution:\n",
      "8 5 . | . . 2 | 4 . .       8 5 9 | 6 1 2 | 4 3 7 \n",
      "7 2 . | . . . | . . 9       7 2 3 | 8 5 4 | 1 6 9 \n",
      ". . 4 | . . . | . . .       1 6 4 | 3 7 9 | 5 2 8 \n",
      "------+-------+------       ------+-------+------\n",
      ". . . | 1 . 7 | . . 2       9 8 6 | 1 4 7 | 3 5 2 \n",
      "3 . 5 | . . . | 9 . .       3 7 5 | 2 6 8 | 9 1 4 \n",
      ". 4 . | . . . | . . .       2 4 1 | 5 9 3 | 7 8 6 \n",
      "------+-------+------       ------+-------+------\n",
      ". . . | . 8 . | . 7 .       4 3 2 | 9 8 1 | 6 7 5 \n",
      ". 1 7 | . . . | . . .       6 1 7 | 4 2 5 | 8 9 3 \n",
      ". . . | . 3 6 | . 4 .       5 9 8 | 7 3 6 | 2 4 1 \n",
      "\n",
      "Puzzle 2:                   Solution:\n",
      ". . 5 | 3 . . | . . .       1 4 5 | 3 2 7 | 6 9 8 \n",
      "8 . . | . . . | . 2 .       8 3 9 | 6 5 4 | 1 2 7 \n",
      ". 7 . | . 1 . | 5 . .       6 7 2 | 9 1 8 | 5 4 3 \n",
      "------+-------+------       ------+-------+------\n",
      "4 . . | . . 5 | 3 . .       4 9 6 | 1 8 5 | 3 7 2 \n",
      ". 1 . | . 7 . | . . 6       2 1 8 | 4 7 3 | 9 5 6 \n",
      ". . 3 | 2 . . | . 8 .       7 5 3 | 2 9 6 | 4 8 1 \n",
      "------+-------+------       ------+-------+------\n",
      ". 6 . | 5 . . | . . 9       3 6 7 | 5 4 2 | 8 1 9 \n",
      ". . 4 | . . . | . 3 .       9 8 4 | 7 6 1 | 2 3 5 \n",
      ". . . | . . 9 | 7 . .       5 2 1 | 8 3 9 | 7 6 4 \n",
      "\n",
      "Puzzle 3:                   Solution:\n",
      "1 2 . | . 4 . | . . .       1 2 8 | 5 4 7 | 6 3 9 \n",
      ". . 5 | . 6 9 | . 1 .       3 4 5 | 8 6 9 | 2 1 7 \n",
      ". . 9 | . . . | 5 . .       6 7 9 | 2 1 3 | 5 4 8 \n",
      "------+-------+------       ------+-------+------\n",
      ". . . | . . . | . 7 .       9 1 2 | 4 8 6 | 3 7 5 \n",
      "7 . . | . 5 2 | . 9 .       7 8 4 | 3 5 2 | 1 9 6 \n",
      ". 3 . | . . . | . . 2       5 3 6 | 7 9 1 | 4 8 2 \n",
      "------+-------+------       ------+-------+------\n",
      ". 9 . | 6 . . | . 5 .       8 9 1 | 6 2 4 | 7 5 3 \n",
      "4 . . | 9 . . | 8 . 1       4 6 7 | 9 3 5 | 8 2 1 \n",
      ". . 3 | . . . | 9 . 4       2 5 3 | 1 7 8 | 9 6 4 \n",
      "\n",
      "Puzzle 4:                   Solution:\n",
      ". . . | 5 7 . | . 3 .       6 2 4 | 5 7 8 | 1 3 9 \n",
      "1 . . | . . . | . 2 .       1 3 5 | 4 9 6 | 8 2 7 \n",
      "7 . . | . 2 3 | 4 . .       7 8 9 | 1 2 3 | 4 5 6 \n",
      "------+-------+------       ------+-------+------\n",
      ". . . | . 8 . | . . 4       2 1 6 | 3 8 5 | 7 9 4 \n",
      ". . 7 | . . 4 | . . .       8 5 7 | 9 6 4 | 2 1 3 \n",
      "4 9 . | . . . | 6 . 5       4 9 3 | 2 1 7 | 6 8 5 \n",
      "------+-------+------       ------+-------+------\n",
      ". 4 2 | . . . | 3 . .       9 4 2 | 6 5 1 | 3 7 8 \n",
      ". . . | 7 . . | 9 . .       5 6 8 | 7 3 2 | 9 4 1 \n",
      ". . 1 | 8 . . | . . .       3 7 1 | 8 4 9 | 5 6 2 \n",
      "\n",
      "Puzzle 5:                   Solution:\n",
      "1 . . | . . 7 | . 9 .       1 6 2 | 8 5 7 | 4 9 3 \n",
      ". 3 . | . 2 . | . . 8       5 3 4 | 1 2 9 | 6 7 8 \n",
      ". . 9 | 6 . . | 5 . .       7 8 9 | 6 4 3 | 5 2 1 \n",
      "------+-------+------       ------+-------+------\n",
      ". . 5 | 3 . . | 9 . .       4 7 5 | 3 1 2 | 9 8 6 \n",
      ". 1 . | . 8 . | . . 2       9 1 3 | 5 8 6 | 7 4 2 \n",
      "6 . . | . . 4 | . . .       6 2 8 | 7 9 4 | 1 3 5 \n",
      "------+-------+------       ------+-------+------\n",
      "3 . . | . . . | . 1 .       3 5 6 | 4 7 8 | 2 1 9 \n",
      ". 4 . | . . . | . . 7       2 4 1 | 9 3 5 | 8 6 7 \n",
      ". . 7 | . . . | 3 . .       8 9 7 | 2 6 1 | 3 5 4 \n",
      "\n",
      "Puzzle 6:                   Solution:\n",
      "1 . . | . 3 4 | . 8 .       1 5 2 | 9 3 4 | 6 8 7 \n",
      ". . . | 8 . . | 5 . .       7 6 3 | 8 2 1 | 5 4 9 \n",
      ". . 4 | . 6 . | . 2 1       9 8 4 | 5 6 7 | 3 2 1 \n",
      "------+-------+------       ------+-------+------\n",
      ". 1 8 | . . . | . . .       6 1 8 | 4 9 3 | 2 7 5 \n",
      "3 . . | 1 . 2 | . . 6       3 7 5 | 1 8 2 | 4 9 6 \n",
      ". . . | . . . | 8 1 .       2 4 9 | 7 5 6 | 8 1 3 \n",
      "------+-------+------       ------+-------+------\n",
      "5 2 . | . 7 . | 9 . .       5 2 1 | 3 7 8 | 9 6 4 \n",
      ". . 6 | . . 9 | . . .       4 3 6 | 2 1 9 | 7 5 8 \n",
      ". 9 . | 6 4 . | . . 2       8 9 7 | 6 4 5 | 1 3 2 \n",
      "\n",
      "Puzzle 7:                   Solution:\n",
      ". . . | 9 2 . | . . .       3 8 7 | 9 2 6 | 4 1 5 \n",
      ". . 6 | 8 . 3 | . . .       5 4 6 | 8 1 3 | 9 7 2 \n",
      "1 9 . | . 7 . | . . 6       1 9 2 | 4 7 5 | 8 3 6 \n",
      "------+-------+------       ------+-------+------\n",
      "2 3 . | . 4 . | 1 . .       2 3 5 | 7 4 9 | 1 6 8 \n",
      ". . 1 | . . . | 7 . .       9 6 1 | 2 5 8 | 7 4 3 \n",
      ". . 8 | . 3 . | . 2 9       4 7 8 | 6 3 1 | 5 2 9 \n",
      "------+-------+------       ------+-------+------\n",
      "7 . . | . 8 . | . 9 1       7 5 4 | 3 8 2 | 6 9 1 \n",
      ". . . | 5 . 7 | 2 . .       6 1 3 | 5 9 7 | 2 8 4 \n",
      ". . . | . 6 4 | . . .       8 2 9 | 1 6 4 | 3 5 7 \n",
      "\n",
      "Puzzle 8:                   Solution:\n",
      ". 6 . | 5 . 4 | . 3 .       8 6 9 | 5 7 4 | 1 3 2 \n",
      "1 . . | . 9 . | . . 8       1 2 4 | 3 9 6 | 7 5 8 \n",
      ". . . | . . . | . . .       3 7 5 | 1 2 8 | 6 9 4 \n",
      "------+-------+------       ------+-------+------\n",
      "9 . . | . 5 . | . . 6       9 3 2 | 8 5 7 | 4 1 6 \n",
      ". 4 . | 6 . 2 | . 7 .       5 4 1 | 6 3 2 | 8 7 9 \n",
      "7 . . | . 4 . | . . 5       7 8 6 | 9 4 1 | 3 2 5 \n",
      "------+-------+------       ------+-------+------\n",
      ". . . | . . . | . . .       2 1 7 | 4 6 9 | 5 8 3 \n",
      "4 . . | . 8 . | . . 1       4 9 3 | 7 8 5 | 2 6 1 \n",
      ". 5 . | 2 . 3 | . 4 .       6 5 8 | 2 1 3 | 9 4 7 \n",
      "\n",
      "Puzzle 9:                   Solution:\n",
      "7 . . | . . . | 4 . .       7 9 8 | 6 3 5 | 4 2 1 \n",
      ". 2 . | . 7 . | . 8 .       1 2 6 | 9 7 4 | 5 8 3 \n",
      ". . 3 | . . 8 | . 7 9       4 5 3 | 2 1 8 | 6 7 9 \n",
      "------+-------+------       ------+-------+------\n",
      "9 . . | 5 . . | 3 . .       9 7 2 | 5 8 6 | 3 1 4 \n",
      ". 6 . | . 2 . | . 9 .       5 6 4 | 1 2 3 | 8 9 7 \n",
      ". . 1 | . 9 7 | . . 6       3 8 1 | 4 9 7 | 2 5 6 \n",
      "------+-------+------       ------+-------+------\n",
      ". . . | 3 . . | 9 . .       6 1 7 | 3 5 2 | 9 4 8 \n",
      ". 3 . | . 4 . | . 6 .       8 3 5 | 7 4 9 | 1 6 2 \n",
      ". . 9 | . . 1 | . 3 5       2 4 9 | 8 6 1 | 7 3 5 \n",
      "\n",
      "Puzzle 10:                  Solution:\n",
      ". . . | . 7 . | . 2 .       5 9 4 | 8 7 6 | 1 2 3 \n",
      "8 . . | . . . | . . 6       8 2 3 | 9 1 4 | 7 5 6 \n",
      ". 1 . | 2 . 5 | . . .       6 1 7 | 2 3 5 | 8 9 4 \n",
      "------+-------+------       ------+-------+------\n",
      "9 . 5 | 4 . . | . . 8       9 6 5 | 4 2 1 | 3 7 8 \n",
      ". . . | . . . | . . .       7 8 1 | 6 5 3 | 9 4 2 \n",
      "3 . . | . . 8 | 5 . 1       3 4 2 | 7 9 8 | 5 6 1 \n",
      "------+-------+------       ------+-------+------\n",
      ". . . | 3 . 2 | . 8 .       1 5 9 | 3 4 2 | 6 8 7 \n",
      "4 . . | . . . | . . 9       4 3 6 | 5 8 7 | 2 1 9 \n",
      ". 7 . | . 6 . | . . .       2 7 8 | 1 6 9 | 4 3 5 \n"
     ]
    }
   ],
   "source": [
    "!java Sudoku -grid -nofile hardest.txt "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What's Next?\n",
    "\n",
    "There are a few things I didn't get a chance to explore; maybe you can:\n",
    "\n",
    "- Would the program be even faster in Golang or C++ or Rust? Or with some more optimizations?\n",
    "- The depth-first search makes a choice to *fill* some square with a digit. What if instead the choice was to *eliminate* a digit from the square? At first glance it seems that would be slower, because more choices would be required, but would constraint propagation make it work well?\n",
    "- On each recursive call, the depth-first search copies the current grid into a new grid (re-using the one in `gridpool[level]`). That requires copying an array of 81 ints. Would it be faster to instead make changes directly to the current grid, and then undo the changes when failure is detected? You would need to keep track of the changes made so that they can be undone. My guess is that this would make the code more complex and not much faster (if any), but you might want to try it.\n",
    "- In the theory of constraint propagation, [shaving](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.175.7143&rep=rep1&type=pdf) means guessing a value for some variable, detecting a contradiction, and then keeping track of the fact that the value is not possible. But in our program, when we guess wrong we don't keep track of anything. Can the program be made faster by incorporating shaving?\n",
    "- Can you create an adversarial puzzle, where the program guesses wrong the maximal number of times? In other words, if you draw a tree of choices, what's a puzzle with a tree that has the solution in the bottom-right corner? How much time and how many backtracks does that puzzle take to solve?\n",
    "- What [other Sudoku strategies](https://bestofsudoku.com/sudoku-strategy) can be implemented? Can you find a suite of strategies that will solve all the puzzles with no search? \n",
    "- Can you develop a system to rank the difficulty of puzzles, based on the complexity of the strategies needed to solve it?\n",
    "- Can you explain the mystery of the outliers?\n",
    "\n",
    "One final word: I finally got around to writing this up after a friend mentioned to me \"*Hey, a while back didn't you do a Sudoku program that could solve like a dozen puzzles a second or something?*\" I felt like Robert Wagner when he had to explain to Dr. Evil that \"a million dollars isn't exactly a lot of money these days,\" or in this case \"12 Hz isn't exactly a lot of puzzles.\" So this is for all of you who were cryogenically frozen in 1967 (and for all of you who weren't).\n",
    "\n",
    "<center>\n",
    "<img src=\"https://upload.wikimedia.org/wikipedia/en/1/16/Drevil_million_dollars.jpg\">\n",
    "<br><i>\"One <b>dozen</b> puzzles per second\"</i>\n",
    "</center>"
   ]
  }
 ],
 "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
}