The 3 by 3 Puzzle Problem.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class puzzle(object):\n",
    "    def __init__(self, order):\n",
    "        self.label = order\n",
    "        for index in range(9):\n",
    "            if order[index] == '0':\n",
    "                self.spot = index\n",
    "                return None\n",
    "    def transition(self, to):\n",
    "        label = self.label\n",
    "        blankLocation = self.spot\n",
    "        newBlankLabel = str(label[to])\n",
    "        newLabel = ''\n",
    "        for i in range(9):\n",
    "            if i == to:\n",
    "                newLabel += '0'\n",
    "            elif i == blankLocation:\n",
    "                newLabel += newBlankLabel\n",
    "            else:\n",
    "                newLabel += str(label[i])\n",
    "        return puzzle(newLabel)\n",
    "    def __str__(self):\n",
    "        return self.label"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def DFSWithGeneratorShortest(start, end, path = [], shortest = None):\n",
    "    #assumes graph is a Digraph\n",
    "    #assumes start and end are nodes in graph\n",
    "    if start.label == end.label:\n",
    "        return path\n",
    "    for shift in shiftDict[start.spot]:\n",
    "        new = start.transition(shift)\n",
    "        if new.label not in path: #avoid cycles\n",
    "            if shortest == None or len(path) < len(shortest):\n",
    "                newPath = DFSWithGeneratorShortest(new,end,path,shortest)\n",
    "                if newPath != None:\n",
    "                    shortest = newPath\n",
    "    return shortest\n",
    "\n",
    "def BFSWithGenerator(start, end, q = []):\n",
    "    initPath = [start]\n",
    "    q.append(initPath)\n",
    "    while len(q) != 0:\n",
    "        tmpPath = q.pop(0)\n",
    "        lastNode = tmpPath[len(tmpPath) - 1]\n",
    "        if lastNode.label == end.label:\n",
    "            return tmpPath\n",
    "        for shift in shiftDict[lastNode.spot]:\n",
    "            new = lastNode.transition(shift)\n",
    "            if notInPath(new, tmpPath):\n",
    "                newPath = tmpPath + [new]\n",
    "                q.append(newPath)\n",
    "    return None\n",
    "\n",
    "def DFSWithGenerator(start, end, stack = []):\n",
    "    #assumes graph is a Digraph\n",
    "    #assumes start and end are nodes in graph\n",
    "    initPath = [start]\n",
    "    stack.insert(0, initPath)\n",
    "    while len(stack)!= 0:\n",
    "        tmpPath = stack.pop(0)\n",
    "        lastNode = tmpPath[len(tmpPath) - 1]\n",
    "        if lastNode.label == end.label:\n",
    "            return tmpPath\n",
    "        for shift in shiftDict[lastNode.spot]:\n",
    "            new = lastNode.transition(shift)\n",
    "            if notInPath(new, tmpPath): #avoid cycles\n",
    "                newPath = tmpPath + [new]\n",
    "                stack.insert(0, newPath)\n",
    "    return None\n",
    "\n",
    "\n",
    "def notInPath(node, path):\n",
    "    for elt in path:\n",
    "        if node.label == elt.label:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "shiftDict = {}\n",
    "shiftDict[0] = [1, 3]\n",
    "shiftDict[1] = [0, 2, 4]\n",
    "shiftDict[2] = [1, 5]\n",
    "shiftDict[3] = [0, 4, 6]\n",
    "shiftDict[4] = [1, 3, 5, 7]\n",
    "shiftDict[5] = [2, 4, 8]\n",
    "shiftDict[6] = [3, 7]\n",
    "shiftDict[7] = [4, 6, 8]\n",
    "shiftDict[8] = [5, 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "goal = puzzle('012345678')\n",
    "test1 = puzzle('125638047')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def printGrid(pzl):\n",
    "    data = pzl.label\n",
    "    print data[0], data[1], data[2]\n",
    "    print data[3], data[4], data[5]\n",
    "    print data[6], data[7], data[8]\n",
    "    print ''\n",
    "\n",
    "def printSolution(path):\n",
    "    for elt in path:\n",
    "        printGrid(elt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 5\n",
      "6 3 8\n",
      "0 4 7\n",
      "\n",
      "1 2 5\n",
      "0 3 8\n",
      "6 4 7\n",
      "\n",
      "1 2 5\n",
      "3 0 8\n",
      "6 4 7\n",
      "\n",
      "1 2 5\n",
      "3 4 8\n",
      "6 0 7\n",
      "\n",
      "1 2 5\n",
      "3 4 8\n",
      "6 7 0\n",
      "\n",
      "1 2 5\n",
      "3 4 0\n",
      "6 7 8\n",
      "\n",
      "1 2 0\n",
      "3 4 5\n",
      "6 7 8\n",
      "\n",
      "1 0 2\n",
      "3 4 5\n",
      "6 7 8\n",
      "\n",
      "0 1 2\n",
      "3 4 5\n",
      "6 7 8\n",
      "\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "path = BFSWithGenerator(test1, goal)\n",
    "print printSolution(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}