Example 3 Snake Puzzle Solver.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Snake Puzzle from an Anonymous User"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modified slightly from Ref: https://notebooks.azure.com/anon-nrcbsq/libraries/puzzles/html/Snake%20Puzzle%20Solver.ipynb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Physical puzzles are a good way to connect computing and real tasks.  Here's an interesting one:\n",
    "\n",
    "![Boxed Snake Puzzle](http://www.craig-wood.com/nick/pub/snake-puzzle/snake-puzzle-boxed.jpg \"Boxed Snake Puzzle\")\n",
    "\n",
    "When you take it out the box it looks like this:\n",
    "\n",
    "![Solved Snake Puzzle](http://www.craig-wood.com/nick/pub/snake-puzzle/snake-puzzle-solved.jpg \"Solved Snake Puzzle\")\n",
    "\n",
    "When you take it apart it looks like this (which explains why it's called \"the snake puzzle\"):\n",
    "\n",
    "![Flat Snake Puzzle](http://www.craig-wood.com/nick/pub/snake-puzzle/snake-puzzle-flat.jpg \"Flat Snake Puzzle\")\n",
    "\n",
    "The way it works is that there is a piece of elastic running through each block.  On the majority of the blocks the elastic runs straight through, but on some of the it goes through a 90 degree bend.  The puzzle is trying to make it back into a cube.\n",
    "\n",
    "After playing with it a while you can find a solution, but can you find a mathematical way to solve it?\n",
    "\n",
    "The first thing to do is find a representation for the puzzle.  Here's one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# definition - number of straight bits, before 90 degree bend\n",
    "snake = [3,2,2,2,1,1,1,2,2,1,1,2,1,2,1,1,2]\n",
    "assert sum(snake) == 27"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That list is simply a list of the lengths of each segment starting from the right side in the photo above.  **What does the second line of executable code mean?  Why is it there?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ans:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The list also gives us a way of calculating how many combinations there are.  At each 90 degree joint, there are 4 possible rotations (ignoring the rotations of the 180 degree blocks) so there are 4<sup>17</sup> total combinations of rotations.  In python we can calcluate that number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17179869184"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "4**len(snake)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4<sup>17</sup> is over 17 billion combinations. That will include some effectively rotations and reflections, but it's still a big number.\n",
    "\n",
    "To find a solution with all those choices seems hard, but with this kind of puzzle it is actually very easy to know when you've gone wrong – as soon as you place a piece outside of the boundary of the 3x3x3 block you know it is wrong and should try something different.\n",
    "\n",
    "So how to represent the solution?  One way is to represent it as a 5x5x5 cube.  This is larger than it needs to be but it lets us have a single-space shell completely around the real cube.  We can then just check that shell to see if a configuration puts a block there.  If it does, we toss out that configuration. We don't need to do any complicated comparisons to see if a piece is out of bounds.  It's a simple trick but it works and saves a lot of code.\n",
    "\n",
    "You can also represent the 3d structure not as an actual 3d array but as a 1D array (or `list` in python speak) of length 5*5*5 = 125.  That's probably easier to conceptualize and certainly easier to handle mathematically.  (This is another reason this is a good puzzle to spend some time on... it shows how thinking about the physical model differently can simplify the computational model.)\n",
    "\n",
    "With the 1D model you have to realize that to move in the `x` direction you add 1, to move in the `y` direction you add 5 and to move in the `z` direction you move 25.  This simplifies the logic of the solver considerably - we don't need to deal with vectors.\n",
    "\n",
    "The basic definitions of the cube look like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "N = 5\n",
    "xstride=1    # number of pieces to move in the x direction\n",
    "ystride=N    # number of pieces to move in the y direction\n",
    "zstride=N*N  # number of pieces to move in the z direction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our `list` we will represent empty space with `0` and space which can't be used with `-1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "empty = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now define the empty cube with the boundary round the edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Define cube as 5 x 5 x 5 with filled in edges but empty middle for\n",
    "# easy edge detection\n",
    "top = [-1]*N*N\n",
    "middle = [-1]*5 + [-1,0,0,0,-1]*3 + [-1]*5\n",
    "cube = top + middle*3 + top"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're going to want a function to turn `x, y, z` coordinates into an index in the `cube` list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def pos(x, y, z):\n",
    "    \"\"\"Convert x,y,z into position in cube list\"\"\"\n",
    "    return x+y*ystride+z*zstride"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So let's see what that cube looks like..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1 -1 -1 -1 -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "\n",
      "-1 -1 -1 -1 -1 \n",
      "-1  .  .  . -1 \n",
      "-1  .  .  . -1 \n",
      "-1  .  .  . -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "\n",
      "-1 -1 -1 -1 -1 \n",
      "-1  .  .  . -1 \n",
      "-1  .  .  . -1 \n",
      "-1  .  .  . -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "\n",
      "-1 -1 -1 -1 -1 \n",
      "-1  .  .  . -1 \n",
      "-1  .  .  . -1 \n",
      "-1  .  .  . -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "\n",
      "-1 -1 -1 -1 -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "-1 -1 -1 -1 -1 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "def print_cube(cube, margin=1):\n",
    "    \"\"\"Print the cube\"\"\"\n",
    "    for z in range(margin,N-margin):\n",
    "        for y in range(margin,N-margin):\n",
    "            for x in range(margin,N-margin):\n",
    "                v = cube[pos(x,y,z)]\n",
    "                if v == 0:\n",
    "                    s = \" . \"\n",
    "                else:\n",
    "                    s = \"%02d \" % v\n",
    "                print(s, sep=\"\", end=\"\")\n",
    "            print()\n",
    "        print()\n",
    "\n",
    "print_cube(cube, margin = 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Normally we'll print it without the margin.\n",
    "\n",
    "Now let's work out how to place a segment.\n",
    "\n",
    "Assuming that the last piece was placed at `position` we want to place a segment of `length` in `direction`.  Note the `assert` to check we aren't placing stuff on top of previous things, or out of the edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def place(cube, position, direction, length, piece_number):\n",
    "    \"\"\"Place a segment in the cube\"\"\"\n",
    "    for _ in range(length):\n",
    "        position += direction\n",
    "        assert cube[position] == empty\n",
    "        cube[position] = piece_number\n",
    "        piece_number += 1\n",
    "    return position"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's just try placing some segments and see what happens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "01 02 03 \n",
      " .  .  . \n",
      " .  .  . \n",
      "\n",
      " .  .  . \n",
      " .  .  . \n",
      " .  .  . \n",
      "\n",
      " .  .  . \n",
      " .  .  . \n",
      " .  .  . \n",
      "\n"
     ]
    }
   ],
   "source": [
    "cube2 = cube[:] # copy the cube\n",
    "place(cube2, pos(0,1,1), xstride, 3, 1)\n",
    "print_cube(cube2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "01 02 03 \n",
      " .  . 04 \n",
      " .  . 05 \n",
      "\n",
      " .  .  . \n",
      " .  .  . \n",
      " .  .  . \n",
      "\n",
      " .  .  . \n",
      " .  .  . \n",
      " .  .  . \n",
      "\n"
     ]
    }
   ],
   "source": [
    "place(cube2, pos(3,1,1), ystride, 2, 4)\n",
    "print_cube(cube2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "01 02 03 \n",
      " .  . 04 \n",
      " .  . 05 \n",
      "\n",
      " .  .  . \n",
      " .  .  . \n",
      " .  . 06 \n",
      "\n",
      " .  .  . \n",
      " .  .  . \n",
      " .  . 07 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "place(cube2, pos(3,3,1), zstride, 2, 6)\n",
    "print_cube(cube2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next thing we'll need is to undo a place.  You'll see why in a moment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def unplace(cube, position, direction, length):\n",
    "    \"\"\"Remove a segment from the cube\"\"\"\n",
    "    for _ in range(length):\n",
    "        position += direction\n",
    "        cube[position] = empty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "01 02 03 \n",
      " .  . 04 \n",
      " .  . 05 \n",
      "\n",
      " .  .  . \n",
      " .  .  . \n",
      " .  .  . \n",
      "\n",
      " .  .  . \n",
      " .  .  . \n",
      " .  .  . \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unplace(cube2, pos(3,3,1), zstride, 2)\n",
    "print_cube(cube2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's write a function which returns whether a move is valid given a current `position` and a `direction` and a `length` of the segment we are trying to place."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_valid(cube, position, direction, length):\n",
    "    \"\"\"Returns True if a move is valid\"\"\"\n",
    "    for _ in range(length):\n",
    "        position += direction\n",
    "        if cube[position] != empty:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid(cube2, pos(3,3,1), zstride, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid(cube2, pos(3,3,1), zstride, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given `is_valid` it is now straight forward to work out what moves are possible at a given time, given a `cube` with a `position`, a `direction` and a `length` we are trying to place."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# directions next piece could go in\n",
    "directions = [xstride, -xstride, ystride, -ystride, zstride, -zstride]\n",
    "\n",
    "def moves(cube, position, direction, length):\n",
    "    \"\"\"Returns the valid moves for the current position\"\"\"\n",
    "    valid_moves = []\n",
    "    for new_direction in directions:\n",
    "        # Can't carry on in same direction, or the reverse of the same direction\n",
    "        if new_direction == direction or new_direction == -direction:\n",
    "            continue\n",
    "        if is_valid(cube, position, new_direction, length):\n",
    "            valid_moves.append(new_direction)\n",
    "    return valid_moves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 25]"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "moves(cube2, pos(3,3,1), ystride, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So that is telling us that you can insert a segment of length 2 using a direction of `-xstride` or `zstride`.  If you look at previous `print_cube()` output you'll see those are the only possible moves.\n",
    "\n",
    "Now we have all the bits to build a recursive solver."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def solve(cube, position, direction, snake, piece_number):\n",
    "    \"\"\"Recursive cube solver\"\"\"\n",
    "    if len(snake) == 0:\n",
    "        print(\"Solution\")\n",
    "        print_cube(cube)\n",
    "        return\n",
    "    length, snake = snake[0], snake[1:]\n",
    "    valid_moves = moves(cube, position, direction, length)\n",
    "    for new_direction in valid_moves:\n",
    "        new_position = place(cube, position, new_direction, length, piece_number)\n",
    "        solve(cube, new_position, new_direction, snake, piece_number+length)\n",
    "        unplace(cube, position, new_direction, length)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This works by being passed in the `snake` of moves left.  If there are no moves left then it must be solved, so we print the solution.  Otherwise it takes the head off the `snake` with `length, snake = snake[0], snake[1:]` and makes the list of valid moves of that `length`.\n",
    "\n",
    "Then we `place` each move, and try to `solve` that cube using a recursive call to `solve`.  We `unplace` the move so we can try again.\n",
    "\n",
    "This very quickly runs through all the possible solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution\n",
      "01 02 03 \n",
      "20 21 04 \n",
      "07 06 05 \n",
      "\n",
      "16 15 14 \n",
      "19 22 13 \n",
      "08 11 12 \n",
      "\n",
      "17 24 25 \n",
      "18 23 26 \n",
      "09 10 27 \n",
      "\n",
      "Solution\n",
      "01 02 03 \n",
      "16 15 14 \n",
      "17 24 25 \n",
      "\n",
      "20 21 04 \n",
      "19 22 13 \n",
      "18 23 26 \n",
      "\n",
      "07 06 05 \n",
      "08 11 12 \n",
      "09 10 27 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Start just off the side\n",
    "position = pos(0,1,1)\n",
    "direction = xstride\n",
    "length = snake[0]\n",
    "# Place the first segment along one edge - that is the only possible place it can go\n",
    "position = place(cube, position, direction, length, 1)\n",
    "# Now solve!\n",
    "solve(cube, position, direction, snake[1:], length+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wow!  It came up with 2 solutions!  Are they really different? Can you show that they are the same solution just rotated and reflected?\n",
    "\n",
    "But how do you use the solution?  Starting from the correct end of the snake, place each piece into its corresponding number.  Take the first layer of the solution as being the bottom (or top - whatever is easiest), the next layer is the middle and the one after the top.\n",
    "\n",
    "![Flat Snake Puzzle Numbered](http://www.craig-wood.com/nick/pub/snake-puzzle/snake-puzzle-flat-numbered.jpg \"Flat Snake Puzzle Numbered\")\n",
    "\n",
    "After a bit of fiddling around you'll get...\n",
    "\n",
    "![Solved Snake Puzzle](http://www.craig-wood.com/nick/pub/snake-puzzle/snake-puzzle-solved.jpg \"Solved Snake Puzzle\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I hope you enjoyed that introduction to puzzle solving with computer.\n",
    "\n",
    "If you want to try one yourselves, use the same technique to solve solitaire."
   ]
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}