8 puzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8 puzzle solver script"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eight_puzzle_solver(start_node):\n",
    "    \"\"\"\n",
    "    Input\n",
    "    start_node: a starting position for the 8 puzzle game\n",
    "                e.g., [0, 1, 3, 4, 2, 5, 7, 8, 6]\n",
    "    \n",
    "    Return: a path to goal node\n",
    "    \n",
    "    goal_node = [1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
    "    \"\"\"\n",
    "    try:\n",
    "        explored, path = eight_puzzle_bfs(start_node)\n",
    "\n",
    "        print(explored)\n",
    "\n",
    "        path_formatted = [[] for i in range(len(path))]\n",
    "        for i in range(len(path)):\n",
    "            path_formatted[i] = [x[1] for x in path[i]]\n",
    "\n",
    "        for i, x in enumerate(path_formatted):\n",
    "            print(\"{0:0=2d}\".format(i), ' : ', x)\n",
    "    except:\n",
    "        print(\"Path not found\")\n",
    "        \n",
    "def eight_puzzle_bfs(start_node):\n",
    "\n",
    "    grid = [31, 32, 33, 21, 22, 23, 11, 12, 13]\n",
    "    \n",
    "    goal_node = [1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
    "    \n",
    "    start_state = tuple((zip(grid, start_node)))\n",
    "    goal_state = tuple((zip(grid, goal_node)))\n",
    "    \n",
    "    #frontier\n",
    "    queue = [start_state]\n",
    "    \n",
    "    #explored nodes\n",
    "    explored = set()\n",
    "    \n",
    "    #tracking parent child\n",
    "    parent_child = {}\n",
    "        \n",
    "    while queue:\n",
    "        current_state = queue.pop(0)\n",
    "        if current_state == goal_state:\n",
    "            #winner_state = current_state\n",
    "            path = reconstruct_path(parent_child, start_state, goal_state)\n",
    "            return 'Path found after exploring '+ str(len(explored)) + ' nodes', path\n",
    "                    \n",
    "        explored.add(current_state)\n",
    "        \n",
    "        legal_moves = possible_moves(current_state, grid)\n",
    "        \n",
    "        neighbours = eight_puzzle_neighbours(current_state, legal_moves)\n",
    "        \n",
    "        #parent_child.append((current_state, set(neighbours)))\n",
    "        \n",
    "        for neighbour in neighbours:\n",
    "            if neighbour not in explored and neighbour not in queue:\n",
    "                queue.append(neighbour)\n",
    "                parent_child[neighbour] = current_state\n",
    "              \n",
    "    return 'Path not found after exploring '+ str(len(explored)) + ' nodes'\n",
    "\n",
    "def reconstruct_path(came_from, start, goal):\n",
    "    current = goal\n",
    "    path = []\n",
    "    while current != start:\n",
    "        path.append(current)\n",
    "        current = came_from[current]\n",
    "    path.append(start) \n",
    "    path.reverse() \n",
    "    return path\n",
    "\n",
    "def eight_puzzle_neighbours(state, legal_moves):\n",
    "    list_of_neighbour_states = []\n",
    "    for x in legal_moves:\n",
    "        list_of_neighbour_states.append(neighbour_state_generate(state, x))\n",
    "    return list_of_neighbour_states\n",
    "\n",
    "def possible_moves(current_state, grid):\n",
    "    for items in current_state:\n",
    "        if items[1] == 0:\n",
    "            zero_cell = items[0]\n",
    "\n",
    "    move_up = zero_cell + 10\n",
    "    move_down = zero_cell - 10\n",
    "    move_right = zero_cell + 1\n",
    "    move_left = zero_cell - 1\n",
    "\n",
    "    moves = [move_up, move_down, move_right, move_left]\n",
    "    legal_moves = [x for x in grid if x in moves]\n",
    "    \n",
    "    return legal_moves\n",
    "\n",
    "def neighbour_state_generate(state, legal_move_cell):\n",
    "    \n",
    "    pre_neighbour_state = [list(x) for x in state]\n",
    "\n",
    "    for x in pre_neighbour_state:\n",
    "        if x[0] == legal_move_cell:\n",
    "            value_to_be_swapped = x[1]\n",
    "\n",
    "\n",
    "    for x in pre_neighbour_state:\n",
    "        if x[1] == 0:\n",
    "            x[1] = value_to_be_swapped\n",
    "\n",
    "    for x in pre_neighbour_state:\n",
    "        if x[0] == legal_move_cell:\n",
    "            x[1] = 0\n",
    "\n",
    "    neighbour_state = tuple([tuple(x) for x in pre_neighbour_state])\n",
    "    \n",
    "    return neighbour_state\n",
    "\n",
    "def check_solvability(state):\n",
    "        \"\"\" Checks if the given state is solvable \"\"\"\n",
    "\n",
    "        inversion = 0\n",
    "        for i in range(len(state)):\n",
    "            for j in range(i + 1, len(state)):\n",
    "                if (state[i] > state[j]) and state[i] != 0 and state[j] != 0:\n",
    "                    inversion += 1\n",
    "\n",
    "        return inversion % 2 == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Input the start position of the puzzle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "start_node = [1, 8, 0, 4, 3, 2, 5, 7, 6] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Check solvability"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check_solvability(start_node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Call the solver to solve the puzzle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path found after exploring 3940 nodes\n",
      "00  :  [1, 8, 0, 4, 3, 2, 5, 7, 6]\n",
      "01  :  [1, 8, 2, 4, 3, 0, 5, 7, 6]\n",
      "02  :  [1, 8, 2, 4, 0, 3, 5, 7, 6]\n",
      "03  :  [1, 0, 2, 4, 8, 3, 5, 7, 6]\n",
      "04  :  [0, 1, 2, 4, 8, 3, 5, 7, 6]\n",
      "05  :  [4, 1, 2, 0, 8, 3, 5, 7, 6]\n",
      "06  :  [4, 1, 2, 5, 8, 3, 0, 7, 6]\n",
      "07  :  [4, 1, 2, 5, 8, 3, 7, 0, 6]\n",
      "08  :  [4, 1, 2, 5, 0, 3, 7, 8, 6]\n",
      "09  :  [4, 1, 2, 0, 5, 3, 7, 8, 6]\n",
      "10  :  [0, 1, 2, 4, 5, 3, 7, 8, 6]\n",
      "11  :  [1, 0, 2, 4, 5, 3, 7, 8, 6]\n",
      "12  :  [1, 2, 0, 4, 5, 3, 7, 8, 6]\n",
      "13  :  [1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "14  :  [1, 2, 3, 4, 5, 6, 7, 8, 0]\n"
     ]
    }
   ],
   "source": [
    "eight_puzzle_solver(start_node)"
   ]
  },
  {
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}