knights tour.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Knight's Tour\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Knight's tour is about a knight who tries to travel through all vertices on the chessboard and each vertex is visited only once. Rules of knight's tour can be found in the following link\n",
    "\n",
    "https://en.wikipedia.org/wiki/Knight%27s_tour\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.animation as pltani\n",
    "import os\n",
    "os.chdir('K:/ecole/github')\n",
    "\n",
    "#graph adt\n",
    "#check the below link for more details\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/graph.py\n",
    "import graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#dfs here is slightly different from other dfs\n",
    "#an organic dfs goes very deep until we cannot find any unvisited children vertices\n",
    "#in that case we move up to the parent vertex to find unvisited sibling vertices\n",
    "#this action violates the rule of travel-once\n",
    "#hence we use a few more lines to adjust the algorithm\n",
    "#when we havent finished visiting all the vertices\n",
    "#any backtracking leads to cancellation of the visited status of the current vertex\n",
    "#becuz this is not the solution we want\n",
    "#we cant visit one vertex twice\n",
    "#we keep doing cancellation\n",
    "#until we find a path that dives very deep and never comes back\n",
    "#in the end, this path would ve visited all the vertices only once\n",
    "#it would be the answer we are looking for\n",
    "#details of organic dfs can be found in the following link\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/BFS%20dfs%20on%20DCG.ipynb\n",
    "def dfs(ADT,start,path):\n",
    "\n",
    "    ADT.visit(start)\n",
    "\n",
    "    path.append(start)\n",
    "\n",
    "    for newpos in ADT.edge(start):\n",
    "\n",
    "        if ADT.go(newpos)==0:\n",
    "\n",
    "            dfs(ADT,newpos,path)\n",
    "\n",
    "    if len(path)<ADT.order():\n",
    "\n",
    "        ADT.clear(start)\n",
    "\n",
    "        path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create graph adt\n",
    "#the movement of knight is very special\n",
    "#for each vertex, there are eight possible next moves at maximum\n",
    "#we also need a semi definite constraint to make sure knight doesnt travel outta chessboard\n",
    "def check_around(ADT,i,j,size):\n",
    "\n",
    "    for x,y in [(i-2,j+1),(i-2,j-1),(i-1,j-2),\n",
    "                (i-1,j+2),(i+1,j-2),(i+1,j+2),\n",
    "                (i+2,j-1),(i+2,j+1)]:\n",
    "\n",
    "        if x<size and x>=0 and y<size and y>=0:\n",
    "\n",
    "            ADT.append((i,j),(x,y),1)\n",
    "            \n",
    "    return ADT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#viz knight s tour\n",
    "def draw_chessboard(ind,*args):\n",
    "    \n",
    "    ax,path,knight=args\n",
    "    \n",
    "    #vertices the knight travelled\n",
    "    for i in range(ind):\n",
    "        ax.scatter(path[i][0]+0.5,path[i][1]+0.5,\n",
    "                    color='red',marker='x',s=200)\n",
    "    \n",
    "    #knight s current position\n",
    "    knight.set_offsets((path[ind][0]+0.5,path[ind][1]+0.5))   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#assume this is an 8 by 8 chessboard\n",
    "size=8\n",
    "\n",
    "#generate graph adt\n",
    "chessboard=graph.graph()\n",
    "for i in range(size):\n",
    "    for j in range(size):\n",
    "        chessboard=check_around(chessboard,i,j,size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#dfs\n",
    "#plz note that there are many possible solutions\n",
    "#this is not the only answer\n",
    "path=[]\n",
    "dfs(chessboard,(0,0),path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "MovieWriter ffmpeg unavailable.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAASwAAAElCAYAAABect+9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJztnW2MXNV5x5/xusiQhraEQkPKS5wWGtJSzC7Q0ASUqMmHfIjaSI2iKEIoitzIrWhLJSpRiUpUpS2V7Mqp3IhKVCUtUUXbhFQVrSiJjDFm8dprY2xjDPgNY4wxxt61vX7ZOf1w53DvnDkz93nOOffcc5b/T7raubP3WWb+zPx8751nnttRShEAAOTAorYfAAAAcIGwAADZAGEBALIBwgIAZAOEBQDIBggLAJANEBYAIBsgLABANkBYAIBsgLAAANmwWLLxpZdeqq655pqGHoqM6elp6na7bT8MWrRoES1btqzth0FE6WRChFyGgVyGopRStTtQHcl3CScmJtTU1JTXowpFp9Np+yG8Tyrfx0wpEyLkMgzkYkcpVfuAcEgIAMgGCAsAkA0QFgAgGyAsAEA2QFgAgGyAsAAA2dCMsP78z4k2b5bVbN5c1AXmi5HrRvIP/0D0yiuymldeKeoCc23kupG89RbR3JysZm6uqAvM9ZHrhvLqq0Szs7Ka2dmiLjBLI9eNRCnFXsbHx1Ut99+vFFGxbNpUv71SxXa65v77WSVEVLt8kUh1ewtne73omi8yt2exZk35HHft4tXs2lXWrFkTJBMiUtd65nJtyFwOHSqf4+nTvJrTp8uaQ4eC5XK9Zy7Xh8pl9+7y+c3M8DKZmSlrdu9mlXAe61LPTJYKahTDQeGFVZUPMaQl3V4Qtg5OCQKXbs9+Y1blQwxpSbcXZJJULlX5EENa0u1zzKUqH2JIS7q9MJcYmbQnLKX4EnKUlSRsSYAeQfPgSshBVtJMksqFKyEHWWWbC1dCjrKS5tJ0Ju0KS6l6GXnISho2J0jPoPnUychRVi6ZJJVLnYwcZZV1LnUy8pCVSy5NZtK+sJQaLiVPWbmEPSrQAEHLGCYlD1m5ZpJULsOk5CGr7HMZJiVPWbnm0lQmaQhLKbuczHUHQr0IAwUtxyYncz1SJknlYpOTuf5By8UmJ3PdgZQy4Qqr+T6sm24i2rSpXB8fL29v2lT8PiKLqEinY/yM3pB27bVEu3aV69ddV97etav4fUSSyWXJEqLTp8v1Cy8sb58+Xfw+Iknk8tM/TTQzU65/+MPl7ZmZ4vcRaTOTOLmb0iJqRVYa80m31j1rSouoFVlpksnFlBZRK7LSJJGLKS2iVmSlaSuTOP+dzZv796yIinVpc2kgzJFlrY0we+WV/j0romJd2lwaiGRymZvr37MiKtalzaWBSCKX2dn+PSuiYl3aXBqItjJpXlimrMzDw8jS6tLgrmyHWngRmrIyDw8jSyuZXExZmYeHkaWVRC6mrMzDw8jSajOTZoVlk5XtnFYkaVWD1k+8ejwe7UVok5XtnFYkaSWTi01WtnNakaSVRC42WdnOaUWSVuuZcM7M6wV9WAE+9UEflh30YQ2CPqxIbQ3odLeDTnc76HQfBJ3ukYSF7xLawXcJ7eC7hIPgu4RDl/DnsJ54orzNaV0wz2lV6z3RI2IU8U/W6ePxan0Qnn66vM1pXTDPaVXrPdH/ZddcgjZdvPdeeZvTumCe06rWe6JHxLjmEmzETHVsDqd1wTynFXDsjh4R45pJ8BEzHKvphX1IeP/98g72TZvYo2WU4v/rwB0R41PHZs0aeQf7rl2s0TKSTIj4I2J86tgcOiTvYD99mjVaRpoLd0SMTx2L3bvlHewzM+zRMpJcJCNifOoUw0G4LmEAJBk2SUqZECGXYSAXOwrXJQQALCQgLABANkBYAIBsgLAAANkAYQEAsgHCAgBkA4QFAMgGUR/W2NiY6nZbm5IEAFi4dJVSY3UbLRb9xcRklUIDXoLNd20/BCJCLsNALnY6nc40ZzscEgIAsgHCAgBkA4QFAMgGCAsAkA0QFgAgGyAsAEA2QFgAgGxoRFhfilw3kt//faJnn5XVPPtsUReYb0SuG8k//RPR66/Lal5/vagLzGWR60bywgtE774rq3n33aIuIBdHrhvJj39M9Pbbspq33y7qQsMZS6oXYow5/RIVw+elA+h1zZdCjppdsaIczL9uHW9u7Lp1Zc2KFbWbcx/rNzxz+UbI8buPPFI+x9de49W89lpZ88gjwXK5zDOXy0LmMjlZPsejR3k1R4+WNZOTQXK5uPfc5oWZzPfqLg75Hnr66fL5HT7My+Tw4bLm6adZJUQ0pTgO4mz0/saCF5MSvAgbu1xSVT7EkJZ0e5XhFVmU6pcPMaQl3T7XXKryIYa0pNsLcpnv/U2utKTbs3OpyocY0pJuX+bSnrAkL6rGL0jJlZCDrHpBN/LmbPxagFwJOcgq61y4EnKQlTQXroRcZcXOhSshR1n1cmlXWJwXV4ArxfKok5GjrHpBB39zRrvacp2MHGWVfS51MnKUlUsudTLykZUolzoZeciql0v7whr1IvOVlfhFOExKHrLqBR30zRlN4pphUvKQ1YLIZZiUPGTlmsswKfnKSpzLMCl5yqqXSxrCsr3YQsjK6UVok5O5Lg862JszusQ1NjmZ6x/EXGxyMtcj5WLKKYSsnHKxyclcd4ArLNE8rE6nw9/YoEtE1cEaivx7KiSP/X2efZbos58dvH/dOqLPfEb853zHhYTOxSkToqJl4ROfGLz/tdeIlsqv37tgcnn3XaKPfGTw/qNHiS65RPznfHKZp/4MukRUO0CqBqdc3n6b6PLLB+8/fJjoMrdmk06ns0kpNVG3XbTGUfM/1FrH6mc+U8ipiqOsQpBMLkuXFnKq4iirECSTyyWXFHKq4igrX0w5+crKmcsuK+RUxUNWEqK9DszRf62NArTtYX32s/Lm0kAkk4ttD+sTn5A3lwYimVxse1gf+Yi8uTQA8zXr0bDtYV1+uby51IEowtK798r4Gf1FaMqquqfVgrSSycWUVXVPqwVpJZOLKavqnlZkaenDQZ1Nt7ceXVqmrKp7WjGkxTnRpRcKcAK17n7JIgKfEtrBp4R28CnhIAv9U0L0YcXPRQT6sOygD2uQhd6HhU73dnJhg053O+h0H2Shd7rju4Tt5cIC3yW0g+8SDpLYdwmDn3TXI2IU8c/oL+ptX60Pwve/X97mtC6YLQ/Vek/0iBjXXIKOmFm7trzNaV0wWx6q9Z7oD8Jdcwn6Qfqrr5a3Oa0LZstDtd6Di6k8sc5tXRij8oR80BEzL71U3ua0LpgtD9X6EHCsphdiWlsyIsanjsWKFfIO9nXrWKNllJLtSXBHxPjUsXnkEXkH+2uvsUbLSHPhjojxqWMzOSnvYD96lDVaRpKLZESMTx2Lp5+Wn0g/fJg9WqaXS1qd7k0geexNgQtj2kEudpCLneQ63QEAwBcICwCQDRAWACAbICwAQDZAWACAbICwAADZAGEBALJB1Ic1Njamut3WJhMBABYuXaVUbWP/YslfXLZsGU1NTbk/pICk1ICXUPNd2w+hD+RiB7lYYR3t4ZAQAJANEBYAIBsgLABANkBYAIBsgLAAANkAYQEAsgHCAgBkQzPC+sM/JHruOVnNc88VdYG5M3LdSP7xH+VjdF99tagLzJcj143k2WeJ3nlHVvPOO41cR9L1es7BrwO9ZQvRe+/Jat57r6gLzBWR60bCGUuql/Hx8fpZp3ffXQ6gX7+eNx91/fqy5u67WSXEGP96JxUXKpBe3ELX3BlyzOzDD5fPcfduXs3u3WXNww8HyYSI1Jc9c/lyyFyqF/44coRXc+RIIxcKucQzl0tC5TI9XT6/Y8d4mRw7VtZMT7NKOI/1Cs9MrhDUKM6Yds5GemEJqyofYkhLur0gbB2cEgTe2BVZqvIhhrSk2wsySSqXqnyIIS3p9jnmUpUPMaQl3V6YS8SrYLUgLKX4EnKUlSRsSYCNX/OOKyEHWUkzSSoXroQcZJVtLlwJOcpKmkuk64y2JCyl6mXkIStp2Jwgo11VuE5GjrJyySSpXOpk5CirrHOpk5GHrFxyiXAl9xaFpdRwKXnKyiXsUYEGCFrGMCl5yMo1k6RyGSYlD1lln8swKXnKyjWXpjJJQ1hK2eVkrjsQ6kUYKGg5NjmZ65EySSoXm5zM9Q9aLjY5mesOpJQJV1jN92HddhvR+vXl+m/+Znl7/fri9xHRVw3uGD+jN6T90i8R7d5drv/yL5e3d+8ufh+RZHK59FKiI0fK9Z//+fL2kSPF7yOSRC4/+7NEx46V6z/3c+XtY8eK30ekzUzi5G5Ki6gVWWnMJ91a96wpLaJWZKVJJhdTWkStyEqTRC6mtIhakZWmrUzi/Heee65/z4qoWJc2lwbCnJna2gzVV1/t37MiKtalzaWBSCaXd97p37MiKtalzaWBSCKX997r37MiKtalzaWBaCuT5oVlyso8PIwsrS4N7sp2qIUXoSkr8/AwsrSSycWUlXl4GFlaSeRiyso8PIwsrTYzaVZYNlnZzmlFklY1aP3Eq8fj0V6ENlnZzmlFklYyudhkZTunFUlaSeRik5XtnFYkabWeCefMvF7QhxXgUx/0YdlBH9Yg6MOK1NaATnc76HS3g073QdDpHklY+C6hHXyX0A6+SzgIvks4dAl/Duvf/q28zWldMM9pVes9ubP3UxH/ZJ0+Hq/WB+EnPylvc1oXzHNa1XpP9IgY11yCjph5+eXyNqd1wTynVa33RI+Icc0l2IiZvXvL25zWBfOcVrXeEz0ixjWT4CNmOFbTC/uQ8O675R3s69ezR8soxf/X4U6h5V3q2Dz8sLyDffdu1mgZSSZE/BExPnVs1q2Td7AfOcIaLSPNhTsixqeOxfS0vIP92DH2aBlJLpIRMT51iuEg0ZWfJyYmFC6kOogkwyZJKRMi5DIM5GJHKVX7gDAiGQCQDRAWACAbICwAQDZAWACAbICwAADZAGEBALIBwgIAZIOoD2tsbEx1u61NSQIALFy6Sqmxuo0Wi/5iYrJKoQEvwea7th8CESGXYSAXO51OZ5qzHQ4JAQDZAGEBALIBwgIAZAOEBQDIBggLAJANEBYAIBsgLABANjQirG9HrhvJX/wF0ZYtspotW4q6wCyPXDeS/fuJTp2S1Zw6VdQF5vOR60ayYwfRiROymhMnirqA3BC5biTvvkt09qys5uzZoi40nLGkeiHGmNNvUzF8XjqAXtd8O+So2QceKAfzc0fHTk+XNQ88ULs597Eu98xlecjxu/v2lc/x5ElezcmTZc2+fcFy+bxnLp8Pmcv27eVzPH6cV3P8eFmzfXuQXG7wzOSGkO+ho0eL59bpKHXmDC+TM2eK7YmKegZENKVCXzVHEpwSBN7Y5ZKq8iGGtKTbqwyvyKJUv3yIIS3p9rnmUpUPMaQl3V6QSzLvoap8ONKSbl/mwhJWI4eEkivB2q4kG4wbbySarnT8L1s2/PBwy5bi95rp6aI+IMnkctFFRCdPlusf+tDww8NTp4rfa06eLOoDkkwuF19MdPx4uf4zPzP88PDEieL3muPHi/pAJJPJBRcQzc0RdTqFEpcsGX54ePZs8Xuliu3n5or6gDR20p0TeKNBazjSiiArTTK5cKQVQVaaZHLhSKthWWmSyYQjrQiyImr4U8JRgUcJWjNKWhFlpUkml1HSiigrTTK5jJJWJFlpkslklLQiyYpIOF6m0+nwN65gBhsqaMljJyK7nDxl5fPt+yZyEWdCZJeTp6wWRC42OXnKyjWXZN5DNjkFkFWn09mklJqo3S6GsIjKgDUh/lVwehGa0tI47ln5jgsJnYtTJkSD0tI47lktmFxMaWkc96xCiFzT2nuoKi2N554VV1jRGkfN/1BrHavm4SFRlMPAYSSTi3l4SBTlMHAYyeRiHh4SNX4YOIxkMtGHh1UaPAysEu05246/W8G2hzXq08OGSSYX2x7WqE8PGyaZXGx7WKM+PWyQZDLRe1hVRn16GJAowqoeb1d/Rg/cdg5L04K0ksnFdg5L04K0ksnFdg5LE1layWRinsM6c4bX8hCIxoVlOzko6TEJxrBPA1uSVjK5DPs0sCVpJZPLsE8DW5BWMpkM+zSQ26cVgEaFNeqTjKiBj2pdaEFayeQyqnWhBWklk8uo1oXI0komk1GtCxGl1ZiwOB+7Rgmc02cVUVrJ5MLps4oorWRy4fRZRZJWMplw+qwiSasRYUl6RBoNXNIUGkFayeQiaQqNIK1kcpE0hTYsrWQykTSFRpBWcGHpETGSHhEdeLU+CP/1X+VtTuuCKa1qvSd6RIxrLkFHzLzzTnmb07pgSqta74keEeOaS9ARM2+8Ud7mtC6Y0qrWe6BHxLhmEnTEzOysrCnUlNbsbMhHQ41Ma5CMiPGpY/HAA/zRMprpadZoGaVkUwm4I2J86tjs28cfLaM5eZI1WkaaC3dEjE8dm+3b+aNlNMePs0bLSHKRjIjxqWNx9Ch/tIzmzBn2aJleLqxpDdE63ZtA8tibAhfGtINc7CAXO8l1ugMAgC8QFgAgGyAsAEA2QFgAgGyAsAAA2QBhAQCyAcICAGSDqA9rbGxMdbutTeEBACxcukqpsbqNFkv+4rJly2hqasr9IQUkpQa8hJrv2n4IfSAXO8jFCutoD4eEAIBsgLAAANkAYQEAsgHCAgBkA4QFAMgGCAsAkA0QFgAgG5oR1p/9GZG0X2tqqqgLzLci141k1SqiHTtkNTt2FHWBuT1y3Ui+8x2il1+W1bz8clEXmFsi1w3l7FkiaZN2t9vIhR+uilw3Es5YUr2Mj4/Xzzq97z6liIpl40befNSNG8ua++5jlRBj/Ou3iFS3t3C214uu+VbIMbMrV5bPkTlOV23fXtasXBkkEyJSt3vmcnvIXFavLp/jzp28mp07y5rVq4PlcotnLreEyuXMGaWWLlXqxhuVmp/nZTI/X2y/dCl7nDHnsV7lmclVghrFGdPO2UgvLGFV5UMMaUm3F4Stg1OCwKXbs9+YVfkQQ1rS7QWZJJVLVT7EkJZ0+xxz0fIh4klLur0wlxiZtCcspfgScpSVJGxJgB5B8+BKyEFW0kySyoUrIQdZZZsLV0KOspLm0nQm7QpLqXoZechKGjYnSM+g+dTJyFFWLpkklUudjBxllXUudTLykJVLLk1m0r6wlBouJU9ZuYQ9KtAAQcsYJiUPWblmklQuw6TkIavscxkmJU9ZuebSVCZpCEspu5zMdQdCvQgDBS3HJidzPVImSeVik5O5/kHLxSYnT1n55NJEJukIS6lBSenFUVY+YVcD1kuAoN0wJaUXB1n5ZpJULqak9OIgqwWTS1VSevGQlW8uoTPhCitO4+jEBNHGjf33bdxY3N8C5pNurXv2+uuJtm/vv2/79uL+Fkgml1/5FaKdO/vv27mzuL8Fkshl0SKiTZv679u0qbi/jYdTsx7rv9sMU1NEN9/cf9/NN8ubSwNhtuO1NkN1xw6iT32q/75PfUreXBqIZHJ5+WWiT36y/75PflLeXBqIJHLpdonGx/vvGx+XN5eGejg1603RvLBMWVX3tFqQVpeIOlTsg1Z/Rv/fbsqquqfVgrSSycWUVXVPqwVpJZGLltWWLUQ33kg0P1/83LKlFWm1mgnnuFEv+JQw0DkJfEpoB58SDoJPCSOddEcflh30YdlBH9Yg6MOKJCx0uttBp7sddLoPgk73SMLCdwnt4LuEdvBdwkHwXcKhS/iT7j/4QXmb07pgtjxU6z3RI2IU8T9dWNTbvlofhP/93/I2p3XBbHmo1ntye++nay63j9pQylNPlbc5rQtmy0O13hM9IsY1l2AjZs6fJzpxojixzmld0C0PN95Y1J0/H+qRvD8ixjWTq0Zt6ALHanphHxLed5/8RPrGjezRMkrx/3XgjojxqWOzcqW8KXT7dtZoGUkmRPwRMT51bFavljeF7tzJGi0jzYU7IsanjsWZM/IT6fPz7NEyklyucsxEWqcYDhJd+XliYkLhQqqDSDJskpQyIUIuw0AudpRStQ8II5IBANkAYQEAsgHCAgBkA4QFAMgGCAsAkA0QFgAgGyAsAEA2iPqwxsbGVLel+TsAgAVNVyk1VrfRYtFfTExWKTTgJdh81/ZDICLkMgzkYqfT6UxztsMhIQAgGyAsAEA2QFgAgGyAsAAA2QBhAQCyAcICAGQDhAUAyIZGhPX1yHUj+b3fI3rmGVnNM88UdYH5WuS6kfzpnxK98IKs5oUXirrAfDVy3Ui+9z2ivXtlNXv3FnUBuShy3Uj+53+I3npLVvPWW0VdaDhjSfVCjDGnX6di+Lx0AL2u+XrIUbPLl5cXK1i7ljc3du3asmb58trNuY/1a565fC3k+N177y2f4+Qkr2Zysqy5995guXzVM5evhszl0UfL57hnD69mz56y5tFHg+RyEZGaJ1JnhZmc7dVdFPI99OST5fM7dIiXyaFDZc2TT7JKiGhKhb5qjuTFpAQvwsYul1SVDzGkJd1eZXhFFqX65UMMaUm3zzWXqnyIIS3p9oJczvb+Jlda0u3ZuVTlQwxpSbcvc2lPWJIXVeMXpORKyEFWvaAbeXM2fi1AroQcZJV1LlwJOchKmgtXQq6yYufClZCjrHq5tCsszosr2iW/62TkKKte0MHfnNGutlwnI0dZZZ9LnYwcZeWSS52MfGQlyqVORh6y6uXSvrBGvch8ZSV+EQ6TkoesekEHfXNGk7hmmJQ8ZLUgchkmJQ9ZueYyTEq+shLnMkxKnrLq5ZKGsGwvthCycnoR2uRkrsuDDvbmjC5xjU1O5voHMRebnMz1SLmYcgohK6dcbHIy1x1ISljVF51efGXl/CI0JaUXB1n1gg7y5gyVizOmpPTiIKsFlYspKb04yMo3l7PGY/CVlXMupqT04iirXi4sYUVrHDX/Q611rN5+O9Hatf33rV1b3N8CyeRyyy1Ek5P9901OFve3QDK5XHMN0Z49/fft2VPcH5kLataj8Qu/QHToUP99hw4V9zdMtNeBOfqvtVGAzzxDdMcd/ffdcYe8uTQQyeTywgtEt97af9+tt8qbSwORTC579xJ9/OP993384/Lm0gCcrVmPxltvEX30o/33ffSj8uZSB6IIq0tEHSr2Qas/o78ITVlV97RakFYyuZiyqu5ptSCtZHIxZVXd04osrbNE9FNEdI6KLM711qNLy5RVdU8rhrQ4x416IY9zEfiUME4uYvApoR18SjjIQv+UEH1Y8XMRgT4sO+jDGmSh92Gh072dXNig090OOt0HWeid7vguYXu5sMB3Ce3gu4SDJPZdwuAn3fWIGEX8M/qLettX64Pwr/9a3ua0LpgtD9V6T/SIGNdcgo6Y+Y//KG9zWhfMlodqvSd6RIxrLkFHzKxbV97mtC6YLQ/Veg8uIqIxKk6sc1sXLuhtP0aBR8xs2VLe5rQumC0P1foQcKymF2JaWzIixqeOxfLl8qbQtWtZo2WUku1JcEfE+NSxufdeeVPo5CRrtIw0F+6IGJ86No8+Km8K3bOHNVpGkotkRIxPHYsnn5SfSD90iD1appcLaw9LdOXnTqfD3zgCksfeFLgwph3kYge52Ol0OpuUUhN122FEMgAgGyAsAEA2QFgAgGyAsAAA2QBhAQCyAcICAGQDhAUAyAZRH9bY2JjqdlubTAQAWLh0lVJjdRstlvzFZcuW0dTUlPtDCkhKDXgJNd+1/RD6QC52kIsV1tEeDgkBANkAYQEAsgHCAgBkA4QFAMgGCAsAkA0QFgAgGyAsAEA2NCOsP/kTouefl9U8/3xRF5i7IteN5PvfJ9q/X1azf39RF5ivRK4byY9+RPTmm7KaN98s6gLj+oYI/kb6938neuMNWc0bbxR1gXG9wnQjV6bmjCXVy/j4eP2s03vuKQfQb9jAm4+6YUNZc889rBJijH+9i4oLFUgvbqFr7go5Zvaxx8rnuG8fr2bfvrLmsceCZEJE6iueuXwlZC5PPFE+x4MHeTUHD5Y1TzwRLJdFROqfidQqYS6renWLQuXy+OPl8ztwgJfJgQNlzeOPs0o4j/UCInWCSB0WZnK4V3eBoEZxxrRzNtILS1hV+RBDWtLtBWHrN5kSvDkbuyJLVT7EkJZ0e0EmSeVSlQ8xpCXdXpjLqt7f5UpLuj0rl6p8iCEt6fbCXA73/i5XWtLt2xWWUnwJOcpKErbkzdb4Ne+4EnKQlTSTpHLhSshBVi65cCXkIit2LlwJOcpKmgtXQq6yaldYStXLyENW0rA5b7poVxWuk5GjrFwySSqXOhk5yso1lzoZucpKlEudjDxk5ZJLnYx8ZNW+sJQaLiVPWbmEPerN5/OmFL8xlRouJQ9ZuWaSVC7DpOQhK59chknJR1biXIZJyVNWrrkMk5KvrNIQllJ2OZnrDoR6c/q+KZ3emErZ5WSuR8okqVxscjLXI+ZiyslXVk652ORkrjvg+vhNOYWQVTrCUmpQUnpxlJVP2NU3o1583pTOb0ylBiWlFwdZ+WaSVC6mpPTiIKsQuawyHoePrJxzMSWlF0dZ+eZy2HgcvrLiCitO4+hv/AbRhg39923YUNzfAuaTbq179qqriPbt679v377i/hZIJpcrriA6eLD/voMHi/tb4I9r1qPwi79IdOBA/30HDhT3t8DlNetNEec1+fzzRJ/+dP99n/60vLk0EObM1NZmqO7fT3T11f33XX21vLk0EMnk8uabRB/7WP99H/uYvLk0EKtq1qPwxhtEV17Zf9+VV8qbSwNxuGa9KZoXlimr6p5WC9LqElGHin3Q6s/ob05TVtU9rRaklUwupqyqe1otSGsVEf0REf0dFXn8XW89qrRMWVX3tFqQ1mEiuoyI3qYik7d761GkxTlu1As+JQx0TgKfEtrBp4SD4FPCSCfd0YdlB31YdtCHNQj6sCIJC53udtDpbged7oOg0z2SsPBdQjv4LqEdfJdwEHyXcOgS/qT744+XtzmtC2bLQ7Xek7t6PxXxP11Y1Nu+Wh+E9evL25zWBbPloVrviR4R45pL0BEz1cvGcVoXzJaHgJedW0REl1BxYp3buvDHve0voYCfYFU/iOK0LpgtDwE/yLqAiC6k4sTiHcToAAAGqUlEQVQ6t3Xh8t72F1IDI2Y4VtML+5DwnnvkJ9I3bGCPllGK/6/DXULLu9SxeewxeVPovn2s0TKSTIj4I2J86tg88YS8KfTgQdZoGWku3BExPnUsHn9cfiL9wAH2aBlJLpIRMT51iuEg0ZWfJyYmFC6kOogkwyZJKRMi5DIM5GJHKVX7gDAiGQCQDRAWACAbICwAQDZAWACAbICwAADZAGEBALIBwgIAZIOoD2tsbEx1u61NSQIALFy6Sqmxuo0Wi/5iYrJKoQEvwea7th8CESGXYSAXO51OZ5qzHQ4JAQDZAGEBALIBwgIAZAOEBQDIBggLAJANEBYAIBsgLABANjQirBVD7r/oQqKnHiG6cImszou/+iuiF1+U1bz4YlEXmG9GrhvJ3/4t0UsvyWpeeqmoC8xtketGMjtLdP68rOb8+aIuIDdFrssGzlhSvRBjzOkKKi5UYLtYwVe+QErtJPU7Xxj8na5ZEXLU7IMPloP5t27lzY3durWsefDB2s25j/WbI3IZteiab4Ycv/vQQ+Vz3LaNV7NtW1nz0EPBcrnNM5fbQuYyM6PU4sVKLVmi1LlzvJpz54rtFy8u6gPkcpNnJjeFfA9FgoimVOir5kiCU5bAf/j3pLo7SP3nd3jbe4ddlQ8xpCXdXmV6pZqqfIghLen2ueai5UPEk5Z0e0EuMTKBsEYEeMFPkTo5XexhndxcrPsEzQ6bKyEHWfWCbuTN2fgLkCshB1llnQtXQg6ykubSdCY5Cquxk+76slAdIuoS0RfOE507V/zu3Hmi3zpX3N/pbdfYA7nhBqKtW8v1X//1wXNaL75Y3K/ZurWoawAzFxtRcvnVXyXatq1c/7VfGzyn9dJLxf2abduKugZIJpfFi4lmZoiWLCGamyP68IcHz2mdP1/cPzdXbDczU9QFJplMEkI0raHT6dRuvPRKoi9/vreylmjl3jJQtYZo0eeIuj8h6qwo77/nGiK6oyj50Y+JXj8w+HdtSB77UCl5ysr1y6zDXmi+L0BRJkTDpeQpq+xzGSYlT1m55NJUJkQOuTREp9PZpJSaqN2QsxumF2LsYt5yA6nZzaTmt5Oa20pqbnW5y6qIlPpuebtLxe/nthbbz24u6jn/HXLZnbUd9pnr8l1Z58XclffZtXfORCn7YZ+5/kHMxXbY53AYGCKXJjJxzqUBiHlIGHwPi4joqiuIfvj3RNdeTfShi4hoLRF927Lhd4noDqLZU0S79xH99h8Q7X+T/XDc/nUw96g0joeBvuNC9L+SGkV+u/ZOmRAN7lFpHA8DF0wu1T0qjcdhoE8uoTMh8sglMNw9rEYOe/e/SXTz7xKt/heiU6epONz7rrFRT1anThOt/l6xvURWzpjntIgaPWdVh/k/oLXzEOY5LaJGz1nVkUwu+pxWlYbOWdWRTCZtwtkN0ws57HJ+7lZS82sqhxeVZX5N8XuXv0uuu7PmYaBeHA4HlfI79CEyDpfb3MU3DwP14nA4uKByqR4G6sXxcNA3l9CZeOUSGGr7U0JNd7I4wf4+lT2tzgqi+cmmH0EF2wl2je3Tw4apnjSt/ow+19V2gl1j+/SwYZLJxTzBfu7c6E8PGySZTNqGYzW9kOe/CvNrSM1u6t/jinYiddgJds8T766PfdhJU9+TqWKGnWD3PPGefS7DTrB7nnhPKROnXBqC2m4cNWV1chWp158qvpaz5/+Kdf27xl+EdVLykFbIF2CIF6KIOil5SCvrXOqk5CGtlDKBsIYEObuK1CN/SerCJcXvLlxSrM+uRKe773bOL0B0uttBp3srtCqsPlmtJPXbv2Xf7ne+UMgM3yUM90Jkge8S2sF3CVuDK6zgJ931+XVFRNcR0XV/Q/TD/7Nv+4OniK7762I7ZdQH4b//u7zNaV0wWx6q9Z7oETGK+B9H669mVOuD8OST5W1O64LZ8lCt90SPiHHNJeiImbm54kQ6t8+q+jWe8+f7e7U80CNiXDNZ0CNmOFbTCzGtLRkR41PH4sEH5S0LW7eyRssoJduT4I6I8alj89BD8paFbdtYo2WkuXBHxPjUsZmZkbcsnDvHGi0jyUUyIsanLhWozU73WEgee1Pgwph2kIsd5GKn1U53AABoAggLAJANEBYAIBsgLABANkBYAIBsgLAAANkAYQEAskE6hUxR/9DDNul2Op3pth8EES2jdMSfSiZEyGUYyMXO1ZyNRI2jAADQJqmYHgAAaoGwAADZAGEBALIBwgIAZAOEBQDIBggLAJANEBYAIBsgLABANkBYAIBs+H+tv7uC+nNeawAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 360x360 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig,ax=plt.subplots(figsize=(5,5))\n",
    "\n",
    "#create black and white chessboard\n",
    "for i in range(size):\n",
    "    for j in range(size):\n",
    "        if (i%2==0 and j%2==0) or (i%2!=0 and j%2!=0):\n",
    "            ax.fill_between([i,i+1],j,j+1,color='black')\n",
    "\n",
    "#knight s trajectory\n",
    "knight=ax.scatter(path[0][0]+0.5,path[0][1]+0.5,\n",
    "                    color='gold',marker='*',s=250)\n",
    "    \n",
    "#chic design\n",
    "ax.set_xlim(0,size)\n",
    "ax.set_ylim(0,size)\n",
    "ax.set_xticks([])\n",
    "ax.set_yticks([])\n",
    "\n",
    "#create animations\n",
    "anim=pltani.FuncAnimation(fig,draw_chessboard,\n",
    "                          frames=size*size,\n",
    "                          interval=700,\n",
    "                          fargs=(ax,path,knight))\n",
    "anim.save('knights tour.gif')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/knights tour.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}