8-Puzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8-puzzle: IA 1 - Professor Li Weigang\n",
    "### Fred Guth - 190050411 - 21/03/2019"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sortedcontainers import SortedDict\n",
    "import heapq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__moves__ guarda as movimentações (swaps) possíveis para cada posição do tabuleiro.\n",
    "O tabuleiro é representado por uma simples lista ou um número. \n",
    "Por exemplo, a posição inicial é o estado [5,4,0,6,1,8,7,3,2] e também pode ser representado por 540618732."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "moves=np.array([[1,3],[0,2,4],[1,5],[1,4,6],[1,3,5,7],[2,4,8],[3,7],[6,4,8],[5,7]])\n",
    "initial = [2,8,3,1,6,4,7,0,5] # 0 é o espaço vazio\n",
    "final = [1,2,3,8,0,4,7,6,5]\n",
    "visited = SortedDict()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# \"Troca\" alguma posição do tabuleiro com o espaço vazio.  Não verifica se o swap é válido.\n",
    "def Swap(state, pos):\n",
    "    empty = state.index(0)\n",
    "    state[empty], state[pos] = state[pos], state[empty]\n",
    "    return state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imprime o tabuleiro\n",
    "def PrintBoard(state):\n",
    "    print (np.asarray(state).reshape((3,3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Transforma a representação do tabuleiro por lista em representação por número\n",
    "#  [0, 2, 3, 8, 4, 1, 7, 6, 5] => 23841765\n",
    "def Numerify(state):\n",
    "    return int(\"\".join(map(str, state[:]))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Transforma a representação do tabuleiro por lista em representação por número\n",
    "# 23841765 => [0, 2, 3, 8, 4, 1, 7, 6, 5]\n",
    "def Listify(number):\n",
    "    list =  [int(x) for x in str(number)]\n",
    "    if (len(list)<9):\n",
    "        list = [0] + list\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imprime todas as posições do tabuleiro do estado inicial ao \"state\"\n",
    "def Trace(state, visited):\n",
    "    stack = []\n",
    "    stack.append(state)\n",
    "    parent = visited[Numerify(state)]['parent']\n",
    "    while (parent is not None):\n",
    "        stack.insert(0, parent)\n",
    "        parent = visited[Numerify(parent)]['parent']\n",
    "    for i, s in enumerate(stack):\n",
    "        print(f'position #{i}:')\n",
    "        PrintBoard(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def TraceTree(depth, visited):\n",
    "    tree = {}\n",
    "    for i in visited:\n",
    "        if (visited[i][\"moves\"] in tree):\n",
    "            tree[visited[i][\"moves\"]].append(i)\n",
    "        else:\n",
    "            tree[visited[i][\"moves\"]]=[i]  \n",
    "    for j in range(0, len(tree)):\n",
    "        print(\"-----------------\")\n",
    "        print(\"depth:\", j)\n",
    "        for k in tree[j]:\n",
    "            PrintBoard(Listify(k))\n",
    "            if (k == Numerify(final)):\n",
    "                print ('*')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Primeira Abordagem: BFS\n",
    "O problema do Breadth-First Search é que não há nenhuma priorização entre os estados enfileirados para serem buscados."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Breadth-First Search\n",
    "def BFS(source):\n",
    "    counter = 0\n",
    "    visited[Numerify(source)]={'moves': 0, 'parent': None}\n",
    "    queue = []\n",
    "    queue.insert(0,source) \n",
    "    while (len(queue) > 0):\n",
    "        u = queue.pop()\n",
    "        g = visited[Numerify(u[:])]['moves'] # m = g(state) = moves to current state\n",
    "        empty = u.index(0) # where is empty\n",
    "        for v in moves[empty]:\n",
    "            state = Swap(u[:], v) # u[:] makes a copy of u\n",
    "            if not(visited.__contains__(Numerify(state))):\n",
    "\n",
    "                visited[Numerify(state)]={'moves':g+1, 'parent': u}\n",
    "                if (Numerify(state) == Numerify(final)):\n",
    "                        print (f'{counter:,} evaluations.')\n",
    "                        print (visited[Numerify(state)])\n",
    "                        return\n",
    "                else:\n",
    "                    counter = counter + 1\n",
    "                    queue.insert(0,state)\n",
    "    return visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "48 evaluations.\n",
      "{'moves': 5, 'parent': [1, 2, 3, 0, 8, 4, 7, 6, 5]}\n"
     ]
    }
   ],
   "source": [
    "BFS(initial)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------\n",
      "depth: 0\n",
      "[[2 8 3]\n",
      " [1 6 4]\n",
      " [7 0 5]]\n",
      "-----------------\n",
      "depth: 1\n",
      "[[2 8 3]\n",
      " [1 0 4]\n",
      " [7 6 5]]\n",
      "[[2 8 3]\n",
      " [1 6 4]\n",
      " [0 7 5]]\n",
      "[[2 8 3]\n",
      " [1 6 4]\n",
      " [7 5 0]]\n",
      "-----------------\n",
      "depth: 2\n",
      "[[2 0 3]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "[[2 8 3]\n",
      " [0 1 4]\n",
      " [7 6 5]]\n",
      "[[2 8 3]\n",
      " [0 6 4]\n",
      " [1 7 5]]\n",
      "[[2 8 3]\n",
      " [1 4 0]\n",
      " [7 6 5]]\n",
      "[[2 8 3]\n",
      " [1 6 0]\n",
      " [7 5 4]]\n",
      "-----------------\n",
      "depth: 3\n",
      "[[0 2 3]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "[[2 0 3]\n",
      " [8 1 4]\n",
      " [7 6 5]]\n",
      "[[2 0 3]\n",
      " [8 6 4]\n",
      " [1 7 5]]\n",
      "[[2 3 0]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "[[2 8 0]\n",
      " [1 4 3]\n",
      " [7 6 5]]\n",
      "[[2 8 0]\n",
      " [1 6 3]\n",
      " [7 5 4]]\n",
      "[[2 8 3]\n",
      " [1 0 6]\n",
      " [7 5 4]]\n",
      "[[2 8 3]\n",
      " [1 4 5]\n",
      " [7 6 0]]\n",
      "[[2 8 3]\n",
      " [6 0 4]\n",
      " [1 7 5]]\n",
      "[[2 8 3]\n",
      " [7 1 4]\n",
      " [0 6 5]]\n",
      "-----------------\n",
      "depth: 4\n",
      "[[0 2 3]\n",
      " [8 1 4]\n",
      " [7 6 5]]\n",
      "[[0 2 3]\n",
      " [8 6 4]\n",
      " [1 7 5]]\n",
      "[[1 2 3]\n",
      " [0 8 4]\n",
      " [7 6 5]]\n",
      "[[2 0 3]\n",
      " [1 8 6]\n",
      " [7 5 4]]\n",
      "[[2 0 3]\n",
      " [6 8 4]\n",
      " [1 7 5]]\n",
      "[[2 0 8]\n",
      " [1 4 3]\n",
      " [7 6 5]]\n",
      "[[2 0 8]\n",
      " [1 6 3]\n",
      " [7 5 4]]\n",
      "[[2 1 3]\n",
      " [8 0 4]\n",
      " [7 6 5]]\n",
      "[[2 3 0]\n",
      " [8 1 4]\n",
      " [7 6 5]]\n",
      "[[2 3 0]\n",
      " [8 6 4]\n",
      " [1 7 5]]\n",
      "[[2 3 4]\n",
      " [1 8 0]\n",
      " [7 6 5]]\n",
      "[[2 6 3]\n",
      " [8 0 4]\n",
      " [1 7 5]]\n",
      "[[2 8 3]\n",
      " [0 1 6]\n",
      " [7 5 4]]\n",
      "[[2 8 3]\n",
      " [1 4 5]\n",
      " [7 0 6]]\n",
      "[[2 8 3]\n",
      " [1 5 6]\n",
      " [7 0 4]]\n",
      "[[2 8 3]\n",
      " [6 4 0]\n",
      " [1 7 5]]\n",
      "[[2 8 3]\n",
      " [6 7 4]\n",
      " [1 0 5]]\n",
      "[[2 8 3]\n",
      " [7 1 4]\n",
      " [6 0 5]]\n",
      "-----------------\n",
      "depth: 5\n",
      "[[0 2 3]\n",
      " [6 8 4]\n",
      " [1 7 5]]\n",
      "[[1 0 3]\n",
      " [2 8 4]\n",
      " [7 6 5]]\n",
      "[[1 2 3]\n",
      " [8 0 4]\n",
      " [7 6 5]]\n",
      "*\n",
      "[[2 3 0]\n",
      " [6 8 4]\n",
      " [1 7 5]]\n",
      "[[2 3 4]\n",
      " [8 6 0]\n",
      " [1 7 5]]\n",
      "[[2 6 3]\n",
      " [0 8 4]\n",
      " [1 7 5]]\n",
      "[[2 6 3]\n",
      " [8 4 0]\n",
      " [1 7 5]]\n",
      "[[2 6 3]\n",
      " [8 7 4]\n",
      " [1 0 5]]\n",
      "[[2 8 0]\n",
      " [6 4 3]\n",
      " [1 7 5]]\n",
      "[[2 8 3]\n",
      " [6 4 5]\n",
      " [1 7 0]]\n",
      "[[2 8 3]\n",
      " [6 7 4]\n",
      " [0 1 5]]\n",
      "[[2 8 3]\n",
      " [6 7 4]\n",
      " [1 5 0]]\n",
      "[[8 2 3]\n",
      " [0 6 4]\n",
      " [1 7 5]]\n"
     ]
    }
   ],
   "source": [
    "TraceTree(5,visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "position #0:\n",
      "[[2 8 3]\n",
      " [1 6 4]\n",
      " [7 0 5]]\n",
      "position #1:\n",
      "[[2 8 3]\n",
      " [1 0 4]\n",
      " [7 6 5]]\n",
      "position #2:\n",
      "[[2 0 3]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "position #3:\n",
      "[[0 2 3]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "position #4:\n",
      "[[1 2 3]\n",
      " [0 8 4]\n",
      " [7 6 5]]\n",
      "position #5:\n",
      "[[1 2 3]\n",
      " [8 0 4]\n",
      " [7 6 5]]\n"
     ]
    }
   ],
   "source": [
    "Trace(final, visited)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Segunda Abordagem: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "moves=np.array([[1,3],[0,2,4],[1,5],[1,4,6],[1,3,5,7],[2,4,8],[3,7],[6,4,8],[5,7]])\n",
    "initial = [2,8,3,1,6,4,7,0,5] # 0 marks where it is empty\n",
    "final = [1,2,3,8,0,4,7,6,5]\n",
    "visited = SortedDict()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Checa o número de posições diferentes entre dois tabuleiros\n",
    "def GetDistance(n1, n2):\n",
    "    s1, s2 = str(Numerify(n1)), str(Numerify(n2))\n",
    "    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A_star: usaremos um heap para fila de prioridade e a função *heuristic* para determinar o custo\n",
    "def A_star(heuristic, source):\n",
    "    counter = 0\n",
    "    visited[Numerify(source)]={'moves': 0, 'parent': None}\n",
    "    queue = [] \n",
    "    heapq.heappush(queue, (0, source))\n",
    "    while (len(queue) > 0):\n",
    "        u = heapq.heappop(queue)[1]\n",
    "        g = visited[Numerify(u)]['moves'] # g = g(state) = moves to current state\n",
    "        empty = u.index(0) # where is empty\n",
    "        for v in moves[empty]:\n",
    "            state = Swap(u[:], v) # u[:] makes a copy of u\n",
    "            counter = counter + 1\n",
    "            if not(visited.__contains__(Numerify(state))):\n",
    "                visited[Numerify(state)]={'moves':g+1, 'parent': u}\n",
    "                if (Numerify(state) == Numerify(final)):\n",
    "                        print (f'{counter:,} evaluations.')\n",
    "                        print (visited[Numerify(state)])\n",
    "                        return\n",
    "                else:\n",
    "                    h = heuristic(state, final)\n",
    "                    heapq.heappush(queue, ((g + h), state)) # f(state)= g(state)+h(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "71 evaluations.\n",
      "{'moves': 5, 'parent': [1, 2, 3, 0, 8, 4, 7, 6, 5]}\n"
     ]
    }
   ],
   "source": [
    "A_star(GetDistance, initial)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "position #0:\n",
      "[[2 8 3]\n",
      " [1 6 4]\n",
      " [7 0 5]]\n",
      "position #1:\n",
      "[[2 8 3]\n",
      " [1 0 4]\n",
      " [7 6 5]]\n",
      "position #2:\n",
      "[[2 0 3]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "position #3:\n",
      "[[0 2 3]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "position #4:\n",
      "[[1 2 3]\n",
      " [0 8 4]\n",
      " [7 6 5]]\n",
      "position #5:\n",
      "[[1 2 3]\n",
      " [8 0 4]\n",
      " [7 6 5]]\n"
     ]
    }
   ],
   "source": [
    "Trace(final, visited)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Terceira Abordagem: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "moves=np.array([[1,3],[0,2,4],[1,5],[1,4,6],[1,3,5,7],[2,4,8],[3,7],[6,4,8],[5,7]])\n",
    "initial = [2,8,3,1,6,4,7,0,5] # 0 marks where it is empty\n",
    "final = [1,2,3,8,0,4,7,6,5]\n",
    "visited = SortedDict()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def manhattan_distance(current, goal):\n",
    "    return sum(abs(b%3 - g%3) + abs(b//3 - g//3)\n",
    "        for b, g in ((current.index(i), goal.index(i)) for i in range(1, 9)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14 evaluations.\n",
      "{'moves': 5, 'parent': [1, 2, 3, 0, 8, 4, 7, 6, 5]}\n"
     ]
    }
   ],
   "source": [
    "A_star(manhattan_distance, initial)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------\n",
      "depth: 0\n",
      "[[2 8 3]\n",
      " [1 6 4]\n",
      " [7 0 5]]\n",
      "-----------------\n",
      "depth: 1\n",
      "[[2 8 3]\n",
      " [1 0 4]\n",
      " [7 6 5]]\n",
      "[[2 8 3]\n",
      " [1 6 4]\n",
      " [0 7 5]]\n",
      "[[2 8 3]\n",
      " [1 6 4]\n",
      " [7 5 0]]\n",
      "-----------------\n",
      "depth: 2\n",
      "[[2 0 3]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "[[2 8 3]\n",
      " [0 1 4]\n",
      " [7 6 5]]\n",
      "[[2 8 3]\n",
      " [1 4 0]\n",
      " [7 6 5]]\n",
      "-----------------\n",
      "depth: 3\n",
      "[[0 2 3]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "[[2 3 0]\n",
      " [1 8 4]\n",
      " [7 6 5]]\n",
      "-----------------\n",
      "depth: 4\n",
      "[[1 2 3]\n",
      " [0 8 4]\n",
      " [7 6 5]]\n",
      "-----------------\n",
      "depth: 5\n",
      "[[1 0 3]\n",
      " [2 8 4]\n",
      " [7 6 5]]\n",
      "[[1 2 3]\n",
      " [8 0 4]\n",
      " [7 6 5]]\n",
      "*\n"
     ]
    }
   ],
   "source": [
    "TraceTree(final, visited)"
   ]
  },
  {
   "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}