futoshiki.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "futoshiki.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyMnjt0L73AHSfUeA3v7T1Fp",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/matteonerini/sudoku-generator-and-solver/blob/main/futoshiki.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I1lddvp_zKkP"
      },
      "source": [
        "# Futoshiki Generator and Solver\r\n",
        "\r\n",
        "Futoshiki is a logic-based puzzle in which the objective is to fill a $d$x$d$ grid with numerical digits from 1 to $d$, according to the following rules:\r\n",
        "- Each row and each column must contain all the digits from 1 to $d$.\r\n",
        "- The numbers must satisfy the inequality signs present on the board.\r\n",
        "\r\n",
        "In this notebook, we propose simple yet interesting recursive algorithms to find all the solutions of a given Futoshiki, and to generate new puzzles such that they have a unique solution."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "awyqrEOpzF1_"
      },
      "source": [
        "# Import relevant libraries\r\n",
        "import numpy as np\r\n",
        "from random import randint, shuffle\r\n",
        "import matplotlib.pyplot as plt\r\n",
        "\r\n",
        "# Utility variables\r\n",
        "d = 4\r\n",
        "numbers = list(range(1,d+1))\r\n",
        "cells = list(range((d*2-1)**2))\r\n",
        "\r\n",
        "# Check if the cell 'board[y,x]' can assume the value 'n'\r\n",
        "def possible(board,y,x,n):\r\n",
        "    # Check if 'n' is already in row 'y' or in column 'x'\r\n",
        "    for i in range(d):\r\n",
        "        if board[y][i*2] == str(n) or board[i*2][x] == str(n):\r\n",
        "            return False\r\n",
        "    # Check the north inequality if present\r\n",
        "    try:\r\n",
        "        if board[y-1][x] == '<' and board[y-2][x] != ' ' and int(board[y-2][x]) > n:\r\n",
        "            return False\r\n",
        "        if board[y-1][x] == '>' and board[y-2][x] != ' ' and int(board[y-2][x]) < n:\r\n",
        "            return False\r\n",
        "    except IndexError:\r\n",
        "        pass\r\n",
        "    # Check the south inequality if present\r\n",
        "    try:\r\n",
        "        if board[y+1][x] == '<' and board[y+2][x] != ' ' and int(board[y+2][x]) < n:\r\n",
        "            return False\r\n",
        "        if board[y+1][x] == '>' and board[y+2][x] != ' ' and int(board[y+2][x]) > n:\r\n",
        "            return False\r\n",
        "    except IndexError:\r\n",
        "        pass\r\n",
        "    # Check the west inequality if present\r\n",
        "    try:\r\n",
        "        if board[y][x-1] == '<' and board[y][x-2] != ' ' and int(board[y][x-2]) > n:\r\n",
        "            return False\r\n",
        "        if board[y][x-1] == '>' and board[y][x-2] != ' ' and int(board[y][x-2]) < n:\r\n",
        "            return False\r\n",
        "    except IndexError:\r\n",
        "        pass\r\n",
        "    # Check the east inequality if present\r\n",
        "    try:\r\n",
        "        if board[y][x+1] == '<' and board[y][x+2] != ' ' and int(board[y][x+2]) < n:\r\n",
        "            return False\r\n",
        "        if board[y][x+1] == '>' and board[y][x+2] != ' ' and int(board[y][x+2]) > n:\r\n",
        "            return False\r\n",
        "    except IndexError:\r\n",
        "        pass\r\n",
        "    return True\r\n",
        "\r\n",
        "# Backtracking algorithm implementation to solve a Futoshiki\r\n",
        "def solve(board):\r\n",
        "    global board_solved\r\n",
        "    global n_solutions\r\n",
        "    for y in range(d):\r\n",
        "        for x in range(d):\r\n",
        "            if board[y*2][x*2] == ' ':\r\n",
        "                for n in range(1,d+1):\r\n",
        "                    if possible(board,y*2,x*2,n):\r\n",
        "                        board[y*2][x*2] = n\r\n",
        "                        solve(board)\r\n",
        "                        board[y*2][x*2] = ' '\r\n",
        "                return\r\n",
        "    print(board)\r\n",
        "    #input(\"More solutions?\")\r\n",
        "    #board_solved = np.copy(board)\r\n",
        "    n_solutions+=1\r\n",
        "\r\n",
        "# Faster implementation of the backtraking algorithm whose objective is to\r\n",
        "# determine if the Futoshiki does not have a unique solution\r\n",
        "def solve_fast(board):\r\n",
        "    global board_solved\r\n",
        "    global n_solutions\r\n",
        "    global end_solver\r\n",
        "    for y in range(d):\r\n",
        "        for x in range(d):\r\n",
        "            if board[y*2][x*2] == ' ':\r\n",
        "                for n in range(1,d+1):\r\n",
        "                    if possible(board,y*2,x*2,n):\r\n",
        "                        board[y*2][x*2] = n\r\n",
        "                        solve_fast(board)\r\n",
        "                        if not(end_solver):\r\n",
        "                            board[y*2][x*2] = ' '\r\n",
        "                return\r\n",
        "    #print(board)\r\n",
        "    n_solutions+=1\r\n",
        "    if n_solutions == 2:\r\n",
        "        end_solver = True\r\n",
        "\r\n",
        "# Randomly fill an empty board with dimension d\r\n",
        "def fill(board):\r\n",
        "    global board_filled\r\n",
        "    d = (len(board)+1)//2\r\n",
        "    for y in range(d):\r\n",
        "        for x in range(d):\r\n",
        "            if board[y*2][x*2] == ' ':\r\n",
        "                shuffle(numbers)\r\n",
        "                for n in numbers:\r\n",
        "                    if possible(board,y*2,x*2,n):\r\n",
        "                        board[y*2][x*2] = n\r\n",
        "                        if ' ' in board[::2, ::2]:\r\n",
        "                            fill(board)\r\n",
        "                            board[y*2][x*2] = ' '\r\n",
        "                        else:\r\n",
        "                            board_filled = np.copy(board)\r\n",
        "                return\r\n",
        "\r\n",
        "# Create a Futoshiki from a fully filled board\r\n",
        "def create(board):\r\n",
        "    global n_solutions\r\n",
        "    global end_solver\r\n",
        "    shuffle(cells)\r\n",
        "    for i in range((d*2-1)**2):\r\n",
        "        y = cells[i] // (d*2-1)\r\n",
        "        x = cells[i] % (d*2-1)\r\n",
        "        backup = board[y][x]\r\n",
        "        board[y][x] = ' '\r\n",
        "        board_copy = np.copy(board)\r\n",
        "        n_solutions = 0\r\n",
        "        end_solver = False\r\n",
        "        solve_fast(board_copy)\r\n",
        "        if n_solutions != 1:\r\n",
        "            board[y][x] = backup\r\n",
        "        #print('\\b\\b\\b\\b{:03d}'.format(i+1) )\r\n",
        "\r\n",
        "# Plot the board to create an enjoyable Futoshiki\r\n",
        "def board2pdf(board):\r\n",
        "    # Create a figure\r\n",
        "    fig, ax = plt.subplots()\r\n",
        "    im = ax.imshow(np.zeros((d*2-1,d*2-1), dtype=int),cmap='binary', vmin=255, vmax=255)\r\n",
        "    # Add the clues to the figure modifying the vertical inequalities\r\n",
        "    for i in range(d*2-1):\r\n",
        "        for j in range(d*2-1):\r\n",
        "            if i % 2 == 1:\r\n",
        "                if board[i,j] == '>':\r\n",
        "                    board[i,j] = u\"\\u2228\"\r\n",
        "                if board[i,j] == '<':\r\n",
        "                    board[i,j] = u\"\\u2227\"\r\n",
        "    for i in range(d*2-1):\r\n",
        "        for j in range(d*2-1):\r\n",
        "            text = ax.text(j, i, board[i,j],\r\n",
        "                           ha='center', va='center', color='k')\r\n",
        "    # Add the lines\r\n",
        "    for i in range(d*2):\r\n",
        "        for j in range(d):\r\n",
        "            plt.axhline(y=i-0.5, xmin=(j*2)/(d*2-1), xmax=(j*2+1)/(d*2-1), linewidth=3, color='k')\r\n",
        "            plt.axvline(x=i-0.5, ymin=(j*2)/(d*2-1), ymax=(j*2+1)/(d*2-1), linewidth=3, color='k')\r\n",
        "    # Plot the figure without axis\r\n",
        "    plt.axis('off')\r\n",
        "    plt.savefig('futoshiki.pdf', bbox_inches='tight')\r\n",
        "    plt.savefig('futoshiki.png', bbox_inches='tight')"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LLVB_OygbYQR"
      },
      "source": [
        "## Futoshiki Resolution\r\n",
        "\r\n",
        "The function `solve`, implementing the backtraking algorithm, is called to solve a given Futoshiki, specified by the variable `board`. Thus, all the possible solutions, i.e. the complete grids, are showed."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ejWU-kmlzWCU",
        "outputId": "a474e1b5-bee0-46d7-9d15-9577279d0622"
      },
      "source": [
        "# Input board\r\n",
        "d = 4\r\n",
        "board = np.array([['1', ' ', ' ', ' ', ' ', ' ', ' '],\r\n",
        "                  [' ', ' ', '<', ' ', ' ', ' ', '<'],\r\n",
        "                  [' ', ' ', ' ', ' ', ' ', ' ', ' '],\r\n",
        "                  [' ', ' ', ' ', ' ', ' ', ' ', ' '],\r\n",
        "                  [' ', ' ', ' ', ' ', ' ', ' ', ' '],\r\n",
        "                  [' ', ' ', ' ', ' ', ' ', ' ', '<'],\r\n",
        "                  [' ', ' ', ' ', ' ', ' ', '>', ' ']])\r\n",
        "\r\n",
        "# Utility variables\r\n",
        "numbers = list(range(1,d+1))\r\n",
        "cells = list(range((d*2-1)**2))\r\n",
        "\r\n",
        "n_solutions = 0\r\n",
        "print('Solution(s):\\n')\r\n",
        "solve(board)\r\n",
        "#print(board_solved)\r\n",
        "print('\\nNumber of solutions:', n_solutions)"
      ],
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Solution(s):\n",
            "\n",
            "[['1' ' ' '2' ' ' '4' ' ' '3']\n",
            " [' ' ' ' '<' ' ' ' ' ' ' '<']\n",
            " ['2' ' ' '3' ' ' '1' ' ' '4']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['3' ' ' '4' ' ' '2' ' ' '1']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' '<']\n",
            " ['4' ' ' '1' ' ' '3' '>' '2']]\n",
            "\n",
            "Number of solutions: 1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "N9S0xJVgbeeV"
      },
      "source": [
        "## Futoshiki Generation\r\n",
        "\r\n",
        "The generation of a Futoshiki with unique solution takes place according to the following steps:\r\n",
        "1. Generate a completely filled board which satisfies the Futoshiki rules with the function `fill`. This will be the unique solution of our Futoshiki.\r\n",
        "2. Iteratively, remove one random element from the board.\r\n",
        "3. Find the number of solutions of the new obtained board with the function `solve_fast`, a simplified Futoshiki solver.\r\n",
        "4. If the board has no longer a unique solution, reinsert the removed element.\r\n",
        "5. Return to Step 2 until a certain number of iteraction is reached. The higher this number, the more difficult is the generated Futoshiki since more cells are removed."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "XKBX8P7T8VU7",
        "outputId": "5697627d-192f-40c7-d576-efd94bd221b6"
      },
      "source": [
        "# Insert the dimension 'd'. Possible values: 4, 5, 6, 7\r\n",
        "d = 6\r\n",
        "\r\n",
        "# Utility variables\r\n",
        "numbers = list(range(1,d+1))\r\n",
        "cells = list(range((d*2-1)**2))\r\n",
        "board_empty = np.full((d*2-1, d*2-1), ' ')\r\n",
        "\r\n",
        "# Fill randomly the empty board and complete it with the inequalities clues\r\n",
        "fill(board_empty)\r\n",
        "print('Filled board randomly generated:')\r\n",
        "print(board_filled, '\\n')\r\n",
        "for i in range(d):\r\n",
        "    for j in range(d):\r\n",
        "        try:\r\n",
        "            board_filled[j*2+1,i*2] = '<' if board_filled[j*2,i*2] < board_filled[j*2+2,i*2] else '>'\r\n",
        "        except IndexError:\r\n",
        "            pass\r\n",
        "        try:\r\n",
        "            board_filled[j*2,i*2+1] = '<' if board_filled[j*2,i*2] < board_filled[j*2,i*2+2] else '>'\r\n",
        "        except IndexError:\r\n",
        "            pass\r\n",
        "print('Complete board:')\r\n",
        "print(board_filled, '\\n')\r\n",
        "\r\n",
        "# Create a Futoshiki\r\n",
        "print('Generated Futoshiki:')\r\n",
        "#print('Progress (/', (d*2-1)**2, '):   ')\r\n",
        "create(board_filled)\r\n",
        "print(board_filled)\r\n",
        "print('Number of clues:', np.count_nonzero(board_filled), '\\n')\r\n",
        "\r\n",
        "# Solve the created Futoshiki\r\n",
        "n_solutions = 0\r\n",
        "print('Solution:')\r\n",
        "solve(board_filled)\r\n",
        "#print(board_solved)\r\n",
        "print('Number of solutions:', n_solutions, '\\n')\r\n",
        "\r\n",
        "# Print the created Futoshiki\r\n",
        "print('Printed generated Futoshiki:')\r\n",
        "board2pdf(board_filled)"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Filled board randomly generated:\n",
            "[['2' ' ' '6' ' ' '1' ' ' '3' ' ' '5' ' ' '4']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['1' ' ' '4' ' ' '3' ' ' '2' ' ' '6' ' ' '5']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['6' ' ' '2' ' ' '4' ' ' '5' ' ' '1' ' ' '3']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['4' ' ' '5' ' ' '6' ' ' '1' ' ' '3' ' ' '2']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['3' ' ' '1' ' ' '5' ' ' '4' ' ' '2' ' ' '6']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['5' ' ' '3' ' ' '2' ' ' '6' ' ' '4' ' ' '1']] \n",
            "\n",
            "Complete board:\n",
            "[['2' '<' '6' '>' '1' '<' '3' '<' '5' '>' '4']\n",
            " ['>' ' ' '>' ' ' '<' ' ' '>' ' ' '<' ' ' '<']\n",
            " ['1' '<' '4' '>' '3' '>' '2' '<' '6' '>' '5']\n",
            " ['<' ' ' '>' ' ' '<' ' ' '<' ' ' '>' ' ' '>']\n",
            " ['6' '>' '2' '<' '4' '<' '5' '>' '1' '<' '3']\n",
            " ['>' ' ' '<' ' ' '<' ' ' '>' ' ' '<' ' ' '>']\n",
            " ['4' '<' '5' '<' '6' '>' '1' '<' '3' '>' '2']\n",
            " ['>' ' ' '>' ' ' '>' ' ' '<' ' ' '>' ' ' '<']\n",
            " ['3' '>' '1' '<' '5' '>' '4' '>' '2' '<' '6']\n",
            " ['<' ' ' '<' ' ' '>' ' ' '<' ' ' '<' ' ' '>']\n",
            " ['5' '>' '3' '>' '2' '<' '6' '>' '4' '>' '1']] \n",
            "\n",
            "Generated Futoshiki:\n",
            "[['2' ' ' ' ' ' ' ' ' ' ' ' ' '<' ' ' '>' ' ']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '<' ' ' ' ']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " [' ' ' ' ' ' ' ' '<' ' ' ' ' ' ' ' ' ' ' '>']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " [' ' ' ' ' ' ' ' '<' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' '1' ' ' ' ' '>' ' ']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " [' ' ' ' '1' ' ' ' ' '>' ' ' ' ' ' ' ' ' ' ']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['5' ' ' ' ' ' ' '2' ' ' ' ' ' ' ' ' ' ' '1']]\n",
            "Number of clues: 14 \n",
            "\n",
            "Solution:\n",
            "[['2' ' ' '6' ' ' '1' ' ' '3' '<' '5' '>' '4']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '<' ' ' ' ']\n",
            " ['1' ' ' '4' ' ' '3' ' ' '2' ' ' '6' ' ' '5']\n",
            " [' ' ' ' ' ' ' ' '<' ' ' ' ' ' ' ' ' ' ' '>']\n",
            " ['6' ' ' '2' ' ' '4' ' ' '5' ' ' '1' ' ' '3']\n",
            " [' ' ' ' ' ' ' ' '<' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['4' ' ' '5' ' ' '6' ' ' '1' ' ' '3' '>' '2']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['3' ' ' '1' ' ' '5' '>' '4' ' ' '2' ' ' '6']\n",
            " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
            " ['5' ' ' '3' ' ' '2' ' ' '6' ' ' '4' ' ' '1']]\n",
            "Number of solutions: 1 \n",
            "\n",
            "Printed generated Futoshiki:\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOcAAADnCAYAAADl9EEgAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAMC0lEQVR4nO3d0Utbdx/H8U8epQycXrghE7tSBqMztWqiTsqKUEZLcY1iZbCQUoqyf6C72K53Ie5iYMGbjdWVDqQXo7YJjmwDm2WOMRkrjEFpBm1HqWFloKLepMJ5Lop9Hp7HZJk5p79v4vsFglD5+mnk4+94zsnvhDzPEwB7/uU6AICdUU7AKMoJGEU5AaMoJ2BUfal/DIVCgZzK9eMMcSgU8iHJzirNZzmbZDuf5WxSMPk8z9txKCsnYFTJlXOb1d842yzns5xNsp3PcjYp+HysnIBRlBMwinICRlVUzgcPHuj48eMKh8M6fPiwLl686FcuYM8LlfqjdvtSSrGvyefzyufzikajWl9fV09Pj65fv65wOLzTrKef+/2HtLV5lrNZn2c5W1DzArmU0traqmg0KklqbGxUe3u7Hj58WMlI7AGFQkGbm5uuY0iSVlZWXEcoyre/Oe/fv69bt26pv7/fr5GoMbdv39Z7772nQ4cOKZfLuY4jSert7VUikdDCwoIvK6GffCnnxsaGRkdHNTU1paamJj9GokZsbm7q888/17Fjx/Tuu+8qHA7r119/VSQScR1NkpTL5RSPxzU9Pa1wOKyJiQktLy+7jvWE53lFPyR5T76kuEKh4J08edL7+OOPS37d9qy/m1cuy/MsZ3vW8xobG7033njDu337trls/+vRo0fe+Pi4V1dX5/3000/PLJ9XpH8VrZye52l8fFzt7e26cOFCJaNQo7788ku1tbXpzJkz+vDDD/XHH3+4jvR/1tbW9Mknn2hoaEi///67ZmZm1NnZ6TpWZSvn999/70nyjhw54nV1dXldXV3e/Pz8M/uNY3We5Wyu5v3111/e1NSU19XV5b355pvevXv3TGRLJBLeK6+84r3//vteLpereN5u8nlF+lfRpZR/ohpOafs1z3I2C/OWlpbU2tqql19+2Xm2ZDKpwcFB1deXdZv5M72UQjkDmGc5m/V5lrMFNa9YObl9DzCKcgJGUU7AqLL+Cg7yDat+sJzPcjbJdj7L2aTg87FyAkZRTsCokpdS9ORiK4BgcSkFqCaUEzCKcgJGUU7AKMoJGEU5UZVWV1fV19enubk511ECQzlRldLptPL5vGZnZ11HCQzlRFVKJpOanJxUNptVoVBwHScQlBNVZ2trS5lMRiMjI+rv71cmk3EdKRCUE1VncXFRkUhEDQ0NGh4eViqVch0pEJQTVSeVSmloaEiSFIvFND8/7zhRMLi3FnCPe2uBakI5AaMoJ2AU5QSMKrmHUFB7pPi9f6jf/Nx71W+8drtn9bUrlouVEzCKcgJGlbU1ptXDgW2W81nOJtnOZzmbFHw+Vk7AKMoJGEU5AaMoJ2AU5QSMopyAUZQTMIpyAkZRTsAoygkYRTkBoygnYBTlBIyinIBRlBMwinICRpX1Zusg37DqB8v5LGeTbOeznE0KPh8rJ2AU5QSM4lkpgHs8KwWoJpQTMIpyAkZRTsAoyunQ6uqq+vr6NDc35zoKfPLRRx89fdL2xsaGBgcHdz2LcjqUTqeVz+c1OzvrOgp8cujQoac/z6+//lovvPDCrmdRToeSyaQmJyeVzWZVKBRcx4EPTpw4oZs3b2pra0s3btxQLBbb9SzK6cjW1pYymYxGRkbU39+vTCbjOhJ80NDQoEgkops3b+rbb7/VqVOndj2LcjqyuLioSCSihoYGDQ8PK5VKuY4En8RiMX3wwQfq6OhQU1PTrudQTkdSqZSGhoYkPflhbp9EQPWLxWL65ZdfKjqklbh9D7CA2/eAakI5AaMoJ2AU5QSMKrlNSVDbMPzNSaiyBLlFRKX5LGeTbOeznE0KJl+xXKycgFGUEzCqrN33rB4ObLOcz3I2yXY+y9mk4POxcgJGUU7AKMoJGEU5AaMoJ2AU5QSMopyAUZQTMIpyAkZRTsAoygkYRTkBoygnYBTlBIyinIBRlBMwqqw3Wwf5hlU/WM5nOZtkO5/lbFLw+Vg5AaMoJ2AUz0oB3ONZKUA1oZyAUZQTMIpyAkZRTsAoyunQ6uqq+vr6NDc35zoKDKKcDqXTaeXzec3OzrqOAoMop0PJZFKTk5PKZrMqFAqu48AYyunI1taWMpmMRkZG1N/fr0wm4zoSjKGcjiwuLioSiaihoUHDw8NKpVKuI8EYyulIKpXS0NCQJCkWi2l+ft5xIljDvbWAe9xbC1QTygkYRTkBoygnYFTJPYSC2iPlb05ClSXI/VsqzWc5m2Q7n+VsUjD5iuVi5QSMopyAUWVtjWn1cGCb5XyWs0m281nOJgWfj5UTMIpyAkZRTsAoyokdjY2NqaWlRR0dHa6j7FmUEzs6f/680um06xiBW1lZcR2hKMqJHQ0MDKi5udl1jMD19vYqkUhoYWHBl7OvfqKc2NNyuZzi8bimp6cVDoc1MTGh5eVl17EkUU7scXV1dTp9+rSuXbumbDaru3fv6sCBA1paWnIdrbybEIBatra2pqtXr+ry5cvat2+fZmZm1NnZ6ToW5cTedvbsWf344496++23deXKFb366quuI/2H53lFP/RkmxLPD9uz9sI8y9nKnffOO+94L730kldfX++1tbV5n3322TPJ96z/rzdu3PAeP37sNJ9XpH8l9xAKhULedoEr9d/3ENb6PMvZrM+znC2oeZ7nsYcQUE0oJ2AU5QSMopyAUWVdSgnyDat+sJzPcjbJdj7L2aTg87FyAkZRTsAonpUCuMd1TqCaUE7AKMoJGEU5AaMoJ2AU5QSMopyAUZQTMIpyAkZRTsAoygkYRTkBoygnYBTlBIyinIBRJbcpCWobBr/3D/Wbn3uv+o3XbvesvnbFcrFyAkZRTsCosnbfs3o4sM1yPsvZJNv5LGeTgs/HygkYRTkBoygnYFRNl3NsbEwtLS3q6OhwHQX4x2q6nOfPn1c6nXYdA9iVmi7nwMCAmpubXccI3MrKiusICEBNl3Ov6O3tVSKR0MLCgi+n92ED5awBuVxO8Xhc09PTCofDmpiY0PLysutYqBDlrAF1dXU6ffq0rl27pmw2q7t37+rAgQNaWlpyHQ0VKOsOIdi3tramq1ev6vLly9q3b59mZmbU2dnpOhYqUNMrZzwe19GjR3Xnzh3t379fly5dch0pEGfPnlU0GtW9e/d05coVfffddzp37pyee+4519FQgZKPAAyFQp7k/z2EtT7vWWdLJpMaHBxUfX15B0K8drbmeZ634w22lDOAeZazWZ9nOVtQ84qVs6YPa4FqRjkBoygnYFRZZxCCfMOqHyzns5xNsp3PcjYp+HysnIBRlBMwquSlFEncRQ0Ej0spQDWhnIBRlBMwinICRlFOwCjKCRhFOQGjKCdgFOUEjKKcgFGUEzCKcgJGUU7AKMoJGEU5AaMoJ2BUyT2Egtojxe/9Q/3m596rfuO12z2rr12xXKycgFGUEzCqrK0xrR4ObLOcz3I2yXY+y9mk4POxcgJGUU7AKMoJGFVxOQ8ePKgjR46ou7tbvb29fmTaEx48eKDjx48rHA7r8OHDunjxoutI8MnY2JhaWlrU0dFR0ZyKn8958OBB/fzzz3rxxRdLf6MqeE6iX/PKmZXP55XP5xWNRrW+vq6enh5dv35d4XA40GzW51nOVu68bDar559/XufOndNvv/32t/N4Pqcxra2tikajkqTGxka1t7fr4cOHjlPBDwMDA2pubq54TsXlDIVCOnnypHp6evTpp59WHGgvun//vm7duqX+/n7XUWBIWdc5S1lcXFRbW5sePXqkEydO6LXXXtPAwIAf2faEjY0NjY6OampqSk1NTa7jwJCKV862tjZJUktLi0ZGRrS0tFRxqL3i8ePHGh0dVSKR0JkzZ1zHgTEVlXNzc1Pr6+tPP//mm28qPkO1V3iep/HxcbW3t+vChQuu48Cgisr5559/6tixY+rq6tLrr7+ut956S6dOnfIrW0374Ycf9MUXX2hhYUHd3d3q7u7WV1995ToWfBCPx3X06FHduXNH+/fv16VLl3Y1p+JLKWV/oxo4Re5i1l6bZzlbUPO4lAJUGcoJGEU5AaMoJ2BUWTchBPmGVT9Yzmc5m2Q7n+VsUvD5Sp6tBeAOh7WAUZQTMIpyAkZRTsAoygkYRTkBo/4Ne6V0YhN+lhEAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_nRlob8cZWk3"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}