solver.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from functools import cache\n",
    "from itertools import zip_longest\n",
    "import sys\n",
    "\n",
    "%load_ext line_profiler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "129\n"
     ]
    }
   ],
   "source": [
    "class Piece():\n",
    "  h_edges: np.ndarray[np.uint8, np.uint8]\n",
    "  v_edges: np.ndarray[np.uint8, np.uint8]\n",
    "  h_height: int\n",
    "  h_width: int\n",
    "  v_height: int\n",
    "  v_width: int\n",
    "\n",
    "  def __init__(self, h_edges: tuple[tuple[bool]] | np.ndarray[np.uint8, np.uint8], v_edges: tuple[tuple[bool]] | np.ndarray[np.uint8, np.uint8]):\n",
    "    h_edges = np.asarray(h_edges)\n",
    "    v_edges = np.asarray(v_edges)\n",
    "\n",
    "    # Trim piece to size\n",
    "    while h_edges.size and ~np.any(h_edges[-1]) and v_edges.size and ~np.any(v_edges[-1]):\n",
    "       h_edges = h_edges[:-1]\n",
    "       v_edges = v_edges[:-1]\n",
    "\n",
    "    while h_edges.size and ~np.any(h_edges[:,-1]) and v_edges.size and ~np.any(v_edges[:,-1]):\n",
    "       h_edges = h_edges[:,:-1]\n",
    "       v_edges = v_edges[:,:-1]\n",
    "    \n",
    "    # Edge case: when all h_edges or v_edges are trimmed from one side\n",
    "    self.h_height = 0 if not h_edges.size else h_edges.shape[0]\n",
    "    self.h_width = 0 if not h_edges.size else h_edges.shape[1]\n",
    "    self.v_height = 0 if not v_edges.size else v_edges.shape[0]\n",
    "    self.v_width = 0 if not v_edges.size else v_edges.shape[1]\n",
    "    self.h_edges = np.packbits(h_edges, axis=0)\n",
    "    self.v_edges = np.packbits(v_edges, axis=0)\n",
    "\n",
    "  def __repr__(self):\n",
    "    h_edges = np.unpackbits(self.h_edges, axis=0, count=self.h_height)\n",
    "    v_edges = np.unpackbits(self.v_edges, axis=0, count=self.v_height)\n",
    "    buffer = []\n",
    "    for h_row, v_row in zip_longest(h_edges, v_edges):\n",
    "        if h_row is not None:\n",
    "          buffer.append(\" \" + \" \".join('-' if h_edge else ' ' for h_edge in h_row))\n",
    "        if v_row is not None:\n",
    "          buffer.append(\" \".join('|' if v_edge else ' ' for v_edge in v_row))\n",
    "    return \"\\n\".join(buffer)\n",
    "  \n",
    "  def __hash__(self):\n",
    "     return hash((tuple(self.h_edges.flatten()), tuple(self.v_edges.flatten())))\n",
    "\n",
    "  def __eq__(self, other):\n",
    "      if isinstance(other, Piece):\n",
    "          return np.array_equal(self.h_edges, other.h_edges) and np.array_equal(self.v_edges, other.v_edges)\n",
    "      return NotImplemented\n",
    "    \n",
    "  def rotated(self):\n",
    "    unpacked_h_edges = np.unpackbits(self.h_edges, axis=0, count=self.h_height)\n",
    "    unpacked_v_edges = np.unpackbits(self.v_edges, axis=0, count=self.v_height)\n",
    "\n",
    "    h_edges = np.rot90(unpacked_v_edges, 1)\n",
    "    v_edges = np.rot90(unpacked_h_edges, 1)\n",
    "\n",
    "    while h_edges.size and ~np.any(h_edges[0]) and v_edges.size and ~np.any(v_edges[0]):\n",
    "      # top row is empty, so we can shift digit up\n",
    "      h_edges = np.roll(h_edges, -1, 0)\n",
    "      v_edges = np.roll(v_edges, -1, 0)\n",
    "\n",
    "    return Piece(h_edges, v_edges)\n",
    "  \n",
    "  @cache\n",
    "  def rotations(self):\n",
    "    a = self\n",
    "    b = a.rotated()\n",
    "    c = b.rotated()\n",
    "    d = c.rotated()\n",
    "    return set((a, b, c, d))\n",
    "\n",
    "pieces = [\n",
    "  Piece(h_edges=((True, False), (True, False), (False, False)), v_edges=((True, True, False), (False, False, False))),\n",
    "  Piece(h_edges=((False, False), (False, False), (False, False)), v_edges=((True, False, False), (True, False, False))),\n",
    "  Piece(h_edges=((True, False), (True, False), (True, False)), v_edges=((False, True, False), (True, False, False))),\n",
    "  Piece(h_edges=((True, False), (True, False), (True, False)), v_edges=((False, True, False), (False, True, False))),\n",
    "  Piece(h_edges=((False, False), (True, False), (False, False)), v_edges=((True, True, False), (False, True, False))),\n",
    "  Piece(h_edges=((True, False), (True, False), (True, False)), v_edges=((True, False, False), (False, True, False))),\n",
    "  Piece(h_edges=((True, False), (True, False), (True, False)), v_edges=((True, False, False), (True, True, False))),\n",
    "  Piece(h_edges=((True, False), (False, False), (False, False)), v_edges=((False, True, False), (False, True, False))),\n",
    "  Piece(h_edges=((True, False), (True, False), (True, False)), v_edges=((True, True, False), (True, True, False))),\n",
    "  Piece(h_edges=((True, False), (True, False), (True, False)), v_edges=((True, True, False), (False, True, False))),\n",
    "]\n",
    "\n",
    "print(sys.getsizeof(pieces[0].h_edges))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       " -\n",
       "| |\n",
       " -"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pieces[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "|\n",
       "|"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pieces[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{   -\n",
       " | | |\n",
       "  - -,\n",
       "  -\n",
       " |  \n",
       "  -\n",
       " | |\n",
       "  -,\n",
       "  -\n",
       " | |\n",
       "  -\n",
       "   |\n",
       "  -,\n",
       "  - -\n",
       " | | |\n",
       "  -  }"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pieces[9].rotations()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ -\n",
       " | |\n",
       "  -}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pieces[0].rotations()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Puzzle():\n",
    "  H_HEIGHT = 5\n",
    "  H_WIDTH = 5\n",
    "  V_HEIGHT = 4\n",
    "  V_WIDTH = 6\n",
    "  h_edges: np.ndarray[np.uint8, np.uint8]\n",
    "  v_edges: np.ndarray[np.uint8, np.uint8]\n",
    "\n",
    "  def __init__(\n",
    "      self,\n",
    "      h_edges=np.packbits(np.zeros((H_HEIGHT,H_WIDTH), dtype=np.uint8), axis=0),\n",
    "      v_edges=np.packbits(np.zeros((V_HEIGHT,V_WIDTH), dtype=np.uint8), axis=0),\n",
    "    ):\n",
    "    self.h_edges = h_edges\n",
    "    self.v_edges = v_edges\n",
    "\n",
    "  def __repr__(self):\n",
    "    h_edges = np.unpackbits(self.h_edges, axis=0, count=self.H_HEIGHT)\n",
    "    v_edges = np.unpackbits(self.v_edges, axis=0, count=self.V_HEIGHT)\n",
    "    buffer = []  \n",
    "    for h_row, v_row in zip_longest(h_edges, v_edges):\n",
    "        if h_row is not None:\n",
    "          buffer.append(\" \" + \" \".join('-' if h_edge else '.' for h_edge in h_row))\n",
    "        if v_row is not None:\n",
    "          buffer.append(\" \".join('|' if v_edge else '.' for v_edge in v_row))\n",
    "    return \"\\n\".join(buffer)\n",
    "\n",
    "  def __hash__(self):\n",
    "    return hash((tuple(self.h_edges.flatten()), tuple(self.v_edges.flatten())))\n",
    "\n",
    "  def __eq__(self, other):\n",
    "    if isinstance(other, Puzzle):\n",
    "        return np.array_equal(self.h_edges, other.h_edges) and np.array_equal(self.v_edges, other.v_edges)\n",
    "    return NotImplemented\n",
    "\n",
    "  def with_piece(self, piece: Piece, v_offset: int, h_offset: int) -> \"Puzzle\":\n",
    "    if (v_offset + piece.h_height > self.H_HEIGHT):\n",
    "      return None\n",
    "    if (h_offset + piece.h_width > self.H_WIDTH):\n",
    "      return None\n",
    "    if (v_offset + piece.v_height > self.V_HEIGHT):\n",
    "      return None\n",
    "    if (h_offset + piece.v_width > self.V_WIDTH):\n",
    "      return None\n",
    "    \n",
    "    mask_h_edges = np.zeros_like(self.h_edges)\n",
    "    if piece.h_edges.size:\n",
    "      mask_h_edges[:,h_offset:h_offset+piece.h_edges.shape[1]] = piece.h_edges >> v_offset\n",
    "\n",
    "    mask_v_edges = np.zeros_like(self.v_edges)\n",
    "    if piece.v_edges.size:\n",
    "      mask_v_edges[:,h_offset:h_offset+piece.v_edges.shape[1]] = piece.v_edges >> v_offset\n",
    "\n",
    "    if np.any(np.bitwise_and(self.h_edges, mask_h_edges)):\n",
    "      return None\n",
    "    if np.any(np.bitwise_and(self.v_edges, mask_v_edges)):\n",
    "      return None\n",
    "\n",
    "    np.bitwise_or(self.h_edges, mask_h_edges, out=mask_h_edges)\n",
    "    np.bitwise_or(self.v_edges, mask_v_edges, out=mask_v_edges)\n",
    "\n",
    "    return Puzzle(mask_h_edges, mask_v_edges)\n",
    "  \n",
    "  def available_spaces(self):\n",
    "    # find top-left corners which are not filled like |-\n",
    "    h_edges = np.unpackbits(self.h_edges, axis=0, count=self.H_HEIGHT)\n",
    "    v_edges = np.unpackbits(self.v_edges, axis=0, count=self.V_HEIGHT)\n",
    "\n",
    "    v_offset = 0\n",
    "    for h_row, v_row in zip_longest(h_edges, v_edges):\n",
    "      if h_row is None:\n",
    "        h_row = (1,) * self.H_WIDTH\n",
    "      if v_row is None:\n",
    "        v_row = (1,) * self.V_WIDTH\n",
    "      \n",
    "      h_offset = 0\n",
    "      for h_edge, v_edge in zip_longest(h_row, v_row):\n",
    "        if not h_edge or not v_edge:\n",
    "          yield (v_offset, h_offset)\n",
    "        h_offset += 1\n",
    "      v_offset += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "78 µs ± 23.3 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit Puzzle().with_piece(pieces[7], 2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timer unit: 1e-07 s\n",
      "\n",
      "Total time: 0.0002883 s\n",
      "File: C:\\Users\\Vidminas\\AppData\\Local\\Temp\\ipykernel_21544\\2184434142.py\n",
      "Function: with_piece at line 36\n",
      "\n",
      "Line #      Hits         Time  Per Hit   % Time  Line Contents\n",
      "==============================================================\n",
      "    36                                             def with_piece(self, piece: Piece, v_offset: int, h_offset: int) -> \"Puzzle\":\n",
      "    37         1         40.0     40.0      1.4      if (v_offset + piece.h_height > self.H_HEIGHT):\n",
      "    38                                                 return None\n",
      "    39         1         13.0     13.0      0.5      if (h_offset + piece.h_width > self.H_WIDTH):\n",
      "    40                                                 return None\n",
      "    41         1         14.0     14.0      0.5      if (v_offset + piece.v_height > self.V_HEIGHT):\n",
      "    42                                                 return None\n",
      "    43         1         10.0     10.0      0.3      if (h_offset + piece.v_width > self.V_WIDTH):\n",
      "    44                                                 return None\n",
      "    45                                               \n",
      "    46         1        562.0    562.0     19.5      mask_h_edges = np.zeros_like(self.h_edges)\n",
      "    47         1         26.0     26.0      0.9      if piece.h_edges.size:\n",
      "    48         1        661.0    661.0     22.9        mask_h_edges[:,h_offset:h_offset+piece.h_edges.shape[1]] = piece.h_edges >> v_offset\n",
      "    49                                           \n",
      "    50         1        263.0    263.0      9.1      mask_v_edges = np.zeros_like(self.v_edges)\n",
      "    51         1         12.0     12.0      0.4      if piece.v_edges.size:\n",
      "    52         1        187.0    187.0      6.5        mask_v_edges[:,h_offset:h_offset+piece.v_edges.shape[1]] = piece.v_edges >> v_offset\n",
      "    53                                           \n",
      "    54         1        614.0    614.0     21.3      if np.any(np.bitwise_and(self.h_edges, mask_h_edges)):\n",
      "    55                                                 return None\n",
      "    56         1        318.0    318.0     11.0      if np.any(np.bitwise_and(self.v_edges, mask_v_edges)):\n",
      "    57                                                 return None\n",
      "    58                                           \n",
      "    59         1         60.0     60.0      2.1      np.bitwise_or(self.h_edges, mask_h_edges, out=mask_h_edges)\n",
      "    60         1         22.0     22.0      0.8      np.bitwise_or(self.v_edges, mask_v_edges, out=mask_v_edges)\n",
      "    61                                           \n",
      "    62         1         81.0     81.0      2.8      return Puzzle(mask_h_edges, mask_v_edges)"
     ]
    }
   ],
   "source": [
    "%lprun -f Puzzle.with_piece Puzzle().with_piece(pieces[7], 2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . ."
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Puzzle()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . -\n",
       ". . . . | |\n",
       " . . . . -"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Puzzle().with_piece(pieces[0], 3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       " - - . . .\n",
       "| . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . ."
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Puzzle().with_piece(pieces[7].rotated(), 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       " - - - . .\n",
       ". | | . . .\n",
       " - - . . .\n",
       ". | . . . .\n",
       " - . . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . ."
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Puzzle().with_piece(pieces[3], 0, 0).with_piece(pieces[4].rotated(), 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       " . . . . .\n",
       ". . . . . .\n",
       " . - . . .\n",
       "| | | . . .\n",
       " - - . . .\n",
       ". . . . . .\n",
       " . . . . .\n",
       ". . . . . .\n",
       " . . . . ."
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Puzzle().with_piece(pieces[9].rotated().rotated().rotated(), 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5))\n"
     ]
    }
   ],
   "source": [
    "emptys = tuple(Puzzle().available_spaces())\n",
    "print(emptys)\n",
    "assert len(emptys) == max(Puzzle.H_HEIGHT, Puzzle.V_HEIGHT) * max(Puzzle.H_WIDTH, Puzzle.V_WIDTH)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5))\n"
     ]
    }
   ],
   "source": [
    "emptys = tuple(Puzzle().with_piece(pieces[8], 1, 0).available_spaces())\n",
    "print(emptys)\n",
    "assert (1, 0) not in emptys\n",
    "assert (2, 0) not in emptys\n",
    "assert len(emptys) == max(Puzzle.H_HEIGHT, Puzzle.V_HEIGHT) * max(Puzzle.H_WIDTH, Puzzle.V_WIDTH) - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# larger pieces ordered first, as this prunes more candidate solutions\n",
    "pieces_order = (8, 9, 6, 5, 2, 0, 4, 3, 7, 1)\n",
    "bad_puzzles = set()\n",
    "\n",
    "# pick a puzzle piece\n",
    "# choose rotation\n",
    "# find top-left free corner\n",
    "# put piece if it fits\n",
    "# check if solved\n",
    "def attempt(puzzle: Puzzle, used_pieces: dict[int, tuple]):\n",
    "  if puzzle in bad_puzzles:\n",
    "    return None\n",
    "  if len(used_pieces) == len(pieces):\n",
    "    return puzzle, used_pieces\n",
    "  \n",
    "  available_spaces = tuple(puzzle.available_spaces())\n",
    "  \n",
    "  for i in pieces_order:\n",
    "    if i in used_pieces:\n",
    "      continue\n",
    "\n",
    "    for rotation in pieces[i].rotations():\n",
    "      for v_offset, h_offset in available_spaces:\n",
    "        candidate = puzzle.with_piece(rotation, v_offset, h_offset)\n",
    "  \n",
    "        if candidate is not None:\n",
    "          if candidate in bad_puzzles:\n",
    "            continue\n",
    "\n",
    "          candidate_used_pieces = used_pieces.copy()\n",
    "          candidate_used_pieces[i] = (rotation, v_offset, h_offset)\n",
    "          result = attempt(candidate, candidate_used_pieces)\n",
    "          if result is not None:\n",
    "            return result\n",
    "\n",
    "  bad_puzzles.add(puzzle)\n",
    "  return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*** KeyboardInterrupt exception caught in code being profiled."
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timer unit: 1e-07 s\n",
      "\n",
      "Total time: 58.0341 s\n",
      "File: C:\\Users\\Vidminas\\AppData\\Local\\Temp\\ipykernel_21544\\3777802545.py\n",
      "Function: attempt at line 10\n",
      "\n",
      "Line #      Hits         Time  Per Hit   % Time  Line Contents\n",
      "==============================================================\n",
      "    10                                           def attempt(puzzle: Puzzle, used_pieces: dict[int, tuple]):\n",
      "    11     10575     939347.0     88.8      0.2    if puzzle in bad_puzzles:\n",
      "    12                                               return None\n",
      "    13     10575     198588.0     18.8      0.0    if len(used_pieces) == len(pieces):\n",
      "    14                                               return puzzle, used_pieces\n",
      "    15                                             \n",
      "    16     10575   11438629.0   1081.7      2.0    available_spaces = tuple(puzzle.available_spaces())\n",
      "    17                                             \n",
      "    18    116286     619946.0      5.3      0.1    for i in pieces_order:\n",
      "    19    105717     639034.0      6.0      0.1      if i in used_pieces:\n",
      "    20     71969     246710.0      3.4      0.0        continue\n",
      "    21                                           \n",
      "    22    126523    6111693.0     48.3      1.1      for rotation in pieces[i].rotations():\n",
      "    23   1751615   12493731.0      7.1      2.2        for v_offset, h_offset in available_spaces:\n",
      "    24   1658840  524990609.0    316.5     90.5          candidate = puzzle.with_piece(rotation, v_offset, h_offset)\n",
      "    25                                             \n",
      "    26   1658839    7969689.0      4.8      1.4          if candidate is not None:\n",
      "    27     33365   12189931.0    365.4      2.1            if candidate in bad_puzzles:\n",
      "    28     22791     109978.0      4.8      0.0              continue\n",
      "    29                                           \n",
      "    30     10574     184070.0     17.4      0.0            candidate_used_pieces = used_pieces.copy()\n",
      "    31     10574     145880.0     13.8      0.0            candidate_used_pieces[i] = (rotation, v_offset, h_offset)\n",
      "    32     10574     151826.0     14.4      0.0            result = attempt(candidate, candidate_used_pieces)\n",
      "    33     10569      85777.0      8.1      0.0            if result is not None:\n",
      "    34                                                       return result\n",
      "    35                                           \n",
      "    36     10569    1773003.0    167.8      0.3    bad_puzzles.add(puzzle)\n",
      "    37     10569      52885.0      5.0      0.0    return None"
     ]
    }
   ],
   "source": [
    "# A blank start does not have a unique solution, so this is just for profiling\n",
    "# Interrupt manually after it runs for about a minute\n",
    "%lprun -f attempt attempt(Puzzle(), {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " . - - - -\n",
      ". . | | | |\n",
      " . - - - -\n",
      ". . | | | |\n",
      " . - . - .\n",
      "| | . . . |\n",
      " . - . - .\n",
      "| | | | | .\n",
      " . - - - .\n",
      "\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " . - - - -\n",
      "| | | | | |\n",
      " . - - - -\n"
     ]
    }
   ],
   "source": [
    "# Puzzle 1 - Starter\n",
    "bad_puzzles = set()\n",
    "puzzle1_config = {\n",
    "  1: (pieces[1], 2, 0),\n",
    "  2: (pieces[2].rotated(), 1, 2),\n",
    "  3: (pieces[3].rotated().rotated(), 2, 1),\n",
    "  4: (pieces[4].rotated(), 0, 1),\n",
    "  6: (pieces[6].rotated(), 3, 2),\n",
    "  7: (pieces[7], 1, 4),\n",
    "  9: (pieces[9].rotated(), 0, 3),\n",
    "}\n",
    "puzzle1 = Puzzle()\n",
    "for starting_piece, v_offset, h_offset in puzzle1_config.values():\n",
    "  puzzle1 = puzzle1.with_piece(starting_piece, v_offset, h_offset)\n",
    "print(puzzle1)\n",
    "print()\n",
    "\n",
    "solution1 = attempt(puzzle1, puzzle1_config)\n",
    "assert solution1 is not None\n",
    "print(solution1[0])\n",
    "assert solution1[1][8] == (pieces[8], 0, 0)\n",
    "assert solution1[1][5] == (pieces[5], 2, 4)\n",
    "assert solution1[1][0] == (pieces[0], 2, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - . -\n",
      ". . . . . .\n",
      " . . . . .\n",
      "\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      ". . | | | |\n",
      " - - - - -\n"
     ]
    }
   ],
   "source": [
    "# Puzzle 2 - Starter\n",
    "bad_puzzles = set()\n",
    "puzzle2_config = {\n",
    "  8: (pieces[8], 0, 0),\n",
    "  4: (pieces[4].rotated(), 0, 1),\n",
    "  3: (pieces[3].rotated(), 0, 3),\n",
    "  9: (pieces[9].rotated().rotated().rotated(), 2, 0),\n",
    "  5: (pieces[5], 1, 2),\n",
    "  6: (pieces[6].rotated().rotated().rotated(), 1, 3),\n",
    "  0: (pieces[0], 2, 4),\n",
    "}\n",
    "puzzle2 = Puzzle()\n",
    "for starting_piece, v_offset, h_offset in puzzle2_config.values():\n",
    "  puzzle2 = puzzle2.with_piece(starting_piece, v_offset, h_offset)\n",
    "print(puzzle2)\n",
    "print()\n",
    "\n",
    "solution2 = attempt(puzzle2, puzzle2_config)\n",
    "assert solution2 is not None\n",
    "print(solution2[0])\n",
    "assert solution2[1][7] == (pieces[7].rotated().rotated().rotated(), 3, 0)\n",
    "assert solution2[1][1] == (pieces[1].rotated(), 4, 2)\n",
    "assert solution2[1][2] == (pieces[2].rotated(), 3, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " . . . . .\n",
      ". . . . . .\n",
      " . . . . .\n",
      ". . . . . .\n",
      " - - - . -\n",
      "| | | | | .\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "\n",
      " - - . - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| . | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n"
     ]
    }
   ],
   "source": [
    "# Puzzle 10 - Starter\n",
    "bad_puzzles = set()\n",
    "puzzle10_config = {\n",
    "  6: (pieces[6], 2, 0),\n",
    "  9: (pieces[9].rotated(), 2, 1),\n",
    "  4: (pieces[4].rotated().rotated().rotated(), 3, 1),\n",
    "  0: (pieces[0], 3, 3),\n",
    "  5: (pieces[5], 2, 4),\n",
    "}\n",
    "puzzle10 = Puzzle()\n",
    "for starting_piece, v_offset, h_offset in puzzle10_config.values():\n",
    "  puzzle10 = puzzle10.with_piece(starting_piece, v_offset, h_offset)\n",
    "print(puzzle10)\n",
    "print()\n",
    "\n",
    "solution10 = attempt(puzzle10, puzzle10_config)\n",
    "assert solution10 is not None\n",
    "print(solution10[0])\n",
    "assert solution10[1][3] == (pieces[3].rotated(), 0, 0)\n",
    "assert solution10[1][8] == (pieces[8].rotated(), 0, 3)\n",
    "assert solution10[1][7] == (pieces[7].rotated(), 1, 0)\n",
    "assert solution10[1][2] == (pieces[2].rotated(), 1, 2)\n",
    "assert solution10[1][1] == (pieces[1], 1, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " . . . . -\n",
      ". . . | | |\n",
      " . . . - -\n",
      ". . . . . .\n",
      " - . - - .\n",
      ". | | | | .\n",
      " - . - - .\n",
      "| . . . . .\n",
      " - . . . .\n",
      "\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      ". | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - . - -\n"
     ]
    }
   ],
   "source": [
    "# Puzzle 16 - Starter\n",
    "bad_puzzles = set()\n",
    "puzzle16_config = {\n",
    "  2: (pieces[2], 2, 0),\n",
    "  8: (pieces[8].rotated(), 2, 2),\n",
    "  9: (pieces[9].rotated().rotated().rotated(), 0, 3),\n",
    "}\n",
    "puzzle16 = Puzzle()\n",
    "for starting_piece, v_offset, h_offset in puzzle16_config.values():\n",
    "  puzzle16 = puzzle16.with_piece(starting_piece, v_offset, h_offset)\n",
    "print(puzzle16)\n",
    "print()\n",
    "\n",
    "solution16 = attempt(puzzle16, puzzle16_config)\n",
    "assert solution16 is not None\n",
    "print(solution16[0])\n",
    "assert solution16[1][3] == (pieces[3].rotated(), 0, 0)\n",
    "assert solution16[1][1] == (pieces[1].rotated(), 0, 2)\n",
    "assert solution16[1][7] == (pieces[7].rotated(), 1, 0)\n",
    "assert solution16[1][5] == (pieces[5].rotated(), 1, 1)\n",
    "assert solution16[1][4] == (pieces[4], 1, 4)\n",
    "assert solution16[1][0] == (pieces[0], 3, 1)\n",
    "assert solution16[1][6] == (pieces[6].rotated(), 3, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " - . . - -\n",
      "| . . | | |\n",
      " - . . . .\n",
      "| | . . . .\n",
      " - . . . -\n",
      ". . . . | .\n",
      " - - . . -\n",
      ". | . . . |\n",
      " - . . . -\n",
      "\n",
      " - - . - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - . - - -\n"
     ]
    }
   ],
   "source": [
    "# Puzzle 112 - Master\n",
    "bad_puzzles = set()\n",
    "puzzle112_config = {\n",
    "  6: (pieces[6], 0, 0),\n",
    "  3: (pieces[3].rotated(), 0, 3),\n",
    "  4: (pieces[4].rotated(), 3, 0),\n",
    "  5: (pieces[5], 2, 4)\n",
    "}\n",
    "puzzle112 = Puzzle()\n",
    "for starting_piece, v_offset, h_offset in puzzle112_config.values():\n",
    "  puzzle112 = puzzle112.with_piece(starting_piece, v_offset, h_offset)\n",
    "print(puzzle112)\n",
    "print()\n",
    "\n",
    "solution112 = attempt(puzzle112, puzzle112_config)\n",
    "assert solution112 is not None\n",
    "print(solution112[0])\n",
    "assert solution112[1][0] == (pieces[0], 0, 1)\n",
    "assert solution112[1][8] == (pieces[8].rotated(), 1, 2)\n",
    "assert solution112[1][1] == (pieces[1], 2, 0)\n",
    "assert solution112[1][2] == (pieces[2].rotated(), 2, 1)\n",
    "assert solution112[1][7] == (pieces[7], 1, 4)\n",
    "assert solution112[1][9] == (pieces[9].rotated().rotated().rotated(), 3, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " . . . . .\n",
      ". . . . . .\n",
      " . - . . .\n",
      "| | | . . .\n",
      " - - . . .\n",
      ". . . . . .\n",
      " . . . . .\n",
      ". . . . . .\n",
      " . . . . .\n",
      "\n",
      " - . - - -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - . -\n",
      "| | | | | |\n",
      " - - - - -\n",
      "| | | | | |\n",
      " - - - - -\n"
     ]
    }
   ],
   "source": [
    "# Puzzle 120 - Master\n",
    "bad_puzzles = set()\n",
    "rot9 = pieces[9].rotated().rotated().rotated()\n",
    "puzzle120 = Puzzle().with_piece(rot9, 1, 0)\n",
    "print(puzzle120)\n",
    "print()\n",
    "\n",
    "solution120 = attempt(puzzle120, {9: (rot9, 1, 0)})\n",
    "assert solution120 is not None\n",
    "print(solution120[0])\n",
    "# total bad solutions = 11115514"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1858018"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(bad_puzzles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{9: (   -\n",
       "  | | |\n",
       "   - -,\n",
       "  1,\n",
       "  0),\n",
       " 8: ( -\n",
       "  | |\n",
       "   -\n",
       "  | |\n",
       "   -,\n",
       "  1,\n",
       "  4),\n",
       " 6: ( - -\n",
       "  | | |\n",
       "   -  ,\n",
       "  0,\n",
       "  3),\n",
       " 5: ( -\n",
       "  |  \n",
       "   -\n",
       "    |\n",
       "   -,\n",
       "  0,\n",
       "  2),\n",
       " 2: ( -  \n",
       "  | | |\n",
       "     -,\n",
       "  3,\n",
       "  3),\n",
       " 0: ( -\n",
       "  | |\n",
       "   -,\n",
       "  0,\n",
       "  0),\n",
       " 3: (    \n",
       "  | | |\n",
       "   - -,\n",
       "  2,\n",
       "  1),\n",
       " 7: (    \n",
       "      |\n",
       "   - -,\n",
       "  3,\n",
       "  0),\n",
       " 4: (  \n",
       "  |  \n",
       "   -\n",
       "  | |\n",
       "    ,\n",
       "  2,\n",
       "  0),\n",
       " 1: ( - -, 4, 2)}"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution120[1]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "inf1b-ptas",
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}