RushHour.ipynb

{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "U78fwbhZ26xA"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "import cv2\n",
        "import random\n",
        "import time\n",
        "from functools import cmp_to_key"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "WckrFTdn-gaX"
      },
      "outputs": [],
      "source": [
        "# Constants\n",
        "HORIZONTAL = 0\n",
        "VERTICAL = 1\n",
        "red = (220,0,0)\n",
        "blue = (0,120,170)\n",
        "\n",
        "class Car:\n",
        "  next_id = 2\n",
        "  @staticmethod\n",
        "  def reset_id_generator():\n",
        "    Car.next_id = 2\n",
        "  \n",
        "  def __init__(self, column:int, row:int, orientation:int, size:int, is_red=False) -> None:\n",
        "    self.color = blue\n",
        "    if is_red:\n",
        "      self.id = 1\n",
        "      self.color = red\n",
        "    else:\n",
        "      self.id = Car.next_id\n",
        "      Car.next_id += 1\n",
        "    self.column = column\n",
        "    self.row = row\n",
        "    self.orientation = orientation\n",
        "    self.size = size\n",
        "\n",
        "  def is_horizontal(self):\n",
        "    return self.orientation == HORIZONTAL \n",
        "  \n",
        "  def occupied_cells(self):\n",
        "    cells = []\n",
        "    if self.is_horizontal():\n",
        "      for dx in range(self.size):\n",
        "        cells.append((self.column + dx, self.row))\n",
        "    else:\n",
        "      for dy in range(self.size):\n",
        "        cells.append((self.column, self.row + dy))\n",
        "    return cells\n",
        "  \n",
        "  # each car has a constant position that never changes and a variable position\n",
        "  # for horizontal cars: the constant position is the row\n",
        "  #                      the variable one is the column\n",
        "  # for vertical cars it is the inverse\n",
        "  def get_variable_position(self):\n",
        "    if self.is_horizontal():\n",
        "      return self.column\n",
        "    return self.row\n",
        "  \n",
        "  def get_constant_position(self):\n",
        "    if self.is_horizontal():\n",
        "      return self.row\n",
        "    return self.column\n",
        "\n",
        "  def possible_moves(self, parking):\n",
        "    moves = []\n",
        "    x = self.column\n",
        "    y = self.row\n",
        "    if self.is_horizontal():\n",
        "      dx = -1\n",
        "      while parking.is_free(x+dx,y) :\n",
        "        moves.append(dx)\n",
        "        dx -= 1\n",
        "      dx = 1\n",
        "      while parking.is_free(x + self.size-1 + dx,y):\n",
        "        moves.append(dx)\n",
        "        dx += 1\n",
        "    else:\n",
        "      dy = -1\n",
        "      while parking.is_free(x,y+dy) :\n",
        "        moves.append(dy)\n",
        "        dy -= 1\n",
        "      dy = 1\n",
        "      while parking.is_free(x,y + self.size-1 + dy):\n",
        "        moves.append(dy)\n",
        "        dy += 1\n",
        "    return moves\n",
        "  \n",
        "  def move(self, dxy):\n",
        "    if self.is_horizontal():\n",
        "      self.column += dxy\n",
        "    else:\n",
        "      self.row += dxy\n",
        "\n",
        "\n",
        "\n",
        "class Parking:\n",
        "  def __init__(self, width:int, height:int) -> None:\n",
        "    self.width = width\n",
        "    self.height = height\n",
        "    self.board = np.zeros((width, height), dtype=int)\n",
        "  \n",
        "  def put_car(self, car:Car):\n",
        "    car_cells = car.occupied_cells()\n",
        "    # check that the car emplacement is free\n",
        "    for (x,y) in car_cells:\n",
        "      if not self.is_free(x,y):\n",
        "        return False\n",
        "    # put the car in parking\n",
        "    for (x,y) in car_cells:\n",
        "      self.board[x,y] = car.id\n",
        "    return True\n",
        "  \n",
        "  def car_on_cell(self,x,y):\n",
        "    if (x<0 or x>=self.width):\n",
        "      return -1\n",
        "    if (y<0 or y>=self.height):\n",
        "      return -1\n",
        "    return self.board[x,y]\n",
        "  \n",
        "  def is_free(self,x,y):\n",
        "    return (self.car_on_cell(x,y) == 0)\n",
        "  \n",
        "  def remove(self, car:Car):\n",
        "    car_cells = car.occupied_cells()\n",
        "    for (x,y) in car_cells:\n",
        "      self.board[x,y] = 0\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "id": "lDmbz8VC-_z-"
      },
      "outputs": [],
      "source": [
        "class RushHour:\n",
        "  def __init__(self, parking) -> None:\n",
        "    self.parking = parking\n",
        "    self.cars = {}\n",
        "    Car.reset_id_generator()\n",
        "    self.car_ids = [] # need to keep a fixed order of the ids for \"int_repr\"\n",
        "    # the maximum possible position for a car (assuming it has a size >1) is: \n",
        "    self.max_pos = max(self.parking.width, self.parking.height) - 2\n",
        "  \n",
        "  def int_repr(self):\n",
        "    # the integer representation is the positions of the cars written in base max_pos\n",
        "    state = 0\n",
        "    power = 1\n",
        "    for id in self.car_ids:\n",
        "      state += power * self.cars[id].get_variable_position()\n",
        "      power *= self.max_pos\n",
        "    return state\n",
        "  \n",
        "  def add_car(self, car:Car):\n",
        "    if self.parking.put_car(car):\n",
        "      self.cars[car.id] = car\n",
        "      self.car_ids.append(car.id)\n",
        "      return True\n",
        "    print(f\"car {car.id} could not be added because position is invalid or taken\")\n",
        "    return False\n",
        "\n",
        "  def possible_moves(self, leave=-1):\n",
        "    moves = []\n",
        "    for car_id in self.cars:\n",
        "      if car_id != leave: \n",
        "        car_moves = self.cars[car_id].possible_moves(self.parking)\n",
        "        for dxy in car_moves:\n",
        "          moves.append((car_id, dxy))\n",
        "    return moves\n",
        "\n",
        "  def move_car(self, move):\n",
        "    \"\"\"\n",
        "    - move must be an available move for the car\n",
        "    \"\"\"\n",
        "    car_id, dxy = move\n",
        "    car = self.cars[car_id]\n",
        "    # move the car\n",
        "    self.parking.remove(car)\n",
        "    car.move(dxy)\n",
        "    # if the parking emplacement is not free, move the car back to its first place\n",
        "    if not self.parking.put_car(car):\n",
        "      car.move(-dxy)\n",
        "      self.parking.put_car(car)\n",
        "      return False\n",
        "    return True\n",
        "  \n",
        "  def cancel_move_car(self, move):\n",
        "    car_id, dxy = move\n",
        "    self.move_car((car_id, -dxy))\n",
        "\n",
        "  def won(self):\n",
        "    \"\"\"\n",
        "    - the game is won if there are no obstacles between the red\n",
        "      car and the last cell of its row\n",
        "    \"\"\"\n",
        "    red_car = self.cars[1]\n",
        "    for column in range(red_car.column + red_car.size, self.parking.width):\n",
        "      if not self.parking.is_free(column, red_car.row):\n",
        "        return False\n",
        "    return True\n",
        "  \n",
        "  def dist_to_exit(self):\n",
        "    red_car = self.cars[1]\n",
        "    return self.parking.width - (red_car.column + red_car.size);"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "CfyTs3_JXo_w"
      },
      "outputs": [],
      "source": [
        "class Drawing:\n",
        "  CELL_SIZE = 50\n",
        "  MARGIN = CELL_SIZE // 8\n",
        "\n",
        "  @staticmethod\n",
        "  def show_grid(parking, img, color=(150,150,150)):\n",
        "    xmin, ymin = 0, 0\n",
        "    xmax = parking.width*Drawing.CELL_SIZE\n",
        "    ymax = parking.height*Drawing.CELL_SIZE\n",
        "    for row in range(1, parking.height):\n",
        "      y = row * Drawing.CELL_SIZE\n",
        "      cv2.line(img, (xmin,y), (xmax,y), color, 1)\n",
        "    for column in range(1, parking.width):\n",
        "      x = column * Drawing.CELL_SIZE\n",
        "      cv2.line(img, (x,ymin), (x,ymax), color, 1)\n",
        "\n",
        "  @staticmethod\n",
        "  def show_car(car, img):\n",
        "    CELL_SIZE = Drawing.CELL_SIZE\n",
        "    MARGIN = Drawing.MARGIN\n",
        "    if car.is_horizontal():\n",
        "      xmin = car.column * CELL_SIZE + MARGIN\n",
        "      ymin = car.row * CELL_SIZE + MARGIN\n",
        "      xmax = (car.column + car.size) * CELL_SIZE - MARGIN\n",
        "      ymax = (car.row + 1) * CELL_SIZE - MARGIN\n",
        "    else:\n",
        "      xmin = car.column * CELL_SIZE + MARGIN\n",
        "      ymin = car.row * CELL_SIZE + MARGIN\n",
        "      xmax = (car.column + 1) * CELL_SIZE - MARGIN\n",
        "      ymax = (car.row + car.size) * CELL_SIZE - MARGIN\n",
        "    cv2.rectangle(img, (xmin,ymin), (xmax,ymax), car.color, (-1))\n",
        "    cv2.rectangle(img, (xmin,ymin), (xmax,ymax), (0,0,0), (2))\n",
        "  \n",
        "  @staticmethod\n",
        "  def show_parking(rush_hour):\n",
        "    parking = rush_hour.parking\n",
        "    img_height = Drawing.CELL_SIZE * parking.height\n",
        "    img_width = Drawing.CELL_SIZE * parking.width\n",
        "    img = np.zeros((img_height, img_width, 3), dtype=\"uint8\")\n",
        "    img[:,:,:] = (200,200,170)\n",
        "\n",
        "    Drawing.show_grid(parking, img)\n",
        "    for car in rush_hour.cars.values():\n",
        "      Drawing.show_car(car, img)\n",
        "    \n",
        "    return img\n",
        "\n",
        "def imshow(img):\n",
        "  plt.figure(figsize=(6,6))\n",
        "  plt.axis('off')\n",
        "  plt.imshow(img) \n",
        "  plt.show() "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0EZ3DuHTXKkW"
      },
      "source": [
        "# **Solver BFS**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "s7kC7iISXvVL"
      },
      "outputs": [],
      "source": [
        "class Solver_BFS:\n",
        "  @staticmethod\n",
        "  def solve(puzzle):\n",
        "    EXECUTE = 1\n",
        "    EXPLORE = 0\n",
        "    CANCEL = -1\n",
        "    queue = []\n",
        "    winning_moves = [] # stack\n",
        "    possible_moves = puzzle.possible_moves()\n",
        "    for move in possible_moves:\n",
        "      queue.append((move, EXPLORE))\n",
        "    visited = []\n",
        "    depth = 1\n",
        "    while len(queue) > 0:\n",
        "      move, action = queue.pop(0)\n",
        "      if action == EXPLORE:\n",
        "        puzzle.move_car(move)\n",
        "        if puzzle.won():\n",
        "          winning_moves.append(move)\n",
        "          break\n",
        "        repr = puzzle.int_repr()\n",
        "        if repr not in visited:\n",
        "          queue.append((move, EXECUTE))\n",
        "          visited.append(repr)\n",
        "          next_moves = puzzle.possible_moves()\n",
        "          for next_move in next_moves:\n",
        "            queue.append((next_move, EXPLORE))\n",
        "          queue.append((move, CANCEL))\n",
        "        puzzle.cancel_move_car(move)\n",
        "      elif action == EXECUTE:\n",
        "        depth += 1\n",
        "        puzzle.move_car(move)\n",
        "        queue.append((move, EXECUTE))\n",
        "        winning_moves.append(move)\n",
        "      else:\n",
        "        depth -= 1\n",
        "        puzzle.cancel_move_car(move)\n",
        "        queue.append((move, CANCEL))\n",
        "        winning_moves.pop()\n",
        "    for move in winning_moves[::-1]:\n",
        "      puzzle.cancel_move_car(move)\n",
        "    winning_moves.append((1,puzzle.dist_to_exit()))\n",
        "    return winning_moves"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pHJdX1diVcHc"
      },
      "source": [
        "# **Solver DFS**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "id": "C1a4OX9PVbB_"
      },
      "outputs": [],
      "source": [
        "class Solver_DFS:\n",
        "  @staticmethod\n",
        "  def solve_backtrack(puzzle, visited, winning_moves, leave=-1, max_moves=np.inf): \n",
        "    if puzzle.won():\n",
        "      return True\n",
        "    if max_moves == 0:\n",
        "      return False\n",
        "    repr = puzzle.int_repr()\n",
        "    if repr in visited:\n",
        "      return False\n",
        "    visited.append(repr)\n",
        "    moves = puzzle.possible_moves(leave=leave)\n",
        "    random.shuffle(moves)\n",
        "    for move in moves:\n",
        "      puzzle.move_car(move)\n",
        "      is_solved =  Solver_DFS.solve_backtrack(\n",
        "      \t  puzzle,\n",
        "          visited,\n",
        "          winning_moves,\n",
        "          leave=move[0],\n",
        "          max_moves=max_moves-1)\n",
        "      puzzle.cancel_move_car(move)\n",
        "      if is_solved:\n",
        "        winning_moves.append(move)\n",
        "        return True\n",
        "    return False\n",
        "  \n",
        "  @staticmethod\n",
        "  def solve(puzzle, max_moves=np.inf):\n",
        "    visited = []\n",
        "    winning_moves = []\n",
        "    solved = Solver_DFS.solve_backtrack(puzzle, visited, winning_moves, max_moves)\n",
        "    winning_moves.reverse()\n",
        "    winning_moves.append((1,puzzle.dist_to_exit()))\n",
        "    return solved, winning_moves\n",
        "\n",
        "  @staticmethod\n",
        "  def solve_best(puzzle, iters:int):\n",
        "    best_moves = []\n",
        "    min_moves = np.inf\n",
        "    for n in range(iters):\n",
        "      solved, winning_moves = Solver_DFS.solve(puzzle, max_moves=max(200, min_moves-1))\n",
        "      if solved and len(winning_moves) < min_moves:\n",
        "        best_moves = winning_moves[:]\n",
        "        min_moves = len(winning_moves)\n",
        "    return best_moves"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lWBdEzLUXVBP"
      },
      "source": [
        "## Tests"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 357
        },
        "id": "bx8vANZmXUMg",
        "outputId": "5ed28239-c8b9-41a5-80cb-114f7dec615d"
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAPEUlEQVR4nO3cT2yc9ZnA8WdmMs5S4lQ0VLmAmwvaSqiAgpRGalRL4QK9gColaLd7CFz2wAUiqu1ltcdCq0VIFK3U1YpDW0WocKNd5VCplrKH4lYo5FIpPaQXO1FFUIsd/G/edw+FQpqJM7Yfz8/vO5/PiZgZ63nzeL7zvjPjdOq6DgB2rlt6AIC2EFSAJIIKkERQAZIIKkASQQVIsm+z//mb3/y8lZ+pWlhYjrW1Ko4cmS49Sqq6ruO99z6IRx45FN1up/Q4qeysedq6s4iIr3/91NBlOUMFSCKoAEkEFSDJpq+hTpq6ruOVV96IJvw67tGjD8bJk8dHvv38/KWYm3t3FyfaXcvLG1FVdUxP90uPsm1t3tnZs89Et+v8TFA/UVVVnDv3i3jrrfONCOrly3+MXq8bs7PH7njb+flL8eabv4wLF343hsm4nTbv7PDhe+P06Sdi//6p0qMU5SnlE1VVxWuv/aQRMY2IuHjx9/HOO78e6bZzc+825oHZZm3e2euv/yxWV9dKj1GcM9Tb+fJMRG8PXl5+eDVidXn79+/vjzh0X9483Flbd1YPIq5dKT3FniKot/Pt70bcc7j0FLd6+4cRl+e3f/9D90Wc+X7ePNxZW3e2shTx6rOlp9hTXPIDJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZLsKz0AY1YPIlaWSk8xWaqN0hMwJoI6aa5diXj12dJTQCu55AdIIqgT4OzZZ+K5575TeoyJd+rU4/HSSy+WHoNd5JJ/AnS73Xj66W/FU089VnqUbbt69eNYW6tiZubu0qNsW7/fj17POUybCeqEmJrqx9RUv/QY2/bRR53o96uYnj5QehS4LU+XAEkEFSDJppf8CwvL45pjrJaW1mMwqG86vsFgUHCi7VlZGQzd0eLijeh0Cgy0i4btrE3+fmfLy8377OrVqx/H0tJnB9H2nQ2zaVDX1qpxzTFWg0EdVVXfdHyDQfOOta7roTtaX2/esdzJsJ21yd/vrKrqQpNs3/r64O8eU+3e2TCbBvXIkelxzTFWCwvLsbZW3XR8GxvNOyO46659Nx1DXddx/fpqzMwciG63Xaeow3bWBrfb2fR0895AvP/+A3Hw4GdvGrZ1Z5vxGipAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgyb7SA+xZ538c0d9feopbLfyh9ASM24eLEW//oPQUtxoMSk+w5wjq7Vy5VHoC+KvVGxGXf1t6Ckbgkv8TnU43Tp9+Ijqd0pOM5oEHvhInTjxaegx2ydGjD8bDD3+19BgjO3Xq8Zia6pceozhnqJ/o9brxwgtn4tq1D6KqqtLj3NGJE4/Gk08+VnoMdsnJk8ej1+vGwYMHSo8ykuefPxO9nvMzQf2cTqcTL7/8YukxICIiZmePxezssdJjsAWeUgCSCCpAkk0v+eu6HtccRbT1+Oq6zcfW1uNq87G187iG2TSo7733wbjmKOL69dXSI+yKixfbuzc7a5427uz48eFf3zSojzxyaDdmKW5x8Uasr1cxM9OMd1BHVdd/fWA+9NCXotttyOe/RmRnzdPWnW1m06C2bcGf+vSzpm07vk8vrbrdTuuOzc6ap60724w3pQCSCCpAEh/snxDz85dibu7d0mOM5OzZZ6LbHe25vq7reOWVNxr9TvKf/rQSv/rVPzTm156H2crO2kxQJ8D8/KV4881fxoULvys9ykgOH743Tp9+Ivbvn9r0dlVVxblzv4i33jrf6KC2wag7aztPKRNgbu7dxsQ0IuL1138Wq6trd7xdVVXx2ms/EdM9YNSdtZ0z1EnT3x9x6L7SU9yqHkRcu7Kz7/HlmYief/FobDJ21jKCOmkO3Rdx5vulp7jVylLEq8/u7Ht8+7sR9xzOmYc7y9hZy7jkB0giqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIk2Vd6AEizdiNiZan0FJNj5UbpCfYcQaU93vi30hMw4VzyAyQRVBqr1+vFhQvnotv1Y1za3NxPY3r67tJjFOeSn8bqdDqxb18vzp//n4ioS4+zLXUd8f771+NrX/tSNPl5YWqqH51Op/QYxQkqjdfkM6O6ruMLX1iJ6em7o9sVpKZr8HMiwN4iqABJNr3kX1hYHtccY7W0tB6DQd3a41tcvBGffzlreXmj3DDbdPXqx7G09NlBTNrO2qDtOxtm06CurVXjmmOsBoM6qqpu7fGtr998XFXVvDds1tcHN+1n0nbWBm3f2TCbBvXIkelxzTFWCwvLsbZWte746rqO69dXY2bmwE1vcExP9wtOtT33338gDh488Lc/T9rO2qCtO9uM11ABkggqQJJtfQ61qqqoqua+LjIYDGIwqGJjo3lv1nyq0+lGr+f5MCIas0c7a78tB7Wu6zh37hfx2ms/2Y15GNHp00/ECy+cmfjfTqnrOr75zX9pxBO8nbXflp8uX3nljfjRj366G7OwBT//+f/G9773n6XHKGpjYyO+8Y1/akRMI+xsEmw5qHVdR10372M4bVPX0ZiQ7KYm/R3YWfvt6Hf5/zEi/itpEEbz7xHxf6WH2Kv++T8ipu8tPcWtzv93xJX3S0/BGOwoqFMRMZM0CKP5QukB9rLpeyPuOVx6ilv195eegDHxliNAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIMm+ndz5jxHxr0mDMJr3d/oNPlyMePsHGaPkGgxKTwA7tqOg/iUifpU0CGOyeiPi8m9LTwGttOVL/qNHH4yHH/7qbszCFjzwwFfixIlHR7pt03Z26tTjMTXVLz0GbNmWz1BPnjwevV43Dh48sBvzjMXKyiDquo677trRCXpRJ048Gk8++dhIt23azp5//kz0el7ep3m2VZTZ2WMxO3sse5axWVhYjrW1Ko4cmS49ytg0fWfQBE4DAJIIKkCSTS/567oe1xxFtPX46rrNx1Z/7r8LDrIDw3YzKTtru02D+t57H4xrjiKuX18tPcKuuHixvXv7/M4GDfzs6p//vDb0cTUpO2uL48eHf33ToD7yyKHdmKW4xcUbsb5excxMM971HlVd//WB+dBDX4put1N6nFTDdraxsVFwou354henbnpcTdrO2m7ToLZtwZ/qfHJYbTu+Ty+tut1O645t2M6aeoyfn3vSdtZ23pQCSCKoAEm29cH++flLMTf3bvYsu+Ls2Wei2/W8QfM06XE2zPLyRlRVHdPTzf014qNHH4yTJ2/zDtQQWw7q/PylePPNX8aFC7/b6l2LOHz43jh9+onYv3+q9CgwsqY9ztrq8uU/Rq/XHfm3DLd86jY3926jlvz66z+L1dW10mPAljTtcdZWFy/+Pt5559cj335n/zpIf3/Eoft29C12RT2IuHal9BSQY68+ztrsw6sRq8tbvtvOgnrovogz39/Rt9gVK0sRrz5begrIsVcfZ2329g8jLs9v+W7erQFIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJNlXegDgDupBxMpS6SkmS7WxrbsJKux1165EvPps6SkYgUt+gCSCCnvQ2bPPxHPPfaf0GBPv1KnH46WXXhz59i75YQ/qdrvx9NPfiqeeeqz0KNt29erHsbZWxczM3aVH2bZ+vx+93ujnnYIKe9TUVD+mpvqlx9i2jz7qRL9fxfT0gdKjjI1LfoAkggqQZNNL/oWF5Vu+try8vc9nlXT16sextNT525+XltZjMKiHHl8bLC7eiE7nzrdrkmE7GwwGBSfanpWVwdCfu0nZWdttGtS1teqWr1VVvWvD7Jb19cFNxzIY1FFV9dDja4P19fYd17CdDQbNO866Hv5zNyk7a7tNg3rkyPQtX5uebt6L5PfffyAOHvzshfGFheVYW6uGHl+T1XUd16+vxszMgeh223W6M2xnGxvNu1q66659Nx3DpO2s7byGCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUiyb0f3/nAx4u0fJI2SaDAoPQElnP9xRH9/6SlutfCH0hMwJjsL6uqNiMu/TRoFdujKpdITMOG2fMl/9OiD8fDDX92NWXbFqVOPx9RUv/QY7IJOpxunTz8RnU7pSUbzwANfiRMnHi09Brtoy2eoJ08ej16vGwcPHtiNedI9//yZ6PW8VNxGvV43XnjhTFy79kFUVVV6nDs6ceLRePLJx0qPwS7a1iX/7OyxmJ09lj0LbFmn04mXX36x9BgQEd7lB0gjqABJBBUgSaeu69IzALSCM1SAJIIKkERQAZIIKkASQQVIIqgASf4fkaRXA/vY4IoAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "# Test Config easy\n",
        "parking = Parking(6,6)\n",
        "easy = RushHour(parking)\n",
        "\n",
        "easy.add_car(Car(0,3,HORIZONTAL, 2, is_red=True))\n",
        "easy.add_car(Car(2,0,HORIZONTAL,2))\n",
        "easy.add_car(Car(3,2,HORIZONTAL,2))\n",
        "easy.add_car(Car(4,4,HORIZONTAL,2))\n",
        "easy.add_car(Car(4,0,VERTICAL,2))\n",
        "easy.add_car(Car(1,0,VERTICAL,2))\n",
        "easy.add_car(Car(3,3,VERTICAL, 3))\n",
        "easy.add_car(Car(2,2,VERTICAL, 2))\n",
        "easy.add_car(Car(0,4,VERTICAL, 2))\n",
        "\n",
        "img = Drawing.show_parking(easy)\n",
        "imshow(img)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "s4UR-vCkqTzL",
        "outputId": "13d6e43e-ef51-4ad5-fd15-0e035519d699"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "number of moves for solving the puzzle with Solver_BFS :  6\n",
            "number of moves for solving the puzzle with Solver_DFS :  6\n"
          ]
        }
      ],
      "source": [
        "moves_BFS = Solver_BFS.solve(easy)\n",
        "moves_DFS = Solver_DFS.solve_best(easy, 20)\n",
        "\n",
        "print(\"number of moves for solving the puzzle with Solver_BFS : \", len(moves_BFS))\n",
        "print(\"number of moves for solving the puzzle with Solver_DFS : \", len(moves_DFS))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 17,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "bHAjGpYbqx8B",
        "outputId": "d5970ec2-6247-4687-b040-5e8de8964063"
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAPEUlEQVR4nO3cT2yc9ZnA8WdmMs5S4lQ0VLmAmwvaSqiAgpRGalRL4QK9gColaLd7CFz2wAUiqu1ltcdCq0VIFK3U1YpDW0WocKNd5VCplrKH4lYo5FIpPaQXO1FFUIsd/G/edw+FQpqJM7Yfz8/vO5/PiZgZ63nzeL7zvjPjdOq6DgB2rlt6AIC2EFSAJIIKkERQAZIIKkASQQVIsm+z//mb3/y8lZ+pWlhYjrW1Ko4cmS49Sqq6ruO99z6IRx45FN1up/Q4qeysedq6s4iIr3/91NBlOUMFSCKoAEkEFSDJpq+hTpq6ruOVV96IJvw67tGjD8bJk8dHvv38/KWYm3t3FyfaXcvLG1FVdUxP90uPsm1t3tnZs89Et+v8TFA/UVVVnDv3i3jrrfONCOrly3+MXq8bs7PH7njb+flL8eabv4wLF343hsm4nTbv7PDhe+P06Sdi//6p0qMU5SnlE1VVxWuv/aQRMY2IuHjx9/HOO78e6bZzc+825oHZZm3e2euv/yxWV9dKj1GcM9Tb+fJMRG8PXl5+eDVidXn79+/vjzh0X9483Flbd1YPIq5dKT3FniKot/Pt70bcc7j0FLd6+4cRl+e3f/9D90Wc+X7ePNxZW3e2shTx6rOlp9hTXPIDJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZLsKz0AY1YPIlaWSk8xWaqN0hMwJoI6aa5diXj12dJTQCu55AdIIqgT4OzZZ+K5575TeoyJd+rU4/HSSy+WHoNd5JJ/AnS73Xj66W/FU089VnqUbbt69eNYW6tiZubu0qNsW7/fj17POUybCeqEmJrqx9RUv/QY2/bRR53o96uYnj5QehS4LU+XAEkEFSDJppf8CwvL45pjrJaW1mMwqG86vsFgUHCi7VlZGQzd0eLijeh0Cgy0i4btrE3+fmfLy8377OrVqx/H0tJnB9H2nQ2zaVDX1qpxzTFWg0EdVVXfdHyDQfOOta7roTtaX2/esdzJsJ21yd/vrKrqQpNs3/r64O8eU+3e2TCbBvXIkelxzTFWCwvLsbZW3XR8GxvNOyO46659Nx1DXddx/fpqzMwciG63Xaeow3bWBrfb2fR0895AvP/+A3Hw4GdvGrZ1Z5vxGipAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgyb7SA+xZ538c0d9feopbLfyh9ASM24eLEW//oPQUtxoMSk+w5wjq7Vy5VHoC+KvVGxGXf1t6Ckbgkv8TnU43Tp9+Ijqd0pOM5oEHvhInTjxaegx2ydGjD8bDD3+19BgjO3Xq8Zia6pceozhnqJ/o9brxwgtn4tq1D6KqqtLj3NGJE4/Gk08+VnoMdsnJk8ej1+vGwYMHSo8ykuefPxO9nvMzQf2cTqcTL7/8YukxICIiZmePxezssdJjsAWeUgCSCCpAkk0v+eu6HtccRbT1+Oq6zcfW1uNq87G187iG2TSo7733wbjmKOL69dXSI+yKixfbuzc7a5427uz48eFf3zSojzxyaDdmKW5x8Uasr1cxM9OMd1BHVdd/fWA+9NCXotttyOe/RmRnzdPWnW1m06C2bcGf+vSzpm07vk8vrbrdTuuOzc6ap60724w3pQCSCCpAEh/snxDz85dibu7d0mOM5OzZZ6LbHe25vq7reOWVNxr9TvKf/rQSv/rVPzTm156H2crO2kxQJ8D8/KV4881fxoULvys9ykgOH743Tp9+Ivbvn9r0dlVVxblzv4i33jrf6KC2wag7aztPKRNgbu7dxsQ0IuL1138Wq6trd7xdVVXx2ms/EdM9YNSdtZ0z1EnT3x9x6L7SU9yqHkRcu7Kz7/HlmYief/FobDJ21jKCOmkO3Rdx5vulp7jVylLEq8/u7Ht8+7sR9xzOmYc7y9hZy7jkB0giqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIk2Vd6AEizdiNiZan0FJNj5UbpCfYcQaU93vi30hMw4VzyAyQRVBqr1+vFhQvnotv1Y1za3NxPY3r67tJjFOeSn8bqdDqxb18vzp//n4ioS4+zLXUd8f771+NrX/tSNPl5YWqqH51Op/QYxQkqjdfkM6O6ruMLX1iJ6em7o9sVpKZr8HMiwN4iqABJNr3kX1hYHtccY7W0tB6DQd3a41tcvBGffzlreXmj3DDbdPXqx7G09NlBTNrO2qDtOxtm06CurVXjmmOsBoM6qqpu7fGtr998XFXVvDds1tcHN+1n0nbWBm3f2TCbBvXIkelxzTFWCwvLsbZWte746rqO69dXY2bmwE1vcExP9wtOtT33338gDh488Lc/T9rO2qCtO9uM11ABkggqQJJtfQ61qqqoqua+LjIYDGIwqGJjo3lv1nyq0+lGr+f5MCIas0c7a78tB7Wu6zh37hfx2ms/2Y15GNHp00/ECy+cmfjfTqnrOr75zX9pxBO8nbXflp8uX3nljfjRj366G7OwBT//+f/G9773n6XHKGpjYyO+8Y1/akRMI+xsEmw5qHVdR10372M4bVPX0ZiQ7KYm/R3YWfvt6Hf5/zEi/itpEEbz7xHxf6WH2Kv++T8ipu8tPcWtzv93xJX3S0/BGOwoqFMRMZM0CKP5QukB9rLpeyPuOVx6ilv195eegDHxliNAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIMm+ndz5jxHxr0mDMJr3d/oNPlyMePsHGaPkGgxKTwA7tqOg/iUifpU0CGOyeiPi8m9LTwGttOVL/qNHH4yHH/7qbszCFjzwwFfixIlHR7pt03Z26tTjMTXVLz0GbNmWz1BPnjwevV43Dh48sBvzjMXKyiDquo677trRCXpRJ048Gk8++dhIt23azp5//kz0el7ep3m2VZTZ2WMxO3sse5axWVhYjrW1Ko4cmS49ytg0fWfQBE4DAJIIKkCSTS/567oe1xxFtPX46rrNx1Z/7r8LDrIDw3YzKTtru02D+t57H4xrjiKuX18tPcKuuHixvXv7/M4GDfzs6p//vDb0cTUpO2uL48eHf33ToD7yyKHdmKW4xcUbsb5excxMM971HlVd//WB+dBDX4put1N6nFTDdraxsVFwou354henbnpcTdrO2m7ToLZtwZ/qfHJYbTu+Ty+tut1O645t2M6aeoyfn3vSdtZ23pQCSCKoAEm29cH++flLMTf3bvYsu+Ls2Wei2/W8QfM06XE2zPLyRlRVHdPTzf014qNHH4yTJ2/zDtQQWw7q/PylePPNX8aFC7/b6l2LOHz43jh9+onYv3+q9CgwsqY9ztrq8uU/Rq/XHfm3DLd86jY3926jlvz66z+L1dW10mPAljTtcdZWFy/+Pt5559cj335n/zpIf3/Eoft29C12RT2IuHal9BSQY68+ztrsw6sRq8tbvtvOgnrovogz39/Rt9gVK0sRrz5begrIsVcfZ2329g8jLs9v+W7erQFIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJNlXegDgDupBxMpS6SkmS7WxrbsJKux1165EvPps6SkYgUt+gCSCCnvQ2bPPxHPPfaf0GBPv1KnH46WXXhz59i75YQ/qdrvx9NPfiqeeeqz0KNt29erHsbZWxczM3aVH2bZ+vx+93ujnnYIKe9TUVD+mpvqlx9i2jz7qRL9fxfT0gdKjjI1LfoAkggqQZNNL/oWF5Vu+try8vc9nlXT16sextNT525+XltZjMKiHHl8bLC7eiE7nzrdrkmE7GwwGBSfanpWVwdCfu0nZWdttGtS1teqWr1VVvWvD7Jb19cFNxzIY1FFV9dDja4P19fYd17CdDQbNO866Hv5zNyk7a7tNg3rkyPQtX5uebt6L5PfffyAOHvzshfGFheVYW6uGHl+T1XUd16+vxszMgeh223W6M2xnGxvNu1q66659Nx3DpO2s7byGCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUiyb0f3/nAx4u0fJI2SaDAoPQElnP9xRH9/6SlutfCH0hMwJjsL6uqNiMu/TRoFdujKpdITMOG2fMl/9OiD8fDDX92NWXbFqVOPx9RUv/QY7IJOpxunTz8RnU7pSUbzwANfiRMnHi09Brtoy2eoJ08ej16vGwcPHtiNedI9//yZ6PW8VNxGvV43XnjhTFy79kFUVVV6nDs6ceLRePLJx0qPwS7a1iX/7OyxmJ09lj0LbFmn04mXX36x9BgQEd7lB0gjqABJBBUgSaeu69IzALSCM1SAJIIKkERQAZIIKkASQQVIIqgASf4fkaRXA/vY4IoAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "move num 1: (3, 1)\n",
            "game won ? False\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAPEElEQVR4nO3cQYyc5XnA8WdmPGvReFwlpvIFNr6gRkICZCTHUqysZC6QC6jSGrXpwXDpgQtYVMql6jGQqAiJoErpIYc0QijhRlJxqBRL9BA2EXJ8ieQczGV3fcAoZdd4Z3e+r4dAjePxenb2mXl3vvn9TrDMWM/Lw/z3+3ZmadV1HQDsX7v0AABNIagASQQVIImgAiQRVIAkggqQ5NBu//A3v/l5Iz9Ttbq6Gf1+FSdO9EqPkqqu6/jww4/jsceORbvdKj1OKjubPU3dWUTEN7+5PHRZrlABkggqQBJBBUiy689Q501d1/Haaz+JWfh13JMnH46zZ0+P/PiVlctx8eIHE5xosjY3d6Kq6uj1uqVHGVuTd3bhwnPRbrs+E9TPVVUVb731y/jFL96biaBeufJRdDrtWFo6dc/Hrqxcjrff/lW8//7vpjAZd9PknR0/fn+cO/dUHD68UHqUonxL+VxVVfHGGz+diZhGRFy69Id4991fj/TYixc/mJkXZpM1eWdvvvmz2Nrqlx6jOFeod/M3ixGdA3h7+cl6xNbm+M/vHo449kDePNxbU3dWDyKuXS09xYEiqHfzd/8c8dXjpae40zs/jLiyMv7zjz0Qcf77efNwb03d2c2NiNefLz3FgeKWHyCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQ5FDpAZiyehBxc6P0FPOl2ik9AVMiqPPm2tWI158vPQU0klt+gCSCOgcuXHguXnjhu6XHmHvLy0/GK6+8XHoMJsgt/xxot9vx7LPfiWeeeaL0KGNbX/8s+v0qFhe/UnqUsXW73eh0XMM0maDOiYWFbiwsdEuPMbZPP21Ft1tFr3ek9ChwV75dAiQRVIAku97yr65uTmuOqdrY2I7BoL7tfIPBoOBE47l5czB0R2trN6LVKjDQBA3bWZP85c42N2fvs6vr65/FxsatQzR9Z8PsGtR+v5rWHFM1GNRRVfVt5xsMZu+sdV0P3dH29uyd5V6G7axJ/nJnVVUXmmR829uDv3hNNXtnw+wa1BMnetOaY6pWVzej369uO9/OzuxdEdx336HbzlDXdVy/vhWLi0ei3W7WJeqwnTXB3XbW683eG4gPPngkjh699aZhU3e2Gz9DBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQ5VHqAA+u9H0d0D5ee4k6rfyw9AdP2yVrEOz8oPcWdBoPSExw4gno3Vy+XngD+bOtGxJXflp6CEbjl/1yr1Y5z556KVqv0JKN56KGvx5kzj5cegwk5efLhePTRb5QeY2TLy0/GwkK39BjFuUL9XKfTjpdeOh/Xrn0cVVWVHueezpx5PJ5++onSYzAhZ8+ejk6nHUePHik9ykhefPF8dDquzwT1S1qtVrz66sulx4CIiFhaOhVLS6dKj8Ee+JYCkERQAZLsestf1/W05iiiqeer6yafrannavLZmnmuYXYN6ocffjytOYq4fn2r9AgTcelSc/dmZ7OniTs7fXr413cN6mOPHZvELMWtrd2I7e0qFhdn4x3UUdX1n1+YjzzytWi3Z+TzXyOys9nT1J3tZtegNm3BX/jis6ZNO98Xt1btdqtxZ7Oz2dPUne3Gm1IASQQVIIkP9s+JlZXLcfHiB6XHGMmFC89Fu+17/SztbJjNzZ2oqjp6vdn9ldSTJx+Os2fv8g7UEII6B1ZWLsfbb/8q3n//d6VHGcnx4/fHuXNPxeHDC6VHKWbWdtZUV658FJ1Oe+TfWHMZMAcuXvxgpl6Yb775s9ja6pceo6hZ21lTXbr0h3j33V+P/HhXqPOmezji2AOlp7hTPYi4drX0FAfTQd1Zk32yHrG1ueenCeq8OfZAxPnvl57iTjc3Il5/vvQUB9NB3VmTvfPDiCsre36aW36AJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQJJDpQcA7qEeRNzcKD3FfKl2xnqaoMJBd+1qxOvPl56CEbjlB0giqHAAXbjwXLzwwndLjzH3lpefjFdeeXnkx7vlhwOo3W7Hs89+J5555onSo4xtff2z6PerWFz8SulRxtbtdqPTGf26U1DhgFpY6MbCQrf0GGP79NNWdLtV9HpHSo8yNW75AZIIKkCSXW/5V1c3pzXHVG1sbMdgUDf2fGtrN6LVuvX3m5vjfaaupPX1z2Jj49Yh5m1nTdD0nQ2za1D7/Wpac0zVYFBHVdWNPd/29u3nqqq60CTj294e3LafedtZEzR9Z8PsGtQTJ3rTmmOqVlc3o9+vGne+uq7j+vWtWFw8Eu32rcudXm/23th48MEjcfTorTcz5m1nTdDUne3Gz1ABkggqQJKxPodaVVVU1ez+XGQwGMRgUMXOzuy9WfOFVqu9pw8cN9ms7NHOmm/PQa3rOt5665fxxhs/ncQ8jOjcuafipZfOR6tpbw3vUV3X8e1v/+NMfIO3s+bb87fL1177SfzoR/85iVnYg5///L/ie9/7t9JjFLWzsxPf+tbfz0RMI+xsHuw5qHVdR13P3sdwmqauY2ZCMkmz9O/AzppvX7/L/7cR8e9JgzCaf4mI/yk9xEH1D/8a0bu/9BR3eu8/Iq7+vvQUTMG+groQEYtJgzCavyo9wEHWuz/iq8dLT3Gn7uHSEzAl3nIESCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQ5tJ8nfxQR/5Q0CKP5/X7/gE/WIt75QcYouQaD0hPAvu0rqP8bEf+dNAhTsnUj4spvS08BjbTnW/6TJx+ORx/9xiRmYQ8eeujrcebM4yM9dtZ2trz8ZCwsdEuPAXu25yvUs2dPR6fTjqNHj0xinqm4eXMQdV3Hffft6wK9qDNnHo+nn35ipMfO2s5efPF8dDp+vM/sGasoS0unYmnpVPYsU7O6uhn9fhUnTvRKjzI1s74zmAUuAwCSCCpAkl1v+eu6ntYcRTT1fHXd5LPVX/rrgoPsw7DdzMvOmm7XoH744cfTmqOI69e3So8wEZcuNXdvX97ZYAY/u/qnP/WHvq7mZWdNcfr08K/vGtTHHjs2iVmKW1u7EdvbVSwuzsa73qOq6z+/MB955GvRbrdKj5Nq2M52dnYKTjSev/7rhdteV/O2s6bbNahNW/AXWp8fq2nn++LWqt1uNe5sw3Y2q2f88tzztrOm86YUQBJBBUgy1gf7V1Yux8WLH2TPMhEXLjwX7bbvG8yeWXqdDbO5uRNVVUevN7u/Rnzy5MNx9uxd3oEaYs9BXVm5HG+//at4//3f7fWpRRw/fn+cO/dUHD68UHoUGNmsvc6a6sqVj6LTaY/8W4Z7vnS7ePGDmVrym2/+LLa2+qXHgD2ZtddZU1269Id4991fj/z4/f3fQbqHI449sK8/YiLqQcS1q6WngBwH9XXWZJ+sR2xt7vlp+wvqsQcizn9/X3/ERNzciHj9+dJTQI6D+jprsnd+GHFlZc9P824NQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSDJodIDAPdQDyJubpSeYr5UO2M9TVDhoLt2NeL150tPwQjc8gMkEVQ4gC5ceC5eeOG7pceYe8vLT8Yrr7w88uPd8sMB1G6349lnvxPPPPNE6VHGtr7+WfT7VSwufqX0KGPrdrvR6Yx+3SmocEAtLHRjYaFbeoyxffppK7rdKnq9I6VHmRq3/ABJBBUgya63/Kurm3d8bXNzvM9nlbS+/llsbLT+/+83NrZjMKiHnq8J1tZuRKt178fNkmE7GwwGBScaz82bg6H/3c3Lzppu16D2+9UdX6uqemLDTMr29uC2swwGdVRVPfR8TbC93bxzDdvZYDB756zr4f/dzcvOmm7XoJ440bvja73e7P2Q/MEHj8TRo7d+ML66uhn9fjX0fLOsruu4fn0rFhePRLvdrMudYTvb2Zm9u6X77jt02xnmbWdN52eoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSH9vXsT9Yi3vlB0iiJBoPSE1DCez+O6B4uPcWdVv9YegKmZH9B3boRceW3SaPAPl29XHoC5tyeb/lPnnw4Hn30G5OYZSKWl5+MhYVu6TGYgFarHefOPRWtVulJRvPQQ1+PM2ceLz0GE7TnK9SzZ09Hp9OOo0ePTGKedC++eD46HT8qbqJOpx0vvXQ+rl37OKqqKj3OPZ0583g8/fQTpcdggsa65V9aOhVLS6eyZ4E9a7Va8eqrL5ceAyLCu/wAaQQVIImgAiRp1XVdegaARnCFCpBEUAGSCCpAEkEFSCKoAEkEFSDJ/wGTv1IqUsmojgAAAABJRU5ErkJggg==",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "move num 2: (6, 1)\n",
            "game won ? False\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAPHUlEQVR4nO3cT4icdZrA8aeqUh3cSUVmEshFe3KRFQSVCJmAwYZ40bnopSPz5xC97MGLBmG9LHPUGZlBmJGFHZY57IqIeHNn8LAwgexhbEUyuQjZQ7x0dw5GXLtjurqr3j2MThJTafvP0/Wr963P55S0VeF586S+/b71VtuqqioA2L126QEAmkJQAZIIKkASQQVIIqgASQQVIMm+zf7jX/7yTiM/U7W4uBr9/jCOHu2VHiVVVVXx8cefxcMPH4p2u1V6nFR2Vj9N3VlExI9+ND9yWc5QAZIIKkASQQVIsul7qDTHwsLFOHfug9Jj7Njq6kYMh1X0et3So+zYsWMPxKlTJ7b8+Drt7OzZZ6Pddn4mqFNgYeFivP32H+P8+Y9KjzLVLl36NDqddszNHf/Ox9ZtZ0eOHI7Tp5+M/ftnSo9SlG8pU+DcuQ9q88JssgsXPon33vvzlh5bt5298cabsbbWLz1Gcc5Qp013f8She0pPMV0+X45YW9358yd1Z9Ug4srl0lNMFEGdNofuiTjzSukppsu7r0VcWtj58yd1Z9dXIl5/rvQUE8UlP0ASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgyb7SAzBm1SDi+krpKabLcKP0BIyJoE6bK5cjXn+u9BTQSC75AZII6hQ4e/bZeP75n5UeY+rNzz8Rr776Uukx2EMu+adAu92OZ575cTz99OOlR9mx5eWvot8fxuzs90qPsmPdbjc6HecwTSaoU2JmphszM93SY+zYl1+2otsdRq93oPQocEe+XQIkEVSAJJte8i8uro5rjrFaWVmPwaBq7PEtLV2LVqv0FLmmbWerq/X77Ory8lexsnLjIJq+s1E2DWq/PxzXHGM1GFQxHFaNPb719eYd17TtbDisCk2yc+vrg1v20/SdjbJpUI8e7Y1rjrFaXFyNfn/YuOOrqiquXl2L2dkD0W436xR12nbW69XvBuK99x6Igwdv3DRs6s424z1UgCSCCpDE51C/ZWOjHjcDWq22D4nDhBHUm1RVFY899vMYDif/TfTTp5+MF188E62m3c6HGnOK87WNjY149NGf1CKmERHvvPOnePnlX5ceA7iJoN6kLjGNiKiqes0L08Al/5389BcRvcOlp7jd+7+PuPzX0lMAIwjqnfQOR3z/SOkpbtfdX3oC4A5c8gMkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkuwrPQDwHT5finj3V6WnuN1gUHqCiSOoMOnWrkVc+rD0FGyBS36YQMeOPRAPPXR/6TG2bH7+iZiZ6ZYeozhnqDCBTp06EZ1OOw4ePFB6lC154YUz0ek4PxNUmFBzc8djbu546THYBt9SAJIIKkCSTS/5q6oa1xxF3Hx8dT3UUTuqquburrnH1eRja+ZxjbJpUD/++LNxzVHE1atrf//1oIafqfvii/7IHV240Ny93byzJrGzejlxYvTXNw3qww8f2otZiltauhbr68OYnb1xB3VjY6PgRDtz990zt+yoqv72wnzwwR9Eu90qOFm+UTtrAjtrlk2D2rQFf6P19WHdfHx1Pdab5/7m0qrdbtX2eO5k1M6awM6axU0pgCSCCpDEB/unxMLCxTh37oPSY2zJ2bPPRrvte32ddjbK6upGDIdV9Hr1/ZHUY8ceiFOn7nAHagRBnQILCxfj7bf/GOfPf1R6lC05cuRwnD79ZOzfP1N6lGLqtrOmunTp0+h02lv+iTWnAVPg3LkPavXCfOONN2NtrV96jKLqtrOmunDhk3jvvT9v+fHOUKdNd3/EoXtKT3G7ahBx5XLpKSbTpO6syT5fjlhb3fbTBHXaHLon4swrpae43fWViNefKz3FZJrUnTXZu69FXFrY9tNc8gMkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkuwrPcDE6l+LuL5SeorbDTdKT8C4VYPJ/LfYZDt8nQnqnfzhn0tPAH9z5XLE68+VnoItcMkPkERQv9bpdOL8+bei3a7HX8n8/BPx6qsvlR6DPXL27LPx/PM/Kz3G1Nvu68wl/9darVbs29eJ99//94ioSo/znbrdbnQ69Yg/29dut+OZZ34cTz/9eOlRdmx5+avo94cxO/u90qPs2HZfZ4L6Lb1efZdPs8zMdGNmplt6jB378stWdLvD6PUOlB5lbJziACQRVIAkm17yLy6ujmuOsVpZWY/BoGrs8S0tXYtW68bvV1fr99nV5eWvYmXlxkFM286aoOk7G2XToPb7w3HNMVaDQRXDYdXY41tfv/W4hsPJv8n2bevrg1v2M207a4Km72yUTYN69GhvXHOM1eLiavT7w8YdX1VVcfXqWszOHoh2+8bpTq9Xvxsb9957IA4evHEzY9p21gRN3dlmvIcKkERQAZLs6HOow+EwhsP6vi8yGAxiMBjGxkb9btZ8o9Vq+2D/1+qyRztrvm0HtaqqeOut/4rf/vY/9mIetuj06SfjxRfPRKtpt4a3qaqqeOyxn9fiG7ydNd+2v13+5jd/iN/97j/3Yha24Z13/hQvv/zr0mMUtbGxEY8++pNaxDTCzqbBtoNaVVVUVf0+htM0VRW1CcleqtPfgZ01365+lv8fI+JfkwZha/4lIv6n9BCT6qe/iOgdLj3F7d7/fcTlv5aegjHYVVBnImI2aRC25h9KDzDJeocjvn+k9BS36+4vPQFj4pYjQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSDJvt08+dOI+KekQdiav+72D/h8KeLdX2WMkmswKD0B7Nqugvp/EfHfSYMwJmvXIi59WHoKaKRtX/IfO/ZAPPTQ/XsxC9tw330/jJMnH9nSY+u2s/n5J2Jmplt6DNi2bZ+hnjp1Ijqddhw8eGAv5hmL69cHUVVV3HXXrk7Qizp58pF46qnHt/TYuu3shRfORKfj7X3qZ0dFmZs7HnNzx7NnGZvFxdXo94dx9Giv9ChjU/edQR04DQBIIqgASTa95K+qalxzFNHU46uqJh9bddOvCw6yC6N2My07a7pNg/rxx5+Na44irl5dKz3Cnrhwobl7u3lngxp+dvWLL/ojX1fTsrOmOHFi9Nc3DerDDx/ai1mKW1q6Fuvrw5idrcdd762qqr+9MB988AfRbrdKj5Nq1M42NjYKTrQzd989c8vratp21nSbBrVpC/5G6+vDatrxfXNp1W63Gndso3ZW12O8ee5p21nTuSkFkERQAZLs6IP9CwsX49y5D7Jn2RNnzz4b7bbvG9RPnV5no6yubsRwWEWvV98fIz527IE4deoOd6BG2HZQFxYuxttv/zHOn/9ou08t4siRw3H69JOxf/9M6VFgy+r2OmuqS5c+jU6nveWfMtz2qdu5cx/UaslvvPFmrK31S48B21K311lTXbjwSbz33p+3/Pjd/d9BuvsjDt2zqz9iT1SDiCuXS08BOSb1ddZkny9HrK1u+2m7C+qheyLOvLKrP2JPXF+JeP250lNAjkl9nTXZu69FXFrY9tPcrQFIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJNlXegDgO1SDiOsrpaeYLsONHT1NUGHSXbkc8fpzpadgC1zyAyQRVJhAZ88+G88//7PSY0y9+fkn4tVXX9ry413ywwRqt9vxzDM/jqeffrz0KDu2vPxV9PvDmJ39XulRdqzb7Uans/XzTkGFCTUz042ZmW7pMXbsyy9b0e0Oo9c7UHqUsXHJD5BEUAGSbHrJv7i4etvXVld39vmskpaXv4qVldbff7+ysh6DQTXy+JpgaelatFrf/bg6GbWzwWBQcKKduX59MPLf3bTsrOk2DWq/P7zta8NhtWfD7JX19cEtxzIYVDEcViOPrwnW15t3XKN2NhjU7ziravS/u2nZWdNtGtSjR3u3fa3Xq9+b5PfeeyAOHrzxxvji4mr0+8ORx1dnVVXF1atrMTt7INrtZp3ujNrZxkb9rpbuumvfLccwbTtrOu+hAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZLs29WzP1+KePdXSaMkGgxKT0AJ7/9bRHd/6Slut/i/pSdgTHYX1LVrEZc+TBoFdunyxdITMOW2fcl/7NgD8dBD9+/FLHtifv6JmJnplh6DPdBqteP06Sej1So9ydbcd98P4+TJR0qPwR7a9hnqqVMnotNpx8GDB/ZinnQvvHAmOh1vFTdRp9OOF188E1eufBbD4bD0ON/p5MlH4qmnHi89BntoR5f8c3PHY27uePYssG2tVit++cuXSo8BEeEuP0AaQQVIIqgASVpVVZWeAaARnKECJBFUgCSCCpBEUAGSCCpAEkEFSPL/jNtERCvSCYsAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "move num 3: (2, -1)\n",
            "game won ? False\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAPIklEQVR4nO3cT2yc9ZnA8WdmYmcpmaA2WeUCbi5oK6ECChKNRESkcIFeQCslqH8OgcseuEDUVbmseixtVYRE0UpbVRzaCiHKjbbKoVItZQ/FrVDIpVL2kF7sRBVBFDvYY8+8eyA0CZ4Y/3k8v3nf+XxOibGj582T+c77zjtDq6qqAGDn2qUHAGgKQQVIIqgASQQVIImgAiQRVIAkezb6j3/601uNfE/V/PxS9HqDOHy4W3qUVFVVxXvvfRAPPngg2u1W6XFS2Vn9NHVnERHf+MbJoctyhgqQRFABkggqQJINX0OdNFVVxcsvvx51/jju3/++HH/4w79Eq8Yvx50580y0257r5+YuxOzsu6XH2BQ7+5SgXjcYDOKNN34bv/nN2VoHtQkOHToYp049EXv3TpcepZi5uQvx5pu/i3Pn/lJ6lE2xs095SrluMBjEq6/+UkzHwGuv/TpWVnqlxyhqdvbd2sQ0ws4+4wz1dv51JqIzVXqKyVH1I65cKj3FeJraG3Hg7tJTrGdn6wjq7fz7f0Z8+VDpKSbH8mLEK8+WnmI8Hbg74vQPS0+xnp2t45IfIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBkT+kBxlbvWsTyYukpJsfytdITwI4J6u28/v3SEwA145IfIImgXtfpdOLcuTei3fZXUtrs7K+i272z9BiwZS75r2u1WrFnTyfOnv1FRFSlx9mWqop4//2r8fWvfyXq/LwwPT0VrVar9BiwZYL6OXU+M6qqKr70peXodu+MdluQYNRqfB4DMF4EFSDJhpf88/NLo5pjpBYXV6Pfrxp7fAsL16JpL0FO2s6WltbKDbNNly9/EouLNw6i6TsbZsOg9nqDUc0xUv1+FYNB1djjW11t3nFN2s4Gg/rdGF1d7d+yn6bvbJgNg3r4cHdUc4zU/PxS9HqDxh1fVVVx9epKzMzsa9xNqUnbWbc7VXCq7bnnnn2xf/++f/6+qTvbiNdQAZIIKkAS70P9nLW1etwMaLXa0el4PoRxIqg3qaoqHn30uzEYjP+L6KdOPREvvHDaJ4pgjDjFuW5tbS0eeeRbtYhpRMRbb/0+Xnzxp6XHAG4iqDepS0wjPv3cfp3mhUngkv92vv2DiO7B0lOsd/bnEZfeLz0FMISg3k73YMSXD5WeYr2pvaUnAG7DJT9AEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIMme0gMAX+DDhYi3f1x6ivX6/dITjB1BhXG3ci3i4p9LT8EmuOSHMXTkyH3xwANfKz3Gpp08+XhMT0+VHqM4Z6gwhk6cOBqdTjv2799XepRNef7509HpOD8TVBhTx48/HMePP1x6DLbAUwpAEkEFSLLhJX9VVaOao4ibj6+uhzpsR1XV3N0197iafGzNPK5hNgzqe+99MKo5irh6deWfv+7X8D11H33UG7qj8+ebu7ebd9YkdlYvR48O//qGQX3wwQO7MUtxCwvXYnV1EDMzN+6grq2tFZxoe+66a/qWHVXVpw/M++//SrTbrYKT5Ru2syaws2bZMKhNW/BnWtcP6+bjq+ux3jz3Z5dW7XartsdzO8N21gR21ixuSgEkEVSAJN7YPyHm5i7E7Oy7pcfYlDNnnol223N9nXY2zNLSWgwGVXS79f1I6pEj98WJE7e5AzWEoE6AubkL8eabv4tz5/5SepRNOXToYJw69UTs3TtdepRi6razprp48W/R6bQ3/Yk1pwETYHb23Vo9MF977dexstIrPUZRddtZU50//9d4550/bvr7naFOmqm9EQfuLj3FelU/4sql0lOMp3HdWZN9eDliZWnLPyaok+bA3RGnf1h6ivWWFyNeebb0FONpXHfWZG//JOLi3JZ/zCU/QBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSDJntIDjK3etYjlxdJTrDdYKz0Bo1b1x/PfYpNt83EmqLfz+vdLTwCfunIp4pVnS0/BJrjkB0giqNd1Op04d+6NaLfr8Vdy8uTj8dJL3ys9BrvkzJln4rnnvlN6jIm31ceZS/7rWq1W7NnTibNnfxERVelxvtDU1FR0OvWIP1vXbrfj6ae/GU899VjpUbbt8uVPotcbxMzMnaVH2batPs4E9XO63foun2aZnp6K6emp0mNs28cft2JqahDd7r7So4yMUxyAJIIKkGTDS/75+aVRzTFSi4ur0e9XjT2+hYVr0Wrd+P3SUv3eu3r58iexuHjjICZtZ03Q9J0Ns2FQe73BqOYYqX6/isGgauzxra7eelyDwfjfZPu81dX+LfuZtJ01QdN3NsyGQT18uDuqOUZqfn4per1B446vqqq4enUlZmb2Rbt943Sn263fjY177tkX+/ffuJkxaTtrgqbubCNeQwVIIqgASbb1PtTBYBCDQX1fF+n3+9HvD2JtrX43az7TarW9sf+6uuzRzppvy0GtqireeOO38eqrv9yNedikU6eeiBdeOB2tpt0a3qKqquLRR79biyd4O2u+LT9dvvzy6/Gzn/1qN2ZhC9566/fx4os/LT1GUWtra/HII9+qRUwj7GwSbDmoVVVFVdXvbThNU1VRm5Dspjr9HdhZ8+3os/z/FhH/nTQIm/NfEfG/pYcYV9/+QUT3YOkp1jv784hL75eeghHYUVCnI2ImaRA250ulBxhn3YMRXz5Ueor1pvaWnoARccsRIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBkz05++G8R8R9Jg7A57+/0D/hwIeLtH2eMkqvfLz0B7NiOgvqPiPhD0iCMyMq1iIt/Lj0FNNKWL/mPHLkvHnjga7sxC1tw771fjWPHHtrU99ZtZydPPh7T01Olx4At2/IZ6okTR6PTacf+/ft2Y56RWF7uR1VVcccdOzpBL+rYsYfiyScf29T31m1nzz9/OjodL+9TP9sqyvHjD8fx4w9nzzIy8/NL0esN4vDhbulRRqbuO4M6cBoAkERQAZJseMlfVdWo5iiiqcdXVU0+tuqmXxccZAeG7WZSdtZ0Gwb1vfc+GNUcRVy9ulJ6hF1x/nxz93bzzvo1fO/qRx/1hj6uJmVnTXH06PCvbxjUBx88sBuzFLewcC1WVwcxM1OPu96bVVWfPjDvv/8r0W63So+TatjO1tbWCk60PXfdNX3L42rSdtZ0Gwa1aQv+TOv6YTXt+D67tGq3W407tmE7q+sx3jz3pO2s6dyUAkgiqABJtvXG/rm5CzE7+272LLvizJlnot32vEH91OlxNszS0loMBlV0u/X9GPGRI/fFiRO3uQM1xJaDOjd3Id5883dx7txftvqjRRw6dDBOnXoi9u6dLj0KbFrdHmdNdfHi36LTaW/6U4ZbPnWbnX23Vkt+7bVfx8pKr/QYsCV1e5w11fnzf4133vnjpr9/Z/93kKm9EQfu3tEfsSuqfsSVS6WngBzj+jhrsg8vR6wsbfnHdhbUA3dHnP7hjv6IXbG8GPHKs6WngBzj+jhrsrd/EnFxbss/5m4NQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSDJntIDAF+g6kcsL5aeYrIM1rb1Y4IK4+7KpYhXni09BZvgkh8giaDCGDpz5pl47rnvlB5j4p08+Xi89NL3Nv39LvlhDLXb7Xj66W/GU089VnqUbbt8+ZPo9QYxM3Nn6VG2bWpqKjqdzZ93CiqMqenpqZienio9xrZ9/HErpqYG0e3uKz3KyLjkB0giqABJNrzkn59fWve1paXtvT+rpMuXP4nFxdY/f7+4uBr9fjX0+JpgYeFatFpf/H11Mmxn/X6/4ETbs7zcH/rvblJ21nQbBrXXG6z72mBQ7dowu2V1tX/LsfT7VQwG1dDja4LV1eYd17Cd9fv1O86qGv7vblJ21nQbBvXw4e66r3W79XuR/J579sX+/TdeGJ+fX4pebzD0+Oqsqqq4enUlZmb2RbvdrNOdYTtbW6vf1dIdd+y55RgmbWdN5zVUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQJI9O/rpDxci3v5x0iiJ+v3SE1DC2f+JmNpbeor15v+v9ASMyM6CunIt4uKfk0aBHbp0ofQETLgtX/IfOXJfPPDA13Zjll1x8uTjMT09VXoMdkGr1Y5Tp56IVqv0JJtz771fjWPHHio9Brtoy2eoJ04cjU6nHfv379uNedI9//zp6HS8VNxEnU47XnjhdFy58kEMBoPS43yhY8ceiieffKz0GOyibV3yHz/+cBw//nD2LLBlrVYrfvSj75UeAyLCXX6ANIIKkERQAZK0qqoqPQNAIzhDBUgiqABJBBUgiaACJBFUgCSCCpDk/wGaZ0kdK3C2igAAAABJRU5ErkJggg==",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "move num 4: (7, -3)\n",
            "game won ? False\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAOuklEQVR4nO3cT4hcBZ7A8V9VpTurpjKMcclFe3MZVpAxkoFMYGQa4kXnMrKQyO7sIXrZg5cYZpm5LHvUUVYECXtYBg+zEoJ6cxxyEGzIHsZWQsxFyEUv3R0GIzN2x+7qrnp7MJqYVCpV3b+uV+/153MybVXze/lZ33qv/tgoiiIA2Lpm2QMA1IWgAiQRVIAkggqQRFABkggqQJJdg/7ln//8Vi0/U7WwsBKdTi8OHGiXPUqqoijiwoUv4rHH9kWz2Sh7nFR2Vj113VlExE9/eqzvspyhAiQRVIAkggqQZOBrqDtNURTx6qtvRJW/jvuXv6zG++//XTQq/HLcqVPPRrM53HN9lXZ26NAjcfTokaFvPz9/KebmPtzGifKMsrM6E9Trer1enDnzx3j77XOVeHDW2f79D8Tx40/F7t3TA29XtZ1dvvx5tFrNmJ09fNfbzs9firNn34vz5z8ew2RbN+zO6s5TynW9Xi9ef/0PlXhg1t3p02/G2lrnrrer2s4uXvw03n33g6FuOzf3YWViGjH8zurOGeqd/P1MRGuq7Cl2jqIbceWzrf2OSd3Zl0sRayubv//U7oh9D+bNkyVjZzUjqHfyT/8e8cP9ZU+xc6wuR7z23NZ+x6Tu7J1XIi7Pb/7++x6MOPFi3jxZMnZWMy75AZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJdpU9wMTqXItYXS57ip1j9VrZE8CWCeqdvPGbsicAKsYlP0ASQb2u1WrF+fNnotn0V1K2ubn/jXb7vrLHgJG55L+u0WjErl2tOHfu9xFRlD3OphRFxCefXI0f//j+qPLzwvT0VDQajbLHgJEJ6i2qfGZUFEXce+9qtNv3RbMpSDBuFT6PAZgsggqQZOAl/8LCyrjmGKvl5fXodovaHt/i4rWo20uQ/XbW7XZLnGhzVle7ff+7u3VnKysbY5wqx9LS17G8fOMg6v4462dgUDud3rjmGKtut4her6jt8a2v1++4+u2s263ecRZF///ubt1Zr1e9N0bX17u37Kfej7N+Bgb1wIH2uOYYq4WFleh0erU7vqIo4urVtZiZ2VO7N6X67Wxjo3pncffcs+t7x3CnnbXbU2WMtyUPPbQn9u7d892f6/o4G8RrqABJBBUgic+h3qIql5GNRjNaLc+HMEkE9SZFUcTPf/6v0etN/ovox48/FS+8cMI3imCCOMW5bmNjI372s3+uREwjIt5660/x29/+V9ljADcR1JtUJaYR33xvv0rzwk7gkv9O/uU/I9oPlD3F7c79T8Rnn5Q9BdCHoN5J+4GIH+4ve4rbTe0uewLgDlzyAyQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGS7Cp7AOAuvlyMeOflsqe4Xbdb9gQTR1Bh0q1di7j8UdlTMASX/DCBDh16JA4efLjsMYZ27NiTMT09VfYYpXOGChPo6NEj0Wo1Y+/ePWWPMpSTJ09Eq+X8TFBhQs3OHo7Z2cNlj8EIPKUAJBFUgCQDL/mLohjXHKW4+fiqeqj9dlQU9d2dnVVPXY+rn4FBvXDhi3HNUYqrV9e+++duBT9T99e/dvru6OLF+u7Nzqrn5p3VxZEj/X8+MKiPPbZvO2Yp3eLitVhf78XMzI13UDc2NkqcaHN+8IPp7+2oKL55YD766P3RbDZKnCyfnVVPv53V3cCg1m3B32pcP6ybj6+qx3rz3N9eWjWbjcoez53YWfX021ndeVMKIImgAiTxwf4dYn7+UszNfVj2GEM5derZaDY911dpZ/2srGxEr1dEu13dr6QeOvRIHD16h3eg+hDUHWB+/lKcPftenD//cdmjDGX//gfi+PGnYvfu6bJHKU3VdlZXly9/Hq1Wc+hvrDkN2AHm5j6s1APz9Ok3Y22tU/YYparazurq4sVP4913Pxj69s5Qd5qp3RH7Hix7itsV3Ygrn5U9xWSa1J3V2ZdLEWsrI99NUHeafQ9GnHix7Clut7oc8dpzZU8xmSZ1Z3X2zisRl+dHvptLfoAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAkl1lDzCxOtciVpfLnuJ2vY2yJ5hcdd1Z0Z3M46qzTe5MUO/kjd+UPQGjquvOrnwW8dpzZU/BEFzyAyQR1OtarVacP38mms1q/JUcO/ZkvPTSr8seo1R13tmpU8/G88//apsn4m5GfZy55L+u0WjErl2tOHfu9xFRlD3OXU1NTUWrVY2QbJc676zZbMYzz/winn76iW2eavssLX0dnU4vZmbuK3uUTRv1cSaot2i3q7v8naquO5uenorp6amyx9i0r75qxNRUL9rtPWWPMjY7+xQHIJGgAiQZeMm/sLAyrjnGanl5PbrdorbHt7h4LRqNG39eWaneZ1eXlr6O5eUbB7HTdlYHdd9ZPwOD2un0xjXHWHW7RfR6RW2Pb339+8fV603+Gza3Wl/vfm8/O21ndVD3nfUzMKgHDrTHNcdYLSysRKfTq93xFUURV6+uxczMnmg2b5zutNvVe2PjoYf2xN69N97M2Gk7q4O67mwQr6ECJBFUgCSb+hxqr9eLXq+6r4t0u93odnuxsVG9N2u+1Wg0d/wH+2HSjBzUoijizJk/xuuv/2E75mFIx48/FS+8cCIadXtrGCps5KC++uob8fbb57ZjFkbw1lt/iitXvojf/W5nf58fJsnI14xFUURRVO9jOHVTFFHpl12gjrb0Xf5/jIj/ThqE4fxHRPxf2UMAfW0pqNMRMZM0CMO5t+wBgDvyNjFAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIMmurdz584j4t6RBGM4nW/0FXy5GvPNyxii5ut2yJ4At21JQ/xYR7ycNwpisXYu4/FHZU0AtjXzJf+jQI3Hw4MPbMQsj+NGP/iEef/wnQ922ajs7duzJmJ6eKnsMGNnIZ6hHjx6JVqsZe/fu2Y55xmJ1tRtFUcQ992zpBL1Ujz/+k/jlL58Y6rZV29nJkyei1fLyPtWzqaLMzh6O2dnD2bOMzcLCSnQ6vThwoF32KGNT9Z1BFTgNAEgiqABJBl7yF0UxrjlKUdfjK4o6H1tdj6vOx1bP4+pnYFAvXPhiXHOU4urVtbJH2BYXL9Z3b3ZWPXXc2ZEj/X8+MKiPPbZvO2Yp3eLitVhf78XMTDXe9R5WUXzzwHz00fuj2WyUPU4qO6ueuu5skIFBrduCv9W4flh1O75vL62azUbtjs3OqqeuOxvEm1IASQQVIMmmPtg/P38p5uY+zJ5lW5w69Ww0m543qJ4qPc76WVnZiF6viHa7ul8jPnTokTh69A7vQPUxclDn5y/F2bPvxfnzH49611Ls3/9AHD/+VOzePV32KDC0qj3O6ury5c+j1WoO/S3DkU/d5uY+rNSST59+M9bWOmWPASOp2uOsri5e/DTeffeDoW+/tf87yNTuiH0PbulXbIuiG3Hls7KngByT+jirsy+XItZWRr7b1oK678GIEy9u6Vdsi9XliNeeK3sKyDGpj7M6e+eViMvzI9/NuzUASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCS7yh4AuIuiG7G6XPYUO0tvY1N3E1SYdFc+i3jtubKnYAgu+QGSCCpMoFOnno3nn/9V2WPseMeOPRkvvfTroW/vkh8mULPZjGee+UU8/fQTZY+yaUtLX0en04uZmfvKHmXTpqamotUa/rxTUGFCTU9PxfT0VNljbNpXXzViaqoX7faeskcZG5f8AEkEFSDJwEv+hYWV2362srK5z2eVaWnp61hebnz35+Xl9eh2i77HVweLi9ei0bj77arEzqqn7jvrZ2BQO53ebT/r9YptG2a7rK93v3cs3W4RvV7R9/jqYH29fsdlZ9VT9531MzCoBw60b/tZu129F8kfemhP7N1744XxhYWV6HR6fY+vyoqiiKtX12JmZk80m/U63bGz6qnrzgbxGipAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgya4t3fvLxYh3Xk4aJVG3W/YEwA60taCuXYu4/FHSKADVNvIl/6FDj8TBgw9vxyzb4tixJ2N6eqrsMYAdYOQz1KNHj0Sr1Yy9e/dsxzzpTp48Ea2Wl4qB7bepS/7Z2cMxO3s4exaASnPqBpBEUAGSCCpAkkZRFGXPAFALzlABkggqQBJBBUgiqABJBBUgiaACJPl/khZSH8P44TYAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "move num 5: (8, -1)\n",
            "game won ? True\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAOx0lEQVR4nO3dQWxc9Z3A8d/MZBwgnlQlVLmAN5dqkRAQpVKIVISl9AJ7aVUpqXbZQ+CyBy4QtWovqz1CixYhpWgPqxUHqCIE3ICKAxKWsgdwURS4IOUCFycIEVRiB3vsmdcDARIynoztn+fNe/58TmQ8Y/3++We+fm/ejGkURREAbF2z7AEA6kJQAZIIKkASQQVIIqgASQQVIMmuYV98771Xa/meqoWFpeh2+3HgQKfsUVIVRRFnz34RBw/ui2azUfY4qexZ9dR1zyIiHnjg2MDNcoQKkERQAZIIKkCSoa+h7jRFUcRzz70YVf447uefL8c779wSjQq/HHfy5GPRbI72s75Ke3bo0D1x9OiRke8/P/9RzM29v40T5dnIntWZoF7V7/fj9Ok347XX3q7Ek7PO9u+/I44ffyR2754aer+q7dn5859Gq9WM2dnDN73v/PxH8corb8WZMx+MYbKtG3XP6s6PlKv6/X6cOvVSJZ6YdffCC3+JlZXuTe9XtT07d+7jeOONd0e679zc+5WJacToe1Z3jlDX85OZiFa77Cl2jqIX8dknW/sek7pnX16MWFna/OPbuyP23Zk3T5aMPasZQV3Pr38X8eP9ZU+xcywvRjz/+Na+x6Tu2evPRpyf3/zj990ZceLpvHmyZOxZzTjlB0giqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIk2VX2ABOreyViebHsKXaO5StlTwBbJqjrefH3ZU8AVIxTfoAkgnpVq9WKM2dOR7Ppr6Rsc3MvR6ezp+wxYMOc8l/VaDRi165WvP32/0VEUfY4m1IUER9+eCnuvff2qPLPhampdjQajbLHgA0T1B+o8pFRURRx223L0ensiWZTkGDcKnwcAzBZBBUgydBT/oWFpXHNMVaLi6vR6xW1Xd+FC1eibi9BDtqzXq9X4kSbs7zcG/jv7od7trS0Nsapcly8+HUsLn6/iLo/zwYZGtRutz+uOcaq1yui3y9qu77V1fqta9Ce9XrVW2dRDP5398M96/erd2F0dbX3g/2p9/NskKFBPXCgM645xmphYSm63X7t1lcURVy6tBIzM9O1uyg1aM/W1qp3FHfrrbuuW8N6e9bptMsYb0vuums69u6d/u7PdX2eDeM1VIAkggqQxPtQf6Aqp5GNRjNardF/Hvb7/ej3q/FaVqvV8sZ+KklQr1EURTz00L9XIjzHjz8STz11YqTwFEURp0+/GadOvTSGybbuzJnTsWtXq+wxYMOc8l+1trYWP//5v1YiphERr7761/jDH/57pPs+99yL8ec/v7zNE+V56KFH46uv/OpEqkdQr1GVmEZ887n9UectiiKKojpvw6nSPsC1nPKv59/+K6JzR9lT3Ojt/4345MPNP/4nMxG//l3ePFm6V/wOWipPUNfTuSPix/vLnuJG7d1be3yrPZnr8n9HoAac8gMkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkuwqewDgJr68EPH6n8qe4ka9XtkTTBxBhUm3ciXi/N/KnoIROOWHCXTo0D1x//13lz3GyI4dezimptplj1E6R6gwgY4ePRKtVjP27p0ue5SRPPnkiWi1HJ8JKkyo2dnDMTt7uOwx2AA/UgCSCCpAkqGn/EVRjGuOUly7vqouddAeFUU99m7w2uxZ1dR1XYMMDerZs1+Ma45SXLq08t1/9yr4nrq//707cI/Onbv+ts8/Xx7XSGnOnfsi9uy5ce6dsmd1cu2e1cWRI4NvHxrUgwf3bccspbtw4UqsrvZjZub7K6hra2slTrQ5P/rR1HV7VBTfPDHvu+/2aDYb393+zju3lDHeltx77+3XXeHeaXtWB4P2rO6GBrVuG/ytxtVlXbu+qq712rm/PbVqNhvX3d6o4NLWW8NO2bM6GLRndeeiFEASQQVI4o39MKHm5z+Kubn3yx5j05aW1qLfL6LTqe5HUg8duieOHl3nCtQAggoTaH7+o3jllbfizJkPyh5lRzt//tNotZojf2LNKT9MoLm598V0Apw793G88ca7I9/fESpMuvbuiH13lj3FzvLlxYiVpQ0/TFBh0u27M+LE02VPsbO8/mzE+fkNP8wpP0ASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgya6yB5hY3SsRy4tlT3Gj/trWHl/0JnNdy1e2/j3sGVk2uWeCup4Xf1/2BNvjs08inn+87Cm2hz2jZE75AZII6lWtVivOnDkdzWY1/kqOHXs4nnnmtyPd9+TJx+KJJx7d5onyzM29HJ3Onpvez56x3TayZxERjaIo1v3ie++9uv4XK2xhYSm63X4cONC54WuXLy9FxOQvu91uxy237L7utqIo4uzZL+LgwX3RbDau+1q3uxorKyvjHHHTpqf3RKNx/fz2rHouXvw6ut1+zMzc/IfjpBq0ZxERDzxwrDHg7l5D/aFRjoyqaGqqHVNT7bLH2Bb2bDJdvtyIdrsfnc502aOMTTXOlQAqQFABkgw95V9YWBrXHGO1uLgavV5R2/VduHAlGgNf4akue1Y9dd+zQYYGtdvtj2uOser1iuj3i9qub3W1fuuyZ9VT9z0bZGhQB11RrYNhV4yrrCiKuHRpJWZmpm+4Ylx19qx66rpnw3gNFSCJoAIk2dT7UPv9fvT71X1dpNfrRa/Xj7W1Lf7SihI1Gs1otfw8hEmy4aAWRRGnT78Zp069tB3zMKLjxx+Jp546ccMnioDybDiozz33Yrz22tvbMQsb8Oqrf43PPvsi/vjH0T9nDGyvDZ8zFkURwz7/z3gURVT6ZReooy19lv+fI+J/kgZhNP8ZEf9f9hDAQFsK6lREzCQNwmhuK3sAYF0uEwMkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkuzayoM/jYj/SBqE0XxY9gDAurYU1K8i4p2kQQCqbsOn/IcO3RP333/3dszCBvz0p/8UDz74s7LHAK6x4SPUo0ePRKvVjL17p7djnrFYXu5FURRx661bOkAv1YMP/ix++ctflD0GcI1NFWV29nDMzh7OnmVsFhaWotvtx4EDnbJHAWrEVX6AJIIKkGToKX9RFOOaoxR1XV9R1HltdV1XnddWz3UNMjSoZ89+Ma45SnHp0krZI2yLc+fqu2/2rHrquGdHjgy+fWhQDx7ctx2zlO7ChSuxutqPmZnqvlNhkKL45ol53323R7PZKHucVPaseuq6Z8MMDWrdNvhbjavLqtv6vj21ajYbtVubPaueuu7ZMC5KASQRVIAkm3pj//z8RzE39372LNvi5MnHotn0c4PqqdLzbJClpbXo94vodNplj7Jphw7dE0ePrnMFaoANB3V+/qN45ZW34syZDzb60FLs339HHD/+SOzePVX2KDCyqj3P6ur8+U+j1WqO/MnQDR+6zc29X6lNfuGFv8TKSrfsMWBDqvY8q6tz5z6ON954d+T7b+23g7R3R+y7c0vfYlsUvYjPPil7Csgxqc+zOvvyYsTK0oYftrWg7rsz4sTTW/oW22J5MeL5x8ueAnJM6vOszl5/NuL8/IYf5moNQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSDJrrIHAG6i6EUsL5Y9xc7SX9vUwwQVJt1nn0Q8/3jZUzACp/wASQQVJtDJk4/FE088WvYYO96xYw/HM8/8duT7O+WHCdRsNuM3v/mX+NWvflH2KJt28eLX0e32Y2ZmT9mjbFq73Y5Wa/TjTkGFCTU11Y6pqXbZY2za5cuNaLf70elMlz3K2DjlB0giqABJhp7yLyws3XDb0tLm3p9VposXv47FxcZ3f15cXI1erxi4vjq4cOFKNBo3v1+V2LPqqfueDTI0qN1u/4bb+v1i24bZLqurvevW0usV0e8XA9dXB6ur9VuXPaueuu/ZIEODeuBA54bbOp3qvUh+113TsXfv9y+MLywsRbfbH7i+KiuKIi5dWomZmeloNut1uGPPqqeuezaM11ABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASXZt6dFfXoh4/U9JoyTq9cqeANiBthbUlSsR5/+WNApAtW34lP/QoXvi/vvv3o5ZtsWxYw/H1FS77DGAHWDDR6hHjx6JVqsZe/dOb8c86Z588kS0Wl4qBrbfpk75Z2cPx+zs4exZACrNoRtAEkEFSCKoAEkaRVGUPQNALThCBUgiqABJBBUgiaACJBFUgCSCCpDkH1m0fE3XhFJQAAAAAElFTkSuQmCC",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "move num 6: (1, 4)\n",
            "game won ? True\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAOwElEQVR4nO3dQWxc9Z3A8d/MZBwgnlQlVLmAN5dqkSIgSqUQqQhL6QX20qpSUu2yh8BlD1wgatVeVnuEFi1CStEeVisOUEUIuAEVByQsZQ/goijkgpQLXJxEKEEldrDHnnk9ECAh48nY/tlv3vPncyLjGev3zz/z9XtvZkyjKIoAYOOaZQ8AUBeCCpBEUAGSCCpAEkEFSCKoAEl2DPvihx++Ucv3VM3NLUS32499+zplj5KqKIo4c+ZyHDiwJ5rNRtnjpLJn1VPXPYuIePjhowM3yxEqQBJBBUgiqABJhl5D3W6KoogXX3wlqvxx3C++WIz3378jGhW+HHfixJPRbI72s75Ke3bw4P44cuTwyPefnT0XMzMfbeJEedayZ3UmqNf1+/04deqdePPN9yrx5KyzvXvviWPHHo+dOyeG3q9qe3b+/OfRajVjevrQbe87O3suXn/93Th9+uMtmGzjRt2zuvMj5bp+vx8nT75aiSdm3b388l9iaal72/tVbc/Onv003n77g5HuOzPzUWViGjH6ntWdI9TV/GQqotUue4rto+hFXPpsY99jXPfsy4sRSwvrf3x7Z8See/PmyZKxZzUjqKv59e8ifry37Cm2j8X5iJee2tj3GNc9e+uFiPOz63/8nnsjjj+XN0+WjD2rGaf8AEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkO8oeYGx1r0Uszpc9xfaxeK3sCWDDBHU1r/y+7AmAinHKD5BEUK9rtVpx+vSpaDb9lZRtZua16HR2lT0GrJlT/usajUbs2NGK9977v4goyh5nXYoi4pNPrsQDD9wdVf65MDHRjkajUfYYsGaC+gNVPjIqiiLuumsxOp1d0WwKEmy1Ch/HAIwXQQVIMvSUf25uYavm2FLz88vR6xW1Xd+FC9eibpcgB+1Zr9crcaL1WVzsDfx398M9W1hY2cKpcly8+HXMz3+/iLo/zwYZGtRut79Vc2ypXq+Ifr+o7fqWl+u3rkF71utVb51FMfjf3Q/3rN+v3gujy8u9H+xPvZ9ngwwN6r59na2aY0vNzS1Et9uv3fqKoogrV5Ziamqydi9KDdqzlZXqHcXdeeeOm9aw2p51Ou0yxtuQ++6bjN27J7/7c12fZ8O4hgqQRFABkngf6g9U5TSy0WhGqzX6z8N+vx/9fjWuZbVaLW/sp5IE9QZFUcSjj/57JcJz7Njj8eyzx0cKT1EUcerUO3Hy5KtbMNnGnT59KnbsaJU9BqyZU/7rVlZW4uc//9dKxDQi4o03/hp/+MN/j3TfF198Jf7859c2eaI8jz76RHz1lV+dSPUI6g2qEtOIbz63P+q8RVFEUVTnbThV2ge4kVP+1fzbf0V07il7ilu9978Rn32y/sf/ZCri17/LmydL95rfQUvlCepqOvdE/Hhv2VPcqr1zY49vtcdzXf7vCNSAU36AJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQJIdZQ8A3MaXFyLe+lPZU9yq1yt7grEjqDDulq5FnP9b2VMwAqf8MIYOHtwfDz10f9ljjOzo0cdiYqJd9hilc4QKY+jIkcPRajVj9+7JskcZyTPPHI9Wy/GZoMKYmp4+FNPTh8oegzXwIwUgiaACJBl6yl8UxVbNUYob11fVpQ7ao6Kox94NXps9q5q6rmuQoUE9c+byVs1RiitXlr77714F31P39793B+7R2bM33/bFF4tbNVKas2cvx65dt869XfasTm7cs7o4fHjw7UODeuDAns2YpXQXLlyL5eV+TE19/wrqyspKiROtz49+NHHTHhXFN0/MBx+8O5rNxne3v//+HWWMtyEPPHD3Ta9wb7c9q4NBe1Z3Q4Natw3+VuP6sm5cX1XXeuPc355aNZuNm25vVHBpq61hu+xZHQzas7rzohRAEkEFSOKN/TCmZmfPxczMR2WPsW4LCyvR7xfR6VT3I6kHD+6PI0dWeQVqAEGFMTQ7ey5ef/3dOH3647JH2dbOn/88Wq3myJ9Yc8oPY2hm5iMxHQNnz34ab7/9wcj3d4QK4669M2LPvWVPsb18eTFiaWHNDxNUGHd77o04/lzZU2wvb70QcX52zQ9zyg+QRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSLKj7AHGVvdaxOJ82VPcqr+ysccXvfFc1+K1jX8Pe0aWde6ZoK7mld+XPcHmuPRZxEtPlT3F5rBnlMwpP0ASQb2u1WrF6dOnotmsxl/J0aOPxfPP/3ak+5448WQ8/fQTmzxRnpmZ16LT2XXb+9kzNtta9iwiolEUxapf/PDDN1b/YoXNzS1Et9uPffs6t3zt6tWFiBj/Zbfb7bjjjp033VYURZw5czkOHNgTzWbjpq91u8uxtLS0lSOu2+Tkrmg0bp7fnlXPxYtfR7fbj6mp2/9wHFeD9iwi4uGHjzYG3N011B8a5cioiiYm2jEx0S57jE1hz8bT1auNaLf70elMlj3KlqnGuRJABQgqQJKhp/xzcwtbNceWmp9fjl6vqO36Lly4Fo2BV3iqy55VT933bJChQe12+1s1x5bq9Yro94varm95uX7rsmfVU/c9G2RoUAe9oloHw14xrrKiKOLKlaWYmpq85RXjqrNn1VPXPRvGNVSAJIIKkMT7UGFM9fv96Pere/2x1+tFr9ePlZUN/nKYEjUazWi1Rj/uFFQYQ0VRxKlT78TJk6+WPcq2duzY4/Hss8dv+eTeagQVxtCLL74Sb775XtljbHtvvPHXuHTpcvzxj6N9nt81VBhDRVHEsN+zwdYoiljTZRdHqDDm/jki/qfsIbaZ/4yI/1/H4wQVxtxEREyVPcQ2c9c6H+eUHyCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQZEfZAwDDfR4R/1H2ENvMJ+t8nKDCmPsqIt4vewhG4pQfxtDBg/vjoYfuL3uMbe+nP/2neOSRn418f0eoMIaOHDkcrVYzdu+eLHuUdVtc7EVRFHHnndXNzCOP/Cx++ctfjHz/6q4Uam56+lBMTx8qe4x1m5tbiG63H/v2dcoeZcs45QdIIqgASYae8hdFsVVzlKKu6yuKOq+truuq89rqua5Bhgb1zJnLWzVHKa5cWSp7hE1x9mx9982eVU8d9+zw4cG3Dw3qgQN7NmOW0l24cC2Wl/sxNVXdV1AHKYpvnpgPPnh3NJuNssdJZc+qp657NszQoNZtg7/VuL6suq3v21OrZrNRu7XZs+qp654N40UpgCSCCpBkXW/sn509FzMzH2XPsilOnHgymk0/N6ieKj3PBllYWIl+v4hOp132KOt28OD+OHJklVegBlhzUGdnz8Xrr78bp09/vNaHlmLv3nvi2LHHY+fOibJHgZFV7XlWV+fPfx6tVnPkT6yt+dBtZuajSm3yyy//JZaWumWPAWtStedZXZ09+2m8/fYHI99/Y5/lb++M2HPvhr7Fpih6EZc+K3sKyDGuz7M6+/JixNLCmh+2saDuuTfi+HMb+habYnE+4qWnyp4Ccozr86zO3noh4vzsmh/m1RqAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQJIdZQ8A3EbRi1icL3uK7aW/sq6HCSqMu0ufRbz0VNlTMAKn/ABJBBXG0IkTT8bTTz9R9hjb3tGjj8Xzz/925Ps75Ycx1Gw24ze/+Zf41a9+UfYo63bx4tfR7fZjampX2aOsW7vdjlZr9ONOQYUxNTHRjomJdtljrNvVq41ot/vR6UyWPcqWccoPkERQAZIMPeWfm1u45baFhfW9P6tMFy9+HfPzje/+PD+/HL1eMXB9dXDhwrVoNG5/vyqxZ9VT9z0bZGhQu93+Lbf1+8WmDbNZlpd7N62l1yui3y8Grq8Olpfrty57Vj1137NBhgZ1377OLbd1OtW7SH7ffZOxe/f3F8bn5hai2+0PXF+VFUURV64sxdTUZDSb9TrcsWfVU9c9G8Y1VIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkASQQVIIqgASQQVIImgAiQRVIAkggqQRFABkggqQBJBBUgiqABJBBUgiaACJBFUgCSCCpBEUAGSCCpAEkEFSCKoAEkEFSCJoAIkEVSAJIIKkERQAZIIKkCSHRt69JcXIt76U9IoiXq9sicAtqGNBXXpWsT5vyWNAlBtaz7lP3hwfzz00P2bMcumOHr0sZiYaJc9BrANrPkI9ciRw9FqNWP37snNmCfdM88cj1bLpWJg863rlH96+lBMTx/KngWg0hy6ASQRVIAkggqQpFEURdkzANSCI1SAJIIKkERQAZIIKkASQQVIIqgASf4BZf98TUpKnjUAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "img = Drawing.show_parking(easy)\n",
        "imshow(img)\n",
        "\n",
        "for i in range(len(moves_BFS)):\n",
        "  move = moves_BFS[i]\n",
        "  easy.move_car(move)\n",
        "  print(f\"move num {i+1}: {move}\")\n",
        "  print(f\"game won ? {easy.won()}\")\n",
        "  img = Drawing.show_parking(easy)\n",
        "  imshow(img)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 357
        },
        "id": "u8Y64a_rVsVV",
        "outputId": "1ff2aeb8-efc1-43cd-a391-99d7b858b951"
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAARWklEQVR4nO3cT2xU9d7H8c85p9OKMBAF043WbshzE4MQSJSEBhLcyF08GBNq/LNAt26EaC47l9frjcQEyZNcY1ioaQy402u6ILkk3SjeECB5chNccDdTCKGGa1vb6ZzzuwtBi50O8+c785vfb96vlbfMNN9zvz3vmTMzbeKcEwCgc6nvAQAgFgQVAIwQVAAwQlABwAhBBQAjBBUAjAw1+sdvvz0b5WeqKpUFVauFxsfLvkcx5ZzTpUu3tWvXVqVp4nscU+wsPLHuTJKeffZI3WXxDBUAjBBUADBCUAHASMPXUBGPixev6sKF73yP0ZTjx19Xmjb3WO+c08mTZxTyr1DfurWk8+cfUhLXS6haWKipKJzK5ZLvUdq2e/dTOnhwb9O3J6gD4OLFq/rii79rZuafvkdpyujoNk1OHtLIyHDD2xVFoampr3Xu3HTQQUX/unbt38qyVAcOPNPU7bnkHwAXLnwXTEwl6fTpz7W8XH3g7Yqi0KlTnxJTdM3ly//SV1/9o+nb8wx10JRGpK2P+55iLZdLN6939j0eG5OycC8v0Ud+vCEtL7R8N4I6aLY+Lh39s+8p1lqalz58o7Pv8eI70iOjNvNgsH35V+naxZbvxiU/ABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARoZ8DwCYqS5KS/O+p0AMilpbdyOoiMeZP/meAAOOS34AMEJQEawsyzQzM6U05ccY3XHkyPN67723m749l/wIVpIkGhrKND39iSTne5y2OCdduTKnHTseVWyPCzdu/KxqtdDY2Ebfo7StVCopy5pfDEFF8MrlcE9Y55wefnhJ5fJGpWniexxTP/2UqFQqVC5v8j1Kz0T2mAgA/hBUADDS8JK/Ulno1Rw9NT+/ojx30R7f7OyiklVXjwsL7X2mzqcbN37W/PxvBzFoO4tB7Durp2FQq9WiV3P0VJ47FYWL9vhWVu4/rqII7w2blZX8vv0M2s5iEPvO6mkY1PHxcq/m6KlKZUHVahHd8TnnNDe3rLGxTfe9wVEulzxO1Z4nntikzZt/ezNj0HYWg1h31givoQKAEYIKAEba+hxqURQqijBeF8myTElsr/bjPrVaGG+6JUna0ofEQzrP6snzXHleBLOfelrdWctBdc5pauprnTr1aat39WJmZkpDQ5nvMdAlzjnt3/9aEOGZnDykY8eONvUAH9p5FqtWdia1ccl/8uQZffTRZy0P5sv+/a/qP//hT7rFqFarad++l4OIqSSdPfuNTpz4oKnbhnaexaqVnUltBNU5J+fC+RhOKCcb2hPSfp1rft7QzrNYtbIzqdPf5X9sTHrxnY6+RVdUF/nbmIPolXel8jbfU6w1/bF0/Ur79+/X8yxmbe6ss6BmJemR0Y6+RVfwV9sHU3lbf/48lkY6u3+/nmcxa3NnfGwKAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAI0O+B0CP/Tgrffm+7ynWynPfE/Svft1ZzCo/tHU3gjpolhela9/7ngKtYGfB4JJ/AOze/ZR27vyD7zGaduTI8xoeLvkew6vQdhar7duf1MTEnqZvzzPUAXDw4F5lWarNmzf5HqUpb711VFk22I/1oe2snqWlXM45bdgQbmYmJvbo8OHnmr59uEeKlhw48IwOHHjG9xhoQeg7q1QWVK0WGh8v+x6lZwb7aQAAGCKoAGCk4SW/c65Xc3RdvWOJ6fhWcy7mY3Or/tvjIB2o/7M4GDuLXcOgXrp0e83Xbt1a6tow3XL58m1t3Lh27rm5ZQ/TdN/ly2v3FovVO8sD/OzqnTvVuufVoOwsFnv31v96w6Du2rV1zdfOn3/IZKBe2rHj0fveLZ2dXdTKSqGxsXDfQa3HuV9OzKefflRpmvgex1S9ndVqNY8TtWfLluH7zqtB21nsGga13oKTAHeepsl9x3LvGGL7Ab53afX7441BvZ2Feoyr5x60ncWON6UAwAhBBQAjfLB/FeecTp48E/S7krduLen8+YeCfGnmnuPHX1ea8liP8BDUu4qi0NTU1zp3bjrooMZgdHSbJicPaWRk2PcoQEt4GnBXURQ6depTYtoHTp/+XMvLVd9jAC3jGeo6/kcSz496J5f0/76HADpEUNfxf5LGfA8xQO5Iav6PpAH9iUt+ADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjAx1dG+XS0vzRqMYWlrs+FvMS7rT+SRo0k++BwAMdBbUm9elD9+wmaTP/K/vAQAEh0t+ADDSclCPH39db775ajdm6YoLFz5TubzxgbfLskwzM1NKUx5jfGt2Z0C/afmSP01TvfTSH/XCC891Yx5zw8MlJUnywNslSaKhoUzT059Ict0frAuck65cmdOOHY8q5MeFZncG9Ju2XkMdHi5peLhkPUtfCPmZkXNODz+8pHJ5o9KUIAG9FvDzGADoLwQVAIw0vOSvVBZ6NUdPzc+vKM9dtMc3O7uo2F6CrLezPM89TtSepaW87s/doOwsdg2DWq0WvZqjp/LcqShctMe3shLfcdXbWZ6Hd5zO1f+5G5Sdxa5hUMfHy72ao6cqlQVVq0V0x+ec09zcssbGNkX3plS9ndVqNY8TtWfDhqH7jmHQdhY7XkMFACMEFQCMdPa7/BEK5TIySVJlGY+HMSuKQkUR7uuPeZ4rz4tgzql6Wj3PCOoqzjnt3/9aED/Ek5OHdOzYUX6jKFLOOU1Nfa1Tpz71PcpAa/U84ynOXbVaTfv2vRxETCXp7NlvdOLEB77HQJecPHlGH330me8xBl6r5xlBXSWUmEq//N5+SPOiNc45ORfm35SISavnGZf863nlXam8zfcUa01/LF2/4nsK9NJjY9KL7/ieYrC0eZ4R1PWUt0mPjPqeYq3SiO8J0GtZqT9/FmPW5nnGJT8AGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGhnwPAJiZ/ptUGvE9xVqVHzq7/4+z0pfv28yC5rS5M4KKeFy/6nuC7lhelK5973sKNIFLfgQrSVJNTh5SkviepDnbtz+piYk9Td129+6ntHPnH7o8ER6klZ1JPENFwLIs1bFjR3Xz5m0VReF7nAeamNijw4efa+q2Bw/uVZal2rx5U5en6p6lpVzOOW3YEG5mWtmZRFARuCRJ9Je/vO17jK44cOAZHTjwjO8x2lapLKhaLTQ+XvY9Ss9wyQ8ARggqABhpeMnvnOvVHF6sPr5QD7XejpyLd3fxHlfMxxbncdXTMKiXLt3u1RxezM0t//rfeZ57nKQ9d+5U6+7o8uV497Z6ZzFhZ2HZu7f+1xsGddeurd2YxbvZ2UWtrBQaG/vtHdRareZxovZs2TJ8346c++XEfPrpR5WmgXyWqEn1dhYDdhaXhkGNbcH33Pvc4urjC/VYV89979IqTZNgj2c99XYWA3YWF96UAgAjBBUAjLT1wf6LF6/qwoXvrGfpiuPHX1ea8rgR0s7qWVioqSicyuWS71Hatnv3Uzp4cJ13MwaIc04nT54J4t3/VnfWclAvXryqL774u2Zm/tnqXb0YHd2myclDGhkZ9j2KN6HtLFbXrv1bWZYG/dtPnSqKQlNTX+vcuekggtrqzlp+6nbhwndBnZinT3+u5eWq7zG8Cm1nsbp8+V/66qt/+B7Dq6IodOrUp0HEVGp9Z539Ln9pRNr6eEffoitcLt287nuK/tSvO4vZjzek5QXfU/Snx8akrA9fxmlzZ50Fdevj0tE/d/QtumJpXvrwDd9T9Kd+3VnMvvyrdO2i7yn604vvSI+M+p5irTZ3xrs1AGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGBnyPUDfqi5KS/O+p1irqHV2f5f353HFrNOdIRgEdT1n/uR7gu64eV368A3fUwBR4pIfAIwQ1LuyLNPMzJTSNIz/S44ceV7vvfd2U7c9fvx1vfnmq12eCA/Sys4QJi7570qSRENDmaanP5HkfI/zQKVSSVnWXPzTNNVLL/1RL7zwXJen6p4bN35WtVpobGyj71Ha1srOECaC+jvlcrgnbCPDwyUND5d8j9G2n35KVCoVKpc3+R4FWBcPlwBghKACgJGGl/yVysKary0shPeZuhs3ftb8fPLr/56fX1Geu7rHF4PZ2UUlyYNvFxJ2Fp56O8vz3ONE7Vlaypv+uWsY1Gq1WPO1ouj/N2x+b2Ulv+9Y8typKFzd44vBykp8x8XOwlNvZ3ke3nE61/zPXcOgjo+X13ytXA7vjY0nntikzZt/ezOjUllQtVrUPb6QOec0N7essbFNStO4nu6ws/DU21mtFt4V7oYNQ03/3PEaKgAYIagAYITPof5OiJck9zj3y4v+tVotusvHPM+V50XQ+0mSlA/2R46gruKc0/79r6kownvhHP1vcvKQjh07qiS2t/PxKx4u76rVatq372Viiq45e/YbnTjxge8x0EUEdRViim5yjp+x2HHJv55X3pXK23xPgRhMfyxdv+J7CvQAQV1PeZv0yKjvKRCD0ojvCdAjXPIDgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABgZKije/84K335vtEohvK88+8x/TepNNL59wEqP/ieoH/163nW5s46C+ryonTt+46+Rd+6ftX3BED8IjvPWr7k3737Ke3c+YduzNIVR448r+Hh0gNvlySpJicPKUl6MBQG0vbtT2piYo/vMbwK7TxrdWctP0M9eHCvsizV5s2bWr2rF2+9dVRZ9uDHjSxLdezYUd28eVtFUfRgsu64c6eqLVuGfY9hbmkpl3NOGzZ0dlHl08TEHh0+/JzvMbwK7TxrdWeJc27df/z227Pr/2PAKpUFVauFxsfLvkcx5ZzTpUu3tWvXVqVpIE8BmsTOwhPrziTp2WeP1F0W7/IDgBGCCgBGCCoAGGn4GioAoHk8QwUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjPwXs+hmr/2hYaEAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "# Test Config hard\n",
        "parking = Parking(6,6)\n",
        "hard = RushHour(parking)\n",
        "\n",
        "hard.add_car(Car(1,2,HORIZONTAL, 2, is_red=True))\n",
        "hard.add_car(Car(3,0,HORIZONTAL,3))\n",
        "hard.add_car(Car(4,1,HORIZONTAL,2))\n",
        "hard.add_car(Car(4,3,HORIZONTAL,2))\n",
        "hard.add_car(Car(2,4,HORIZONTAL,2))\n",
        "hard.add_car(Car(1,5,HORIZONTAL,3))\n",
        "hard.add_car(Car(2,0,VERTICAL,2))\n",
        "hard.add_car(Car(3,1,VERTICAL,3))\n",
        "hard.add_car(Car(0,1,VERTICAL, 2))\n",
        "hard.add_car(Car(0,4,VERTICAL, 2))\n",
        "hard.add_car(Car(1,3,VERTICAL, 2))\n",
        "hard.add_car(Car(5,4,VERTICAL, 2))\n",
        "\n",
        "img = Drawing.show_parking(hard)\n",
        "imshow(img)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mV5z0S4eXDEx",
        "outputId": "00e3a48a-b2a7-4379-d5d1-c103f9750369"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "number of moves for solving the puzzle with Solver_BFS :  26\n"
          ]
        }
      ],
      "source": [
        "moves_BFS = Solver_BFS.solve(hard)\n",
        "\n",
        "print(\"number of moves for solving the puzzle with Solver_BFS : \", len(moves_BFS))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 357
        },
        "id": "u0YIjMFBl1Tf",
        "outputId": "255e84b2-bde1-4ca5-b787-4b8190290164"
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFUCAYAAAB7ksS1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAROUlEQVR4nO3dT2xU9d7H8c85pzMVYSACho32dmMeE4MQSJQEUhLcwF1cjUlrFBfg1g00Gtm5vF6fSEwKeZJrDAswjUF3l2u6ILlNulG8IUDy5Em4C55NCyHUgG1tp3PO7y64/LPD9EznO/Ob85v3a6VlhnyP3573zJmZ1sg5JwBA62LfAwBAKAgqABghqABghKACgBGCCgBGCCoAGOlr9Ic//ng+yM9UTU/Pq1rNNDhY8T2KKeecLl++o507tyiOI9/jmGJnxRPqziTp9deH6y6LZ6gAYISgAoARggoARhq+hvo0ly5d0+TkT9aztMXo6FHFcb7HDeecTp48oyL/OO7t24u6ePEZRQV+Oa6ZnYUs1PMsZE0H9dKla/r2279rauqf7ZjH3LZtWzUyckj9/eWGt8uyTOPjF/TddxOFDmoI8u4sZKGeZ6Fr+iFlcvKnwixZkk6f/kZLS9VVb5dlmcbGzhLTLpB3ZyEL9TwL3Zou+R8q9UtbXjAaxZBLpVs3Wvs7nh+QkpLJOMjBYmehCvk8C0xrQd3ygnTkz0ajGFqck778oLW/4+2Ppee22cyD1VnsLFQhn2eB4VVkADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjPT5HqBrVRekxTnfU/SOxQXfEwAtI6hPc+YT3xMAKBgu+QHACEH9jyRJNDU1rjjmP4lvk5PnVKms9z0G0DQu+f8jiiL19SWamPhakvM9zpo4J129Oqvt2zeryI8L5XJJURT5HgNoGkH9nSI/M3LO6dlnF1WprFccEySg0wr8PAYAugtBBQAjDS/5p6fnV3xtfr7WtmHa5ebN3zQ39+gSeG5uWWnq6h5fCGZmFhTaS5C9tjPOs2JqGNRqNVvxtSwr3hs2y8vpE8eSpk5Z5uoeXwiWl8M7rl7bGedZMTUM6uBgZcXXKpVS24Zplxdf3KCNGzc8/Pfp6XlVq1nd4ysy55xmZ5c0MLAhuDelem1nnGfFxGuoAGCEoAKAET6H+ju1WjHeDIiiWEmS//EwyzJlWTFey0qShA/2By7U84ygPsY5p6Gh9wsRnpGRQzp+/Eiu8DjnND5+QWNjZzswWeumpsbV15f4HgNtEup5JnHJ/1CtVtPeve8WYsmSdP78Dzpx4otctz158oxOnTrX5onsDA0d1r17/OrEEIV8nkkE9QlFWbJ0/+f2887rnJNzxfkYTpH2gOYVab/NnGcSl/xP996nUmWr7ylWmvhKunF17fd/fkB6+2O7eaxUF/gdtL0osPOMoD5NZav03DbfU6xU6m/t/kmpO4+L/ztCbwrsPOOSHwCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACN9vgcAsIpfZqTvP/c9xUpp6nuCrkNQgW63tCBd/9n3FMiBS36gC+3a9Yp27HjZ9xi5DQ8fVLlc8j2GdzxDBbrQgQN7lCSxNm7c4HuUXI4dO6Ik4fkZQQW61P79r2n//td8j4Em8JACAEYIKgAYaXjJ75zr1BxtV+9YHv9aUQ+1/nGFsbvVdhaSUHZWT6jnWT0Ng3r58p0VX7t9e3FtE3l05codrV+/cu7Z2aWH/5wW8DN1d+9W6+7oypUnvxbqzkLy+52FJMTzbM+e+rdtGNSdO7es+NrFi8+sfTJPtm/f/MS7pTMzC1pezjQw8OhrtVrNx2gt2bSp/MSOnLt/Yr766mbFcfTw66HuLARP21kIQj3PGmkY1HoLjgq48ziOnjiWB8fw+NeK+s38+NwPLkuedrxFkmdnIXjazkIQ6nnW8HZtngMAegZBBQAjfLAfheac08mTZwr9Dvnt24u6ePGZQr4088Do6FHFMc/PCCoKK8syjY9f0HffTRQ6qCHYtm2rRkYOqb+/7HsUr3hIQWFlWaaxsbPEtAucPv2NlpaqvsfwjmeoCMZ/Sert50edlUr6X99DdBmCimD8j6QB30P0kLuSdvseostwyQ8ARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoCRvpbu7VJpcc5oFEOLC63/HdWF7jy2rNba/QPe2Zyku61Pgpx+9T1AF2otqLduSF9+YDNJtznzie8J2iPgnf3J9wDoeVzyA4CRpoM6OnpUH354uB2ztMXk5DlVKutXvV2SJJqaGlccF+MxZnj4oD777KNct2VnaLe8Owtd05f8cRzrnXf+qLfeeqMd85grl0uKomjV20VRpL6+RBMTX0ty7R+sRaVSSUmSLyTsrHs5J129Oqvt2zeryI8LeXcWujW9hloul1Qul6xn6QqhPsqys+7knNOzzy6qUlmvOCZIRVfgx0QA6C4EFQCMNLzkn56e79QcHTU3t6w0dcEe38zMgkJ7OYudFU+9naVp6nGitVlcTHN/3zUMarWamQzUbdLUKctcsMe3vBzecbGz4qm3szQt3nE6l//7rmFQBwcrJgN1m+npeVWrWXDH55zT7OySBgY2BPcGBzsrnno7q9Va/Ek/D9at68v9fcdrqABghKACgJE1fQ41yzJlWfFeC3kgTVOlaVbIy49GnLt/bLVardCXj0mSNPUh8aLsMYri3D+MgWJqOqjOOY2PX9DY2Nl2zANoampcfX1Jrts65zQ09H4hHuBHRg7p+PEj/ERRwJp+uDx58oxOnTrXjlkASdLQ0GHdu7f6rxis1Wrau/fdQsRUks6f/0EnTnzhewy0UdNBdc7JuWL+3DSKoZlAFiWm0v2XZIo0L5rX2u9DfX5Aevtjo1HQ06oLrf8O2vc+lSpbbeaxNPGVdOOq7ynQAa0FNSlJz20zGgU9zeL/IlDZ2p3fj6V+3xOgQ3jLEQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACN9Ld37lxnp+8+NRkFPS1PfE8CHib9KpX7fU6w0/a813a21oC4tSNd/bumvANDDblzzPYGppi/5d+16RTt2vNyOWQBJ0vDwQZXLJd9joA2iKNbIyCFFke9J8nnppT9o377duW/f9DPUAwf2KElibdy4odm7do3FxVTOOa1b19oT9G50925VmzaVfY/RkmPHjihJeHk/REkS6/jxI7p1646yLPM9zqr27dutN998I/ft11SU/ftf0/79r63lrl1henpe1WqmwcGK71FMOed0+fId7dy5RXFckKcA6DlRFOkvf/nI9xhtwdMAADBCUAHASMNLfudcp+bwItTjcy7kY3OP/bPHQVpQbze9srPQNQzq5ct3OjWHF7OzS75HaIsrV8Ld2+M7Swv42dW7d6t1z6te2Vko9uyp//WGQd25c0s7ZvFuZmZBy8uZBgaK+0mFepy7f2K++urm4N6UqrezWq3mcaK12bSp/MR51Ws7C13DoIa24AcefAYutON7cGkVx1Fwx1ZvZ0U9xsfn7rWdhY43pQDACEEFACPh/agQ6rp06ZomJ3/yPUYuo6NHFcc81hdpZ/XMz9eUZU6VSnF/jHjXrld04MBT3oGqg6D2gEuXrunbb/+uqal/+h4ll23btmpk5JD6+4v9I7StKNrOQnX9+v8rSeLcPxnK04AeMDn5U6FOzNOnv9HSUtX3GF4VbWehunLl//S3v/0j9+15htprSv3Slhd8T7GSS6VbN3xP0Z26dWch++WmtDTf9N0Iaq/Z8oJ05M++p1hpcU768gPfU3Snbt1ZyL7/b+n6pabvxiU/ABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARggqABghqABghKACgBGCCgBGCCoAGCGoAGCEoAKAEYIKAEYIKgAYIagAYISgAoARggoARvp8DwCYqS5Ii3O+p1gpq7V2f5d253GFbI07I6gIx5lPfE/QHrduSF9+4HsK5MAlPwAYIagorCRJNDU1rjguxrfx8PBBffbZR7luOzp6VB9+eLjNE2E1zexM4pIfBRZFkfr6Ek1MfC3J+R5nVaVSSUmSL/5xHOudd/6ot956o81Ttc/Nm7+pWs00MLDe9yhr1szOJIKKAFQqxT1hGymXSyqXS77HWLNff41UKmWqVDb4HqVjinGtBAAFQFABwEjDS/7p6flOzdFRc3PLSlMX7PHNzCwoih79+/x8i5+D9ODmzd80N/foIHptZyEIfWf1NAxqtZp1ao6OSlOnLHPBHt/y8pPHlWXd/4bN7y0vp0/sp9d2FoLQd1ZPw6AODlY6NUdHTU/Pq1rNgjs+55xmZ5c0MLBBcfzo6U6lUrw3Nl58cYM2bnz0Zkav7SwEoe6sEV5DBQAjBBUAjKzpc6hZlinLivu6SJqmStNMtVrx3qx5IIripj5wHLIi79G5+9+PtVqt0Jf8SZIoCu1dtTVoOqjOOY2PX9DY2Nl2zIOcRkYO6fjxIz3/Teyc09DQ+4V+gA/B1NS4+voS32N41/RTnJMnz+jUqXPtmAVNOH/+B5048YXvMbyq1Wrau/ddYtoFhoYO6949fsVg00F1zsm54n0MJzTOiZCI/wbdgj3c19rP8j8/IL39sdEoyGXiK+nGVd9TdKf3PpUqW31P0TuqC+H+Dto1ai2oSUl6bpvRKMil1O97gu5V2cr3YyfxfxFYgbeJAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMEJQAcAIQQUAIwQVAIwQVAAwQlABwAhBBQAjBBUAjBBUADBCUAHACEEFACMEFQCMEFQAMNLX0r1/mZG+/9xoFOQy/a/W7t+tO0vT1v+Oib9Kpf7W/x7kY7GzwLQW1KUF6frPRqOgI0Le2Y1rvidAj2v6kn/Xrle0Y8fL7ZgFTXjppT9o377duW5btJ0NDx9UuVxa9XZRFGtk5JCiqANDoaG8Owtd089QDxzYoySJtXHjhnbM0xGLi6mcc1q3rrUn6D7t27dbb775Rq7bFm1nx44dUZKs/lifJLGOHz+iW7fuKMuyDkzWHnfvVrVpU9n3GC3Ju7PQRc65p/7hjz+ef/ofFtj09Lyq1UyDgxXfo5hyzuny5TvauXOL4jisp23srHhC3Zkkvf76cN1l8ZACAEYIKgAYIagAYKTha6gAgPx4hgoARggqABghqABghKACgBGCCgBGCCoAGPk32yGO2j/wi+gAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 432x432 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "# Test Config hardest\n",
        "parking = Parking(6,6)\n",
        "hardest = RushHour(parking)\n",
        "\n",
        "hardest.add_car(Car(3,2,HORIZONTAL, 2, is_red=True))\n",
        "hardest.add_car(Car(1,0,HORIZONTAL,2))\n",
        "hardest.add_car(Car(0,3,HORIZONTAL,3))\n",
        "hardest.add_car(Car(0,5,HORIZONTAL,2))\n",
        "hardest.add_car(Car(3,5,HORIZONTAL,2))\n",
        "hardest.add_car(Car(4,4,HORIZONTAL,2))\n",
        "hardest.add_car(Car(0,0,VERTICAL,3))\n",
        "hardest.add_car(Car(1,1,VERTICAL,2))\n",
        "hardest.add_car(Car(2,1,VERTICAL,2))\n",
        "hardest.add_car(Car(4,0,VERTICAL,2))\n",
        "hardest.add_car(Car(3,3,VERTICAL,2))\n",
        "hardest.add_car(Car(2,4,VERTICAL,2))\n",
        "hardest.add_car(Car(5,1,VERTICAL,3))\n",
        "\n",
        "img = Drawing.show_parking(hardest)\n",
        "imshow(img)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "c-91yPLIYNIa",
        "outputId": "05b52484-a781-412f-b528-3f27b3815e3f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "number of moves for solving the puzzle with Solver_BFS :  51\n"
          ]
        }
      ],
      "source": [
        "moves_BFS = Solver_BFS.solve(hardest)\n",
        "\n",
        "print(\"number of moves for solving the puzzle with Solver_BFS : \", len(moves_BFS))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3.8.3 ('base')",
      "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.8.3"
    },
    "vscode": {
      "interpreter": {
        "hash": "e987e41af8e2d571e9d5552d0785b64b3544a288c0bac11510e379ae00bbea3c"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}