Peg_Solitaire_Code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Peg Solitaire Solver\n",
    "### El Aamrani Ahmed - Lhourti Wassim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import cvxopt\n",
    "import cvxopt.glpk\n",
    "from cvxopt import matrix\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Starting reprensentation\n",
    "ps = np.ones(33)\n",
    "ps[16]=0 #Central hole has no peg in the starting representation\n",
    "\n",
    "#Final representation\n",
    "pf = np.zeros(33)\n",
    "pf[16]=1 #Central hole is the only filled hole in the final representation\n",
    "\n",
    "#Defining 'l' parameter\n",
    "l = int(np.sum(ps)-np.sum(pf))\n",
    "\n",
    "#Defining 'm' parameter\n",
    "m = 76 # It corresponds to the number of possible jumps in an English peg solitaire problem\n",
    "\n",
    "#Defining cost_matrix\n",
    "cost_matrix = matrix(np.zeros(l*m), tc='d')\n",
    "\n",
    "#Defining binary variables\n",
    "B = set(range(l*m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Implementing matrix A (please refer to the report for its definition)\n",
    "\n",
    "#First, implementing A1\n",
    "A10= np.array([[1,0,0,0,0], [1,1,0,0,0], [-1,1,1,0,0], [0,-1,1,1,0], [0,0,-1,1,1], [0,0,0,-1,1], [0,0,0,0,-1]])\n",
    "\n",
    "A11 = np.zeros((33,1))\n",
    "A11[0]=1\n",
    "A11[1]=1\n",
    "A11[2]=-1\n",
    "\n",
    "A12 = np.zeros((33,1))\n",
    "A12[3]=1\n",
    "A12[4]=1\n",
    "A12[5]=-1\n",
    "\n",
    "A13 = np.vstack((np.zeros((6,5)), A10, np.zeros((20,5))))\n",
    "\n",
    "A14 = np.vstack((np.zeros((13,5)), A10, np.zeros((13,5))))\n",
    "\n",
    "A15 = np.vstack((np.zeros((20,5)), A10, np.zeros((6,5))))\n",
    "\n",
    "A16 = np.zeros((33,1))\n",
    "A16[27]=1\n",
    "A16[28]=1\n",
    "A16[29]=-1\n",
    "\n",
    "A17 = np.zeros((33,1))\n",
    "A17[30]=1\n",
    "A17[31]=1\n",
    "A17[32]=-1\n",
    "\n",
    "A1 = np.hstack((A11,A12,A13,A14,A15,A16,A17))\n",
    "\n",
    "\n",
    "#Then, implementing A2\n",
    "A20= np.array([[-1,0,0,0,0], [1,-1,0,0,0], [1,1,-1,0,0], [0,1,1,-1,0], [0,0,1,1,-1], [0,0,0,1,1], [0,0,0,0,1]])\n",
    "\n",
    "A21 = np.zeros((33,1))\n",
    "A21[0]=-1\n",
    "A21[1]=1\n",
    "A21[2]=1\n",
    "\n",
    "A22 = np.zeros((33,1))\n",
    "A22[3]=-1\n",
    "A22[4]=1\n",
    "A22[5]=1\n",
    "\n",
    "A23 = np.vstack((np.zeros((6,5)), A20, np.zeros((20,5))))\n",
    "\n",
    "A24 = np.vstack((np.zeros((13,5)), A20, np.zeros((13,5))))\n",
    "\n",
    "A25 = np.vstack((np.zeros((20,5)), A20, np.zeros((6,5))))\n",
    "\n",
    "A26 = np.zeros((33,1))\n",
    "A26[27]=-1\n",
    "A26[28]=1\n",
    "A26[29]=1\n",
    "\n",
    "A27 = np.zeros((33,1))\n",
    "A27[30]=-1\n",
    "A27[31]=1\n",
    "A27[32]=1\n",
    "\n",
    "A2 = np.hstack((A21,A22,A23,A24,A25,A26,A27))\n",
    "\n",
    "\n",
    "#Then, implementing A3\n",
    "A31 = np.vstack((-np.eye(3), np.eye(3), np.zeros((2,3)), np.eye(3), np.zeros((22,3))))\n",
    "\n",
    "A32 = np.vstack((np.zeros((3,3)), -np.eye(3), np.zeros((2,3)), np.eye(3), np.zeros((4,3)), np.eye(3), np.zeros((15,3))))\n",
    "\n",
    "A33 = np.vstack((np.zeros((6,7)), -np.eye(7), np.eye(7), np.eye(7), np.zeros((6,7))))\n",
    "\n",
    "A34 = np.vstack((np.zeros((15,3)), -np.eye(3), np.zeros((4,3)), np.eye(3), np.zeros((2,3)), np.eye(3), np.zeros((3,3))))\n",
    "\n",
    "A35 = np.vstack((np.zeros((22,3)), -np.eye(3), np.zeros((2,3)), np.eye(3), np.eye(3)))\n",
    "\n",
    "A3 = np.hstack((A31,A32,A33,A34,A35))\n",
    "\n",
    "\n",
    "#Then, implementing A4\n",
    "A41 = np.vstack((np.eye(3), np.eye(3), np.zeros((2,3)), -np.eye(3), np.zeros((22,3))))\n",
    "\n",
    "A42 = np.vstack((np.zeros((3,3)), np.eye(3), np.zeros((2,3)), np.eye(3), np.zeros((4,3)), -np.eye(3), np.zeros((15,3))))\n",
    "\n",
    "A43 = np.vstack((np.zeros((6,7)), np.eye(7), np.eye(7), -np.eye(7), np.zeros((6,7))))\n",
    "\n",
    "A44 = np.vstack((np.zeros((15,3)), np.eye(3), np.zeros((4,3)), np.eye(3), np.zeros((2,3)), -np.eye(3), np.zeros((3,3))))\n",
    "\n",
    "A45 = np.vstack((np.zeros((22,3)), np.eye(3), np.zeros((2,3)), np.eye(3), -np.eye(3)))\n",
    "\n",
    "A4 = np.hstack((A41,A42,A43,A44,A45))\n",
    "\n",
    "# Concatenating A_i horizontally to constitute A\n",
    "A = np.hstack((A1,A2,A3,A4)).astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let us define equality matrices. There are two kind of equality constraints. \n",
    "\n",
    "# Let us consider first equality constraints (4) - Please refer to the report\n",
    "E11 = np.hstack((np.eye(m) for i in range(l)))\n",
    "E1 = np.matmul(A,E11)\n",
    "\n",
    "e1 = (ps - pf).reshape((33,1))\n",
    "\n",
    "# Let us consider the second king of equality constraints (6) - Please refer to the report\n",
    "E2 = np.zeros((l,l*m))\n",
    "for i in range(l):\n",
    "    E2[i][(i*m):((i+1)*m)] = np.ones((1,m))\n",
    "\n",
    "e2 = np.ones((l,1))\n",
    "\n",
    "# Concatenating vertically equality matrices\n",
    "E = np.vstack((E1,E2))\n",
    "E = matrix(E, tc='d')\n",
    "\n",
    "e = np.vstack((e1,e2))\n",
    "e = matrix(e, tc='d')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let us define inequality matrices. There are one kind (5) of equality constraints with 2 sides.\n",
    "\n",
    "# Let us consider first the \" >= 0 \" side\n",
    "for k in range(l):\n",
    "    I1k1 = np.hstack((np.eye(m) for i in range(k+1)))\n",
    "    if k == l-1:\n",
    "        I1k = I1k1\n",
    "    else:\n",
    "        I1k2 = np.hstack((np.zeros((m,m)) for j in range(k+1,l)))\n",
    "        I1k = np.hstack((I1k1,I1k2))\n",
    "    A1k = np.matmul(A,I1k)\n",
    "    if k == 0:\n",
    "        I1 = A1k\n",
    "    else:\n",
    "        I1 = np.vstack((I1, A1k))\n",
    "\n",
    "i10 = ps.reshape((33,1))\n",
    "i1 = np.vstack((i10 for  i in range(l)))\n",
    "\n",
    "# Let us consider first the \" <= 0 \" side\n",
    "for k in range(l):\n",
    "    I2k1 = np.hstack((-1*np.eye(m) for i in range(k+1)))\n",
    "    if k == l-1:\n",
    "        I2k = I2k1\n",
    "    else:\n",
    "        I2k2 = np.hstack((np.zeros((m,m)) for j in range(k+1,l)))\n",
    "        I2k = np.hstack((I2k1,I2k2))\n",
    "    A2k = np.matmul(A,I2k)\n",
    "    if k == 0:\n",
    "        I2 = A2k\n",
    "    else:\n",
    "        I2 = np.vstack((I2, A2k))\n",
    "\n",
    "i20 = np.ones((33,1)) - ps.reshape((33,1))\n",
    "i2 = np.vstack((i20 for  i in range(l)))\n",
    "\n",
    "#Concatenating inequality matrices\n",
    "I = np.vstack((I1,I2))\n",
    "I = matrix(I, tc='d')\n",
    "\n",
    "i = np.vstack((i1,i2))\n",
    "i = matrix(i, tc='d')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--------------------------------------------------- Validation step ---------------------------------------------------\n",
      "This feasible solution verifies the 'IP1' equality constraints : True\n",
      "This feasible solution verifies the 'IP1' inequality constraints : True\n",
      "-----------------------------------------------------------------------------------------------------------------------\n",
      "You can change any move within the sequence and see that these constraints are no longer true !\n"
     ]
    }
   ],
   "source": [
    "# Verifying conditions for a feasible solution taken from \"https://www.youtube.com/watch?v=Bt6GpGvUNeQ\"\n",
    "# Wa translated this feasible solution into our notations\n",
    "\n",
    "# Each row corresponds to a sequence among l=31 sequences\n",
    "# Each column is equivalent to the corresponding jump in the set J of cardinal 76\n",
    "\n",
    "# The sequence of youtube video moves \n",
    "youtube_sol = [61,3,57,41,19,57,51,12,32,63,12,34,56,72,18,56,62,25,5,50,25,15,49,24,22,64,13,27,52,28,8]\n",
    "\n",
    "# Defining the solution matrix\n",
    "youtube_solution = np.zeros((l,m))\n",
    "youtube_solution[np.arange(l), youtube_sol]  = np.ones(l)\n",
    "\n",
    "#Reshape the solution to a vector instead of a matrix\n",
    "youtube_solution = youtube_solution.reshape((l*m,1))\n",
    "\n",
    "print(\"--------------------------------------------------- Validation step ---------------------------------------------------\")\n",
    "print(\"This feasible solution verifies the 'IP1' equality constraints :\", np.array_equal(np.matmul(E,youtube_solution),e))\n",
    "print(\"This feasible solution verifies the 'IP1' inequality constraints :\", np.sum(np.matmul(I,youtube_solution)<=i)==I.size[0])\n",
    "print(\"-----------------------------------------------------------------------------------------------------------------------\")\n",
    "print(\"You can change any move within the sequence and see that these constraints are no longer true !\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------------------------------------------------------------------------------------------------------------\n",
      "The above line of code (***) is an implmentation for the \"IP1\" integer program formulation\n",
      "You could run this code but we've realized that it takes an infinite time of computing\n",
      "Thus, the necessity of exploring other ways to solve this problem.\n",
      "-----------------------------------------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "# Solving the problem\n",
    "\n",
    "#(status, optimal_x) = cvxopt.glpk.ilp(c=cost_matrix,G=I,h=i,A=E,b=e,B=B) (***)\n",
    "\n",
    "print(\"-----------------------------------------------------------------------------------------------------------------------\")\n",
    "print(\"The above line of code (***) is an implmentation for the \\\"IP1\\\" integer program formulation\")\n",
    "print(\"You could run this code but we've realized that it takes an infinite time of computing\")\n",
    "print(\"Thus, the necessity of exploring other ways to solve this problem.\")\n",
    "print(\"-----------------------------------------------------------------------------------------------------------------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# An alternative way is to implement a backtrack search using upper_bounds for the number of specific moves (using RUB)\n",
    "# and using pagoda function\n",
    "\n",
    "\n",
    "# Here we shuffle columns of A, in order to explore randomly moves among the 76 possible ones\n",
    "# When fixing seed=82, we have better performances\n",
    "np.random.seed(seed=82)\n",
    "s = np.arange(A.shape[1])\n",
    "np.random.shuffle(s)\n",
    "A = A[:,s]\n",
    "\n",
    "\n",
    "# Defining matrices for RUB integer program\n",
    "Erub = matrix(A, tc='d')\n",
    "    \n",
    "Irub = -1*np.eye(m)\n",
    "Irub = matrix(Irub, tc='d')\n",
    "\n",
    "irub = np.zeros((m,1))\n",
    "irub = matrix(irub, tc='d')\n",
    "\n",
    "Srub = set(range(m))\n",
    "\n",
    "\n",
    "# Taking an example of 3 pagoda functions that were given in the original paper\n",
    "pagval1_array = np.array([1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1])\n",
    "pagval2_array = np.array([0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0])\n",
    "pagval3_array = np.array([0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0])\n",
    "\n",
    "# Computing pagoda value for the finishing configuration\n",
    "pagval1_end = np.matmul(pagval1_array.T,pf)\n",
    "pagval2_end = np.matmul(pagval2_array.T,pf)\n",
    "pagval3_end = np.matmul(pagval3_array.T,pf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Defining a function that solves RUB program given the jump j, the starting and finishing configurations\n",
    "\n",
    "def solveRUB(jump, starting_config, finishing_config):\n",
    "    cost = np.zeros(m)\n",
    "    cost[jump] = -1\n",
    "    cost = matrix(cost, tc='d')\n",
    "    \n",
    "    erub = matrix((starting_config - finishing_config).reshape((33,1)), tc='d')\n",
    "    \n",
    "    (status, optimal_x) = cvxopt.glpk.ilp(c=cost,G=Irub,h=irub,A=Erub,b=erub,I=Srub)\n",
    "    \n",
    "    if optimal_x:\n",
    "        x_jump = np.matmul(cost.T, optimal_x)\n",
    "        x_jump = x_jump[0][0]\n",
    "        return(-1*x_jump)\n",
    "    else:\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Defining a function which states if a start configuration (actually an intermediate configuration) is legal or not\n",
    "# meaning wether it is a binary vector or not, knowing that its elements are integers\n",
    "\n",
    "def legal(start):\n",
    "    for i in range(len(start)):\n",
    "        if start[i]<0 or start[i]>1:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Defining a recursive function that takes in input the intermediate configuration \"start\", the finishing configuration \"end\n",
    "# which remains always the same, the list of upper bounds, the dictionary of searches already computed, and the path which is\n",
    "# updated at each stage.\n",
    "\n",
    "def search(start, end, upper_bound, path, dictionary):\n",
    "    \n",
    "    reste = int(np.sum(start)-np.sum(end))\n",
    "    \n",
    "    if reste <= 0:\n",
    "        return(np.array_equal(start,end))\n",
    "    \n",
    "    else:\n",
    "        pagval1_t = np.matmul(pagval1_array.T,start)\n",
    "        pagval2_t = np.matmul(pagval2_array.T,start)\n",
    "        pagval3_t = np.matmul(pagval3_array.T,start)\n",
    "\n",
    "        if pagval1_t < pagval1_end or pagval2_t < pagval2_end or pagval3_t < pagval3_end:\n",
    "            return False\n",
    "        \n",
    "        else:\n",
    "            \n",
    "            for j in range(m):\n",
    "                \n",
    "                optimal_x = solveRUB(j, start, end)\n",
    "                \n",
    "                if optimal_x is None:\n",
    "                    return False\n",
    "                \n",
    "                else:\n",
    "                    if upper_bound[j] <= 0:\n",
    "                        continue\n",
    "\n",
    "                    u_j = np.zeros(m)\n",
    "                    u_j[j] = 1\n",
    "\n",
    "                    move = start - np.matmul(A,u_j)\n",
    "\n",
    "                    if legal(move):\n",
    "                        start = move\n",
    "\n",
    "                        upper_bound[j] = upper_bound[j] - 1\n",
    "                        path.append(s[j])\n",
    "\n",
    "                        mytuple = hash(tuple(start))\n",
    "\n",
    "                        if mytuple in dictionary.keys():\n",
    "                            y = dictionary[mytuple]\n",
    "                        else:\n",
    "                            y = search(start, end, upper_bound, path, dictionary)\n",
    "                            dictionary[mytuple] = y\n",
    "\n",
    "                        if y == 1:\n",
    "                            return True\n",
    "                        else:\n",
    "                            upper_bound[j] = upper_bound[j] + 1\n",
    "                            start = start + np.matmul(A,u_j)\n",
    "                            path.pop()\n",
    "\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Defining the backtrack peg solver\n",
    "\n",
    "def backtrack_peg_solver(starting_config, finishing_config):\n",
    "    dictionary = {}\n",
    "    upper_bound = np.zeros(m)\n",
    "    path = []\n",
    "    \n",
    "    for jump in range(m):\n",
    "        optimal_x = solveRUB(jump, starting_config, finishing_config)\n",
    "        if optimal_x is None:\n",
    "            print(\"Infeasible problem\")\n",
    "            return None\n",
    "        else:\n",
    "            upper_bound[jump] = optimal_x\n",
    "    \n",
    "    if search(starting_config, finishing_config, upper_bound, path, dictionary) == 0:\n",
    "        print(\"Infeasible problem\")\n",
    "        return None\n",
    "    \n",
    "    print(\"Feasible problem\")\n",
    "    return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Feasible problem\n",
      "The list of moves composing the feasible solution is : \n",
      "--> [61, 47, 13, 54, 32, 55, 12, 32, 63, 12, 21, 34, 32, 56, 72, 62, 45, 2, 22, 57, 41, 19, 57, 25, 50, 3, 5, 25, 67, 53, 29]\n",
      "The elapsed computing time is : 3.25 s\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "solution = backtrack_peg_solver(ps, pf)\n",
    "end = time.time()\n",
    "print(\"The list of moves composing the feasible solution is : \\n-->\", solution)\n",
    "print(\"The elapsed computing time is :\", round(end - start,2), \"s\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--------------------------------------------------- Validation step ---------------------------------------------------\n",
      "This solution verifies the 'IP1' equality constraints : True\n",
      "This solution verifies the 'IP1' inequality constraints : True\n",
      "-----------------------------------------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "#Verifying whether the solution verifies the \\\"IP1\\\" integer program formulation that was first defined in the Notebook\n",
    "\n",
    "feasible_sol = np.zeros((l,m))\n",
    "# 'solution' is the list of moves \n",
    "feasible_sol[np.arange(l),solution]  = np.ones(l)\n",
    "\n",
    "#Reshape the feasible solution to a vector instead of a matrix\n",
    "feasible_sol = feasible_sol.reshape((l*m,1))\n",
    "\n",
    "print(\"--------------------------------------------------- Validation step ---------------------------------------------------\")\n",
    "print(\"This solution verifies the 'IP1' equality constraints :\", np.array_equal(np.matmul(E,feasible_sol),e))\n",
    "print(\"This solution verifies the 'IP1' inequality constraints :\", np.sum(np.matmul(I,feasible_sol)<=i)==I.size[0])\n",
    "print(\"-----------------------------------------------------------------------------------------------------------------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------------------------------------------------------------------------------------------------------------\n",
      "This peg solitaire solver is adapted for any starting and finishing configuration which are defined in 'In[2]'\n",
      "-----------------------------------------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "print(\"-----------------------------------------------------------------------------------------------------------------------\")\n",
    "print(\"This peg solitaire solver is adapted for any starting and finishing configuration which are defined in 'In[2]'\")\n",
    "print(\"-----------------------------------------------------------------------------------------------------------------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------Initial Configuration------\n",
      "\n",
      "              ●●●  \n",
      "              ●●●  \n",
      "            ●●●●●●●\n",
      "            ●●●o●●●\n",
      "            ●●●●●●●\n",
      "              ●●●  \n",
      "              ●●●  \n",
      "\n",
      "-------------Move 1-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●●●o●●●\n",
      "            ●●●●●●●\n",
      "            ●●●●●●●\n",
      "              ●●●  \n",
      "              ●●●  \n",
      "\n",
      "-------------Move 2-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●●●●●●●\n",
      "            ●●●o●●●\n",
      "            ●●●o●●●\n",
      "              ●●●  \n",
      "              ●●●  \n",
      "\n",
      "-------------Move 3-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●●●●●●●\n",
      "            ●●●o●●●\n",
      "            ●oo●●●●\n",
      "              ●●●  \n",
      "              ●●●  \n",
      "\n",
      "-------------Move 4-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●●●●●●●\n",
      "            ●●●o●●●\n",
      "            ●o●●●●●\n",
      "              o●●  \n",
      "              o●●  \n",
      "\n",
      "-------------Move 5-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●●●●●●●\n",
      "            ●●●o●●●\n",
      "            ●●oo●●●\n",
      "              o●●  \n",
      "              o●●  \n",
      "\n",
      "-------------Move 6-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●●●●●●●\n",
      "            ●●●o●●●\n",
      "            ●●o●●●●\n",
      "              oo●  \n",
      "              oo●  \n",
      "\n",
      "-------------Move 7-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●●●●●●●\n",
      "            ●●●o●●●\n",
      "            oo●●●●●\n",
      "              oo●  \n",
      "              oo●  \n",
      "\n",
      "-------------Move 8-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●●●●●●●\n",
      "            ●●●o●●●\n",
      "            o●oo●●●\n",
      "              oo●  \n",
      "              oo●  \n",
      "\n",
      "-------------Move 9-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            o●●●●●●\n",
      "            o●●o●●●\n",
      "            ●●oo●●●\n",
      "              oo●  \n",
      "              oo●  \n",
      "\n",
      "-------------Move 10-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            o●●●●●●\n",
      "            o●●o●●●\n",
      "            oo●o●●●\n",
      "              oo●  \n",
      "              oo●  \n",
      "\n",
      "-------------Move 11-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●oo●●●●\n",
      "            o●●o●●●\n",
      "            oo●o●●●\n",
      "              oo●  \n",
      "              oo●  \n",
      "\n",
      "-------------Move 12-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●oo●●●●\n",
      "            o●●o●●●\n",
      "            oo●●oo●\n",
      "              oo●  \n",
      "              oo●  \n",
      "\n",
      "-------------Move 13-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●oo●●●●\n",
      "            o●●o●●●\n",
      "            o●oooo●\n",
      "              oo●  \n",
      "              oo●  \n",
      "\n",
      "-------------Move 14-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●oo●●●●\n",
      "            o●●o●●●\n",
      "            o●oo●o●\n",
      "              ooo  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 15-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●o●  \n",
      "            ●oo●●●●\n",
      "            o●●oo●●\n",
      "            o●oooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 16-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●oo  \n",
      "            ●oo●o●●\n",
      "            o●●o●●●\n",
      "            o●oooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 17-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●oo  \n",
      "            ●●o●o●●\n",
      "            oo●o●●●\n",
      "            oooooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 18-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●oo  \n",
      "            oo●●o●●\n",
      "            oo●o●●●\n",
      "            oooooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 19-------------\n",
      "\n",
      "              ●●●  \n",
      "              ●oo  \n",
      "            o●ooo●●\n",
      "            oo●o●●●\n",
      "            oooooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 20-------------\n",
      "\n",
      "              o●●  \n",
      "              ooo  \n",
      "            o●●oo●●\n",
      "            oo●o●●●\n",
      "            oooooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 21-------------\n",
      "\n",
      "              o●●  \n",
      "              ●oo  \n",
      "            o●ooo●●\n",
      "            oooo●●●\n",
      "            oooooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 22-------------\n",
      "\n",
      "              ●oo  \n",
      "              ●oo  \n",
      "            o●ooo●●\n",
      "            oooo●●●\n",
      "            oooooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 23-------------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            o●●oo●●\n",
      "            oooo●●●\n",
      "            oooooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 24-------------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            o●●o●oo\n",
      "            oooo●●●\n",
      "            oooooo●\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 25-------------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            o●●o●o●\n",
      "            oooo●●o\n",
      "            ooooooo\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 26-------------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            ooo●●o●\n",
      "            oooo●●o\n",
      "            ooooooo\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 27-------------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            ooooo●●\n",
      "            oooo●●o\n",
      "            ooooooo\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 28-------------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            oooo●oo\n",
      "            oooo●●o\n",
      "            ooooooo\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 29-------------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            ooooooo\n",
      "            ooooo●o\n",
      "            oooo●oo\n",
      "              oo●  \n",
      "              ooo  \n",
      "\n",
      "-------------Move 30-------------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            ooooooo\n",
      "            oooo●●o\n",
      "            ooooooo\n",
      "              ooo  \n",
      "              ooo  \n",
      "\n",
      "------Final Configuration------\n",
      "\n",
      "              ooo  \n",
      "              ooo  \n",
      "            ooooooo\n",
      "            ooo●ooo\n",
      "            ooooooo\n",
      "              ooo  \n",
      "              ooo  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "#Graphical representation of the solution \n",
    "\n",
    "#As A has been shuffled before, we recreate the initial A matrix\n",
    "A = np.hstack((A1,A2,A3,A4)).astype(int)\n",
    "\n",
    "def print_config(p):\n",
    "    #This function gives a graphical representation of a given configuration p\n",
    "    \n",
    "    #Convert p to a string type array\n",
    "    str_p = np.char.mod('%d', p)\n",
    "    #Replace integers by black and white dots\n",
    "    for i in range(len(str_p)):\n",
    "        if str_p[i] == '0':\n",
    "            str_p[i] = 'o'\n",
    "        elif str_p[i] == '1':\n",
    "            str_p[i] = '\\u25CF'\n",
    "        else:\n",
    "            return(False)\n",
    "    #Convert the array to a string\n",
    "    string_sol = ''.join(str_p)\n",
    "    #Represent each line\n",
    "    first_line = '              ' + string_sol[:3] + '  '  \n",
    "    second_line = '              ' + string_sol[3:6] + '  '\n",
    "    third_line = '            ' + string_sol[6:13]  \n",
    "    fourth_line = '            ' + string_sol[13:20]\n",
    "    fifth_line = '            ' + string_sol[20:27]\n",
    "    sixth_line = '              ' + string_sol[27:30] + '  '\n",
    "    seventh_line = '              ' + string_sol[30:] + '  '\n",
    "    #Concatenate lines\n",
    "    config = first_line + '\\n' + second_line + '\\n' + third_line + '\\n' + fourth_line + '\\n' + fifth_line + '\\n' + sixth_line + '\\n' + seventh_line + '\\n'\n",
    "    print(config)\n",
    "    #return(config)\n",
    "\n",
    "def print_solution(solution):\n",
    "    #This function prints the solution's sequence\n",
    "    print('------Initial Configuration' + '------\\n')\n",
    "    #result = []\n",
    "    print_config(ps)\n",
    "    p = ps\n",
    "    zeros = np.zeros(m)\n",
    "    for i in range(len(solution)-1):\n",
    "        zeros[solution[i]] = 1\n",
    "        p = p - np.matmul(A,zeros)\n",
    "        print('-------------Move ' + str(i+1) +'-------------\\n')\n",
    "        print_config(p)\n",
    "        #result.append(print_config(p))\n",
    "        zeros = np.zeros(m)\n",
    "    print('------Final Configuration' + '------\\n')\n",
    "    print_config(pf)\n",
    "    #result.append(print_config(pf))\n",
    "    #str3 = ' '.join(result)\n",
    "    #print(str3)\n",
    "    \n",
    "\n",
    "print_solution(solution)\n"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}