Simple Puzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Big Cat Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## importing packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from gurobipy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining constants"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "values = {\n",
    "    \"TF\": 1,\n",
    "    \"LF\": 2,\n",
    "    \"PF\": 3,\n",
    "    \"JF\": 4,\n",
    "    \"TB\":-1,\n",
    "    \"LB\":-2,\n",
    "    \"PB\":-3,\n",
    "    \"JB\":-4,\n",
    "}\n",
    "\n",
    "translator = {v: k for k, v in values.items()}\n",
    "\n",
    "TIGER_FRONT = values[\"TF\"]\n",
    "LION_FRONT = values[\"LF\"]\n",
    "PHANTER_FRONT = values[\"PF\"]\n",
    "JAGUAR_FRONT = values[\"JF\"]\n",
    "TIGER_BACK = values[\"TB\"]\n",
    "LION_BACK = values[\"LB\"]\n",
    "PHANTER_BACK = values[\"PB\"]\n",
    "JAGUAR_BACK = values[\"JB\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining Tile class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tile:    \n",
    "    def __init__(self,left,top,bottom,right,index):\n",
    "        self.left = left\n",
    "        self.top = top\n",
    "        self.bottom = bottom\n",
    "        self.right = right\n",
    "        self.index = index\n",
    "        \n",
    "    def rotate(self,steps):\n",
    "        if steps == 0:\n",
    "            return self\n",
    "        else:\n",
    "            return Tile(self.top,self.right,self.left,self.bottom,self.index).rotate(steps - 1)\n",
    "    def __str__(self):\n",
    "        return \"\\n\".join([\" \".join(e) for e in self.arrstr()])\n",
    "    \n",
    "    def arrstr(self):\n",
    "        return np.array([\n",
    "            [\"  \",translator[self.top],\"  \"],\n",
    "            [translator[self.left],\"%2.d\" % (self.index,),translator[self.right]],\n",
    "            [\"  \",translator[self.bottom],\"  \"]\n",
    "        ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining helper functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "left = np.vectorize(lambda x : x.left)\n",
    "top = np.vectorize(lambda x : x.top)\n",
    "right = np.vectorize(lambda x : x.right)\n",
    "bottom = np.vectorize(lambda x : x.bottom)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initializing tile pieces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   JB   \n",
      "TF  0 TB\n",
      "   LF   \n",
      "   JF   \n",
      "JB  1 LB\n",
      "   PF   \n",
      "   LF   \n",
      "LB  2 TB\n",
      "   JF   \n",
      "   TF   \n",
      "TF  3 JF\n",
      "   LB   \n",
      "   TB   \n",
      "TB  4 LF\n",
      "   PF   \n",
      "   PF   \n",
      "TF  5 LB\n",
      "   JF   \n",
      "   LB   \n",
      "PB  6 PB\n",
      "   JF   \n",
      "   PB   \n",
      "JB  7 LF\n",
      "   PF   \n",
      "   PB   \n",
      "TF  8 PF\n",
      "   JB   \n"
     ]
    }
   ],
   "source": [
    "basic_tiles = [\n",
    "    Tile(\n",
    "        TIGER_FRONT, JAGUAR_BACK,\n",
    "        LION_FRONT, TIGER_BACK,\n",
    "        0\n",
    "    ),\n",
    "    Tile(\n",
    "        JAGUAR_BACK,JAGUAR_FRONT,\n",
    "        PHANTER_FRONT,LION_BACK,\n",
    "        1\n",
    "    ),\n",
    "    Tile(\n",
    "        LION_BACK,LION_FRONT,\n",
    "        JAGUAR_FRONT,TIGER_BACK,\n",
    "        2\n",
    "    ),\n",
    "    Tile(\n",
    "        TIGER_FRONT,TIGER_FRONT,\n",
    "         LION_BACK,JAGUAR_FRONT,\n",
    "        3\n",
    "    ),\n",
    "    Tile(\n",
    "        TIGER_BACK, TIGER_BACK,\n",
    "        PHANTER_FRONT, LION_FRONT,\n",
    "        4\n",
    "    ),\n",
    "    Tile(\n",
    "        TIGER_FRONT,PHANTER_FRONT,\n",
    "        JAGUAR_FRONT, LION_BACK,\n",
    "        5\n",
    "    ),\n",
    "    Tile(\n",
    "        PHANTER_BACK, LION_BACK,\n",
    "        JAGUAR_FRONT, PHANTER_BACK,\n",
    "        6\n",
    "    ),\n",
    "    Tile(\n",
    "        JAGUAR_BACK, PHANTER_BACK,\n",
    "        PHANTER_FRONT, LION_FRONT,\n",
    "        7\n",
    "    ),\n",
    "    Tile(\n",
    "        TIGER_FRONT, PHANTER_BACK,\n",
    "        JAGUAR_BACK, PHANTER_FRONT,\n",
    "        8\n",
    "    ),\n",
    "]\n",
    "\n",
    "for e in basic_tiles:\n",
    "    print(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initializing Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Academic license - for non-commercial use only\n"
     ]
    }
   ],
   "source": [
    "m = Model()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding constrains\n",
    "### Defining all possible tiles\n",
    "$i$: index of the tile  \n",
    "$rot$: rotation of the tile  \n",
    "$pos$: position of the tile \n",
    "  \n",
    "$tile_{i,rot}$:  defines the value of the tiles.  \n",
    "$t_{i,rot,pos}$: are the Integer program variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "tiles = np.array([[tile.rotate(rot) for rot in range(4)] for tile in basic_tiles])\n",
    "tiles_variable = np.array([[[m.addVar(vtype=GRB.BINARY, name=\"tile_%d_rot_%d_pos_%d\" % (tile_index, rot, pos)) for pos in range(9)] for rot in range(4)] for tile_index in range(len(basic_tiles))])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For each tile, one state only must exist  \n",
    "$\\forall{i}{\\sum_{rot}{\\sum_{pos}{t_{i,rot,pos}}}} = 1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(9):\n",
    "    m.addConstr(np.sum(tiles_variable[i,:,:]) == 1,name=\"one_state_for_tile_%d\" % (i,))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For each slot, one tile only must exist  \n",
    "$\\forall{pos}{\\sum_{i}{\\sum_{rot}{t_{i,rot,pos}}}} = 1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "for pos in range(9):\n",
    "    m.addConstr(np.sum(tiles_variable[:,:,pos]) == 1, name=\"one_tile_in_pos_%d\" % (pos,))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The slot indexing   \n",
    "<table>\n",
    "  <tr>\n",
    "    <th>0</th>\n",
    "    <th>1<br></th>\n",
    "    <th>2</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td>3</td>\n",
    "    <td>4</td>\n",
    "    <td>5</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td>6</td>\n",
    "    <td>7</td>\n",
    "    <td>8</td>\n",
    "  </tr>\n",
    "</table>  \n",
    "\n",
    "### Side matching  \n",
    "$ \\sum_{i}{\\sum_{rot}{right(tile_{i,rot}) \\cdot t_{i,rot,0}}} + \\sum_{i}{\\sum_{rot}{left(tile_{i,rot}) \\cdot t_{i,rot,1}}} = 0$  \n",
    "\n",
    "$ \\sum_{i}{\\sum_{rot}{right(tile_{i,rot}) \\cdot t_{i,rot,1}}} + \\sum_{i}{\\sum_{rot}{left(tile_{i,rot}) \\cdot t_{i,rot,2}}} = 0$    \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{right(tile_{i,rot}) \\cdot t_{i,rot,3}}} + \\sum_{i}{\\sum_{rot}{left(tile_{i,rot}) \\cdot t_{i,rot,4}}} = 0$   \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{right(tile_{i,rot}) \\cdot t_{i,rot,4}}} + \\sum_{i}{\\sum_{rot}{left(tile_{i,rot}) \\cdot t_{i,rot,5}}} = 0$    \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{right(tile_{i,rot}) \\cdot t_{i,rot,6}}} + \\sum_{i}{\\sum_{rot}{left(tile_{i,rot}) \\cdot t_{i,rot,7}}} = 0$   \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{right(tile_{i,rot}) \\cdot t_{i,rot,7}}} + \\sum_{i}{\\sum_{rot}{left(tile_{i,rot}) \\cdot t_{i,rot,8}}} = 0$   \n",
    "  \n",
    "### Top and bottom matching\n",
    "$ \\sum_{i}{\\sum_{rot}{bottom(tile_{i,rot}) \\cdot t_{i,rot,0}}} + \\sum_{i}{\\sum_{rot}{top(tile_{i,rot}) \\cdot t_{i,rot,3}}} = 0$    \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{bottom(tile_{i,rot}) \\cdot t_{i,rot,1}}} + \\sum_{i}{\\sum_{rot}{top(tile_{i,rot}) \\cdot t_{i,rot,4}}} = 0$  \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{bottom(tile_{i,rot}) \\cdot t_{i,rot,2}}} + \\sum_{i}{\\sum_{rot}{top(tile_{i,rot}) \\cdot t_{i,rot,5}}} = 0$  \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{bottom(tile_{i,rot}) \\cdot t_{i,rot,3}}} + \\sum_{i}{\\sum_{rot}{top(tile_{i,rot}) \\cdot t_{i,rot,6}}} = 0$  \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{bottom(tile_{i,rot}) \\cdot t_{i,rot,4}}} + \\sum_{i}{\\sum_{rot}{top(tile_{i,rot}) \\cdot t_{i,rot,7}}} = 0$  \n",
    "  \n",
    "$ \\sum_{i}{\\sum_{rot}{bottom(tile_{i,rot}) \\cdot t_{i,rot,5}}} + \\sum_{i}{\\sum_{rot}{top(tile_{i,rot}) \\cdot t_{i,rot,8}}} = 0$  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def side_matching(m,tiles,tiles_variable,i,j):\n",
    "    m.addConstr(np.sum(right(tiles)*tiles_variable[:,:,i]) + np.sum(left(tiles)*tiles_variable[:,:,j]) == 0, name=\"tile_%d_right_equal_tile_%d_left\" % (i,j))\n",
    "    \n",
    "def vertical_matching(m,tiles,tiles_variable,i,j):\n",
    "    m.addConstr(np.sum(bottom(tiles)*tiles_variable[:,:,i]) + np.sum(top(tiles)*tiles_variable[:,:,j]) == 0, name=\"tile_%d_bottom_equal_tile_%d_top\" % (i,j))\n",
    "\n",
    "side_matching(m,tiles,tiles_variable,0,1)\n",
    "side_matching(m,tiles,tiles_variable,1,2)\n",
    "side_matching(m,tiles,tiles_variable,3,4)\n",
    "side_matching(m,tiles,tiles_variable,4,5)\n",
    "side_matching(m,tiles,tiles_variable,6,7)\n",
    "side_matching(m,tiles,tiles_variable,7,8)\n",
    "\n",
    "vertical_matching(m,tiles,tiles_variable,0,3)\n",
    "vertical_matching(m,tiles,tiles_variable,1,4)\n",
    "vertical_matching(m,tiles,tiles_variable,2,5)\n",
    "vertical_matching(m,tiles,tiles_variable,3,6)\n",
    "vertical_matching(m,tiles,tiles_variable,4,7)\n",
    "vertical_matching(m,tiles,tiles_variable,5,8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimize a model with 30 rows, 324 columns and 1512 nonzeros\n",
      "Variable types: 0 continuous, 324 integer (324 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 4e+00]\n",
      "  Objective range  [0e+00, 0e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Presolve time: 0.02s\n",
      "Presolved: 30 rows, 324 columns, 1404 nonzeros\n",
      "Variable types: 0 continuous, 324 integer (324 binary)\n",
      "\n",
      "Root relaxation: objective 0.000000e+00, 49 iterations, 0.00 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0    0.00000    0   26          -    0.00000      -     -    0s\n",
      "     0     0    0.00000    0   32          -    0.00000      -     -    0s\n",
      "     0     0    0.00000    0   32          -    0.00000      -     -    0s\n",
      "     0     0    0.00000    0   32          -    0.00000      -     -    0s\n",
      "     0     2    0.00000    0    8          -    0.00000      -     -    0s\n",
      "*  426     6              14       0.0000000    0.00000  0.00%  21.9    0s\n",
      "\n",
      "Cutting planes:\n",
      "  Cover: 76\n",
      "  MIR: 1\n",
      "  GUB cover: 25\n",
      "  Inf proof: 1\n",
      "  Zero half: 2\n",
      "\n",
      "Explored 485 nodes (10726 simplex iterations) in 0.33 seconds\n",
      "Thread count was 4 (of 4 available processors)\n",
      "\n",
      "Solution count 1: 0 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "m.write(\"model.lp\")\n",
    "m.optimize()\n",
    "m.write(\"model.sol\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parse solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "output = np.array([[\"  \" for _ in range(9)] for _ in range(9)])\n",
    "\n",
    "tiles_value = np.vectorize(lambda x : x.X)(tiles_variable)\n",
    "for i, rot, pos  in np.argwhere(tiles_value):\n",
    "    output[3*(pos//3):3*(pos//3) + 3,3*(pos%3):3*(pos%3) + 3] = tiles[i,rot].arrstr()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   JF       PF       LB   \n",
      "TF  3 LB LF  7 JB JF  2 LF\n",
      "   TF       PB       TB   \n",
      "   TB       PF       TF   \n",
      "PF  4 TB TF  5 LB LF  0 JB\n",
      "   LF       JF       TB   \n",
      "   LB       JB       TF   \n",
      "PB  6 PB PF  1 JF JB  8 PB\n",
      "   JF       LB       PF   \n"
     ]
    }
   ],
   "source": [
    "print(\"\\n\".join([\" \".join(e) for e in output]))"
   ]
  }
 ],
 "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.1"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}