Puzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Aristotle Number Challenge\n",
    "\n",
    "I recently got a new wooden puzzle. And while it's usually fun to try to solve it manually, it's also very tempting to think of a way to solve it programmatically.\n",
    "\n",
    "This one doesn't escape the rule. And since it's about numbers and additions, seems to be even more suitable to \"computational brute-force\".\n",
    "\n",
    "## Representation\n",
    "\n",
    "The puzzle looks like this:\n",
    "\n",
    "![Puzzle photo](./puzzle.jpg)\n",
    "\n",
    "There are 15 rows and the goal is to make every row add up to 38.\n",
    "\n",
    "It can be represented as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "BOARD = '''\n",
    "..a.b.c..\n",
    ".d.e.f.g.\n",
    "h.i.j.k.l\n",
    ".m.n.o.p.\n",
    "..q.r.s..\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which corresponds to 15 equations, with all the numbers between 1 and 19 inclusive.\n",
    "\n",
    "### Rows\n",
    "\n",
    "$$  a + b + c = 38 $$\n",
    "\n",
    "$$ d + e + f + g = 38 $$\n",
    "\n",
    "$$ h + i + j + k + l = 38 $$\n",
    "\n",
    "$$  m + n + o + p = 38 $$\n",
    "\n",
    "$$ q + r + s = 38 $$\n",
    "\n",
    "### Left diagonals\n",
    "\n",
    "$$ a + d + h = 38 $$\n",
    "\n",
    "$$ b + e + i + m = 38 $$\n",
    "\n",
    "$$ c + f + j + n + q = 38 $$\n",
    "\n",
    "$$ g + k + o + r = 38 $$\n",
    "\n",
    "$$ l + p + s = 38 $$\n",
    "\n",
    "### Right diagonals\n",
    "\n",
    "$$ h + m + q = 38 $$\n",
    "\n",
    "$$ d + i + n + r = 38 $$\n",
    "\n",
    "$$ a + e + j + o + s = 38$$\n",
    "\n",
    "$$ b + f + k + p = 38 $$\n",
    "\n",
    "$$ c + g + l = 38 $$\n",
    "\n",
    "Writing the representation in Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from string import ascii_lowercase as letters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "N = 19\n",
    "TOTAL = 38\n",
    "ids = list(range(N))\n",
    "np.random.seed(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rather than copying the equations manually one by one, let's have a function that does it automatically given a board layout."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def generate_equations_from_board(board):\n",
    "    b = np.array([list(s) for s in board.split('\\n') if s], dtype=np.str)\n",
    "    res = [''.join(np.asarray(line)).replace('.', '') for line in b]\n",
    "    \n",
    "    def parse_diagonals(mat):\n",
    "        for i in range(-10, 10):\n",
    "            s = ''.join(np.asarray(np.diag(mat, i))).replace('.', '')\n",
    "            if s:\n",
    "                yield s\n",
    "                \n",
    "    res += list(parse_diagonals(b)) + list(parse_diagonals(np.rot90(b.T)))\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "equations = generate_equations_from_board(BOARD)\n",
    "n_eq = len(equations)\n",
    "goal = np.array([TOTAL] * n_eq)\n",
    "\n",
    "assert n_eq == 15"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's also define a function to print the solution with an hexagonal shape, so it's easier to visualize with the wooden puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def print_board(layout, values):\n",
    "    board = layout\n",
    "    for c in layout:\n",
    "        if c in letters:\n",
    "            board = board.replace(c, str(values[letters.index(c)]).zfill(2))\n",
    "    board = board.replace('.', '  ')\n",
    "    print(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That we can test with a random ordering:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    11  02  09    \n",
      "  19  15  17  07  \n",
      "05  03  06  14  10\n",
      "  08  18  12  04  \n",
      "    01  16  13    \n",
      "\n"
     ]
    }
   ],
   "source": [
    "print_board(BOARD, np.random.permutation(ids) + 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It looks good enough!\n",
    "\n",
    "There are a few ways to solve puzzle. In our case, we will look at two different approaches: stochastic and exact.\n",
    "\n",
    "## Simulated Annealing\n",
    "\n",
    "The first approach that we can try is called [Simulated Annealing](https://en.wikipedia.org/wiki/Simulated_annealing). I tend to think of it as the \"lazy\" option because we simply define the state of the problem and let the computer search a solution for us. Here are the steps involved:\n",
    "\n",
    "- Start from a random board.\n",
    "- Constantly swap two pieces and see if we are getting closer to the solution.\n",
    "- Sometimes, keep the new board even though it doesn't look better at first, because it might get better later (escaping the local minima).\n",
    "\n",
    "Let's first represent the system of linear equations as a matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],\n",
       "        [0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0],\n",
       "        [1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1],\n",
       "        [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],\n",
       "        [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = np.mat([[1 if letters[i] in eq else 0 for i in range(N)] for eq in equations])\n",
    "m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simulated annealing also requires two main functions:\n",
    "\n",
    "- `neighbor`: to generate a new board from the current one\n",
    "- `cost`: to evaluate the quality of the current board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def neighbor(board):\n",
    "    # take to pieces and swap them\n",
    "    new_board = np.array(board)\n",
    "    i, j = np.random.choice(ids, 2)\n",
    "    new_board[i], new_board[j] = new_board[j], new_board[i]\n",
    "    return new_board\n",
    "\n",
    "\n",
    "def cost(board):\n",
    "    # calculate how far the current board is from the goal board (full of 38)\n",
    "    v = board * m.T\n",
    "    return np.linalg.norm(goal - v, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can build on top of that and implement the simulated annealing routine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def solve_sa(layout):\n",
    "    np.random.seed(0)\n",
    "    # initial state: [1, 2, ..., 19]\n",
    "    solution = np.array(list(range(1, N + 1)))\n",
    "    curr_cost = cost(solution)\n",
    "    temp, alpha, it = 1.0, 0.995, 0\n",
    "    while curr_cost > 0:\n",
    "        new_solution = neighbor(solution)\n",
    "        new_cost = cost(new_solution)\n",
    "        diff = new_cost - curr_cost\n",
    "        if diff <= 0 or np.exp(-diff / temp) > np.random.rand():\n",
    "            solution = new_solution\n",
    "            curr_cost = new_cost\n",
    "\n",
    "        if it % 500 == 0 and temp > 0.2:\n",
    "            temp *= alpha\n",
    "            \n",
    "        it += 1\n",
    "    \n",
    "    print('Found after', it, 'iterations:\\n')\n",
    "    print_board(layout, solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found after 496207 iterations:\n",
      "\n",
      "\n",
      "    15  13  10    \n",
      "  14  08  04  12  \n",
      "09  06  05  02  16\n",
      "  11  01  07  19  \n",
      "    18  17  03    \n",
      "\n",
      "CPU times: user 41.3 s, sys: 133 ms, total: 41.4 s\n",
      "Wall time: 41.4 s\n"
     ]
    }
   ],
   "source": [
    "%time solve_sa(BOARD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes, we found a solution, even though it took some time. Numpy makes it handy to do matrix multiplications, but comes at a cost with lots of time spent creating arrays over and over.\n",
    "\n",
    "Another thing to notice: the parameters for the simulated annealing routine (temperature decay, minimum temperature...) were choosen after a few tries and influence quite a lot the time it takes for the algorithm to terminate.\n",
    "\n",
    "Alright, now the cool thing is that we can simply put the pieces of wood in the right order (and pretend to be thinking hard for the people watching behind):\n",
    "\n",
    "![Solution](./solution.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursive approach\n",
    "\n",
    "There is another way to tackle the puzzle, in a more exact and predictive manner.\n",
    "\n",
    "Here is the idea:\n",
    "\n",
    "- Place the pieces one by one and in order on the board\n",
    "- If the new configuration conflicts with the equations, remove the last piece and continue with the next one\n",
    "\n",
    "At first, it sounds like a brute-force approach. And it is. There are 19 pieces to place at 19 different spots, which gives:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1978419655660313589123979 configurations with repetition of numbers.\n",
      "121645100408832000 permutations.\n"
     ]
    }
   ],
   "source": [
    "from math import factorial\n",
    "print(19 ** 19, 'configurations with repetition of numbers.')\n",
    "print(factorial(19), 'permutations.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Needless to say that it is too big. Fortunately, brute forcing is still possible if we can prune many branches early when some of the equations are not met.\n",
    "\n",
    "Using the default board order:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "..a.b.c..\n",
      ".d.e.f.g.\n",
      "h.i.j.k.l\n",
      ".m.n.o.p.\n",
      "..q.r.s..\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(BOARD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initializing the board with zeros, and starting to place the pieces recursively (a, then b, then c), we get:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    01  02  03    \n",
      "  00  00  00  00  \n",
      "00  00  00  00  00\n",
      "  00  00  00  00  \n",
      "    00  00  00    \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tmp_board = [0] * N\n",
    "for pos, piece in enumerate('abc'):\n",
    "    tmp_board[letters.index(piece)] = pos + 1\n",
    "print_board(BOARD, tmp_board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first line is full, but the numbers don't add up to 38. In that case there is no need to continue placing the 16 other pieces and the branch can be cut early.\n",
    "\n",
    "The key part of the recursive approach can be implemented in a `is_valid` function which decides whether a board configuration is valid or not. A board is valid if **for each of the 15 equations**:\n",
    "\n",
    "- The equation is not full yet (less than 3 numbers known)\n",
    "- or the equation is full and the numbers add up to 38\n",
    "\n",
    "Instead of writing all the tests for the 15 equations by hand, we can once again generate them automatically:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Code:\n",
      "def is_valid(b):\n",
      "\treturn (((b[2] + b[1] + b[0] == 38) or not (b[2] and b[1] and b[0])) and\n",
      "\t\t((b[18] + b[17] + b[16] == 38) or not (b[18] and b[17] and b[16])) and\n",
      "\t\t((b[16] + b[12] + b[7] == 38) or not (b[16] and b[12] and b[7])) and\n",
      "\t\t((b[11] + b[6] + b[2] == 38) or not (b[11] and b[6] and b[2])) and\n",
      "\t\t((b[7] + b[3] + b[0] == 38) or not (b[7] and b[3] and b[0])) and\n",
      "\t\t((b[18] + b[15] + b[11] == 38) or not (b[18] and b[15] and b[11])) and\n",
      "\t\t((b[6] + b[5] + b[4] + b[3] == 38) or not (b[6] and b[5] and b[4] and b[3])) and\n",
      "\t\t((b[15] + b[14] + b[13] + b[12] == 38) or not (b[15] and b[14] and b[13] and b[12])) and\n",
      "\t\t((b[17] + b[13] + b[8] + b[3] == 38) or not (b[17] and b[13] and b[8] and b[3])) and\n",
      "\t\t((b[15] + b[10] + b[5] + b[1] == 38) or not (b[15] and b[10] and b[5] and b[1])) and\n",
      "\t\t((b[12] + b[8] + b[4] + b[1] == 38) or not (b[12] and b[8] and b[4] and b[1])) and\n",
      "\t\t((b[17] + b[14] + b[10] + b[6] == 38) or not (b[17] and b[14] and b[10] and b[6])) and\n",
      "\t\t((b[11] + b[10] + b[9] + b[8] + b[7] == 38) or not (b[11] and b[10] and b[9] and b[8] and b[7])) and\n",
      "\t\t((b[18] + b[14] + b[9] + b[4] + b[0] == 38) or not (b[18] and b[14] and b[9] and b[4] and b[0])) and\n",
      "\t\t((b[16] + b[13] + b[9] + b[5] + b[2] == 38) or not (b[16] and b[13] and b[9] and b[5] and b[2])))\n",
      "Evaluating the code...\n",
      "done.\n"
     ]
    }
   ],
   "source": [
    "def generate_is_valid_function(board):\n",
    "    eqs = generate_equations_from_board(board)\n",
    "    # check smaller equations first\n",
    "    eqs.sort(key=lambda eq: len(eq))\n",
    "    code = []\n",
    "    for eq in eqs:\n",
    "        # place the large positions first because they are more likely to\n",
    "        # be empty, which will make the test will fail faster\n",
    "        pos = [letters.index(c) for c in eq]\n",
    "        pos.sort(key=lambda p: -p)\n",
    "        summation = ' + '.join('b[%s]' % p for p in pos) + ' == %s' % TOTAL\n",
    "        full = ' and '.join('b[%s]' % p for p in pos)\n",
    "        code.append('((%s) or not (%s))' % (summation, full))\n",
    "    \n",
    "    return 'def is_valid(b):\\n\\treturn (' + ' and\\n\\t\\t'.join(code) + ')'\n",
    "    \n",
    "code = generate_is_valid_function(BOARD)\n",
    "\n",
    "print('Code:')\n",
    "print(code)\n",
    "\n",
    "print('Evaluating the code...')\n",
    "# 'is_valid' goes under the global scope\n",
    "exec(code)\n",
    "assert 'is_valid' in globals()\n",
    "print('done.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The recursive search implements the trial and error idea. The `find_all` parameter can be used to continue the search beyond the first match."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def solve_recursive(layout, find_all=False):\n",
    "    board = [0] * N\n",
    "    used = [0] * (N + 1)\n",
    "    \n",
    "    def place(i):\n",
    "        if i == N:\n",
    "            # base case, all the pieces are on the board\n",
    "            print_board(layout, board)\n",
    "            return not find_all\n",
    "        \n",
    "        for j in range(1, N + 1):\n",
    "            if used[j]:\n",
    "                # piece number j already used\n",
    "                continue\n",
    "                \n",
    "            # place the piece on the board\n",
    "            board[i] = j\n",
    "            used[j] = 1\n",
    "            \n",
    "            # stop the recursion if the current configuration\n",
    "            # is not valid or a solution has been found\n",
    "            if is_valid(board) and place(i + 1):\n",
    "                return True\n",
    "            \n",
    "            # remove the piece from the board\n",
    "            board[i] = 0\n",
    "            used[j] = 0\n",
    "            \n",
    "        return False\n",
    "    \n",
    "    place(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    03  17  18    \n",
      "  19  07  01  11  \n",
      "16  02  05  06  09\n",
      "  12  04  08  14  \n",
      "    10  13  15    \n",
      "\n",
      "CPU times: user 6.73 s, sys: 0 ns, total: 6.73 s\n",
      "Wall time: 6.73 s\n"
     ]
    }
   ],
   "source": [
    "%time solve_recursive(BOARD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The program terminates rather quickly compared to the stochastic approach. However, we notice that the first number is a 3, which means that it was still the beginning of the search.\n",
    "\n",
    "One speed improvement is to first check the equations with only 3 numbers, as they will fail the test quicker than equations with 4 or 5 numbers.\n",
    "\n",
    "It means that the board must be reordered to first fill the equations with 3 numbers, and then the others. The iteration goes through the numbers in order from 1 to 19, so the board can be reordered in a spiral manner:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    03  17  18    \n",
      "  19  07  01  11  \n",
      "16  02  05  06  09\n",
      "  12  04  08  14  \n",
      "    10  13  15    \n",
      "\n",
      "CPU times: user 493 ms, sys: 6.67 ms, total: 500 ms\n",
      "Wall time: 501 ms\n"
     ]
    }
   ],
   "source": [
    "ALT_BOARD = '''\n",
    "..a.b.c..\n",
    ".l.m.n.d.\n",
    "k.r.s.o.e\n",
    ".j.q.p.f.\n",
    "..i.h.g..\n",
    "'''\n",
    "exec(generate_is_valid_function(ALT_BOARD))\n",
    "%time solve_recursive(ALT_BOARD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same result, but much faster!\n",
    "\n",
    "Now that all the tools are defined, we can let the program run a bit longer to find other solutions, which will for most of them only be symetries of the one found above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    03  17  18    \n",
      "  19  07  01  11  \n",
      "16  02  05  06  09\n",
      "  12  04  08  14  \n",
      "    10  13  15    \n",
      "\n",
      "\n",
      "    03  19  16    \n",
      "  17  07  02  12  \n",
      "18  01  05  04  10\n",
      "  11  06  08  13  \n",
      "    09  14  15    \n",
      "\n",
      "\n",
      "    09  11  18    \n",
      "  14  06  01  17  \n",
      "15  08  05  07  03\n",
      "  13  04  02  19  \n",
      "    10  12  16    \n",
      "\n",
      "\n",
      "    09  14  15    \n",
      "  11  06  08  13  \n",
      "18  01  05  04  10\n",
      "  17  07  02  12  \n",
      "    03  19  16    \n",
      "\n",
      "\n",
      "    10  12  16    \n",
      "  13  04  02  19  \n",
      "15  08  05  07  03\n",
      "  14  06  01  17  \n",
      "    09  11  18    \n",
      "\n",
      "\n",
      "    10  13  15    \n",
      "  12  04  08  14  \n",
      "16  02  05  06  09\n",
      "  19  07  01  11  \n",
      "    03  17  18    \n",
      "\n",
      "\n",
      "    15  13  10    \n",
      "  14  08  04  12  \n",
      "09  06  05  02  16\n",
      "  11  01  07  19  \n",
      "    18  17  03    \n",
      "\n",
      "\n",
      "    15  14  09    \n",
      "  13  08  06  11  \n",
      "10  04  05  01  18\n",
      "  12  02  07  17  \n",
      "    16  19  03    \n",
      "\n",
      "\n",
      "    16  12  10    \n",
      "  19  02  04  13  \n",
      "03  07  05  08  15\n",
      "  17  01  06  14  \n",
      "    18  11  09    \n",
      "\n",
      "\n",
      "    16  19  03    \n",
      "  12  02  07  17  \n",
      "10  04  05  01  18\n",
      "  13  08  06  11  \n",
      "    15  14  09    \n",
      "\n",
      "\n",
      "    18  11  09    \n",
      "  17  01  06  14  \n",
      "03  07  05  08  15\n",
      "  19  02  04  13  \n",
      "    16  12  10    \n",
      "\n",
      "\n",
      "    18  17  03    \n",
      "  11  01  07  19  \n",
      "09  06  05  02  16\n",
      "  14  08  04  12  \n",
      "    15  13  10    \n",
      "\n",
      "CPU times: user 15.1 s, sys: 3.33 ms, total: 15.1 s\n",
      "Wall time: 15.1 s\n"
     ]
    }
   ],
   "source": [
    "%time solve_recursive(ALT_BOARD, find_all=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Take away\n",
    "\n",
    "Using the simulated annealing approach, we found one solution and stopped the program. It was quick to implement and didn't require deep thinking. It was however easily stuck in local optima, with most of the equations equal to 38 and a few equal to 37 or 39. It also required quite a lot of parameter tweaking (number of iterations and temperature decay) to get the program to converge fast.\n",
    "\n",
    "The second approach has the advantage of finding all the solutions rather quickly. It requires a bit more analysis and a better representation of the problem, but speeds up the search significantly.\n",
    "\n",
    "Regarding the execution speed, the Python program takes 12 seconds to output the 12 solutions, which is reasonnable. I implemented the same logic in C++ just by curiosity (available [here](//gist.githubusercontent.com/jtpio/2d80fce07761e783a88146722625e2ad/raw/314978bdbee355372d440ffa7977d7bb67c544c6/solver.cpp)), and the program terminates in a fraction of a second. If we want blazing fast programs, it is always possible to use a more adequate programming language for that!\n",
    "\n",
    "And that concludes it, for another toy puzzle shamelessly solved with code :)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

puzzle.jpg

solution.jpg

solver.cpp