Backtracking_Feasible_&_Infeasible_case_analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/kaledai069/Crossword-Generator/blob/master/Backtracking_Feasible_%26_Infeasible_case_analysis.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "xbO8Vjqkb5Ty",
    "outputId": "0a2caf6e-a3e1-4560-9557-ea96a2737168"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mounted at /content/gdrive\n"
     ]
    }
   ],
   "source": [
    "from google.colab import drive\n",
    "drive.mount(\"/content/gdrive\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Rq0s9NZDlFIn"
   },
   "source": [
    "### Important Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "gRZlnGWpkjV4"
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "import random\n",
    "import heapq\n",
    "import time\n",
    "import pandas as pd\n",
    "import requests\n",
    "import json\n",
    "import os\n",
    "import re\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from pprint import pprint\n",
    "from PIL import Image\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "from pprint import pprint\n",
    "from tqdm import tqdm\n",
    "from PIL import Image, ImageDraw, ImageFont\n",
    "from IPython.display import display"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CA_DATASET = \"/content/gdrive/MyDrive/Clue-Answer Dataset/Clue-Answer-Dataset_Version_2.csv\"\n",
    "\n",
    "clue_answer_df = pd.read_csv(CA_DATASET)\n",
    "clue_answer_df['Unsegmented'] = clue_answer_df['Segmented Answer'].apply(lambda x: str(x).replace(' ', ''))\n",
    "clue_answer_df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "MvPfgTI9mrL-"
   },
   "source": [
    "### Crossword Variable & Back-tracking with Arc-Consistency"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "z-bOxR5WlEap"
   },
   "outputs": [],
   "source": [
    "class Variable():\n",
    "\n",
    "    ACROSS = \"across\"\n",
    "    DOWN = \"down\"\n",
    "\n",
    "    def __init__(self, i, j, direction, length):\n",
    "        \"\"\"Create a new variable with starting point, direction, and length.\"\"\"\n",
    "        self.i = i\n",
    "        self.j = j\n",
    "        self.direction = direction\n",
    "        self.length = length\n",
    "        self.cells = []\n",
    "        for k in range(self.length):\n",
    "            self.cells.append(\n",
    "                (self.i + (k if self.direction == Variable.DOWN else 0),\n",
    "                 self.j + (k if self.direction == Variable.ACROSS else 0))\n",
    "            )\n",
    "\n",
    "    def __hash__(self):\n",
    "        return hash((self.i, self.j, self.direction, self.length))\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return (\n",
    "            (self.i == other.i) and\n",
    "            (self.j == other.j) and\n",
    "            (self.direction == other.direction) and\n",
    "            (self.length == other.length)\n",
    "        )\n",
    "\n",
    "    def __str__(self):\n",
    "        return f\"({self.i}, {self.j}) {self.direction} : {self.length}\"\n",
    "\n",
    "    def __repr__(self):\n",
    "        direction = repr(self.direction)\n",
    "        return f\"Variable({self.i}, {self.j}, {direction}, {self.length})\"\n",
    "\n",
    "class Crossword():\n",
    "    def __init__(self, grid, words_file, file_path = True):\n",
    "        self.structure = []\n",
    "\n",
    "        self.height = len(grid) # the number of rows in the grid\n",
    "        self.width = len(grid[0]) # the number of columns in the grid\n",
    "        for i in range(len(grid)):\n",
    "            row = []\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == '':\n",
    "                  row.append(False)\n",
    "                else:\n",
    "                  row.append(True)\n",
    "            self.structure.append(row)\n",
    "\n",
    "        if not file_path:\n",
    "            self.words = [word.upper() for word in words_file]\n",
    "\n",
    "        else:\n",
    "            # Save vocabulary list\n",
    "            with open(words_file) as f:\n",
    "                self.words = set(f.read().upper().splitlines()) # to remove all the duplicates\n",
    "                self.words = list(self.words)\n",
    "                for _ in range(5):\n",
    "                    random.shuffle(self.words)\n",
    "            self.words = set(self.words)\n",
    "\n",
    "        # Determine variable set\n",
    "        self.variables = set()\n",
    "\n",
    "        for i in range(self.height):\n",
    "            for j in range(self.width):\n",
    "\n",
    "                # Vertical words\n",
    "                starts_word = (\n",
    "                    self.structure[i][j]\n",
    "                    and (i == 0 or not self.structure[i - 1][j])\n",
    "                )\n",
    "                if starts_word:\n",
    "                    length = 1\n",
    "                    for k in range(i + 1, self.height):\n",
    "                        if self.structure[k][j]:\n",
    "                            length += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    if length > 1:\n",
    "                        self.variables.add(Variable(\n",
    "                            i=i, j=j,\n",
    "                            direction=Variable.DOWN,\n",
    "                            length=length\n",
    "                        ))\n",
    "\n",
    "                # Horizontal words\n",
    "                starts_word = (\n",
    "                    self.structure[i][j]\n",
    "                    and (j == 0 or not self.structure[i][j - 1])\n",
    "                )\n",
    "                if starts_word:\n",
    "                    length = 1\n",
    "                    for k in range(j + 1, self.width):\n",
    "                        if self.structure[i][k]:\n",
    "                            length += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    if length > 1:\n",
    "                        self.variables.add(Variable(\n",
    "                            i=i, j=j,\n",
    "                            direction=Variable.ACROSS,\n",
    "                            length=length\n",
    "                        ))\n",
    "\n",
    "        # Compute overlaps for each word\n",
    "        # For any pair of variables v1, v2, their overlap is either:\n",
    "        #    None, if the two variables do not overlap; or\n",
    "        #    (i, j), where v1's ith character overlaps v2's jth character\n",
    "        self.overlaps = dict()\n",
    "        self.overlaps_positions = dict()\n",
    "        for v1 in self.variables:\n",
    "            for v2 in self.variables:\n",
    "                if v1 == v2:\n",
    "                    continue\n",
    "                cells1 = v1.cells\n",
    "                cells2 = v2.cells\n",
    "                intersection = set(cells1).intersection(cells2)\n",
    "                if not intersection:\n",
    "                    self.overlaps[v1, v2] = None\n",
    "                else:\n",
    "                    intersection = intersection.pop()\n",
    "                    self.overlaps[v1, v2] = (\n",
    "                        cells1.index(intersection),\n",
    "                        cells2.index(intersection)\n",
    "                    )\n",
    "                    for cell in cells1:\n",
    "                        for cell_ in cells2:\n",
    "                            if cell == cell_:\n",
    "                                self.overlaps_positions[v1, v2] = cell\n",
    "                                break\n",
    "\n",
    "    def neighbors(self, var):\n",
    "        \"\"\"Given a variable, return set of overlapping variables.\"\"\"\n",
    "        return set(\n",
    "            v for v in self.variables\n",
    "            if v != var and self.overlaps[v, var]\n",
    "        )\n",
    "\n",
    "class CrosswordCreator():\n",
    "\n",
    "    def __init__(self, crossword, do_random = False):\n",
    "        \"\"\"\n",
    "        Create new CSP crossword generate.\n",
    "        \"\"\"\n",
    "        self.crossword = crossword\n",
    "        self.ASSIGNMENT_COUNT = 0\n",
    "        self.states = []\n",
    "        self.do_random = do_random\n",
    "        self.memoization_cache = dict()\n",
    "        self.t_revise_time = 0\n",
    "        self.t_revise_called = 0\n",
    "\n",
    "        # setting up the domains for each of the variables\n",
    "        self.domains = {\n",
    "            var: [self.get_required_length_answers(var.length)]\n",
    "            for var in self.crossword.variables\n",
    "        }\n",
    "\n",
    "    # enforcing the node consistency here\n",
    "    def get_required_length_answers(self, ans_length):\n",
    "        output = []\n",
    "        for word in self.crossword.words:\n",
    "            if len(word) == ans_length:\n",
    "                output.append(word.upper())\n",
    "        random.shuffle(output)\n",
    "        # output = output[:5000]\n",
    "        return set(output)  # lets get the domain answers in list format\n",
    "\n",
    "    def letter_grid(self, assignment):\n",
    "        \"\"\"\n",
    "        Return 2D array representing a given assignment.\n",
    "        \"\"\"\n",
    "        letters = [\n",
    "            [None for _ in range(self.crossword.width)]\n",
    "            for _ in range(self.crossword.height)\n",
    "        ]\n",
    "        for variable, word in assignment.items():\n",
    "            direction = variable.direction\n",
    "            for k in range(len(word)):\n",
    "                i = variable.i + (k if direction == Variable.DOWN else 0)\n",
    "                j = variable.j + (k if direction == Variable.ACROSS else 0)\n",
    "                letters[i][j] = word[k]\n",
    "        return letters\n",
    "\n",
    "    def print(self, assignment):\n",
    "        \"\"\"\n",
    "        Print crossword assignment to the terminal.\n",
    "        \"\"\"\n",
    "        letters = self.letter_grid(assignment)\n",
    "        for i in range(self.crossword.height):\n",
    "            for j in range(self.crossword.width):\n",
    "                if self.crossword.structure[i][j]:\n",
    "                    print(letters[i][j] or \" \", end=\"\")\n",
    "                else:\n",
    "                    print(\"██\", end=\"\")\n",
    "            print()\n",
    "\n",
    "    def display_only_grid(self, assignment, block_size = 25, f_size = 15, filename = None):\n",
    "        \"\"\"\n",
    "        Save crossword assignment to an image file.\n",
    "        \"\"\"\n",
    "\n",
    "        cell_size = block_size\n",
    "        cell_border = 2\n",
    "        interior_size = cell_size - 2 * cell_border\n",
    "        letters = self.letter_grid(assignment)\n",
    "\n",
    "        # Create a blank canvas\n",
    "        img = Image.new(\n",
    "            \"RGB\",\n",
    "            (self.crossword.width * cell_size,\n",
    "             self.crossword.height * cell_size),\n",
    "            \"black\"\n",
    "        )\n",
    "        font = ImageFont.truetype(\"./Roboto-Regular.ttf\", f_size)\n",
    "        draw = ImageDraw.Draw(img)\n",
    "\n",
    "        for i in range(self.crossword.height):\n",
    "            for j in range(self.crossword.width):\n",
    "\n",
    "                rect = [\n",
    "                    (j * cell_size + cell_border,\n",
    "                     i * cell_size + cell_border),\n",
    "                    ((j + 1) * cell_size - cell_border,\n",
    "                     (i + 1) * cell_size - cell_border)\n",
    "                ]\n",
    "                if self.crossword.structure[i][j]:\n",
    "                    draw.rectangle(rect, fill=\"white\")\n",
    "                    if letters[i][j]:\n",
    "                        _, _, w, h = draw.textbbox((0, 0), letters[i][j], font=font)\n",
    "                        draw.text(\n",
    "                            (rect[0][0] + ((interior_size - w) / 2),\n",
    "                             rect[0][1] + ((interior_size - h) / 2) - 5),\n",
    "                            letters[i][j], fill=\"black\", font=font\n",
    "                        )\n",
    "        if filename is not None:\n",
    "            img.save(filename)\n",
    "        return img\n",
    "\n",
    "    ### here starts the main solving category\n",
    "    def solve(self):\n",
    "        \"\"\"\n",
    "        Enforce node and arc consistency, and then solve the CSP.\n",
    "        \"\"\"\n",
    "        self.ac3()\n",
    "        return self.backtrack(dict())\n",
    "\n",
    "    def enforce_node_consistency(self):\n",
    "        \"\"\"\n",
    "        Update `self.domains` such that each variable is node-consistent.\n",
    "        (Remove any values that are inconsistent with a variable's unary\n",
    "         constraints; in this case, the length of the word.)\n",
    "        \"\"\"\n",
    "        for variable in self.crossword.variables:\n",
    "            valid_words = set()\n",
    "            for word in self.domains[variable][-1]:\n",
    "                if len(word) == variable.length:\n",
    "                    valid_words.add(word)\n",
    "            self.domains[variable][-1] = valid_words\n",
    "\n",
    "    def revise(self, x, y, forward_checking = False):\n",
    "        \"\"\"\n",
    "            Make variable `x` arc consistent with variable `y`.\n",
    "            To do so, remove values from `self.domains[x]` for which there is no\n",
    "            possible corresponding value for `y` in `self.domains[y]`.\n",
    "\n",
    "            Return True if a revision was made to the domain of `x`; return\n",
    "            False if no revision was made.\n",
    "        \"\"\"\n",
    "\n",
    "        start_t = time.time()\n",
    "        revised = False\n",
    "        overlap = self.crossword.overlaps[x, y]\n",
    "\n",
    "        if overlap:\n",
    "            y_chars = set(word[overlap[1]] for word in self.domains[y][-1])  # Use a set for faster membership tests\n",
    "            x_domain = self.domains[x][-1]\n",
    "\n",
    "            # Optimize: Use list comprehension for faster filtering\n",
    "            x_domain = {word for word in x_domain if word[overlap[0]] in y_chars}\n",
    "\n",
    "            if len(x_domain) < len(self.domains[x][-1]):\n",
    "                revised = True\n",
    "                if forward_checking:\n",
    "                    self.domains[x].append(x_domain)\n",
    "                else:\n",
    "                    self.domains[x][-1] = x_domain\n",
    "\n",
    "        end_t = time.time()\n",
    "        self.t_revise_time += end_t - start_t\n",
    "        self.t_revise_called += 1\n",
    "\n",
    "        return revised\n",
    "\n",
    "    def ac3(self, arcs=None, f_checking = False):\n",
    "        if arcs is None:\n",
    "            arcs = deque([(v1, v2) for v1 in self.crossword.variables for v2 in self.crossword.neighbors(v1)])\n",
    "        else:\n",
    "            arcs = deque(arcs)\n",
    "\n",
    "        revised_arcs = set()\n",
    "\n",
    "        while arcs:\n",
    "            x, y = arcs.popleft()  # Efficient pop from the left\n",
    "\n",
    "            # check if the arc has already been revised\n",
    "            if (x, y) in revised_arcs:\n",
    "                continue\n",
    "\n",
    "            if self.revise(x, y, forward_checking = f_checking):\n",
    "                if len(self.domains[x][-1]) == 0:\n",
    "                    return False\n",
    "                revised_arcs.add((x, y))\n",
    "                for z in self.crossword.neighbors(x) - {y}:\n",
    "                    arcs.append((z, x))\n",
    "                    revised_arcs.add((z, x))\n",
    "        return True\n",
    "\n",
    "    def assignment_complete(self, assignment):\n",
    "        self.ASSIGNMENT_COUNT += 1\n",
    "        self.states.append(assignment)\n",
    "        return len(assignment.keys()) == len(self.crossword.variables)\n",
    "\n",
    "    # phind AI\n",
    "    def consistent(self, assignment):\n",
    "        \"\"\"\n",
    "            Return True if `assignment` is consistent (i.e., words fit in crossword\n",
    "            puzzle without conflicting characters); return False otherwise.\n",
    "        \"\"\"\n",
    "        values = set()\n",
    "        for var, word in assignment.items():\n",
    "            if word in values or len(word) != var.length:\n",
    "                return False\n",
    "            values.add(word)\n",
    "            for neighbor in self.crossword.neighbors(var):\n",
    "                overlap = self.crossword.overlaps[var, neighbor]\n",
    "                if neighbor in assignment and assignment[var][overlap[0]] != assignment[neighbor][overlap[1]]:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def order_domain_values(self, var, assignment, temp_var_domain):\n",
    "        # start_t = time.time()\n",
    "        values_penalty = Counter()\n",
    "        for neighbor in self.crossword.neighbors(var):\n",
    "            if neighbor not in assignment:\n",
    "                overlap = self.crossword.overlaps[var, neighbor]\n",
    "                neighbor_list = [value[overlap[1]] for value in list(self.domains[neighbor][-1])]\n",
    "\n",
    "                for value in temp_var_domain:\n",
    "                    letter_to_be_searched = neighbor_list.count(value[overlap[0]])\n",
    "                    values_penalty[value] += len(neighbor_list) - letter_to_be_searched\n",
    "\n",
    "        priority_queue = [(-values_penalty[value], value) for value in temp_var_domain]\n",
    "        heapq.heapify(priority_queue)\n",
    "        # end_t = time.time()\n",
    "        # print(\"Ordering the domain values: \", end_t - start_t)\n",
    "        return [value for _, value in priority_queue]\n",
    "\n",
    "\n",
    "    def select_unassigned_variable(self, assignment):\n",
    "        \"\"\"\n",
    "            Ordering:\n",
    "              Return an unassigned variable not already part of `assignment`.\n",
    "              Choose the variable with the minimum number of remaining values - MRV\n",
    "              in its domain. If there is a tie, choose the variable with the highest\n",
    "              degree. If there is a tie, any of the tied variables are acceptable\n",
    "              return values.\n",
    "        \"\"\"\n",
    "        var_penalty = {}\n",
    "        for var in self.crossword.variables:\n",
    "            if var not in assignment:\n",
    "                var_penalty[var] = len(self.domains[var][-1])\n",
    "                # var_penalty[var] = var.length\n",
    "        vars = sorted(var_penalty, key= lambda v: var_penalty[v], reverse = True)\n",
    "        return vars[0]\n",
    "\n",
    "    def backtrack(self, assignment):\n",
    "        \"\"\"\n",
    "            Using Backtracking Search, take as input a partial assignment for the\n",
    "            crossword and return a complete assignment if possible to do so.\n",
    "\n",
    "            `assignment` is a mapping from variables (keys) to words (values).\n",
    "\n",
    "            If no assignment is possible, return None.\n",
    "        \"\"\"\n",
    "        if self.assignment_complete(assignment):\n",
    "            return assignment  # base case\n",
    "\n",
    "        # lets have some caching done here\n",
    "        assignment_key = frozenset(assignment.items())\n",
    "        if assignment_key in self.memoization_cache:\n",
    "            self.ASSIGNMENT_COUNT += 1\n",
    "            return self.memoization_cache[assignment_key]\n",
    "\n",
    "        var = self.select_unassigned_variable(assignment)\n",
    "\n",
    "        did_shorten_domain = False\n",
    "        # print(\"Before: \", len(self.domains[var][-1]))\n",
    "\n",
    "        temp_domain_var = self.domains[var][-1].copy()\n",
    "        if len(assignment.keys()) > 0:\n",
    "            for variable in self.crossword.variables:\n",
    "                if var != variable and variable in assignment.keys():\n",
    "                    overlap = self.crossword.overlaps[var, variable]\n",
    "                    if overlap:\n",
    "                        ref_cross_section_word = assignment[variable]\n",
    "                        ref_intersection_letter = ref_cross_section_word[overlap[1]]\n",
    "\n",
    "                        # Filter the words in the domain of var\n",
    "                        did_shorten_domain = True\n",
    "                        temp_domain_var = {word for word in temp_domain_var if word[overlap[0]] == ref_intersection_letter}\n",
    "\n",
    "        if did_shorten_domain:\n",
    "            self.domains[var].append(temp_domain_var)\n",
    "\n",
    "        revised_neighbor_list = []\n",
    "        # lets insert the ac3-arc consistency in the back-track recursive loop\n",
    "        arc_list = deque([(neighbor, var) for neighbor in self.crossword.neighbors(var)])\n",
    "        revised_arcs = set()\n",
    "\n",
    "        while arc_list:\n",
    "            x, y = arc_list.pop()\n",
    "\n",
    "            if (x, y) in revised_arcs:\n",
    "                continue\n",
    "\n",
    "            if self.revise(x, y, forward_checking = True):\n",
    "                revised_neighbor_list.append(x)\n",
    "\n",
    "            for z in self.crossword.neighbors(x) - {y}:\n",
    "                arc_list.append((z, x))\n",
    "                revised_arcs.add((z, x))\n",
    "\n",
    "        # print(\"After: \", len(self.domains[var][-1]))\n",
    "\n",
    "        # lets introduce the randomness in iterating the values of the assigned variabel\n",
    "        if self.do_random:\n",
    "            shuffled_curr_domain = list(self.domains[var][-1].copy())\n",
    "            random.shuffle(shuffled_curr_domain)\n",
    "\n",
    "        domain_values = shuffled_curr_domain if self.do_random else list(self.domains[var][-1])\n",
    "\n",
    "        # for value in self.order_domain_values(var, assignment, domain_values):\n",
    "        for value in domain_values:\n",
    "            new_assignment = assignment.copy()\n",
    "            new_assignment[var] = value\n",
    "            if self.consistent(new_assignment):\n",
    "                result = self.backtrack(new_assignment)\n",
    "\n",
    "                if result is not None:\n",
    "                    self.memoization_cache[assignment_key] = result\n",
    "                    return result\n",
    "\n",
    "        for n in revised_neighbor_list:\n",
    "            self.domains[n].pop()\n",
    "\n",
    "        if did_shorten_domain:\n",
    "            self.domains[var].pop()\n",
    "\n",
    "        self.memoization_cache[assignment_key] = None\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "p1P0dXDCcqWt"
   },
   "outputs": [],
   "source": [
    "word_list_small = './all_answers.txt'\n",
    "word_list_large = \"/content/gdrive/MyDrive/Crossword Generator/new_answer_list.txt\"\n",
    "word_list_gutenberg = \"/content/gutenberg_lexicon.txt\"\n",
    "\n",
    "# 4x4 grid\n",
    "grid_4 = [['', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', '']]\n",
    "\n",
    "# 5x5 grid\n",
    "grid_5 = [['A', 'A', 'A', 'A', ''],\n",
    "          ['A', 'A', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', 'A', 'A'],\n",
    "          ['', 'A', 'A', 'A', 'A'],]\n",
    "\n",
    "# 6x6 grid\n",
    "grid_6 = [['A', 'A', 'A', '', '', ''],\n",
    "          ['A', 'A', 'A', 'A', 'A', ''],\n",
    "          ['A', 'A', 'A', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', 'A', 'A', 'A'],\n",
    "          ['', 'A', 'A', 'A', 'A', 'A'],\n",
    "          ['', '', '', 'A', 'A', 'A']]\n",
    "\n",
    "grid_7 = [['', '', '', 'A', 'A', 'A', 'A'],\n",
    "          ['', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', '', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "          ['A', 'A', 'A', 'A', 'A', 'A', ''],\n",
    "          ['A', 'A', 'A', 'A', '', '', ''],\n",
    "          ]\n",
    "\n",
    "grid_7_1 = [['A', 'A', 'A', '', 'A', 'A', 'A'],\n",
    "            ['A', 'A', 'A', '', 'A', 'A', 'A'],\n",
    "            ['A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['', '', 'A', 'A', 'A', '', ''],\n",
    "            ['A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "            ['A', 'A', 'A', '', 'A', 'A', 'A'],\n",
    "            ['A', 'A', 'A', '', 'A', 'A', 'A'],\n",
    "            ]\n",
    "\n",
    "# brits style\n",
    "grid_7_2 = [\n",
    "              ['A', 'A', 'A', 'A', '', '', ''],\n",
    "              ['', 'A', '', 'A', '', 'A', ''],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['', 'A', '', 'A', '', 'A', ''],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['', 'A', '', 'A', '', 'A', ''],\n",
    "              ['', '', '', 'A', 'A', 'A', 'A'],\n",
    "           ]\n",
    "\n",
    "# brits style\n",
    "grid_11_1 = [\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A'],\n",
    "              ['A', '', 'A', '', '', '', 'A', '', 'A', '', 'A'],\n",
    "              ['A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['A', '', 'A', '', 'A', '', 'A', '', 'A', '', 'A'],\n",
    "              ['', 'A', 'A', 'A', 'A', 'A', 'A', 'A', '', '', 'A'],\n",
    "              ['A', '', 'A', '', 'A', '', 'A', '', 'A', '', 'A'],\n",
    "              ['A', '', '', 'A', 'A', 'A', 'A', 'A', 'A', 'A', ''],\n",
    "              ['A', '', 'A', '', 'A', '', 'A', '', 'A', '', 'A'],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A'],\n",
    "              ['A', '', 'A', '', 'A', '', '', '', 'A', '', 'A'],\n",
    "              ['A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A', 'A', 'A']\n",
    "            ]\n",
    "\n",
    "# brits style\n",
    "grid_15_1 = [\n",
    "              ['A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['', 'A', '', 'A', '', 'A', '', '', 'A', '', 'A', '', 'A', '', 'A'],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['', 'A', '', 'A', '', 'A', '', '', 'A', '', 'A', '', 'A', '', 'A'],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['', 'A', '', 'A', '', 'A', '', 'A', '', 'A', '', 'A', '', '', 'A'],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['', '', '', 'A', '', 'A', '', 'A', '', 'A', '', 'A', '', '', ''],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['A', '', '', 'A', '', 'A', '', 'A', '', 'A', '', 'A', '', 'A', ''],\n",
    "              ['A', 'A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['A', '', 'A', '', 'A', '', 'A', '', '', 'A', '', 'A', '', 'A', ''],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'],\n",
    "              ['A', '', 'A', '', 'A', '', 'A', '', '', 'A', '', 'A', '', 'A', ''],\n",
    "              ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', '', 'A', 'A', 'A', 'A']\n",
    "            ]\n",
    "\n",
    "\n",
    "config = {\n",
    "    'word_list': word_list_small,\n",
    "    'grid': grid_5\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "l5s5zhTolZY2"
   },
   "outputs": [],
   "source": [
    "start_t = time.time()\n",
    "crossword = Crossword(config['grid'], config['word_list'])\n",
    "creator = CrosswordCreator(crossword, do_random = True)\n",
    "assignment = creator.solve()\n",
    "end_t = time.time()\n",
    "\n",
    "print(\"Total time taken: \", end_t - start_t, 'seconds')\n",
    "print(\"Total back-tracks: \", creator.ASSIGNMENT_COUNT)\n",
    "print(\"Total time taken in revise function: \", creator.t_revise_time)\n",
    "print(\"Total times revise function is called: \", creator.t_revise_called)\n",
    "# pprint(assignment)\n",
    "\n",
    "if assignment is not None:\n",
    "    display(creator.display_only_grid(assignment, block_size = 50, f_size = 25))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "r45xm08Ojyea"
   },
   "outputs": [],
   "source": [
    "def get_grid_nums(grid):\n",
    "    rows = len(grid)\n",
    "    cols = len(grid[0])\n",
    "\n",
    "    mask_grid = [[0] * rows for col in range(cols)]\n",
    "\n",
    "    for i in range(rows):\n",
    "        for j in range(cols):\n",
    "            if config['grid'][i][j] == '':\n",
    "                mask_grid[i][j] = 'B'\n",
    "\n",
    "    temp_grid = copy.deepcopy(mask_grid)\n",
    "\n",
    "    for i in range(rows):\n",
    "        for j in range(cols):\n",
    "            if (i - 1) == -1 or (j - 1) == -1:\n",
    "                if mask_grid[i][j] != 'B':\n",
    "                    temp_grid[i][j] = 8\n",
    "            elif temp_grid[i][j] == 'B':\n",
    "                continue\n",
    "            elif mask_grid[i - 1][j] == 'B' or mask_grid[i][j - 1] == 'B':\n",
    "                temp_grid[i][j] = 8\n",
    "\n",
    "    count = 1\n",
    "    for i in range(rows):\n",
    "        for j in range(cols):\n",
    "            if temp_grid[i][j] == 8:\n",
    "                temp_grid[i][j] = count\n",
    "                count += 1\n",
    "\n",
    "    return temp_grid\n",
    "\n",
    "def get_answers_by_letters(grid):\n",
    "    answer_grid = copy.deepcopy(grid)\n",
    "    for var, answer in assignment.items():\n",
    "        if var.direction == 'across':\n",
    "            for i in range(len(answer)):\n",
    "                answer_grid[var.i][var.j + i] = answer[i]\n",
    "\n",
    "        elif var.direction == 'down':\n",
    "            for i in range(len(answer)):\n",
    "                answer_grid[var.i + i][var.j] = answer[i]\n",
    "    return answer_grid\n",
    "\n",
    "def draw_grid_solution(grid, grid_nums, answer_grid = None):\n",
    "\n",
    "    black_square_color = 'black'\n",
    "    text_color = 'black'\n",
    "    cell_size = 50\n",
    "\n",
    "    x_offset = 15\n",
    "    y_offset = 15\n",
    "\n",
    "    height = len(grid) * cell_size + 1 + 2 * y_offset\n",
    "    width = len(grid[0]) * cell_size + 1 + 2 * x_offset\n",
    "\n",
    "    img = Image.new(\"RGB\", (width, height), \"white\")\n",
    "    draw = ImageDraw.Draw(img)\n",
    "\n",
    "    font = ImageFont.load_default()\n",
    "\n",
    "    # Adjust font size\n",
    "    font_size = 10  # Set your desired font size\n",
    "    font_grid_num = ImageFont.truetype(\"/content/Roboto-Regular.ttf\", font_size)\n",
    "    font_letter = ImageFont.truetype(\"/content/Roboto-Bold.ttf\", 20)\n",
    "\n",
    "    for row in range(len(grid)):\n",
    "        for col in range(len(grid[row])):\n",
    "            x = col * cell_size + x_offset\n",
    "            y = row * cell_size + y_offset\n",
    "            rect = [(x, y), (x + cell_size, y + cell_size)]\n",
    "\n",
    "            if grid[row][col] == '':\n",
    "                draw.rectangle(rect, fill = black_square_color)\n",
    "            else:\n",
    "                draw.rectangle(rect, outline = \"black\")\n",
    "                if grid_nums[row][col] != 0:\n",
    "                    draw.text((x + cell_size // 2 - 20, y + cell_size // 2 - 22), str(grid_nums[row][col]), fill = text_color, font = font_grid_num)\n",
    "                if answer_grid is not None:\n",
    "                    draw.text((x + cell_size // 2 - 6, y + cell_size // 2 - 12), answer_grid[row][col], fill = text_color, font = font_letter)\n",
    "    display(img)\n",
    "\n",
    "# lets get the across and down clues\n",
    "\n",
    "def get_clues(assignment):\n",
    "    across_clues = []\n",
    "    down_clues = []\n",
    "\n",
    "    for var, answer in assignment.items():\n",
    "        relevant_clues = clue_answer_df[clue_answer_df['Unsegmented'] == answer.lower()]['Clue'].tolist()\n",
    "        clue = random.choice(relevant_clues)\n",
    "        if var.direction == 'across':\n",
    "            across_clues.append((grid_nums[var.i][var.j], clue.capitalize()))\n",
    "        else:\n",
    "            down_clues.append((grid_nums[var.i][var.j], clue.capitalize()))\n",
    "\n",
    "    across_clues.sort(key = lambda x: x[0])\n",
    "    down_clues.sort(key = lambda x: x[0])\n",
    "    across_clues = list(map(lambda x: f\"{x[0]}. {x[1]}\", across_clues))\n",
    "    down_clues = list(map(lambda x: f\"{x[0]}. {x[1]}\", down_clues))\n",
    "\n",
    "    return across_clues, down_clues\n",
    "\n",
    "def generate_crossword_image(grid, grid_nums, answer_grid, across_clues, down_clues):\n",
    "    black_square_color = 'black'\n",
    "    text_color = 'black'\n",
    "    cell_size = 50\n",
    "    margin = 20  # Adjust the margin between grid and clues\n",
    "\n",
    "    x_offset = 15\n",
    "    y_offset = 15\n",
    "    clue_pad_x = 20\n",
    "    clue_pad_y = 3\n",
    "\n",
    "    base_height = len(grid) * cell_size + 1 + 2 * y_offset\n",
    "    base_width = len(grid[0]) * cell_size + 1 + x_offset\n",
    "\n",
    "    font_size = 10  # Set your desired font size\n",
    "    font_grid_num = ImageFont.truetype(\"/content/Roboto-Regular.ttf\", font_size)\n",
    "    font_letter = ImageFont.truetype(\"/content/Roboto-Bold.ttf\", 18)\n",
    "    font_clue = ImageFont.truetype(\"/content/Roboto-Regular.ttf\", 14)  # Adjust clue font size\n",
    "    font_clue_heading = ImageFont.truetype(\"/content/Roboto-Bold.ttf\", 16)\n",
    "\n",
    "    # lets find out how the clues would take up the size\n",
    "    max_w = 0\n",
    "    max_h = 0\n",
    "    total_height = 0\n",
    "    for clue in across_clues + down_clues:\n",
    "        _, _, w, h = font_clue.getbbox(clue)\n",
    "        if w > max_w:\n",
    "            max_w = w\n",
    "        if h > max_h:\n",
    "            max_h = h\n",
    "        total_height += clue_pad_y +  h\n",
    "\n",
    "    width = base_width + 2 * clue_pad_x + max_w\n",
    "    height = base_height if base_height > total_height else total_height\n",
    "\n",
    "    img = Image.new(\"RGB\", (width, height), \"white\")\n",
    "    draw = ImageDraw.Draw(img)\n",
    "\n",
    "    clue_spacing = max_h + clue_pad_y\n",
    "\n",
    "    # Draw crossword grid\n",
    "    for row in range(len(grid)):\n",
    "        for col in range(len(grid[row])):\n",
    "            x = col * cell_size + margin\n",
    "            y = row * cell_size + y_offset\n",
    "            rect = [(x, y), (x + cell_size, y + cell_size)]\n",
    "\n",
    "            if grid[row][col] == '':\n",
    "                draw.rectangle(rect, fill=black_square_color)\n",
    "            else:\n",
    "                draw.rectangle(rect, outline=\"black\")\n",
    "                if grid_nums[row][col] != 0:\n",
    "                    draw.text((x + cell_size // 2 - 20, y + cell_size // 2 - 22), str(grid_nums[row][col]),\n",
    "                              fill=text_color, font=font_grid_num)\n",
    "                if answer_grid is not None:\n",
    "                    draw.text((x + cell_size // 2 - 6, y + cell_size // 2 - 12), answer_grid[row][col],\n",
    "                              fill=text_color, font=font_letter)\n",
    "\n",
    "    # Draw across clues\n",
    "    x_clues = base_width + clue_pad_x  # Adjust the starting point for across clues\n",
    "    y_clues = 15  # Adjust the starting point for across clues\n",
    "\n",
    "    draw.text((x_clues, y_clues), \"Across\", fill = text_color, font = font_clue_heading)\n",
    "    for i, clue in enumerate(across_clues, start = 1):\n",
    "        draw.text((x_clues, y_clues + i * clue_spacing), f\"{clue}\", fill = text_color, font=font_clue)\n",
    "\n",
    "    # Draw down clues\n",
    "    y_clues += len(across_clues) * clue_spacing + 30  # Adjust the starting point for down clues\n",
    "\n",
    "    draw.text((x_clues, y_clues), \"Down\", fill=text_color, font = font_clue_heading)\n",
    "    for i, clue in enumerate(down_clues, start = 1):\n",
    "        draw.text((x_clues, y_clues + i * clue_spacing), f\"{clue}\", fill = text_color, font = font_clue)\n",
    "\n",
    "    display(img)  # Display the generated crossword image\n",
    "\n",
    "grid = config['grid']\n",
    "grid_nums = get_grid_nums(grid)\n",
    "answer_grid = get_answers_by_letters(grid)\n",
    "across_clues, down_clues = get_clues(assignment)\n",
    "\n",
    "generate_crossword_image(grid, grid_nums, None, across_clues, down_clues)\n",
    "generate_crossword_image(grid, grid_nums, answer_grid, across_clues, down_clues)\n",
    "draw_grid_solution(grid, grid_nums, answer_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "ct8kiPLiq3Nc",
    "outputId": "ab1276c8-cb46-4ade-816b-b412bc3c147e"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████████████████████████████████████████████████████████████████████████| 5000/5000 [00:18<00:00, 269.48it/s]\n",
      "100%|██████████████████████████████████████████████████████████████████████████████| 5000/5000 [00:18<00:00, 275.76it/s]\n",
      "100%|██████████████████████████████████████████████████████████████████████████████| 5000/5000 [00:16<00:00, 294.50it/s]\n",
      "100%|██████████████████████████████████████████████████████████████████████████████| 5000/5000 [00:14<00:00, 351.04it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Total time taken:  67.95315265655518\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "variable = list(creator.crossword.variables)[0]\n",
    "\n",
    "start_t = time.time()\n",
    "values_penalty = Counter()\n",
    "for neighbor in creator.crossword.neighbors(variable):\n",
    "    overlap = creator.crossword.overlaps[variable, neighbor]\n",
    "    for value in tqdm(list(creator.domains[variable][0])[:5000], ncols = 120):\n",
    "        for value_1 in list(creator.domains[neighbor][0])[:5000]:\n",
    "            if value[overlap[0]] != value_1[overlap[1]]:\n",
    "                values_penalty[value] += 1\n",
    "end_t = time.time()\n",
    "print(\"\\nTotal time taken: \", end_t - start_t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "r1-EijwEu7aw",
    "outputId": "72a91b5d-6c2c-4d26-e8b7-4a49bb6831c9"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|███████████████████████████████████████████████████████████████████████████| 10000/10000 [00:04<00:00, 2487.19it/s]\n",
      "100%|███████████████████████████████████████████████████████████████████████████| 10000/10000 [00:02<00:00, 3906.52it/s]\n",
      "100%|███████████████████████████████████████████████████████████████████████████| 10000/10000 [00:02<00:00, 4577.34it/s]\n",
      "100%|███████████████████████████████████████████████████████████████████████████| 10000/10000 [00:02<00:00, 4561.07it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Total time taken:  11.032546520233154\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "values_penalty = Counter()\n",
    "no_samples = 10000\n",
    "start_t = time.time()\n",
    "for neighbor in creator.crossword.neighbors(variable):\n",
    "    overlap = creator.crossword.overlaps[variable, neighbor]\n",
    "    neighbor_list = [value[overlap[1]] for value in list(creator.domains[neighbor][0])[:no_samples]]\n",
    "\n",
    "    for value in tqdm(list(creator.domains[variable][0])[:no_samples], ncols = 120):\n",
    "        letter_to_be_searched = neighbor_list.count(value[overlap[0]])\n",
    "        values_penalty[value] += len(neighbor_list) - letter_to_be_searched\n",
    "\n",
    "priority_queue = [(-values_penalty[value], value) for value in list(creator.domains[variable][0])[:no_samples]]\n",
    "heapq.heapify(priority_queue)\n",
    "\n",
    "end_t = time.time()\n",
    "\n",
    "print(\"\\nTotal time taken: \", end_t - start_t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "-qW-y9rFWY5C"
   },
   "source": [
    "#### Lets load the heavily loaded crosswords:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "background_save": true,
     "base_uri": "https://localhost:8080/",
     "height": 499
    },
    "id": "EZUvoGh5Wccf",
    "outputId": "de717a80-c328-4c4d-bc06-3378e5d26e1c"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeEAAAHiCAYAAADf3nSgAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAAA8dElEQVR4nO3deZBdZZ3/8c+5++3t9r6ntyyEJGQhAURUkEUEZVNG3BG3mvEPxSl1Sv/QmfqJVaPlDE5pjaOU1DhCuaEQcBDFCTBQIDELTQLp0J3udHrfb3ff/d5zfn/EvhLBsdM3nadP5/2qOpWk+3TyfXLvOZ/zPOc5z7Ucx3EEAADOOo/pAgAAOFcRwgAAGEIIAwBgCCEMAIAhhDAAAIYQwgAAGEIIAwBgCCEMAIAhhDAAAIb4FrujZVnLWQcAAKvKYhakXHQIA2eD1+vV5ZdfrkgkYrqUgvT09Kizs1OXXnqp6uvrTZdTkOHhYT333HPaunWr1q5da7qcgszMzOipp55SW1ubtm7darqcgiSTSe3Zs0fJZNJ0KSiEs0iS2NiWfSsqKnL279/v2Lbt6u3uu+92LMtydu/ebbyWQrdf/vKXjiTnW9/6lvFaCt327dvnhMNh5zOf+YzxWgrdBgcHnYaGBuPHLNtf3haDnjBWHMuyVs3tj9XQloX6V0NbXm01tGU1tOFcx8QsAAAMIYQBADCE4Wi4zsKMw0QioXQ6rVgsJr/fr5qaGtcNzzmOo2w2q9nZWUWjUdm2La/Xq/LycgWDQRUVFZkucdEcx1Eul1MsFtPU1JRyuZwkqaqqSoFAQEVFRa57fRbE43ElEolTXh+Phz4MCkcIw7VOnDihwcFB7d+/X3V1dfrABz7gupN8NpvV3Nycnn76aT355JOKx+MqLi7WNddco9bWVp1//vmmS1w027Y1Pz+vF154Qbt379b8/Lwk6eabb9aaNWu0efNmwxUu3fHjx/Xyyy8rlUqppKRE1157rQKBgOmysAoQwnCdRCKh6elpjYyMaGRkRH19fXIcZ1HP5K00c3Nz+v3vf694PK4NGzYoEonItm09//zzSqfTrgrhTCajV155RfF4XBs3blQoFJLX61VnZ6empqa0adMm110k5XI5JZNJ9fT06Nlnn1VVVZXq6+td+V7DykQIw3USiYQGBwc1OjqqsbEx9ff3KxgMmi5rSWZnZ/Xss8+qo6NDW7du1caNGzUzM6P7779f4XDYdHmnJZ1O6+jRowqHw9q2bZvWrFkjn8+nO++8U+Pj43rve99rusTTtnCroLu7W88884y2bdsmv99PCOOMIYThOmVlZdq4caNaW1sVjUb1hz/8QV6v13RZS1JXV6ePfOQjCofD+fu/mUxGZWVlrgvhoqIiXXXVVcpms8pmsxocHNTU1JQaGhrU3Nzsul6wJI2Ojuq+++6T3+/XbbfdpsnJSdMlYZUhhOE6fr9ffr9fZWVlKioqUiAQcOUJXpLC4bA6Ojryw+kDAwOamppSbW2t61YN8/l8qq+vVzwe19TUlKLRqEZHRxUOh1VcXGy6vNPiOI4SiYSi0aiGh4fV0dGhjo4OxWIx06VhlSGEgRXAtm1lMhndd999mpiY0Ac/+EE1NDSYLmtJUqmUpqenNTAwoP7+fvn9foVCIdNlnZZsNqu9e/dqYmJC5513nhobG1VTUyO/32+6NKwyhDBg0MK9xYGBAfX19amoqEitra2qq6tTaWmp4epOTzab1djYmDKZjMLhsNra2lRcXKy9e/cqGo2aLu+0OI6j8fFxjY+Pa3Z2VrZta3p6Oj//YGpqSpFIxHU9fKw8hDCwAnR2dupXv/qVrr32WrW1tamxsVFerzcf0m4Ybk+n03rppZcUiUTU0dGhNWvWKJ1O69e//rV8Pnedamzb1uDgoIaHhzU3N6d4PK5YLKbBwUFVVFToxIkTsm2bEEbB3HVkAKvMzMyM9u7dq71796q7u1vl5eXq6enRH/7wB7W3t2v79u0qLS11xexvy7IUCoXU19en3/3udyorK5Pf71dlZaWamppMl3da/H6/3v72tyuRSCibzWp8fFxjY2Pav3+/gsGgWlpaXHfPHisTIQxXsyxLJSUlru2RpFIpnThxIr9a1szMjLLZrEZGRuT3+7Vx40bXrJplWZbC4bASiYRefvnl/MS56upq1dbWmi7vtHi9Xp133nn5P4+MjGhoaEjz8/OyLEsVFRWuu8+NlYkQhqsVFRXpy1/+sjwejyuXEayurtbf/M3f6KabblI6nZbf788PPS8s9eiWdgWDQW3ZskXr16/X2972tvxQeigUOqVdblRdXa2Kior85ym7YWQC7kAIw9U8Ho+qq6tNl7FkPp9PZWVlpss4IyzLUjAYVCAQUElJiWzbluM48vl8rg5g6eTr5PP5CF+ccYQwgDPOsizXLqACnE2EMIAzyu29XuBscsfNJgAAViFCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBCf6QKAV3McR8lkUvF43HQpBclkMpKkVCrl+rakUilJUjqdXjVtyWazrm9LMpmU4zimy0CBLGeRr6JlWctdCyDLsrRhwwYVFRWZLqUgY2NjGhwcVEdHhyKRiOlyCjIzM6Pe3l41NzerpqbGdDkFicfjOnr0qKqrq9Xc3Gy6nIJkMhl1dXXlL/iw8iwmXukJY0WxLEter1der9d0KQXxeE7e6VkNbVmo3+PxrIq2WJa1Ktpi27Ykqby8XOvWrTNcTWFs29aRI0ckSRs3bswfP27V3d2tmZmZRe1LTxgrSjgc1p49e7Rt2zbTpRTkO9/5jj7/+c/r5z//ua6//nrT5RTk4Ycf1nve8x5985vf1Kc+9SnT5RTk4MGDuvLKK/Wxj31M3/jGN0yXU5Dh4WFddtll2rVrl37yk5+4+hydSCR05ZVXSpL+53/+R+Fw2HBFS+c4jm677TY9/PDD9IThPpZlKRgMKhQKmS6lID7fyUMrEAi4vi2BQECS5Pf7V01bvF6v69sSDAbzI0ehUMjVIWzbdr736/bj33Gc0xplcXefHwAAFyOEAQAwhOFouNbc3NxrHtMoLi7Oz6x28/AccKY5jqNcLqd0Oq1kMqlgMCi/3y+/3++qYyWRSCiTySiTyeSP/YVfy8rK5PP55PF4XNMmQhiu9Ytf/ELPPvus0ul0/iB817vepXe84x2uOQCBsyWbzWp4eFhHjx7VU089pUsuuUQdHR1au3Zt/l65G/zhD3/QkSNH1Nvbm3/uO5VKKZvN6pOf/KTrHgskhOE6juPItm0lEgklEglt2rQpP5Gjrq7OcHXAyrLQA47FYtq/f7/i8bja2tpUVVWlkpIS112wVlZWqqWlRcFgMN8b7unp0fHjxyWdnEDoJoQwXMe2bWWzWdm2rVAopNtvv/014eu2EwuwnNLptCYmJvSTn/xE27Zt00c/+lGVlZXlZ1i7yaZNm7Rp0yZJf7og/+lPf6pjx46pqKhIRUVFrmoTIQzXyWQyikajGh8fV39/v+677z41NDRo3bp1am5uVmNjo+kSgRWlp6dHfX19chxH/f39+ulPf6oNGzaooaFBGzZsUDAYNF3ior06YGdnZ3X48GFJ0s6dO13ZsyeE4Tq5XE7JZDI/waSzs1MjIyPK5XIKh8Oqr6+XZVmuOxiB5eA4jsbGxjQ8PCyfz6f5+Xm99NJLchxHiURC7e3t+XvCbjtm4vG4urq6FAgEtG7dOlc+X0wIw3WCwaCqq6t122236ZprrtGaNWvU19en7373u/J6vWptbVVRUVF+wQzgXDc9Pa25uTlt3bpVHR0deuMb36gf/vCH+sUvfqGdO3cqFAq5chnP6elpPf7447r++uv11re+VaWlpaZLOm2cpeA6tm0rnU6ruLhYXq9X9fX1ikajSqVSSqfTSqfTrl72DjjTFlbWKi4uVmVlperq6mRZlmKxWH5+hZtC2LZtzc7Oam5uLr9iWFlZmSvXnCaE4TqJRELDw8NKp9OSTi5BGA6HVVdXJ7/fr3g87sorYmC5lJSUqLy8XH6/X+FwWB6PR+FwWCUlJcrlcspms66aVZzL5fTiiy9qbGxMmzdvVn19vSsDWCKE4UI+n08lJSV67rnndPz4cXV3dysajeZnS0ciEVdd1QPLybIstbW1KRgMas+ePRobG9P4+Limp6dVXl6uUCjkqgCWTobwCy+8oGw2q127dqmxsdF197MXEMJwnYUQ7u3t1bPPPqtjx47lr4IXQhjAn7S0tMjv9+v48ePq6+tTb2+vAoGAKisrXRvCXV1dKi0t1fbt21VcXGy6pCUjhOE6fr9fpaWl+sAHPqAbbrghPxPa6/WqqqrKdHnAihMIBNTY2KgvfelLsm1bjuMoEAjI7/errKzMdHmnLRQK6c4775TX61VZWZmrR74IYbiOx+ORx+NRc3OzHMdROp2WZVmuWwMXOBsWLlC9Xq82bNiQvwfs8/lcG15er1dr1641XcYZQQjD9dy07i1gmsfj4ZhZQQhhuBo9X+D0cMysLO6c0w0AwCpACAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABjiM10A8Occx5Ft26bLKIjjOPlfacvKsdAWSauiLX++udWra19t77O/xnIWubdlWUsuCFgsr9eryy67TJFIxHQpBTl27JgOHz6siy++WHV1dabLKcjIyIj27t2rLVu2qL293XQ5BYlGo3r66afV2tqqLVu2mC6nIMlkUk899ZQqKip00UUXmS6nILlcTs8884wk6bLLLpPX6zVcUWH27t2rkZGRRYUxIYwVxbIs1dTUyO/3my6lIPPz84pGo6qqqlIoFDJdTkGSyaQmJydVXl6u4uJi0+UUJJPJaHx8XMXFxa6/0LNtW6OjowoEAqqqqjJdTkEcx9H4+LgkqaamxvV5Mzk5qWQySQjDfcLhsHbv3q3NmzebLqUg99xzj77yla/oP//zP3X11VebLqcgjz32mO644w599atf1Uc/+lHT5RTk0KFDuvHGG/WhD31I//RP/2S6nIKMjY3p2muv1Y4dO/SDH/zAdDkFSSaTuummmyRJDz30kOsvXD/60Y/q17/+9aJCmHvCWFEsy1J1dbUaGhpMl1KQsrIySVJFRYXr21JRUSHpZJvc3pbh4WFZlqWioiLXt8VxHHm9XoVCIdXX17u6oxSPx/OjX3V1dSoqKjJc0dI5jnNaFxHMjgYAwBBCGAAAQxiOhuss3GfJZrPK5XJyHEeWZcnn88nj8cjj4doSgDsQwnAd27aVy+X02GOP6aWXXtL8/LwqKyv1hje8QS0tLWpqajJdIgAsCl0GuE4qldL4+LhmZmY0NzenYDCoXC6no0ePampqynR5ALBo9IThOmNjY3r22WeVyWS0du1aveMd71Bvb6/+8R//UYFAQBdccIHpEgFgUegJw3VCoZBqamqUSCQ0ODiovr6+/GIS4XDYdHkAsGiEMFxn4bnIZDKpgYEBdXd3a3R0VNXV1YQwAFdhOBqu5jiORkdHZdu2gsGgfD7e0gDcg54wXCebzWp+fl6BQECRSEThcFh+v1/ZbFa2bbv+E2UAnDvoNsB1RkZG9Pjjj+v888/XxRdfrI0bN+qVV17R448/romJCWWzWXm9Xlcv4wfg3EAIw3XC4bAaGho0MzOj2dlZJZNJjY6OqqioSIFAQJZlEcAAXIEQhutUVFTowgsv1IMPPqjOzk7V1dXJ5/OppqZGpaWl3BcG4BqcreA6JSUlamtr06233qqrr75aXq9XHo9Hfr+f1bIAuAohDNcJBAIKBAIqLy+X4zhKp9OyLCs/FA0AbkEIw9Usy1IwGDRdBgAsCSEM16LXC8DteE4YAABDCGEAAAwhhAEAMIQQBgDAEEIYAABDCGEAAAwhhAEAMIQQBgDAEEIYAABDCGEAAAwhhAEAMIQQBgDAEEIYAABDCGEAAAwhhAEAMIQQBgDAEEIYAABDCGEAAAwhhAEAMIQQBgDAEEIYAABDCGEAAAwhhAEAMIQQBgDAEEIYAABDCGEAAAwhhAEAMIQQBgDAEEIYAABDCGEAAAzxmS4AeLV0Oq2vf/3rqqmpMV1KQQ4ePCjHcfS9731Pv/3tb02XU5Bjx45Jkh544AF1d3cbrqYw4+PjymQyevLJJ/WZz3zGdDkFicViikaj6uzs1J133mm6nIJks1mdOHFCkvT5z39ePp+7o6mzs3PR+1qO4ziL2tGy5PV6FQwGl1zYSuA4jpLJpCzLUjAYlGVZpksqSCqVkm3bCoVCrm9LOp1WNps1XQbOAT6fT4FAwHQZBVk4l3k8nlVxXk6lUpK0as7LuVxOi4nX07rcuPzyy/XNb37T1f9ByWRSH/nIR+TxeHTvvfe6+s3rOI4++9nP6qWXXtL999+v6upq0yUV5Otf/7ruv/9+02XgHHDbbbfp85//vOkyCjI+Pq73v//92rJli/7lX/7F9eflO+64Q5J07733KhQKGa5o6RzH0d///d9rz549i9r/tEI4Eolo27Ztrn6x4/G4wuGwPB6PLrjgAoXDYdMlLZnjOCorK5Pf79emTZvU0NBguqSCuP0iAu5RXV2tbdu2mS6jIENDQ/L7/avqvCxJF1xwgYqKigxXtHSO4ygSiSx6fyZmAQBgCCEMAIAhZ3QK2qtvQr/6968eJlmJQyavd/PccRxZlpWv96+1bSW168/b83+15dV/fvU+wLnidI7/P993JR7/cJczPg88m80qGo3qv//7vxWLxZRMJnXRRRepra1N9fX1K3rqeTqdVnd3tyYmJtTf369LL71U69atk3Ty4Mvlctq/f786Ozvz9zB27dql2tpaNTc3G67+VLlcTj09PZqamlJPT4+2bNmi7du3n7LP9PS0BgYGdPz4cSUSCV1//fUqKSkxUzBgWDQaVX9/v06cOKG5uTldd911+Xt76XRayWRSv/3tbzU6OqpUKqWGhgadd955am9vV0VFheHq4VZnPBHn5+c1NTWlgYEBxeNxZTIZDQ4Oyu/3q7q6esWGcCaTUSKR0Pj4uE6cOKFDhw7p/PPPz38/l8tpdnZWo6Oj6uvrUy6XUzgcVm9vr7xe74oK4Ww2q1QqpYmJCQ0NDenw4cOqra3Nf99xHKXT6Xx7uru7NTc3p2uuucZg1YA5qVRKc3NzGh0dVU9PjyYnJ3XllVfmvx+PxzU5OamhoSENDw8rl8spl8vJ5/OppqaGEMaSnfHh6CeffFKjo6PavHmzampq1Nraqvvuu0+/+93v9NWvfnXFTj0/fvy4JiYm1N3drd7eXh04cOCUg3Bqakp79uxROp3WunXr9Ja3vEWJREL/7//9P11xxRUraqbl8PBwPlwHBgZ04MABbdy4Mf/9dDqtrq4ujYyMqLe3V4cOHdLs7KzS6bTBqgEzMpmMjh49mg/gQ4cOaXx8PP/cqnRy8YWnnnpKF1xwgXbt2qXzzjtPTz75pL7//e+rrq5Oa9asMdgCuNmy9ITn5+dVWlqqSCSi8vLyfC/Stu0z/c+dMSUlJbJtWx0dHYrFYrJt+5T7P5lMRhMTE4pEIqqpqVFZWZksy1Imk1Emk1Eul5PH41kR94bC4bDKy8vV1tYm27bz2wKPx6OysjI5jiOPx6PDhw9rZmbGXMGAQZZlqaysLP/nV155RaOjo6cc/9XV1dq4caNaWlpUXl6uUCgkr9f7mvMEcLrOeAjHYjHF43GVl5ervLxcRUVF+dVQVuqb1bIs1dfXq76+Xhs2bJBlWXr00Ufl8fxp8ng6ndbIyIiqqqrU0tKioqIixeNx+f1+eTwe5XK5FTOxqbq6WtXV1Vq3bp2qq6v185///JS2BAIBtbW15f+8b98+jY6OGqgUMM/v96u1tVXSyWdUDx8+rN7e3lOO5U2bNmnTpk2SJNu2NTs7K0n55/SBpTrjIbxlyxYNDAzokUceUVFRkWpra/Xyyy8rHo+v2BCW/vrsxoWJWQuzJhd+ZuH3K+mKeDEXAn9ppjRwLvprx4xlWXIcR7Zta2pqSj/72c/k8/l06623rqj5IHCfMxrClmWpublZjuPke5LDw8OanJxc9DqabrWa2wac6xaO70QioampKb3wwgvatGmTrrrqKlVWVhquDm52xnvCjY2Nqqmp0V133aVUKqV4PK6HH35YJ06ccPWwjd/vV01NjRzH0cTEhNasWZOfZew4zqpYdBzAX5bL5XT//fdrfHxcN9xwg1paWrRmzZoV+8QH3OGM94T9fn8+nObn5zU9Pa3q6mqFQiFXf2pJMBhUY2OjUqmUent7VVxcrGQyqZKSkvxa1ABWp9nZWU1NTam3t1eTk5Nat26dJiYm1NPTo9raWhUXF3MhjiVZlku4+fl5PfDAAxobG9PY2Jje/e53a/v27a5eCKK8vFxvectb9OCDD+rRRx/V008/reLiYq1fv15NTU2mywOwjLq6uvTcc8/p4MGDikajkiSv1ytJuvnmm7VlyxbV1dXRK8ZpW5Z3TDgc1pve9CbF43HFYjFt3LhR5eXlruktdnR06CMf+Uh+tSzp5AFXVlamSy65RNXV1QoGg/lPMKmvrzdY7f+ttrZWt99++ykLj/y5yy+/XOedd56rL5KAM+Wyyy7TmjVrTvkknObmZl166aWqra1VKpVSTU1Nvte7fv16lZWVueb8hpVl2UL4DW94w3L81WdFa2tr/pGFBT6fTyUlJdq5c6cuvPBCZTIZSSfvFa/kIaiamhq95z3v+YvftyxLl1566VmsCFjZLrroIl100UWnfK2xsVGNjY2v+TpQKMZOlohhJwBAoUiSJVgpi3IAANyNmxgAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYAghDACAIYQwAACGEMIAABhCCAMAYIjvdHbu7u7W3XffLcuylqueZZdOpzU2NibLsvTtb39bfr/fdElL5jiOjh07pvn5eX3/+99XWVmZ6ZIKcuDAAdMl4Bxx4MAB3X333abLKMjs7Kzm5+dX1XlZkr797W8rEAgYrmjpHMdRd3f3ove3HMdxFrXjH19gN7/QCxaaTFtWlkW+FYEzYjUdM7RlZVloy2LOaafVE7700kv1xS9+0dX/SalUSl/4whfk8Xj0z//8z66/4rrrrrvU3d2tf/3Xf1VFRYXpkgryve99Tw8//LDpMnAOuPHGG/WJT3zCdBkFmZqa0mc/+1lt2LBBX/rSl1x/Xv6Hf/gHSdI///M/KxgMGq5o6RzH0de+9jU999xzi9r/tEK4vr5e73znO139Ysfjcd11113yeDy67rrrFA6HTZe0ZI7j6J577tHAwICuvvpqNTQ0mC6pIL/97W9Nl4BzRHt7u975zneaLqMgQ0NDCoVCq+a8/LWvfU2SdN1116moqMhwRUvnOI5+8IMfLHp/JmYBAGAIIQwAgCGEMAAAhpzWPeFXW5j1lUgkNDAwoMnJSU1MTOjSSy9VdXW1JCmbzSqVSunAgQMaGBhQIpFQeXm5tmzZourqatdPJALgfgvnsrm5OY2MjGhkZESxWExvfvObVVJS8pr9E4mEurq6lMlklM1mtWHDBlVVVZ3tsrFKLDmEJSmXyymZTGpwcFC9vb3q6+vTpk2b8iGcyWQUi8V09OhRHT58WPPz86qrq1NJSYkCgQAhDGBFyOVyisViGhgY0JEjRzQ1NaVdu3adEsILYZ1KpfTKK68olUopm82qvr6eEMaSLTmEbdvWsWPHNDExoWPHjunIkSPq6urSu9/97vw+IyMj2rt3r+rq6tTW1qaWlhb19PTonnvu0Qc+8AG1traekUYAwFJlMhl1d3drbGxMx44d0+HDhzU+Pq5UKvWafWdnZ9Xf368f//jHKikpUWtrq3bt2mWgaqwWSw5hy7Lk9XoVDAZVWVkpv9+vRCIh27b/9Jf7fCoqKlJFRYVKSkoUCoXk9XqVSCSUzWbPSAMAoBCWZcnn8ykcDquyslIej0fJZPKUc9mCwcFBDQwM5M9l6XT6dfcDFqugEO7o6JDjONq+fbsSiYQOHjx4yrNqzc3NampqUjQa1fz8vDo7OzUyMqINGzYwFA1gRfD5fFq/fr0cx9GuXbvU39+vwcHB1zx3a9u2fvWrX2l4eFg33XSTpqam1NfXZ6ZorBoFhfDr/fp6+6TTac3Pz2tsbEzRaFShUEg+X0G3owHgjFjMkrwTExMaGxtTKBRSbW2tysvLlUwmz1aJWMWWNQkdx5HjOEqlUorFYpqcnFQsFlMgEJDX613OfxoAzpiJiQl1dXWpqKhIJSUlKi0t1dTUlGzbzp/npNWx7jHOrmUN4YmJCfX09Ki6ulqNjY269dZbdfToUd17773asWPHcv7TAHDGTExM6OjRo4pGo8pkMjp06JAmJyd14sQJ7dy5U5FIRM3NzYzw4bQt6zsmnU4rGo3K6/Uqk8koEonI5/Mpk8kwmQGAa/h8PoVCofzaBxMTE0okEkqn0/nnhfkUMCzFsoawz+dTcXGxfvWrX6mnp0eVlZUKBoPavHlz/lliAFjpdu3ape3bt8txHCWTSR05ckQ9PT06ePCgNm3apPb2dnk8LECI03fGQrijo0PXXnutKisr818Lh8Oqr6/X1q1bVVtbq6KiIgWDQZWWlqq+vv5M/dMAcMZs2bJFgUBAxcXF+a/5fL78ULPX61VTU5P8fr/C4bBqa2uZ44IlO2MhfMkll+iSSy455WtlZWUqLS3NP8qUzWZlWZb8fj8TGACsSFdffbWuvvrqv/j9QCCglpYWtbS0sFAHCnZWZhFYlpV/IJ7wBQDgpGUP4VeHLkM2AAD8CTMJAAAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQ3+nsPDw8rIceekiWZS1XPcsulUppZmZGHo9HjzzyiAKBgOmSlsxxHI2MjCiZTOqxxx5TRUWF6ZIKcuzYMdMl4Bxx7NgxPfTQQ6bLKMjU1JSSyeSqOi9L0iOPPKJgMGi2oAI4jqPh4eFF7285juMsakcXv8AAAJxti4nX0+oJb926VR/72MdcHcjpdFp33323LMvSnXfeKb/fb7qkJXMcR/fcc49OnDihz33ucyorKzNdUkEeeOABPfnkk6bLwDngiiuu0Lve9S7TZRQkGo3qG9/4hlpbW/Xxj398VZyXJenOO+90/QjlPffcoxdffHHRP7AokpxbbrnFsW17sT+yIsViMWfHjh3Ozp07nXg8brqcgti27dx4441OU1OTMzQ0ZLqcgn360592JLGxLfv2mc98xvTbvWCDg4NOY2Ojc/PNN6+K8/KFF17oXHjhhU4sFjNdTkFs23ZuvvlmR1pcvDIxCwAAQwhhAAAMIYQBADDktCZmvZrzx1lfqVRK4+PjmpmZUTQa1ZYtW1ReXn7KfgcOHNDAwIByuVz+65s3b9b69eslMfMagDkL57J4PK7JyUlNTU0pkUho27ZtKioqOmW/+fl5xWIxdXV1qaysTI2NjYpEIgqFQqbKh8stOYSlk2/KZDKpY8eOqa+vT319fWpsbMyH8MKb+7nnntMzzzyjTCaT/9oHP/hBrVu3jgAGYNxCwB47dkxdXV2anJzU+vXr8yG8cN6KRqMaHh7Wb37zG7W0tOiSSy5RIBAghLFkBfWE+/r6NDk5qb6+PnV1deno0aOKxWKn7JPNZmXbtoqKivThD39YkUhEklRfX08AAzAum82qr69PY2Nj6uvr05EjRzQ+Pq5UKnXKPqlUSr/85S81PT2td7zjHaqpqVF9fT0BjIIUFMKZTEbZbFZer1eZTEbRaFTZbDa/j23bymQy+f2qqqpUW1urUCikQCBACAMwznEcpdNp5XI5eb1eJZNJRaPRU26fpVIpRaNR9fX1KRqNqqioSKFQSB6Ph/MYCrLkEPZ4PFq7dq06Ojq0Y8cOOY6jw4cPn/KGTCaTmpyc1ODgoI4ePaqvf/3rampq0kUXXXTKPWEAMMXv9+u8886Tbdu6+OKLNTY2ptHR0VPOZf39/Tp06JDm5+c1Ozur7373u2pra9O2bdu0fft2NTQ0GGwB3GzJIWxZlny+kz/u9/vzv381r9erUCikDRs2yLZttbS0SJIOHz6s6upqtba2yufzyeNhkjYAM159LpNOnrf+3ELvOBKJqLi4WOvWrVMul1NnZ6daW1tVV1cny7LoFeO0LWv6BQIBRSIRXXvttfrEJz6hT3ziE7r44ov1xBNPqKenR/F4XLZtL2cJAFCwRCKh6elpNTU16cILL9Qdd9yhtrY2/eY3v9HQ0NApt+GA07GsIZxIJDQ2NqZYLKZsNiuPx6NwOKzq6mr5fD4lEglCGMCKFwgEVFZWppKSEhUVFcnj8cjv96u4uFiWZSmbzS5qsX7gzxX0iNJfk81mFYvFND8/r1wup0QioVwup+LiYvl8PgIYgCsEg0GVlpbmw3ahAxEOh+XxeAhgLNmyhnAwGFRVVZUeffRRHTx4UM3Nzcpms8pmsyouLlZdXd3r3n8BgJWko6ND1dXV+u53v6uBgQEdPHhQ2WxWDQ0NikQiCofD3A/GkpyxEK6vr9eOHTtUWlr6p7/c51MoFFJdXZ1aWlpUUVEhj8ejmpoa1dbWvu5kLgAwqaWlRdu2bTvl+d9gMKhIJKLW1lb5/X6VlpbK5/Pl570wuRRLdcZS8IorrtDll19+ytWgz+dTaWmp3ve+98lxHKVSKVmWpWAwyFUjgBXp5ptv1s033/yac5nP59Mdd9wh27aVTqfl9Xrl9/s5l6EgZyyEX296/sKfLcuS4zj5D2pmKj+Aler1erWvPpdZlpVfbIgeMAp11saD//xZPABwI85lOJO4jAMAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQwhhAAAMIYQBADCEEAYAwBBCGAAAQ3yns/PMzIwOHDiwXLWcFalUSvF4XB6PRy+88IICgYDpkgoSjUaVyWR06NAhDQ8Pmy6nIOPj46ZLwDlifHxc+/fvN11GQSYmJpTJZFbVeVmSXnjhBQWDQcMVFWZmZmbR+1qO4ziL2tGy5PF4XP+f4ziOUqmUJCkYDMqyLMMVFSaVSsm2bYVCIde3JZ1OK5fLmS4D5wCv1+v6C3DHcZRMJjkvr0AL5+XFxOtphfC6det0ww03FFygSdlsVj/+8Y9lWZZuu+02+XynNRiw4uzevVujo6N6//vfr+LiYtPlFOSJJ57Qiy++qPe+972qqakxXU5BDhw4oCeeeEI33XSTOjo6TJdTkJ6eHu3evVtvfetbtX37dtPlFGRsbEw/+clPlM1mTZeCc8Ci4tVZJEnOLbfc4ti2vdgfWZFisZizY8cOZ+fOnU48HjddTkFs23ZuvPFGp6mpyRkaGjJdTsE+/elPO0VFRc6BAwdMl1Kwu+++27Esy3n44YdNl1KwBx980JHk/Nu//ZvpUgq2b98+JxwOO5LY2JZ9WwwmZgEAYAghDACAIYQwAACGLHlWkvPHG84LU+RjsZhisZja2tpUUlIiSZqdndXo6Kji8bjS6XT+57LZrJqbm1VXVye/3y+Ph2sBvL6F91k0GlUikdDU1JTKysq0Zs2a/Pdt29b8/Lx6e3uVzWZl27bq6+tVXFysioqKFfP+WmjL3Nxcvi3BYFDt7e2yLCvfllQqpZ6eHmUyGWWzWTU2NioSiai4uHjFtMW2bWUyGU1MTGh0dFTZbFZer1cNDQ0qLi5WJBKRbdvKZrPq7u5WKpVSJpNRRUWFIpGIKioq5Pf7TTcDMK7gqcHxeFxHjhxRb2+v+vr69KEPfSgfwoODg9qzZ4/6+/vzz01lMhnF43HddNNNuvrqqxWJRFbMiQUrk+M46u/v19DQkPbt26eNGzequbk5/xhDNpvV4OCgfvSjH+Uv+K655hq1tbVp586dK+79NTw8rIGBAe3bt0/V1dVqbW2V1+uVdLItk5OT+tnPfqbZ2VnFYjFdf/312rx5s9rb21dMW2zbViwW0759+/T4448rkUgoHA7r2muvVWtrq8rKypTL5RSLxfIz+Ofm5rRjxw5dcMEF2r59OyEMqMCe8NDQkCYnJzU4OKi+vj698sorSiQS+X0aGhp0xRVXKBaL5Z+bOn78uB5++GEFAgGVlJTkTz7A64lGo5qamtKJEyc0PDysV155ReXl5fnv53I5HT58WCMjI6qrq1NTU5Pq6ur07LPPqr+/X9u3b18xj6HFYjGNjY3pxIkTGhwcVHd3txKJRL6H7DiODhw4oPHxcXV0dCgcDqu8vFw9PT3q7e3Vxz72MUUiEcOtOCkajerxxx9XNpvVRRddpJqaGuVyOT355JPatm2bNm/erGPHjmloaEiRSETV1dVau3aturq69Oijj6qtrU1lZWWmmwEYV1AIR6PR/FD09PS0RkZG8g9cS1J5eXn+hOn88cHyUCikRx99VH6/X6FQqOAGYHVLJpOamprS/Py85ubmNDo6espqNLZta3h4WNPT0youLtbatWt1/vnn68EHH8xf+K0UmUxG09PTmpubywdyOBw+ZZ/e3l6Nj49r3bp1amhoUHt7u/bt26eXX345f0tnJUgmk+ru7lZLS4s2bNigdevWKRaL6Xvf+54qKiokSaOjo+rr61NJSYnq6up02WWXqbu7W52dnYrFYvmLD7cvzAAUYskh7PF4tG7dOrW1tWnr1q3yeDzq6ur6i8Nl6XRaTz/9tGZmZnTFFVeopaVlyUXj3FFdXa1IJKL169drZGREzzzzzCmjJx6PR62trbJtW88995ykk3MRSkpKVFVVtaJO8GVlZdq0aZPWr1+vubk57d2795ReuuM4+YCuqalRVVWVSktLZdu2ksnk4h78P0tqa2v1yU9+Un6/X4FAQNlsVqlUSmVlZSoqKpJ0clnFoaEhvfGNb1R9fb18Pl9+/4X7xStllAIwZclHgGVZCgaDCgaDKi4uVjgc/j9PeLZtq7+/X7Ztq729fcUMq2Fl8/l88vl8CofDSiQS8ng8p7zPLMtSIBCQ1+tVMplUNBrVxMREfim/lRTCXq9X4XBY4XBYXq/3NQFkWZbKysqUTCY1NDSkZDKpVCqlmZkZpdPpFRXCfr9fNTU1chxHjuPo6NGjGhoaUktLi+rq6iSdvL+dTqcVCAQUCARkWVZ++duFnwPOdWftMjSTyejZZ59VY2OjPvzhD3MFjDNm4eRuWZZmZ2c1NDQkSa5bT9eyLF100UXq6+vTf/zHf8jn86mqqkpHjhyRbdsramh9wUKP9oEHHtDQ0JA+/vGPq76+Pv+9XC4nj8eTHyFbeJ1WanuAs23Zk9BxHI2OjmpsbEw1NTWqra2V1+tdMbM84W65XE5Hjx7VzMyMdu3apfr6elVVVWn37t2anJxUNpt11WNwlZWV8ng8eve7350PMNu2NTMzs6ImMS70Ynt6enT48GFVVVWprq5OdXV1Ki0tlWVZCoVCKi4uVjwez39CzkJov95IAHAuOitHwcjIiPr7+1VfX6/6+np5vd4VNUwI98rlcurp6ZFlWbr44ovV3NysqqoqPfDAA5qdnVUul3PNsKdlWaqoqFB5ebmampqUSCQUjUY1OjqqEydOrLjQyuVy6u7u1qOPPqprrrlG7e3tqqyslN/vl+M4CofDKi0tza8hkMvllMvlZNs2IQz80Vk5Cvbt26cXX3xR73vf+9TY2Hg2/kmcI3w+n3bu3Kn+/n7dd999+cUgstmsaxeDmZ2d1SOPPKKpqSmNj49r69atuvTSS1fUp2RNT0/riSee0PPPP68jR44oGAzq8OHD2rNnj9auXavLLrtM7e3tqqio0E9/+lNlMhk98cQTisfj2rJlS37yFnCuO2MhvLCK0evdh/N6vfL7/fmhQmApvF6vmpqaTnkPeTwe1dXVKR6P5x+D83q9qq2tzd/6WImjLh6PRw0NDfmFbV5tYTZ0MplUOp1WTU2NWltbV1TPcaFGv9+v6urq/GfzxmIxJRIJ5XI5RSIRBYNB+f1+pVIpzc/Pq6ysTOXl5a67Xw8slzN2VL/tbW/TFVdc8Zpnfy3L0vve9z7lcjkFg0HX9UqwclRVVemuu+46JVg9Ho/a29vV2tqqN77xjfkhz0AgkH8kZiUKhUL64he/KMuyXnOvNxKJ6IMf/GB+GUu/37/iLiYqKyt166235v+/Xz1r3ePx5P/fHcfRl7/8ZeVyufz9+ZX8ugBn2xkLYb/f/xcPLK56cSZ4PJ7XDGMuhJjH45HP58vfc/T5fCv6gs+yrNcs1LFg4fGqlczj8eR7v39NOBzOz5RmUiZwqpUzvgUUYKEXtpKGbPEnr35MCcCfcFQAAGAIIQwAgCGEMAAAhhDCAAAYQggDAGAIIQwAgCGEMAAAhhDCAAAYQggDAGAIIQwAgCGEMAAAhhDCAAAYQggDAGAIIQwAgCGEMAAAhhDCAAAYQggDAGAIIQwAgCGEMAAAhhDCAAAYQggDAGAIIQwAgCGEMAAAhhDCAAAYQggDAGAIIQwAgCGEMAAAhhDCAAAYQggDAGAIIQwAgCG+09k5mUxqaGhouWo5K5LJpDKZjDwej4aHhxUMBk2XVJBkMinbtjU6Oirbtk2XU5BYLCbHcTQ+Pq7BwUHT5RQkGo1KkiYnJ13flqmpKUkn2+T2toyPj8txHNNlAHmWs8h3pGVZCoVCqqiokGVZy13XsnEcRxMTE5Kk6upq17dlenpa6XRaNTU18nq9pksqSDQaVTweV3V1tfx+v+lyCjI/P6/Z2VlVVlYqFAqZLqcgyWRSU1NTKisrU0lJielyCpLJZDQ+Pm66DJwjFhOvp9UTrqio0MUXX+zq4MrlcnrqqadkWZZ27drl6uByHEe///3vNTMzox07drj+ZN/Z2anjx49ry5YtikQipsspSE9Pj1588UVt2LBB9fX1psspyPDwsH7/+9+rtbVVa9euNV1OQWZmZvS///u/yuVypksBTnIWSZJzyy23OLlczrFt27Xb/Py8s337dmfnzp1OLBYzXk8hWy6Xc2688UanqanJGRoaMl5PodunP/1pp6ioyNm/f7/xWgrd7r77bseyLGf37t3Gayl0++Uvf+lIcr71rW8Zr6XQbd++fU44HHYksbEt+7YYp9UTlk4OS7u5J/zq+t3elj+3Wtqyml6X1dCW1Xq8ACsBs6MBADCEEAYAwJDTHo5e4DiOcrmcUqmUxsfHZdu2HMdRWVmZQqHQKbMoE4mE0um0YrGYAoGA62clAwBwJiw5hKWTz3UeP35c//Vf/6VEIqFMJqPLL79c7e3t2rVrl3y+k399f3+/BgcHtX//fjU1Nem9730vIQwAOOctOYRzuZw6Ozs1MTGhtWvXKhwOKxwO6/jx45qcnNT27duVyWQ0PT2tkZERjY6O6vjx465+JAgAgDNpyfeEc7mcDhw4oJ6eHm3evFlvectbdNNNN2lwcFDPPfecstmsYrGYBgcH8yHc19en0dHRM1k/AACuteSesN/v1y233CLbthWJRGRZlhKJhMLhsEpLS2VZliKRiDZu3KjW1lZNT09r79699IQBAPijJYewx+PRmjVr8styTU1NaXx8XCUlJfL5fPJ4PAoEAgoEAvnJWn6/n3vBAAD8UUETs6Q/zZJ++umntXv3bt1yyy1at26d6z8YAQCA5VbQI0rSyYXqX3zxRc3Ozqq1tVWNjY08ggQAwCIUvFjH2NiY7rvvPs3Ozuqaa67R2rVrVVVVJcuy+MgwAAD+DwU9ovT888+rq6tLPT09+dnQnZ2dKi8v11ve8haVlpa6/qPPAABYLkvuCTuOo6GhIQ0PDyubzWpubk6jo6M6evSojh49qng8rnQ6nd/fsiyVlpaqqKjojBQOAIDbLbkn7PP59Pa3v11XXnmlbr/9dnm93vwKWR6PR6WlpfJ4/pTxJSUl+spXviKv18v9YgAAVEAIW5Z1WkPNHo9HNTU1S/3nAABYdfgUJQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQ3+nsnMvllEgklquWsyKRSMi27fzvHccxXNHSOY6jXC4nx3GUTCYVj8dNl1SQbDa7atqSyWQkSalUyvVtSaVSkqR0Or1q2gKsFJazyBSyLEvl5eXq6OhY7pqWlW3b6urqkmVZ2rBhgzwedw8G9PT0KB6Pa+PGjfL7/abLKciJEyc0OTmpDRs2qKioyHQ5BRkbG9PAwIDWrl2rSCRiupyCzMzM6NixY2publZtba3pcgoSj8fV1dXl6otvuMdi3men1ROemZnR/v37l1zQSnPw4EHTJZwRfr9flmXJsizTpRRkoX7asrKsxrYAK8Vp9YSxMjU1Nenpp59WXV2d6VIK8rnPfU733nuv9uzZo61bt5oupyDf+c539IUvfEE///nPdd1115kupyCPPPKI3vOe9+ib3/ym/u7v/s50OQV54YUXdOWVV7r+thrc4Yz3hLFyBYNBhcNh02UUxOfzybKsVdGWhVsDgUDA9W0JBAKSTrZptbQFWCncfUMUAAAXI4QBADCE4ehVyLZtOY6jubk52bYt27YVCATk9/sVCATk8Xhk27bS6fQpj2mFw2H5fL78RC8AwPIihFehZDKpubk5/ehHP9LY2JiSyaQ2btyozZs3a+vWrSotLdXc3Jw6Ozv161//WslkUl6vV1deeaWam5u1ZcsW000AgHMCIbwKDQ8Pa3BwUOFwWPX19QqFQsrlcjp48KDa29sVDAbV1dWlyclJVVVVKRAIyOfz6ejRo0qlUoQwAJwlhPAq9OKLL2rfvn267LLL1NDQoPPPP1/333+/fvjDH+rNb36zQqGQHnvsMVVXV+uSSy7RunXr5PP59KlPfUqDg4O68cYbGY4GgLOAEF6FduzYoTVr1qiurk7BYFCpVEoej0elpaXyer0qLS3VDTfcoFAopMrKSgWDQcXjcRUXF7t+pSoAcBNCeBVqbW1VS0uLpJPr/U5OTuaXHfX5fAqFQtqxY0d+Qtb09LTm5+dVUlKi4uJik6UDwDmFEF7Fcrmcjh8/rn//93/Xxo0b9bd/+7dqamrKf3/hAyAeeughvfTSS7rpppvU1NTEUDQAnCWE8CrkOI5s21ZfX58GBgbk9/tVUVGhNWvWKBgM5nvA0WhUQ0NDSiQSCoVCamxsVE1NjeHqAeDcQQivUul0Wvfdd59yuZxuuOEGtbS0nNILlqSXXnpJP/rRj/SmN71Ju3btUkdHh4LBoKGKAeDcQwivQr29vTpx4oSOHTumXC6nF154QX19fSovL9cFF1ygoqIi9fX1qbOzU/39/Xr55Zc1NzengYEB1dbWasuWLQqHwwQyACwzQngV6u/v18GDBzU0NKRsNquXXnpJlmXJ4/GooqJClZWVOnjwoLq6ujQ2Nqbu7m5NT09Lkjo6OrRmzRp5PB5CGACWGSG8Cu3YsUPr16/XVVddJcdx8o8dWZal6urq/D3iq666Srfffnt+uUpJCoVCqq6uzv8ZALB8ONOuQpFIRJFI5DX3gF+N54EBwDw+RQkAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwhBAGAMAQQhgAAEMIYQAADCGEAQAwxGe6AJwZjuPIcRzTZRRkof7V0JYFq6Etq/F1AVYKy1nkUWVZ1nLXgiUKhUK6/PLLFQwGTZdSkEOHDun48eN605vepEgkYrqcghw7dkyHDh3SJZdcorq6OtPlFGRkZETPP/+8LrjgArW3t5supyDRaFRPP/20crmc6VJwDlhMvBLCAAAsg8XE66KHoxmGAgDgzGJiFgAAhhDCAAAYQggDAGAIIQwAgCGEMAAAhhDCAAAYQggDAGAIIQwAgCGEMAAAhvx//IzrGoY/ABAAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 600x600 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from grid_generator_latest import generate_grid\n",
    "\n",
    "json_data = generate_grid(grid_size = 9, b_factor = 2.5, display_grid = True)\n",
    "\n",
    "rows = json_data['size']['rows']\n",
    "cols = json_data['size']['cols']\n",
    "grid = json_data['grid']\n",
    "reshaped_grid = [grid[i:i + rows] for i in range(0, len(grid), rows)]\n",
    "\n",
    "grid = []\n",
    "for i in reshaped_grid:\n",
    "    row = []\n",
    "    for j in i:\n",
    "        if j == '.':\n",
    "            row.append('')\n",
    "        else:\n",
    "            row.append('A')\n",
    "    grid.append(row)\n",
    "# pprint(grid)\n",
    "\n",
    "start_t = time.time()\n",
    "crossword = Crossword(grid, word_list_path)\n",
    "creator = CrosswordCreator(crossword, do_random = True)\n",
    "# creator = CrosswordParallelSolver(crossword, do_random = True)\n",
    "assignment = creator.solve()\n",
    "end_t = time.time()\n",
    "print(\"Total time taken: \", end_t - start_t, 'seconds')\n",
    "print(\"Total back-tracks: \", creator.ASSIGNMENT_COUNT)\n",
    "print(\"Total time taken in revise function: \", creator.t_revise_time)\n",
    "print(\"Total times revise function is called: \", creator.t_revise_called)\n",
    "pprint(assignment)\n",
    "creator.save(assignment, block_size = 50, f_size = 25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "gVsM4XuPZ5Z3"
   },
   "source": [
    "#### Basic analysis between variables and their intersection / overlaps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "iKqA1tJROdGY",
    "outputId": "d31cf0e6-b15a-43ba-b7bc-d702f781fb98"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Variable (0, 0) down : 3\n",
      "Neighbor (0, 0) across : 3\n",
      "Overlap Position (0, 0)\n",
      "Neighbor (2, 0) across : 4\n",
      "Overlap Position (2, 0)\n",
      "Neighbor (1, 0) across : 4\n",
      "Overlap Position (1, 0)\n",
      "--------------------------------------------------\n",
      "Variable (3, 1) across : 3\n",
      "Neighbor (1, 3) down : 3\n",
      "Overlap Position (2, 2)\n",
      "Neighbor (0, 1) down : 4\n",
      "Overlap Position (0, 3)\n",
      "Neighbor (0, 2) down : 4\n",
      "Overlap Position (1, 3)\n",
      "--------------------------------------------------\n",
      "Variable (0, 1) down : 4\n",
      "Neighbor (3, 1) across : 3\n",
      "Overlap Position (3, 0)\n",
      "Neighbor (2, 0) across : 4\n",
      "Overlap Position (2, 1)\n",
      "Neighbor (0, 0) across : 3\n",
      "Overlap Position (0, 1)\n",
      "Neighbor (1, 0) across : 4\n",
      "Overlap Position (1, 1)\n",
      "--------------------------------------------------\n",
      "Variable (0, 2) down : 4\n",
      "Neighbor (3, 1) across : 3\n",
      "Overlap Position (3, 1)\n",
      "Neighbor (2, 0) across : 4\n",
      "Overlap Position (2, 2)\n",
      "Neighbor (0, 0) across : 3\n",
      "Overlap Position (0, 2)\n",
      "Neighbor (1, 0) across : 4\n",
      "Overlap Position (1, 2)\n",
      "--------------------------------------------------\n",
      "Variable (2, 0) across : 4\n",
      "Neighbor (0, 0) down : 3\n",
      "Overlap Position (0, 2)\n",
      "Neighbor (1, 3) down : 3\n",
      "Overlap Position (3, 1)\n",
      "Neighbor (0, 1) down : 4\n",
      "Overlap Position (1, 2)\n",
      "Neighbor (0, 2) down : 4\n",
      "Overlap Position (2, 2)\n",
      "--------------------------------------------------\n",
      "Variable (1, 3) down : 3\n",
      "Neighbor (3, 1) across : 3\n",
      "Overlap Position (2, 2)\n",
      "Neighbor (2, 0) across : 4\n",
      "Overlap Position (1, 3)\n",
      "Neighbor (1, 0) across : 4\n",
      "Overlap Position (0, 3)\n",
      "--------------------------------------------------\n",
      "Variable (0, 0) across : 3\n",
      "Neighbor (0, 0) down : 3\n",
      "Overlap Position (0, 0)\n",
      "Neighbor (0, 1) down : 4\n",
      "Overlap Position (1, 0)\n",
      "Neighbor (0, 2) down : 4\n",
      "Overlap Position (2, 0)\n",
      "--------------------------------------------------\n",
      "Variable (1, 0) across : 4\n",
      "Neighbor (0, 0) down : 3\n",
      "Overlap Position (0, 1)\n",
      "Neighbor (1, 3) down : 3\n",
      "Overlap Position (3, 0)\n",
      "Neighbor (0, 1) down : 4\n",
      "Overlap Position (1, 1)\n",
      "Neighbor (0, 2) down : 4\n",
      "Overlap Position (2, 1)\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "for var in crossword.variables:\n",
    "    print(\"Variable\", var)\n",
    "    for neighbor in crossword.neighbors(var):\n",
    "        print(\"Neighbor\", neighbor)\n",
    "        print(\"Overlap Position\", crossword.overlaps[var, neighbor])\n",
    "    print(\"-\" * 50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "vB0IXOktlegQ"
   },
   "outputs": [],
   "source": [
    "creator.save(assignment, '/content/output_5x5_3.png')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "6yXpR9w6lnVr",
    "outputId": "a0df26db-6269-40a2-c1c5-5798b6cff353"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BENITA\n",
      "RUDNER\n",
      "TIBIAL\n",
      "OLDBAG\n",
      "DEART\n",
      "LOUIE\n",
      "BOLED\n",
      "EATRE\n",
      "BLOB\n",
      "BBRT\n",
      "GATE\n",
      "RLEE\n"
     ]
    }
   ],
   "source": [
    "words = open(\"/content/all_answers.txt\").read().splitlines()\n",
    "for var, ans in assignment.items():\n",
    "    if ans.lower() in words:\n",
    "        print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Lbh0fvpDm7iX"
   },
   "source": [
    "Let me try something out here, so, if the answers are within the list of the words to be made the domain of the variables, the backtracking would easily find the answers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vMqYFndmnNAd"
   },
   "source": [
    "<b> 1. Get clues and their gold answers from NYT or somewhere <br>\n",
    "<b> 2. Form a words dictionary of about 5000 words which would include those answers <br>\n",
    "<b> 3. Test if the back-tracking would find the answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "Khl1LafRmKaL"
   },
   "outputs": [],
   "source": [
    "def get_grid_answers(dateStr):\n",
    "\n",
    "    headers = {\n",
    "        'Referer': 'https://www.xwordinfo.com/JSON/'\n",
    "    }\n",
    "    # mm/dd/yyyy\n",
    "    url = 'https://www.xwordinfo.com/JSON/Data.ashx?date=' + dateStr\n",
    "\n",
    "    response = requests.get(url, headers=headers)\n",
    "\n",
    "    answer_list = []\n",
    "    two_d_grid = []\n",
    "    grid_structure = []\n",
    "\n",
    "    grid_data = {}\n",
    "    if response.status_code == 200:\n",
    "        bytevalue = response.content\n",
    "        jsonText = bytevalue.decode('utf-8').replace(\"'\", '\"')\n",
    "        grid_data = json.loads(jsonText)\n",
    "        answer_list.extend(grid_data['answers']['across'])\n",
    "        answer_list.extend(grid_data['answers']['down'])\n",
    "\n",
    "        rows = cols = grid_data['size']['rows']\n",
    "        initial_grid = grid_data['grid']\n",
    "\n",
    "        for i in range(0, len(initial_grid), cols):\n",
    "            two_d_grid.append(initial_grid[i:i+cols])\n",
    "\n",
    "        for grid_row in two_d_grid:\n",
    "            row = []\n",
    "            for element in grid_row:\n",
    "                if element == '.':\n",
    "                    row.append('')\n",
    "                else:\n",
    "                    row.append('#')\n",
    "            grid_structure.append(row)\n",
    "        return answer_list, grid_structure\n",
    "    else:\n",
    "        print(f\"Request failed with status code {response.status_code}.\")\n",
    "        return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zDH-l3v_pTvP"
   },
   "source": [
    "<b> Let's prepare a custom answer list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 206
    },
    "id": "rksKD8a4pwRC",
    "outputId": "d7760647-cbd2-4885-b89d-a8dae0f9d77f"
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "  <div id=\"df-0bac63c6-10c4-4325-a4cc-832a39e6c34c\" class=\"colab-df-container\">\n",
       "    <div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>answer</th>\n",
       "      <th>answer_len</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>taxpro</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>warm</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>decaf</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>mussel</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>aaamap</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>\n",
       "    <div class=\"colab-df-buttons\">\n",
       "\n",
       "  <div class=\"colab-df-container\">\n",
       "    <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-0bac63c6-10c4-4325-a4cc-832a39e6c34c')\"\n",
       "            title=\"Convert this dataframe to an interactive table.\"\n",
       "            style=\"display:none;\">\n",
       "\n",
       "  <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\" viewBox=\"0 -960 960 960\">\n",
       "    <path d=\"M120-120v-720h720v720H120Zm60-500h600v-160H180v160Zm220 220h160v-160H400v160Zm0 220h160v-160H400v160ZM180-400h160v-160H180v160Zm440 0h160v-160H620v160ZM180-180h160v-160H180v160Zm440 0h160v-160H620v160Z\"/>\n",
       "  </svg>\n",
       "    </button>\n",
       "\n",
       "  <style>\n",
       "    .colab-df-container {\n",
       "      display:flex;\n",
       "      gap: 12px;\n",
       "    }\n",
       "\n",
       "    .colab-df-convert {\n",
       "      background-color: #E8F0FE;\n",
       "      border: none;\n",
       "      border-radius: 50%;\n",
       "      cursor: pointer;\n",
       "      display: none;\n",
       "      fill: #1967D2;\n",
       "      height: 32px;\n",
       "      padding: 0 0 0 0;\n",
       "      width: 32px;\n",
       "    }\n",
       "\n",
       "    .colab-df-convert:hover {\n",
       "      background-color: #E2EBFA;\n",
       "      box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
       "      fill: #174EA6;\n",
       "    }\n",
       "\n",
       "    .colab-df-buttons div {\n",
       "      margin-bottom: 4px;\n",
       "    }\n",
       "\n",
       "    [theme=dark] .colab-df-convert {\n",
       "      background-color: #3B4455;\n",
       "      fill: #D2E3FC;\n",
       "    }\n",
       "\n",
       "    [theme=dark] .colab-df-convert:hover {\n",
       "      background-color: #434B5C;\n",
       "      box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
       "      filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
       "      fill: #FFFFFF;\n",
       "    }\n",
       "  </style>\n",
       "\n",
       "    <script>\n",
       "      const buttonEl =\n",
       "        document.querySelector('#df-0bac63c6-10c4-4325-a4cc-832a39e6c34c button.colab-df-convert');\n",
       "      buttonEl.style.display =\n",
       "        google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
       "\n",
       "      async function convertToInteractive(key) {\n",
       "        const element = document.querySelector('#df-0bac63c6-10c4-4325-a4cc-832a39e6c34c');\n",
       "        const dataTable =\n",
       "          await google.colab.kernel.invokeFunction('convertToInteractive',\n",
       "                                                    [key], {});\n",
       "        if (!dataTable) return;\n",
       "\n",
       "        const docLinkHtml = 'Like what you see? Visit the ' +\n",
       "          '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
       "          + ' to learn more about interactive tables.';\n",
       "        element.innerHTML = '';\n",
       "        dataTable['output_type'] = 'display_data';\n",
       "        await google.colab.output.renderOutput(dataTable, element);\n",
       "        const docLink = document.createElement('div');\n",
       "        docLink.innerHTML = docLinkHtml;\n",
       "        element.appendChild(docLink);\n",
       "      }\n",
       "    </script>\n",
       "  </div>\n",
       "\n",
       "\n",
       "<div id=\"df-10556c15-7a3a-466e-99be-17fb8778e92f\">\n",
       "  <button class=\"colab-df-quickchart\" onclick=\"quickchart('df-10556c15-7a3a-466e-99be-17fb8778e92f')\"\n",
       "            title=\"Suggest charts\"\n",
       "            style=\"display:none;\">\n",
       "\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
       "     width=\"24px\">\n",
       "    <g>\n",
       "        <path d=\"M19 3H5c-1.1 0-2 .9-2 2v14c0 1.1.9 2 2 2h14c1.1 0 2-.9 2-2V5c0-1.1-.9-2-2-2zM9 17H7v-7h2v7zm4 0h-2V7h2v10zm4 0h-2v-4h2v4z\"/>\n",
       "    </g>\n",
       "</svg>\n",
       "  </button>\n",
       "\n",
       "<style>\n",
       "  .colab-df-quickchart {\n",
       "      --bg-color: #E8F0FE;\n",
       "      --fill-color: #1967D2;\n",
       "      --hover-bg-color: #E2EBFA;\n",
       "      --hover-fill-color: #174EA6;\n",
       "      --disabled-fill-color: #AAA;\n",
       "      --disabled-bg-color: #DDD;\n",
       "  }\n",
       "\n",
       "  [theme=dark] .colab-df-quickchart {\n",
       "      --bg-color: #3B4455;\n",
       "      --fill-color: #D2E3FC;\n",
       "      --hover-bg-color: #434B5C;\n",
       "      --hover-fill-color: #FFFFFF;\n",
       "      --disabled-bg-color: #3B4455;\n",
       "      --disabled-fill-color: #666;\n",
       "  }\n",
       "\n",
       "  .colab-df-quickchart {\n",
       "    background-color: var(--bg-color);\n",
       "    border: none;\n",
       "    border-radius: 50%;\n",
       "    cursor: pointer;\n",
       "    display: none;\n",
       "    fill: var(--fill-color);\n",
       "    height: 32px;\n",
       "    padding: 0;\n",
       "    width: 32px;\n",
       "  }\n",
       "\n",
       "  .colab-df-quickchart:hover {\n",
       "    background-color: var(--hover-bg-color);\n",
       "    box-shadow: 0 1px 2px rgba(60, 64, 67, 0.3), 0 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
       "    fill: var(--button-hover-fill-color);\n",
       "  }\n",
       "\n",
       "  .colab-df-quickchart-complete:disabled,\n",
       "  .colab-df-quickchart-complete:disabled:hover {\n",
       "    background-color: var(--disabled-bg-color);\n",
       "    fill: var(--disabled-fill-color);\n",
       "    box-shadow: none;\n",
       "  }\n",
       "\n",
       "  .colab-df-spinner {\n",
       "    border: 2px solid var(--fill-color);\n",
       "    border-color: transparent;\n",
       "    border-bottom-color: var(--fill-color);\n",
       "    animation:\n",
       "      spin 1s steps(1) infinite;\n",
       "  }\n",
       "\n",
       "  @keyframes spin {\n",
       "    0% {\n",
       "      border-color: transparent;\n",
       "      border-bottom-color: var(--fill-color);\n",
       "      border-left-color: var(--fill-color);\n",
       "    }\n",
       "    20% {\n",
       "      border-color: transparent;\n",
       "      border-left-color: var(--fill-color);\n",
       "      border-top-color: var(--fill-color);\n",
       "    }\n",
       "    30% {\n",
       "      border-color: transparent;\n",
       "      border-left-color: var(--fill-color);\n",
       "      border-top-color: var(--fill-color);\n",
       "      border-right-color: var(--fill-color);\n",
       "    }\n",
       "    40% {\n",
       "      border-color: transparent;\n",
       "      border-right-color: var(--fill-color);\n",
       "      border-top-color: var(--fill-color);\n",
       "    }\n",
       "    60% {\n",
       "      border-color: transparent;\n",
       "      border-right-color: var(--fill-color);\n",
       "    }\n",
       "    80% {\n",
       "      border-color: transparent;\n",
       "      border-right-color: var(--fill-color);\n",
       "      border-bottom-color: var(--fill-color);\n",
       "    }\n",
       "    90% {\n",
       "      border-color: transparent;\n",
       "      border-bottom-color: var(--fill-color);\n",
       "    }\n",
       "  }\n",
       "</style>\n",
       "\n",
       "  <script>\n",
       "    async function quickchart(key) {\n",
       "      const quickchartButtonEl =\n",
       "        document.querySelector('#' + key + ' button');\n",
       "      quickchartButtonEl.disabled = true;  // To prevent multiple clicks.\n",
       "      quickchartButtonEl.classList.add('colab-df-spinner');\n",
       "      try {\n",
       "        const charts = await google.colab.kernel.invokeFunction(\n",
       "            'suggestCharts', [key], {});\n",
       "      } catch (error) {\n",
       "        console.error('Error during call to suggestCharts:', error);\n",
       "      }\n",
       "      quickchartButtonEl.classList.remove('colab-df-spinner');\n",
       "      quickchartButtonEl.classList.add('colab-df-quickchart-complete');\n",
       "    }\n",
       "    (() => {\n",
       "      let quickchartButtonEl =\n",
       "        document.querySelector('#df-10556c15-7a3a-466e-99be-17fb8778e92f button');\n",
       "      quickchartButtonEl.style.display =\n",
       "        google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
       "    })();\n",
       "  </script>\n",
       "</div>\n",
       "\n",
       "    </div>\n",
       "  </div>\n"
      ],
      "text/plain": [
       "   answer  answer_len\n",
       "0  taxpro           6\n",
       "1    warm           4\n",
       "2   decaf           5\n",
       "3  mussel           6\n",
       "4  aaamap           6"
      ]
     },
     "execution_count": 250,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = open(\"/content/all_answers.txt\").read().splitlines()\n",
    "words_df = pd.DataFrame(words, columns = ['answer'])\n",
    "words_df['answer_len'] = words_df['answer'].apply(len)\n",
    "words_df.head(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "uXQvJZu6qlkb"
   },
   "outputs": [],
   "source": [
    "def get_answers_by_len(answers_df, answer_len, no_samples = 100):\n",
    "    grouped_by_len = answers_df.groupby('answer_len')\n",
    "    out_answers_list = grouped_by_len.get_group(answer_len)['answer'].tolist()\n",
    "    random.shuffle(out_answers_list)\n",
    "    return out_answers_list[:no_samples]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "mDaeSsFgs9yO",
    "outputId": "6faaa24a-02cf-4cc0-e68a-9092b52b873a"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of Custom Answer List before addition:  880\n",
      "Length of Custom Answer List after addition:  948\n"
     ]
    }
   ],
   "source": [
    "date_str = \"1/20/2023\"\n",
    "answer_list, grid = get_grid_answers(date_str)\n",
    "\n",
    "if answer_list is not None:\n",
    "    answer_len_ = set()\n",
    "    for answer in answer_list:\n",
    "        answer_len_.add(len(answer))\n",
    "\n",
    "    custom_answer_list = []\n",
    "    for ans_len in answer_len_:\n",
    "        custom_answer_list.extend(get_answers_by_len(words_df, ans_len, 110))\n",
    "\n",
    "    print('Length of Custom Answer List before addition: ', len(custom_answer_list))\n",
    "\n",
    "    custom_answer_list.extend(answer_list)\n",
    "    print(\"Length of Custom Answer List after addition: \", len(custom_answer_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "4sSWqstpt4V2"
   },
   "source": [
    "Let's now test the hypothesis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 390
    },
    "id": "dQoRBiF88bMt",
    "outputId": "861341e1-536a-4319-f9db-8d4689b0c3fb"
   },
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-282-303675f74b1d>\u001b[0m in \u001b[0;36m<cell line: 5>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;31m# creator = CrosswordCreator(crossword)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0mcreator\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mCrosswordParallelSolver\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcrossword\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdo_random\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m \u001b[0massignment\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcreator\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msolve\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0mend_t\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtime\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36msolve\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m    248\u001b[0m         \u001b[0;31m# self.enforce_node_consistency() # already being handled during initialization\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    249\u001b[0m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mac3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 250\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    251\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    252\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0menforce_node_consistency\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    475\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 476\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    478\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mbacktrack\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    473\u001b[0m             \u001b[0mnew_assignment\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0massignment\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcopy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    474\u001b[0m             \u001b[0mnew_assignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 475\u001b[0;31m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconsistent\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    476\u001b[0m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbacktrack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnew_assignment\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    477\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mconsistent\u001b[0;34m(self, assignment)\u001b[0m\n\u001b[1;32m    350\u001b[0m                 \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    351\u001b[0m             \u001b[0mvalues\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mword\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 352\u001b[0;31m             \u001b[0;32mfor\u001b[0m \u001b[0mneighbor\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcrossword\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    353\u001b[0m                 \u001b[0moverlap\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcrossword\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0moverlaps\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mneighbor\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    354\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mneighbor\u001b[0m \u001b[0;32min\u001b[0m \u001b[0massignment\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0massignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0moverlap\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0massignment\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mneighbor\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0moverlap\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36mneighbors\u001b[0;34m(self, var)\u001b[0m\n\u001b[1;32m    135\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mneighbors\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvar\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    136\u001b[0m         \u001b[0;34m\"\"\"Given a variable, return set of overlapping variables.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 137\u001b[0;31m         return set(\n\u001b[0m\u001b[1;32m    138\u001b[0m             \u001b[0mv\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mv\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvariables\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    139\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mv\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mvar\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0moverlaps\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36m<genexpr>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m    137\u001b[0m         return set(\n\u001b[1;32m    138\u001b[0m             \u001b[0mv\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mv\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvariables\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 139\u001b[0;31m             \u001b[0;32mif\u001b[0m \u001b[0mv\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mvar\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0moverlaps\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    140\u001b[0m         )\n\u001b[1;32m    141\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-241-7ff80031307c>\u001b[0m in \u001b[0;36m__eq__\u001b[0;34m(self, other)\u001b[0m\n\u001b[1;32m     20\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mhash\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdirection\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlength\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     21\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 22\u001b[0;31m     \u001b[0;32mdef\u001b[0m \u001b[0m__eq__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mother\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     23\u001b[0m         return (\n\u001b[1;32m     24\u001b[0m             \u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mi\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mother\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mand\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "start_t = time.time()\n",
    "crossword = Crossword(grid, custom_answer_list, False)\n",
    "# creator = CrosswordCreator(crossword)\n",
    "creator = CrosswordParallelSolver(crossword, do_random = True)\n",
    "assignment = creator.solve()\n",
    "end_t = time.time()\n",
    "\n",
    "print(\"Total time taken: \", end_t - start_t)\n",
    "assignment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "gVPjNObw3S1c",
    "outputId": "ec28632d-b4bb-466b-810f-05f0da60ac0c"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "66\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "66"
      ]
     },
     "execution_count": 220,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = open(\"/content/all_answers.txt\").read().splitlines()\n",
    "print(len(answer_list))\n",
    "\n",
    "counter = 0\n",
    "for ans in answer_list:\n",
    "    if ans.lower() in words:\n",
    "        counter += 1\n",
    "counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "eQp5DRcLyLKX",
    "outputId": "f8d724a0-9bfb-4527-ec30-b31a98085b1e"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "1777it [01:37, 18.21it/s]\n"
     ]
    }
   ],
   "source": [
    "for i, state in tqdm(enumerate(creator.states), ncols = 70):\n",
    "    creator.save(state, f\"/content/Images 4x4/output_4x4_{i}.png\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "r-S7AQFCwHu-"
   },
   "outputs": [],
   "source": [
    "creator.save(assignment, '/content/output_21x21_1.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "3kJ6qEtFzRUg"
   },
   "source": [
    "<b> Lets make a gif out of this"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "QnexLqMbwxvO",
    "outputId": "930733b6-d36e-442e-d3e9-da450534984a"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████| 1777/1777 [00:00<00:00, 10534.18it/s]\n"
     ]
    }
   ],
   "source": [
    "def sort_by_last_digit(filename):\n",
    "    last_digit = int(filename.split('_')[-1].split('.')[0])\n",
    "    return last_digit\n",
    "\n",
    "def create_gif(images_folder, output_gif_path):\n",
    "    image_files = sorted([f for f in os.listdir(images_folder) if f.endswith(('.png', '.jpg', '.jpeg', '.gif'))])\n",
    "    image_files = sorted(image_files, key = sort_by_last_digit)\n",
    "\n",
    "    images = []\n",
    "    for image_file in tqdm(image_files, ncols = 50):\n",
    "        image_path = os.path.join(images_folder, image_file)\n",
    "        img = Image.open(image_path)\n",
    "        images.append(img)\n",
    "\n",
    "    images[0].save(output_gif_path, save_all=True, append_images=images[1:], duration = 40, loop = 0)\n",
    "\n",
    "images_folder = \"/content/Images 4x4\"\n",
    "output_gif_path = \"/content/output 4x4_1.gif\"\n",
    "\n",
    "create_gif(images_folder, output_gif_path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "WtJkp0VkH7X2",
    "outputId": "4538b608-d116-4553-dfa9-867994d5e73a"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total time taken by list comprehension:  5.096344947814941 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['haabs', 'hambo', 'halbe']"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocabulary = open(\"/content/all_answers.txt\").read().splitlines()\n",
    "\n",
    "vocabulary = [word for word in vocabulary if len(word) == 5]\n",
    "\n",
    "t_time = 0\n",
    "for _ in range(10):\n",
    "    start_t = time.time()\n",
    "    filtered_words = [word for word in vocabulary if word[0] == 'h' and word[1] == 'a' and word[3] == 'b']\n",
    "    end_t = time.time()\n",
    "    t_time += end_t - start_t\n",
    "print(\"Total time taken by list comprehension: \", t_time / 10 * 1000, \"ms\")\n",
    "filtered_words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "opyCNymx1iZ5",
    "outputId": "5304187d-71ba-4833-edf8-ad897eb5ab5e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total time taken by regex:  18.933749198913574 ms\n"
     ]
    }
   ],
   "source": [
    "t_time = 0\n",
    "\n",
    "for _ in range(10):\n",
    "    start_t = time.time()\n",
    "    pattern = re.compile(r'h.{1}a.{1}b')\n",
    "    filtered_words = [word for word in vocabulary if pattern.match(word)]\n",
    "    end_t = time.time()\n",
    "    t_time += end_t - start_t\n",
    "print(\"Total time taken by regex: \", t_time / 10 * 1000, 'ms')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "7Khb8LxjJZgh",
    "outputId": "a2a6fc01-fdf7-40e8-dc03-46e87f59b1f1"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(30213, 5)\n",
      "Total time taken by numpy:  13.385152816772461 ms\n",
      "<class 'list'>\n"
     ]
    }
   ],
   "source": [
    "words = open(\"/content/all_answers.txt\").read().splitlines()\n",
    "\n",
    "t_time = 0\n",
    "words = [word for word in words if len(word) == 5]\n",
    "\n",
    "char_array = np.array([list(word) for word in words])\n",
    "print(char_array.shape)\n",
    "\n",
    "for _ in range(10):\n",
    "    start_t = time.time()\n",
    "    vocabulary = np.array(words)\n",
    "    condition = (char_array[:, 0] == 'h') & (char_array[:, 1] == 'a') & (char_array[:, 3] == 'b')\n",
    "    filtered_words = vocabulary[condition].tolist()\n",
    "    end_t = time.time()\n",
    "    t_time += end_t - start_t\n",
    "\n",
    "print(\"Total time taken by numpy: \", t_time / 10 * 1000, 'ms')\n",
    "print(type(filtered_words))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "G7WOn9KzLZDk"
   },
   "source": [
    "So, among various retrieval method for given pattern, i find that if the char_array is previously-given then numpy method is the fastest and efficeint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ZHwrorPSLjVX"
   },
   "outputs": [],
   "source": [
    "class Variable():\n",
    "\n",
    "    ACROSS = \"across\"\n",
    "    DOWN = \"down\"\n",
    "\n",
    "    def __init__(self, i, j, direction, length):\n",
    "        \"\"\"Create a new variable with starting point, direction, and length.\"\"\"\n",
    "        self.i = i\n",
    "        self.j = j\n",
    "        self.direction = direction\n",
    "        self.length = length\n",
    "        self.cells = []\n",
    "        for k in range(self.length):\n",
    "            self.cells.append(\n",
    "                (self.i + (k if self.direction == Variable.DOWN else 0),\n",
    "                 self.j + (k if self.direction == Variable.ACROSS else 0))\n",
    "            )\n",
    "\n",
    "    def __hash__(self):\n",
    "        return hash((self.i, self.j, self.direction, self.length))\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return (\n",
    "            (self.i == other.i) and\n",
    "            (self.j == other.j) and\n",
    "            (self.direction == other.direction) and\n",
    "            (self.length == other.length)\n",
    "        )\n",
    "\n",
    "    def __str__(self):\n",
    "        return f\"({self.i}, {self.j}) {self.direction} : {self.length}\"\n",
    "\n",
    "    def __repr__(self):\n",
    "        direction = repr(self.direction)\n",
    "        return f\"Variable({self.i}, {self.j}, {direction}, {self.length})\"\n",
    "\n",
    "class Crossword():\n",
    "    def __init__(self, grid, words_file, file_path = True):\n",
    "        self.structure = []\n",
    "\n",
    "        self.height = len(grid) # the number of rows in the grid\n",
    "        self.width = len(grid[0]) # the number of columns in the grid\n",
    "        for i in range(len(grid)):\n",
    "            row = []\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == '':\n",
    "                  row.append(False)\n",
    "                else:\n",
    "                  row.append(True)\n",
    "            self.structure.append(row)\n",
    "\n",
    "        if not file_path:\n",
    "            self.words = [word.upper() for word in words_file]\n",
    "\n",
    "        else:\n",
    "            # Save vocabulary list\n",
    "            with open(words_file) as f:\n",
    "                self.words = set(f.read().upper().splitlines()) # to remove all the duplicates\n",
    "                self.words = list(self.words)\n",
    "                for _ in range(5):\n",
    "                    random.shuffle(self.words)\n",
    "            self.words = set(self.words)\n",
    "\n",
    "        # Determine variable set\n",
    "        self.variables = set()\n",
    "\n",
    "        for i in range(self.height):\n",
    "            for j in range(self.width):\n",
    "\n",
    "                # Vertical words\n",
    "                starts_word = (\n",
    "                    self.structure[i][j]\n",
    "                    and (i == 0 or not self.structure[i - 1][j])\n",
    "                )\n",
    "                if starts_word:\n",
    "                    length = 1\n",
    "                    for k in range(i + 1, self.height):\n",
    "                        if self.structure[k][j]:\n",
    "                            length += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    if length > 1:\n",
    "                        self.variables.add(Variable(\n",
    "                            i=i, j=j,\n",
    "                            direction=Variable.DOWN,\n",
    "                            length=length\n",
    "                        ))\n",
    "\n",
    "                # Horizontal words\n",
    "                starts_word = (\n",
    "                    self.structure[i][j]\n",
    "                    and (j == 0 or not self.structure[i][j - 1])\n",
    "                )\n",
    "                if starts_word:\n",
    "                    length = 1\n",
    "                    for k in range(j + 1, self.width):\n",
    "                        if self.structure[i][k]:\n",
    "                            length += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    if length > 1:\n",
    "                        self.variables.add(Variable(\n",
    "                            i=i, j=j,\n",
    "                            direction=Variable.ACROSS,\n",
    "                            length=length\n",
    "                        ))\n",
    "\n",
    "        # Compute overlaps for each word\n",
    "        # For any pair of variables v1, v2, their overlap is either:\n",
    "        #    None, if the two variables do not overlap; or\n",
    "        #    (i, j), where v1's ith character overlaps v2's jth character\n",
    "        self.overlaps = dict()\n",
    "        self.overlaps_positions = dict()\n",
    "        for v1 in self.variables:\n",
    "            for v2 in self.variables:\n",
    "                if v1 == v2:\n",
    "                    continue\n",
    "                cells1 = v1.cells\n",
    "                cells2 = v2.cells\n",
    "                intersection = set(cells1).intersection(cells2)\n",
    "                if not intersection:\n",
    "                    self.overlaps[v1, v2] = None\n",
    "                else:\n",
    "                    intersection = intersection.pop()\n",
    "                    self.overlaps[v1, v2] = (\n",
    "                        cells1.index(intersection),\n",
    "                        cells2.index(intersection)\n",
    "                    )\n",
    "                    for cell in cells1:\n",
    "                        for cell_ in cells2:\n",
    "                            if cell == cell_:\n",
    "                                self.overlaps_positions[v1, v2] = cell\n",
    "                                break\n",
    "\n",
    "    def neighbors(self, var):\n",
    "        \"\"\"Given a variable, return set of overlapping variables.\"\"\"\n",
    "        return set(\n",
    "            v for v in self.variables\n",
    "            if v != var and self.overlaps[v, var]\n",
    "        )\n",
    "\n",
    "class CrosswordCreator():\n",
    "\n",
    "    def __init__(self, crossword, n = None):\n",
    "        \"\"\"\n",
    "        Create new CSP crossword generate.\n",
    "        \"\"\"\n",
    "        self.crossword = crossword\n",
    "        self.ASSIGNMENT_COUNT = 0\n",
    "        self.states = []\n",
    "        self.no_values = n\n",
    "        # setting up the domains for each of the variables\n",
    "        self.domains = {\n",
    "            var: self.get_required_length_answers(var.length)\n",
    "            for var in self.crossword.variables\n",
    "        }\n",
    "\n",
    "    # enforcing the node consistency here\n",
    "    def get_required_length_answers(self, ans_length):\n",
    "        output = []\n",
    "        for word in self.crossword.words:\n",
    "            if len(word) == ans_length:\n",
    "                output.append(word)\n",
    "        random.shuffle(output)\n",
    "        # output = output[:self.no_values]\n",
    "        return output\n",
    "\n",
    "    def letter_grid(self, assignment):\n",
    "        \"\"\"\n",
    "        Return 2D array representing a given assignment.\n",
    "        \"\"\"\n",
    "        letters = [\n",
    "            [None for _ in range(self.crossword.width)]\n",
    "            for _ in range(self.crossword.height)\n",
    "        ]\n",
    "        for variable, word in assignment.items():\n",
    "            direction = variable.direction\n",
    "            for k in range(len(word)):\n",
    "                i = variable.i + (k if direction == Variable.DOWN else 0)\n",
    "                j = variable.j + (k if direction == Variable.ACROSS else 0)\n",
    "                letters[i][j] = word[k]\n",
    "        return letters\n",
    "\n",
    "    def print(self, assignment):\n",
    "        \"\"\"\n",
    "        Print crossword assignment to the terminal.\n",
    "        \"\"\"\n",
    "        letters = self.letter_grid(assignment)\n",
    "        for i in range(self.crossword.height):\n",
    "            for j in range(self.crossword.width):\n",
    "                if self.crossword.structure[i][j]:\n",
    "                    print(letters[i][j] or \" \", end=\"\")\n",
    "                else:\n",
    "                    print(\"██\", end=\"\")\n",
    "            print()\n",
    "\n",
    "    def save(self, assignment, filename):\n",
    "        \"\"\"\n",
    "        Save crossword assignment to an image file.\n",
    "        \"\"\"\n",
    "        from PIL import Image, ImageDraw, ImageFont\n",
    "        cell_size = 100\n",
    "        cell_border = 2\n",
    "        interior_size = cell_size - 2 * cell_border\n",
    "        letters = self.letter_grid(assignment)\n",
    "\n",
    "        # Create a blank canvas\n",
    "        img = Image.new(\n",
    "            \"RGBA\",\n",
    "            (self.crossword.width * cell_size,\n",
    "             self.crossword.height * cell_size),\n",
    "            \"black\"\n",
    "        )\n",
    "        font = ImageFont.truetype(\"/content/Roboto-Regular.ttf\", 80)\n",
    "        draw = ImageDraw.Draw(img)\n",
    "\n",
    "        for i in range(self.crossword.height):\n",
    "            for j in range(self.crossword.width):\n",
    "\n",
    "                rect = [\n",
    "                    (j * cell_size + cell_border,\n",
    "                     i * cell_size + cell_border),\n",
    "                    ((j + 1) * cell_size - cell_border,\n",
    "                     (i + 1) * cell_size - cell_border)\n",
    "                ]\n",
    "                if self.crossword.structure[i][j]:\n",
    "                    draw.rectangle(rect, fill=\"white\")\n",
    "                    if letters[i][j]:\n",
    "                        _, _, w, h = draw.textbbox((0, 0), letters[i][j], font=font)\n",
    "                        draw.text(\n",
    "                            (rect[0][0] + ((interior_size - w) / 2),\n",
    "                             rect[0][1] + ((interior_size - h) / 2) - 10),\n",
    "                            letters[i][j], fill=\"black\", font=font\n",
    "                        )\n",
    "        img.save(filename)\n",
    "\n",
    "    ### here starts the main solving category\n",
    "    def solve(self):\n",
    "        \"\"\"\n",
    "        Enforce node and arc consistency, and then solve the CSP.\n",
    "        \"\"\"\n",
    "        # self.enforce_node_consistency() # already being handled during initialization\n",
    "        self.ac3()\n",
    "        return self.backtrack(dict())\n",
    "\n",
    "    def enforce_node_consistency(self):\n",
    "        \"\"\"\n",
    "        Update `self.domains` such that each variable is node-consistent.\n",
    "        (Remove any values that are inconsistent with a variable's unary\n",
    "         constraints; in this case, the length of the word.)\n",
    "        \"\"\"\n",
    "        for variable in self.crossword.variables:\n",
    "            valid_words = set()\n",
    "            for word in self.domains[variable]:\n",
    "                if len(word) == variable.length:\n",
    "                    valid_words.add(word)\n",
    "            self.domains[variable] = valid_words\n",
    "\n",
    "    def revise(self, x, y):\n",
    "        \"\"\"\n",
    "            Make variable `x` arc consistent with variable `y`.\n",
    "            To do so, remove values from `self.domains[x]` for which there is no\n",
    "            possible corresponding value for `y` in `self.domains[y]`.\n",
    "\n",
    "            Return True if a revision was made to the domain of `x`; return\n",
    "            False if no revision was made.\n",
    "        \"\"\"\n",
    "        revised = False\n",
    "        overlap = self.crossword.overlaps[x, y]\n",
    "        y_chars = {word[overlap[1]] for word in self.domains[y]}  # Precompute the y's second character set\n",
    "        self.domains[x] = {word for word in self.domains[x] if word[overlap[0]] in y_chars}\n",
    "        if len(self.domains[x]) < len(self.domains[y]):\n",
    "            revised = True\n",
    "        return revised\n",
    "\n",
    "    def ac3(self, arcs=None):\n",
    "        if arcs is None:\n",
    "            arcs = deque([(v1, v2) for v1 in self.crossword.variables for v2 in self.crossword.neighbors(v1)])\n",
    "        else:\n",
    "            arcs = deque(arcs)\n",
    "\n",
    "        while arcs:\n",
    "            x, y = arcs.popleft()  # Efficient pop from the left\n",
    "            if self.revise(x, y):\n",
    "                if not self.domains[x][-1]:\n",
    "                    return False\n",
    "                for z in self.crossword.neighbors(x) - {y}:\n",
    "                    arcs.append((z, x))\n",
    "        return True\n",
    "\n",
    "    def assignment_complete(self, assignment):\n",
    "        \"\"\"\n",
    "        Return True if `assignment` is complete (i.e., assigns a value to each\n",
    "        crossword variable); return False otherwise.\n",
    "        \"\"\"\n",
    "        self.ASSIGNMENT_COUNT += 1\n",
    "        # if len(assignment.keys()) / len(self.crossword.variables) >= 0.85:\n",
    "        #     return True\n",
    "        self.states.append(assignment)\n",
    "        complete = True\n",
    "        vars_in_assignment = set(var for var in assignment)\n",
    "        # Checking if all vars in the crossword has been assigned\n",
    "        if vars_in_assignment != self.crossword.variables:\n",
    "            complete = False\n",
    "        for var in assignment:\n",
    "            # making sure no var is empty\n",
    "            assert isinstance(assignment[var], str)\n",
    "            if not assignment[var]:\n",
    "                complete = False\n",
    "        return complete\n",
    "\n",
    "    # phind AI\n",
    "    def consistent(self, assignment):\n",
    "        \"\"\"\n",
    "          Return True if `assignment` is consistent (i.e., words fit in crossword\n",
    "          puzzle without conflicting characters); return False otherwise.\n",
    "        \"\"\"\n",
    "        values = set()\n",
    "        for var, word in assignment.items():\n",
    "            if word in values or len(word) != var.length:\n",
    "                return False\n",
    "            values.add(word)\n",
    "            for neighbor in self.crossword.neighbors(var):\n",
    "                overlap = self.crossword.overlaps[var, neighbor]\n",
    "                if neighbor in assignment and assignment[var][overlap[0]] != assignment[neighbor][overlap[1]]:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def order_domain_values(self, var, assignment, temp_var_domain):\n",
    "        \"\"\"\n",
    "        Return a list of values in the domain of `var`, in order by\n",
    "        the number of values they rule out for neighboring variables.\n",
    "        The first value in the list should be the one that rules out\n",
    "        the fewest values among the neighbors of `var`.\n",
    "        \"\"\"\n",
    "        values_penalty = {value: 0 for value in self.domains[var]}\n",
    "        for neighbor in self.crossword.neighbors(var):\n",
    "            if neighbor not in assignment:\n",
    "                overlap = self.crossword.overlaps[var, neighbor]\n",
    "                for value in temp_var_domain:\n",
    "                    for value2 in self.domains[neighbor]:\n",
    "                        if value[overlap[0]] != value2[overlap[1]]:\n",
    "                            values_penalty[value] += 1\n",
    "\n",
    "        # Use a priority queue (heap) for efficient retrieval of the least constraining values\n",
    "        priority_queue = [(-values_penalty[value], value) for value in temp_var_domain]\n",
    "        heapq.heapify(priority_queue)\n",
    "\n",
    "        return [value for _, value in priority_queue]\n",
    "\n",
    "    def select_unassigned_variable(self, assignment):\n",
    "        \"\"\"\n",
    "        Ordering:\n",
    "          Return an unassigned variable not already part of `assignment`.\n",
    "          Choose the variable with the minimum number of remaining values - MRV\n",
    "          in its domain. If there is a tie, choose the variable with the highest\n",
    "          degree. If there is a tie, any of the tied variables are acceptable\n",
    "          return values.\n",
    "        \"\"\"\n",
    "\n",
    "        var_penalty = {}\n",
    "        for var in self.crossword.variables:\n",
    "            if var not in assignment:\n",
    "                # var_penalty[var] = len(self.domains[var][-1])\n",
    "                var_penalty[var] = var.length\n",
    "        vars = sorted(var_penalty, key= lambda v: var_penalty[v], reverse = True)\n",
    "        # return vars[0]\n",
    "        # if the two first variables have the same domain size\n",
    "        if len(vars) > 1 and var_penalty[vars[0]] == var_penalty[vars[1]]:\n",
    "            # Check number of neighbors and return highest degree\n",
    "            if len(self.crossword.neighbors(vars[0])) < len(self.crossword.neighbors(vars[1])):\n",
    "                return vars[1]\n",
    "        return vars[0]\n",
    "\n",
    "    # # Modify the backtrack method\n",
    "    # def backtrack(self, assignment):\n",
    "    #     \"\"\"\n",
    "    #     Using Backtracking Search, take as input a partial assignment for the\n",
    "    #     crossword and return a complete assignment if possible to do so.\n",
    "\n",
    "    #     `assignment` is a mapping from variables (keys) to words (values).\n",
    "\n",
    "    #     If no assignment is possible, return None.\n",
    "    #     \"\"\"\n",
    "    #     if self.assignment_complete(assignment):\n",
    "    #         return assignment  # base case\n",
    "    #     var = self.select_unassigned_variable(assignment)\n",
    "    #     print(\"Before: \", len(self.domains[var]))\n",
    "    #     if len(assignment.keys()) > 0:\n",
    "    #         for variable in self.crossword.variables:\n",
    "    #             if var == variable:\n",
    "    #                 continue\n",
    "    #             if variable in assignment.keys():\n",
    "    #                 overlap = self.crossword.overlaps[var, variable]\n",
    "    #                 # overlap[1] -> index of the overlapping letter in the y i.e. Variable\n",
    "    #                 # overlap[0] -> index of the overlapping letter in the x i.e. var\n",
    "    #                 if overlap:\n",
    "    #                     ref_cross_section_word = assignment[variable]\n",
    "    #                     ref_intersection_letter = ref_cross_section_word[overlap[1]]\n",
    "    #                     # i.e. in the var domain there should be letter 'ref_intersection_letter' in the overlap[0] position\n",
    "    #                     self.domains[var] = [word for word in self.domains[var] if word[overlap[0]] == ref_intersection_letter]\n",
    "\n",
    "    #     # for value in self.order_domain_values(var, assignment):\n",
    "    #     print(\"After: \", len(self.domains[var]))\n",
    "    #     new_assignment = assignment.copy()\n",
    "    #     for value in self.domains[var]:\n",
    "    #          # or dict(assignment)\n",
    "    #         new_assignment[var] = value\n",
    "    #         if self.consistent(new_assignment):\n",
    "    #             result = self.backtrack(new_assignment)\n",
    "    #             if result is not None:\n",
    "    #                 return result\n",
    "    #     return None\n",
    "\n",
    "    def backtrack(self, assignment):\n",
    "        \"\"\"\n",
    "        Using Backtracking Search, take as input a partial assignment for the\n",
    "        crossword and return a complete assignment if possible to do so.\n",
    "\n",
    "        `assignment` is a mapping from variables (keys) to words (values).\n",
    "\n",
    "        If no assignment is possible, return None.\n",
    "        \"\"\"\n",
    "        if self.assignment_complete(assignment):\n",
    "            return assignment  # base case\n",
    "\n",
    "        var = self.select_unassigned_variable(assignment)\n",
    "\n",
    "        # print(\"Before: \", len(self.domains[var]))\n",
    "\n",
    "        # Create a copy of self.domains for this branch\n",
    "        original_domains = {var: set(words) for var, words in self.domains.items()}\n",
    "\n",
    "\n",
    "        # original_domain = set(self.domains[var][-1])\n",
    "\n",
    "        did_shorten_domain = False\n",
    "\n",
    "        if len(assignment.keys()) > 0:\n",
    "            for variable in self.crossword.variables:\n",
    "                if var == variable:\n",
    "                    continue\n",
    "\n",
    "                if variable in assignment.keys():\n",
    "                    overlap = self.crossword.overlaps[var, variable]\n",
    "                    if overlap:\n",
    "                        ref_cross_section_word = assignment[variable]\n",
    "                        ref_intersection_letter = ref_cross_section_word[overlap[1]]\n",
    "                        # Filter the words in the domain of var\n",
    "\n",
    "                        self.domains[var] = {word for word in self.domains[var] if word[overlap[0]] == ref_intersection_letter}\n",
    "                        did_shorten_domain = True\n",
    "\n",
    "                        # self.domains[var].append({word for word in self.domains[var][-1] if word[overlap[0]] == ref_intersection_letter})\n",
    "\n",
    "        # print(\"After: \", len(self.domains[var]))\n",
    "\n",
    "        new_assignment = assignment.copy()\n",
    "        for value in self.domains[var]:\n",
    "            # Use the original_domains during recursive calls\n",
    "            self.domains = original_domains.copy()\n",
    "            new_assignment[var] = value\n",
    "            if self.consistent(new_assignment):\n",
    "                # self.domains[var].append(original_domain.copy())\n",
    "                result = self.backtrack(new_assignment)\n",
    "\n",
    "                if result is not None:\n",
    "                    return result\n",
    "\n",
    "        # if did_shorten_domain:\n",
    "        #     self.domains[var].pop()\n",
    "        return None\n"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyPy4GGZIhlnzVzVy4ncXLCM",
   "include_colab_link": true,
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}