Puzzles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Logger\n",
    "\n",
    "\n",
    "\n",
    "| ID | English Name of Puzzles | Chinese Translation | Finished? |\n",
    "| :----:  | :-----: | :-----: | :----: |\n",
    "| 1 | Standard Sudoku  | 标准数独 | ✅ |\n",
    "| 2 | Alphadoku | 25 by 25 字母独| ✅  |\n",
    "| 3 | Killer Sudoku | 杀手数独 | ✅  |\n",
    "| 4 | Petite Killer Sudoku(X-sum Sudoku)| 小杀手数独 | ✅ |\n",
    "| 5 | Consecutive Sudoku | 连续数独 | ✅ |\n",
    "| 6 | Sandwich Sudoku | 三明治数独 | ✅ |\n",
    "| 7 | Cryptarithmetic Puzzle | 破译密码 | ✅ |\n",
    "| 8 |  thermometer Sudoku | 温度计数独 | ✅ |\n",
    "| 9 | Jigsaw Sudoku | 锯齿数独 | ✅ | \n",
    "| 10 | Anti-Knight Sudoku | 无马数独 | ✅ | \n",
    "| 11 | Anti-King Sudoku | 无缘数独 | ✅ |\n",
    "| 12 | Black-White Sudoku | 黑白点数独 | ❌ |\n",
    "| 13 | Arrow Sudoku | 箭头数独 | ✅ |\n",
    "| 14 | Greater-Than Sudoku | 不等式数独 | ✅ |\n",
    "| 15 | Vudoku | V-宫数独 | ✅ | \n",
    "\n",
    "\n",
    "\n",
    "# Reference\n",
    "\n",
    "> https://github.com/dguzelkokar/Solving-Akari-using-Google-OR-Tools\n",
    "> \n",
    "> src: https://www.kaggle.com/code/pintowar/modeling-a-sudoku-solver-with-or-tools\n",
    "> \n",
    "> src: [Jigsaw](https://cn.gridpuzzle.com/jigsaw-killer-sudoku)\n",
    "> \n",
    "> src: [hakank's site](http://www.hakank.org/google_or_tools/)\n",
    ">\n",
    "> [Puzzle Site](https://puzzlemadness.co.uk/slitherlink/large/2023/10/18)\n",
    "> \n",
    "> Sandwich Sudoku: [Github Repo](https://github.com/awkwardbunny/z3-sudoku) in z3 solver\n",
    ">\n",
    "> [Solver Site](https://webpbn.com/survey/)\n",
    ">\n",
    "> https://github.com/LiorSinai/NonogramSolver/\n",
    ">\n",
    "> https://webpbn.com/play.cgi?id=27\n",
    ">\n",
    "> https://webpbn.com/survey/\n",
    ">\n",
    "> https://rosettacode.org/wiki/Nonogram_solver#Python (`Very Useful!`)\n",
    ">\n",
    "> https://github.com/CPMpy/cpmpy/\n",
    ">\n",
    "> https://cs.carleton.edu/cs_comps/1516/slither/index.php\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from itertools import combinations\n",
    "from ortools.sat.python import cp_model as cp\n",
    "import math\n",
    "\n",
    "class CompoundSudokuSolver:\n",
    "    \n",
    "    def __init__(\n",
    "        self, \n",
    "        grid, \n",
    "        X = 9, \n",
    "        Y = 9, \n",
    "        std_rule = True,\n",
    "        killer = None,\n",
    "        petite_killer = None,\n",
    "        consecutive = None,\n",
    "        sandwich = None,\n",
    "        anti_knight = None,\n",
    "        anti_king = None,\n",
    "        arrow = None,\n",
    "        thermo = None, \n",
    "        greater_than = None,\n",
    "        jigsaw = None,\n",
    "        vudoku = None,\n",
    "        all_nine = None,\n",
    "        XV = None,\n",
    "        even_odd = None,\n",
    "        kropki = None,\n",
    "        diagonal = False) -> None:\n",
    "        \n",
    "        self.grid = grid\n",
    "        self.X = X\n",
    "        self.Y = Y\n",
    "        self.std_rule = std_rule\n",
    "        self.model = cp.CpModel()\n",
    "        self.solver = cp.CpSolver()\n",
    "        self.x = {}\n",
    "        self.killer = killer\n",
    "        self.petite_killer = petite_killer\n",
    "        self.consecutive = consecutive\n",
    "        self.sandwich = sandwich\n",
    "        self.anti_knight = anti_knight\n",
    "        self.anti_king = anti_king\n",
    "        self.arrow = arrow\n",
    "        self.thermo = thermo\n",
    "        self.diagonal = diagonal\n",
    "        self.greater_than = greater_than\n",
    "        self.jigsaw = jigsaw\n",
    "        self.vudoku = vudoku\n",
    "        self.all_nine = all_nine\n",
    "        self.XV = XV\n",
    "        self.evan_odd = even_odd\n",
    "        self.kropki = kropki\n",
    "        # list (tuple), \n",
    "        # 7 2\n",
    "        # 8 2\n",
    "        # 10 3 \n",
    "        # first tuple value indicates the index of corner\n",
    "        # second tuple value indicates the shape of corner:\n",
    "        #     0:    ｜        2:--｜\n",
    "        #         __｜            ｜\n",
    "        # \n",
    "        #     1:  ｜          3: ｜--\n",
    "        #         ｜__           ｜\n",
    "\n",
    "        self.aux_sand = None\n",
    "        self.vudoku_aux = None\n",
    "        self.consecutive_aux = None\n",
    "        self.result = \"\"\n",
    "        \n",
    "        assert X == Y\n",
    "\n",
    "        for i in range(Y):\n",
    "            for j in range(X):\n",
    "                if self.grid[i * self.Y + j] == \"0\":\n",
    "                    self.x[i, j] = self.model.NewIntVar(1, self.X, f'x[{i}, {j}]')\n",
    "                else:\n",
    "                    self.x[i, j] = int(self.grid[i * self.X + j])\n",
    "                \n",
    "    def addStandardConstr(self):\n",
    "        \n",
    "        \"\"\"_summary_\n",
    "            Add standard Sudoku Constraint\n",
    "        \"\"\"\n",
    "        \n",
    "        for i in range(self.Y):\n",
    "            row = [self.x[i, j] for j in range(self.X)]\n",
    "            self.model.AddAllDifferent(row)\n",
    "            col = [self.x[j, i] for j in range(self.Y)]\n",
    "            self.model.AddAllDifferent(col)\n",
    "        \n",
    "        for i in range(int(math.sqrt(self.X)) - 1):\n",
    "            for j in range(int(math.sqrt(self.Y)) - 1):\n",
    "                l = int(math.sqrt(self.X))\n",
    "                cell = [\n",
    "                    self.x[r, c]\n",
    "                    for r in range(i* l, i * l + l)\n",
    "                    for c in range(j* l, j * l + l)\n",
    "                ]\n",
    "                self.model.AddAllDifferent(cell)\n",
    "    \n",
    "    def addConsecutiveConstr(self):\n",
    "    # c = sum([x[i] == val for i in range(len(x))])\n",
    "    \n",
    "    # n = len(x)\n",
    "    # b = [model.NewBoolVar(f\"b[{i}]\")  for i in range(n)]\n",
    "    # for i in range(n):\n",
    "    #     model.Add((x[i] == val)).OnlyEnforceIf(b[i])\n",
    "    #     model.Add((x[i] != val)).OnlyEnforceIf(b[i].Not())\n",
    "    # model.Add(c == sum(b))\n",
    "        self.consecutive_aux = {}\n",
    "        for idx, sub_char in enumerate(self.consecutive):\n",
    "            sub_a, sub_b = idx // 17, idx % 17\n",
    "            if sub_char == \".\":\n",
    "                self.consecutive_aux[f\"{sub_a}_{sub_b}_1\"] = self.model.NewBoolVar(name = f\"{sub_a}_{sub_b}_1\")\n",
    "                self.consecutive_aux[f\"{sub_a}_{sub_b}_2\"] = self.model.NewBoolVar(name = f\"{sub_a}_{sub_b}_2\")\n",
    "                if sub_b <= 7:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b)] - self.x[int(sub_a), int(sub_b) + 1] == 1).OnlyEnforceIf(self.consecutive_aux[f\"{sub_a}_{sub_b}_1\"])\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b)] - self.x[int(sub_a), int(sub_b) + 1] != 1).OnlyEnforceIf(self.consecutive_aux[f\"{sub_a}_{sub_b}_1\"].Not())\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b)] - self.x[int(sub_a), int(sub_b) + 1] == -1).OnlyEnforceIf(self.consecutive_aux[f\"{sub_a}_{sub_b}_2\"])\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b)] - self.x[int(sub_a), int(sub_b) + 1] != -1).OnlyEnforceIf(self.consecutive_aux[f\"{sub_a}_{sub_b}_2\"].Not())\n",
    "                    self.model.Add(self.consecutive_aux[f\"{sub_a}_{sub_b}_1\"] + self.consecutive_aux[f\"{sub_a}_{sub_b}_2\"] == 0)\n",
    "                elif sub_b <= 16:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b) - 8] - self.x[int(sub_a) + 1, int(sub_b) - 8] == 1).OnlyEnforceIf(self.consecutive_aux[f\"{sub_a}_{sub_b}_1\"])\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b) - 8] - self.x[int(sub_a) + 1, int(sub_b) - 8] != 1).OnlyEnforceIf(self.consecutive_aux[f\"{sub_a}_{sub_b}_1\"].Not())\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b) - 8] - self.x[int(sub_a) + 1, int(sub_b) - 8] == -1).OnlyEnforceIf(self.consecutive_aux[f\"{sub_a}_{sub_b}_2\"])\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b) - 8] - self.x[int(sub_a) + 1, int(sub_b) - 8] != -1).OnlyEnforceIf(self.consecutive_aux[f\"{sub_a}_{sub_b}_2\"].Not())\n",
    "                    self.model.Add(self.consecutive_aux[f\"{sub_a}_{sub_b}_1\"] + self.consecutive_aux[f\"{sub_a}_{sub_b}_2\"] == 0)\n",
    "                continue\n",
    "            if sub_b <= 7:\n",
    "                self.model.AddAbsEquality(1, self.x[int(sub_a), int(sub_b)] - self.x[int(sub_a), int(sub_b) + 1])\n",
    "            elif sub_b <= 16:\n",
    "                self.model.AddAbsEquality(1, self.x[int(sub_a), int(sub_b) - 8] - self.x[int(sub_a) + 1, int(sub_b) - 8])\n",
    "        # for _, cage in enumerate(self.consecutive):\n",
    "        #     self.model.AddAbsEquality(1, self.x[cage[0][0], cage[0][1]] - self.x[cage[1][0], cage[1][1]])\n",
    "             \n",
    "    def addDiagonalConstr(self):\n",
    "        \n",
    "        \"\"\"_summary_\n",
    "            Add diagonal Constraints.\n",
    "        \"\"\"\n",
    "        \n",
    "        ltr = []\n",
    "        rtl = []\n",
    "        for i in range(self.Y):\n",
    "            ltr.append(self.x[i, i])\n",
    "            rtl.append(self.x[self.X - i - 1, i])\n",
    "        self.model.AddAllDifferent(ltr)\n",
    "        self.model.AddAllDifferent(rtl)\n",
    "            \n",
    "    def printgrid(self):    \n",
    "        \n",
    "        \"\"\"_summary_\n",
    "            Print the final grid\n",
    "        \"\"\"\n",
    "    \n",
    "        for i in range(self.Y):\n",
    "            for j in range(self.X):\n",
    "                print(self.solver.Value(self.x[i, j]), end=\" \")\n",
    "                self.result += str(self.solver.Value(self.x[i, j]))\n",
    "            print()\n",
    "        print()\n",
    "\n",
    "        print(\"NumConflicts:\", self.solver.NumConflicts())\n",
    "        print(\"NumBranches:\", self.solver.NumBranches())\n",
    "        print(\"WallTime:\", self.solver.WallTime())\n",
    "        \n",
    "        # for i in range(9):\n",
    "        #     for j in range(6):\n",
    "        #         print(self.solver.Value(self.aux_sand[\"R\", i, j]))\n",
    "    \n",
    "    def addKillerConstr(self):\n",
    "        \"\"\"_summary_\n",
    "            Add killer constraint from data\n",
    "        \"\"\"\n",
    "        \n",
    "        for (res, segment) in self.killer:\n",
    "            cage = [self.x[i[0], i[1]] for i in segment]\n",
    "            self.model.Add(sum(cage) == res)\n",
    "            self.model.AddAllDifferent(cage)\n",
    "    \n",
    "    def addPetiteKillerConstr(self):\n",
    "        \"\"\"_summary_\n",
    "            增加小杀手数独约束\n",
    "        Raises:\n",
    "            Exception: _description_\n",
    "            Exception: _description_\n",
    "        \"\"\"\n",
    "        if len(self.petite_killer[0]) != self.X:\n",
    "            raise Exception(\"小杀手数独斜行和数量有误。\")\n",
    "        for line in self.petite_killer:\n",
    "            if line[0] == \"TL\":\n",
    "                for i in range(self.X - 1):\n",
    "                    constrCages = []\n",
    "                    for j in range(i + 1):\n",
    "                        constrCages.append(self.x[j, i - j])\n",
    "                    self.model.Add(sum(constrCages) == line[i + 1])\n",
    "\n",
    "            elif line[0] == \"RT\":\n",
    "                \n",
    "                for i in range(self.X - 1):\n",
    "                    constrCages = []\n",
    "                    for j in range(i + 1):\n",
    "                        constrCages.append(self.x[j, self.X - i + j - 1])\n",
    "                    self.model.Add(sum(constrCages) == line[i + 1])\n",
    "\n",
    "            elif line[0] == \"BR\":\n",
    "                for i in range(self.X - 1):\n",
    "                    constrCages = []\n",
    "                    for j in range(self.X - 1 - i):\n",
    "                        constrCages.append(self.x[self.X - 1 - j, 1 + i +  j])\n",
    "                    self.model.Add(sum(constrCages) == line[i + 1])\n",
    "\n",
    "                    \n",
    "            elif line[0] == \"LB\":\n",
    "            \n",
    "                for i in range(self.X - 1):\n",
    "                    constrCages = []\n",
    "                    for j in range(self.X - 1 - i):\n",
    "                        constrCages.append(self.x[1 + j + i,  j])\n",
    "                    self.model.Add(sum(constrCages) == line[i + 1])\n",
    "\n",
    "            else:\n",
    "                raise Exception(\"检查小杀手数独位置元素字符串, 必须为TL / RT / BR / LB 中的一个\")\n",
    "\n",
    "    def addThermoConstr(self):\n",
    "        \"\"\"_summary_\n",
    "            Thermo constraints\n",
    "        \"\"\"\n",
    "        for thermo_ in self.thermo:\n",
    "            for idx in range(len(thermo_) - 1):\n",
    "                self.model.Add(self.x[thermo_[idx][0], thermo_[idx][1]] < self.x[thermo_[idx + 1][0], thermo_[idx + 1][1]])\n",
    "        \n",
    "    def addSandwichConstr(self):\n",
    "        \"\"\"\n",
    "            Add sandwich Sudoku Constrs\n",
    "        \"\"\"\n",
    "        self.aux_sand = {}\n",
    "        \n",
    "        # x[i,j] = 9 -> Bool = True\n",
    "        # x[i,j] <= 8 -> Bool = False\n",
    "        # False -> x[i, j] <= 8\n",
    "        \n",
    "        # True\n",
    "        for nums in self.sandwich:\n",
    "            if nums[0] == \"R\":\n",
    "                for idx, num in enumerate(nums[1:]):\n",
    "                    if num < 0:\n",
    "                        continue\n",
    "                    # cnt = 0\n",
    "                    for index, cbn in enumerate(combinations([i for i in range(self.X)], 2)):\n",
    "\n",
    "                        self.aux_sand[\"R\", idx, index,  0] = self.model.NewBoolVar(f\"R, {idx}, {index}, 0\")\n",
    "                        self.aux_sand[\"R\", idx, index,  1] = self.model.NewBoolVar(f\"R, {idx}, {index}, 1\")\n",
    "                        self.aux_sand[\"R\", idx, index,  2] = self.model.NewBoolVar(f\"R, {idx}, {index}, 2\")\n",
    "                        self.aux_sand[\"R\", idx, index,  3] = self.model.NewBoolVar(f\"R, {idx}, {index}, 3\")\n",
    "                        self.aux_sand[\"R\", idx, index,  4] = self.model.NewBoolVar(f\"R, {idx}, {index}, 4\")\n",
    "                        self.aux_sand[\"R\", idx, index,  5] = self.model.NewBoolVar(f\"R, {idx}, {index}, 5\")\n",
    "\n",
    "                        \n",
    "                        self.model.Add(self.x[cbn[0], idx] == 1).OnlyEnforceIf(self.aux_sand[\"R\", idx, index, 0])\n",
    "                        self.model.Add(self.x[cbn[0], idx] >= 2).OnlyEnforceIf(self.aux_sand[\"R\", idx, index, 0].Not())\n",
    "\n",
    "                        \n",
    "                        self.model.Add(self.x[cbn[1], idx] == 9).OnlyEnforceIf(self.aux_sand[\"R\", idx, index, 1])\n",
    "                        self.model.Add(self.x[cbn[1], idx] <= 8).OnlyEnforceIf(self.aux_sand[\"R\", idx, index, 1].Not())\n",
    "                        \n",
    "                        self.model.Add(self.aux_sand[\"R\", idx,  index, 0] + self.aux_sand[\"R\", idx, index,  1] == 2).OnlyEnforceIf(self.aux_sand[\"R\", idx, index, 4])\n",
    "                        self.model.Add(self.aux_sand[\"R\", idx,  index, 0] + self.aux_sand[\"R\", idx, index,  1] <= 1).OnlyEnforceIf(self.aux_sand[\"R\", idx, index, 4].Not())\n",
    "                        \n",
    "                        self.model.Add(sum(self.x[j, idx] for j in range(cbn[0] + 1, cbn[1] )) == num).OnlyEnforceIf(self.aux_sand[\"R\",idx, index, 4])\n",
    "                        # self.model.Add(sum(self.x[j, idx] for j in range(cbn[0] + 1, cbn[1] - 1)) != num).OnlyEnforceIf(self.aux_sand[\"R\",idx, index, 4])\n",
    "                        \n",
    "                        self.model.Add(self.x[cbn[0], idx] == 9).OnlyEnforceIf(self.aux_sand[\"R\", idx, index,  2])\n",
    "                        self.model.Add(self.x[cbn[0], idx] <= 8).OnlyEnforceIf(self.aux_sand[\"R\", idx, index,  2].Not())\n",
    "\n",
    "                        \n",
    "                        self.model.Add(self.x[cbn[1], idx] == 1).OnlyEnforceIf(self.aux_sand[\"R\", idx, index,  3])\n",
    "                        self.model.Add(self.x[cbn[1], idx] >= 2).OnlyEnforceIf(self.aux_sand[\"R\", idx, index,  3].Not())\n",
    "\n",
    "                        \n",
    "                        self.model.Add(self.aux_sand[\"R\", idx, index, 2] + self.aux_sand[\"R\", idx, index,  3] == 2).OnlyEnforceIf(self.aux_sand[\"R\", idx, index, 5])\n",
    "                        self.model.Add(self.aux_sand[\"R\", idx, index, 2] + self.aux_sand[\"R\", idx, index,  3] <= 1).OnlyEnforceIf(self.aux_sand[\"R\", idx, index, 5].Not())\n",
    "                        \n",
    "                        self.model.Add(sum(self.x[j, idx] for j in range(cbn[0] + 1, cbn[1] )) == num).OnlyEnforceIf(self.aux_sand[\"R\",idx, index, 5])\n",
    "                       \n",
    "                   \n",
    "                        \n",
    "            elif nums[0] == \"C\":\n",
    "                if nums[0] == \"R\":\n",
    "                    for idx, num in enumerate(nums[1:]):\n",
    "                        if num < 0:\n",
    "                            continue\n",
    "                        # cnt = 0\n",
    "                        for index, cbn in enumerate(combinations([i for i in range(self.X)], 2)):\n",
    "                            self.aux_sand[\"C\", idx, index,  0] = self.model.NewBoolVar(f\"R, {idx}, {index}, 0\")\n",
    "                            self.aux_sand[\"C\", idx, index,  1] = self.model.NewBoolVar(f\"R, {idx}, {index}, 1\")\n",
    "                            self.aux_sand[\"C\", idx, index,  2] = self.model.NewBoolVar(f\"R, {idx}, {index}, 2\")\n",
    "                            self.aux_sand[\"C\", idx, index,  3] = self.model.NewBoolVar(f\"R, {idx}, {index}, 3\")\n",
    "                            self.aux_sand[\"C\", idx, index,  4] = self.model.NewBoolVar(f\"R, {idx}, {index}, 4\")\n",
    "                            self.aux_sand[\"C\", idx, index,  5] = self.model.NewBoolVar(f\"R, {idx}, {index}, 5\")\n",
    "\n",
    "                            \n",
    "                            self.model.Add(self.x[idx, cbn[0]] == 1).OnlyEnforceIf(self.aux_sand[\"C\", idx, index, 0])\n",
    "                            self.model.Add(self.x[idx, cbn[0]] >= 2).OnlyEnforceIf(self.aux_sand[\"C\", idx, index, 0].Not())\n",
    "\n",
    "                            \n",
    "                            self.model.Add(self.x[idx, cbn[1]] == 9).OnlyEnforceIf(self.aux_sand[\"C\", idx, index, 1])\n",
    "                            self.model.Add(self.x[idx, cbn[1]] <= 8).OnlyEnforceIf(self.aux_sand[\"C\", idx, index, 1].Not())\n",
    "                            \n",
    "                            self.model.Add(self.aux_sand[\"C\", idx,  index, 0] + self.aux_sand[\"C\", idx, index,  1] == 2).OnlyEnforceIf(self.aux_sand[\"C\", idx, index, 4])\n",
    "                            self.model.Add(self.aux_sand[\"C\", idx,  index, 0] + self.aux_sand[\"C\", idx, index,  1] <= 1).OnlyEnforceIf(self.aux_sand[\"C\", idx, index, 4].Not())\n",
    "                            \n",
    "                            self.model.Add(sum(self.x[idx, j] for j in range(cbn[0] + 1, cbn[1] )) == num).OnlyEnforceIf(self.aux_sand[\"R\",idx, index, 4])\n",
    "                            # self.model.Add(sum(self.x[j, idx] for j in range(cbn[0] + 1, cbn[1] - 1)) != num).OnlyEnforceIf(self.aux_sand[\"R\",idx, index, 4])\n",
    "                            \n",
    "                            self.model.Add(self.x[idx, cbn[0]] == 9).OnlyEnforceIf(self.aux_sand[\"C\", idx, index,  2])\n",
    "                            self.model.Add(self.x[idx, cbn[0]] <= 8).OnlyEnforceIf(self.aux_sand[\"C\", idx, index,  2].Not())\n",
    "\n",
    "                            \n",
    "                            self.model.Add(self.x[idx, cbn[1]] == 1).OnlyEnforceIf(self.aux_sand[\"C\", idx, index,  3])\n",
    "                            self.model.Add(self.x[idx, cbn[1]] >= 2).OnlyEnforceIf(self.aux_sand[\"C\", idx, index,  3].Not())\n",
    "\n",
    "                            \n",
    "                            self.model.Add(self.aux_sand[\"C\", idx, index, 2] + self.aux_sand[\"C\", idx, index,  3] == 2).OnlyEnforceIf(self.aux_sand[\"C\", idx, index, 5])\n",
    "                            self.model.Add(self.aux_sand[\"C\", idx, index, 2] + self.aux_sand[\"C\", idx, index,  3] <= 1).OnlyEnforceIf(self.aux_sand[\"C\", idx, index, 5].Not())\n",
    "                            self.model.Add(sum(self.x[idx, j] for j in range(cbn[0] + 1, cbn[1] )) == num).OnlyEnforceIf(self.aux_sand[\"R\",idx, index, 4]) \n",
    "\n",
    "    def addAntiKnightConstr(self):\n",
    "        \n",
    "        offsets = [\n",
    "            (-2, 1), \n",
    "            (-2, -1), \n",
    "            (-1, 2), \n",
    "            (-1, -2), \n",
    "            (1, 2), \n",
    "            (1, -2), \n",
    "            (2, 1), \n",
    "            (2, -1)\n",
    "        ]\n",
    "        for i in range(self.Y):\n",
    "            for j in range(self.X):\n",
    "                for offset in offsets:\n",
    "                    if (i + offset[0] >= 0 and i + offset[0] < self.Y) and (j + offset[1] >= 0 and j + offset[1] < self.X):\n",
    "                        self.model.Add(self.x[i, j] != self.x[i + offset[0], j + offset[1]])\n",
    "        \n",
    "    def addAntiKingConstr(self):\n",
    "        \n",
    "        offs = [-1, 0, 1]\n",
    "        for i in range(self.Y):\n",
    "            for j in range(self.X):\n",
    "                for ofx in offs:\n",
    "                    for ofy in offs:\n",
    "                        if (i + ofx >= 0 and i + ofx < self.Y) and (j + ofy >= 0 and j + ofy < self.X) and (ofy != 0 and ofx != 0):\n",
    "                            self.model.Add(self.x[i, j] != self.x[i + ofx, j + ofy])\n",
    "        \n",
    "    def addArrowConstr(self):\n",
    "\n",
    "        for arrow_ in self.arrow:\n",
    "            self.model.Add(self.x[arrow_[0][0], arrow_[0][1]] == sum([self.x[ar[0], ar[1]] for ar in arrow_[1:]]))\n",
    "            \n",
    "    def addGreaterThanConstr(self):\n",
    "        for idx, sub_ in enumerate(self.greater_than):\n",
    "            if sub_ == \".\":\n",
    "                continue\n",
    "            sub_a, sub_b = idx // 17, idx % 17\n",
    "            if sub_ == \">\":\n",
    "                if sub_b <= 7:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b)] > self.x[int(sub_a), int(sub_b) + 1])\n",
    "                    print(f\"[{int(sub_a)}, {int(sub_b)}] > [{int(sub_a)}, {int(sub_b) + 1}]\")\n",
    "                elif sub_b <= 16:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b) - 8] > self.x[int(sub_a) + 1, int(sub_b) - 8])\n",
    "            elif sub_ == \"<\":\n",
    "                if sub_b <= 7:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b)] < self.x[int(sub_a), int(sub_b) + 1])\n",
    "                elif sub_b <= 16:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b) - 8] < self.x[int(sub_a) + 1, int(sub_b) - 8])\n",
    "\n",
    "    def addJigsawConstr(self):\n",
    "        for i in range(self.Y):\n",
    "            row = [self.x[i, j] for j in range(self.X)]\n",
    "            self.model.AddAllDifferent(row)\n",
    "            col = [self.x[j, i] for j in range(self.Y)]\n",
    "            self.model.AddAllDifferent(col)\n",
    "        new_grid = dict()\n",
    "        for idx, char_ in enumerate(self.jigsaw):\n",
    "            if char_ not in new_grid:\n",
    "                new_grid[char_] = []\n",
    "            new_grid[char_].append(idx)\n",
    "        \n",
    "        for k, v in new_grid.items():\n",
    "            cell = [self.x[idx // 9, idx % 9] for idx in v]\n",
    "            self.model.AddAllDifferent(cell)\n",
    "\n",
    "    def addVudokuConstr(self):\n",
    "        self.vudoku_aux = [self.model.NewBoolVar(f\"aux_{i}\") for i in range(3 * len(self.vudoku))]\n",
    "        for idx, val  in enumerate(self.vudoku):\n",
    "            cornerCentral, cornerShape = val[0], val[1]\n",
    "            xx, yy  = cornerCentral // self.Y, cornerCentral % self.Y\n",
    "            aroundCorner = []\n",
    "            if cornerShape == 0:\n",
    "                aroundCorner = [(xx, yy - 1), (xx - 1, yy)]\n",
    "            elif cornerShape == 1:\n",
    "                aroundCorner = [(xx - 1, yy), ((xx, yy + 1))]\n",
    "            elif cornerShape == 2:\n",
    "                aroundCorner = [(xx, yy - 1), (xx + 1, yy )]\n",
    "            else:\n",
    "                aroundCorner = [(xx, yy + 1), (xx + 1, yy )]\n",
    "\n",
    "            self.model.Add(\n",
    "                (self.x[aroundCorner[0][0], aroundCorner[0][1]] + self.x[aroundCorner[1][0], aroundCorner[1][1]] == self.x[xx, yy])).OnlyEnforceIf(self.vudoku_aux[idx * 3])\n",
    "            self.model.Add(\n",
    "                (self.x[aroundCorner[0][0], aroundCorner[0][1]] + self.x[aroundCorner[1][0], aroundCorner[1][1]] != self.x[xx, yy])).OnlyEnforceIf(self.vudoku_aux[idx * 3].Not())\n",
    "            self.model.Add(\n",
    "                (self.x[aroundCorner[0][0], aroundCorner[0][1]] - self.x[aroundCorner[1][0], aroundCorner[1][1]] == self.x[xx, yy])).OnlyEnforceIf(self.vudoku_aux[idx * 3 + 1])\n",
    "            self.model.Add(\n",
    "                (self.x[aroundCorner[0][0], aroundCorner[0][1]] - self.x[aroundCorner[1][0], aroundCorner[1][1]] != self.x[xx, yy])).OnlyEnforceIf(self.vudoku_aux[idx * 3 + 1].Not())\n",
    "            self.model.Add(\n",
    "                (self.x[aroundCorner[1][0], aroundCorner[1][1]] - self.x[aroundCorner[0][0], aroundCorner[0][1]] == self.x[xx, yy])).OnlyEnforceIf(self.vudoku_aux[idx * 3 + 2])\n",
    "            self.model.Add(\n",
    "                (self.x[aroundCorner[1][0], aroundCorner[1][1]] - self.x[aroundCorner[0][0], aroundCorner[0][1]] != self.x[xx, yy])).OnlyEnforceIf(self.vudoku_aux[idx * 3 + 2].Not())\n",
    "            self.model.Add(sum(self.vudoku_aux[idx * 3 : idx * 3 + 3]) == 1)\n",
    "            \n",
    "            # 限制上述情况只能取一种发生\n",
    "            \n",
    "    def addAllNineConstr(self):\n",
    "        all_nine_dict = dict()\n",
    "        for idx, cell in enumerate(self.all_nine):\n",
    "            if cell == \"0\":\n",
    "                continue\n",
    "            else:\n",
    "                if cell not in all_nine_dict:\n",
    "                    all_nine_dict[cell] = []\n",
    "                all_nine_dict[cell].append((idx // self.X, idx % self.Y))\n",
    "        for _, cells in all_nine_dict.items():\n",
    "            self.model.AddAllDifferent([self.x[cell[0], cell[1]] for cell in cells])\n",
    "    \n",
    "    def addXVConstr(self):\n",
    "        # Sudoku XV(Evil) https://gridpuzzle.com/vx-sudoku/159j0\n",
    "        for idx, sub_ in enumerate(self.XV):\n",
    "            if sub_ == \".\":\n",
    "                continue\n",
    "            sub_a, sub_b = idx // 17 , idx % 17 \n",
    "            if sub_ == \"V\":\n",
    "                if sub_b <= 7:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b)] + self.x[int(sub_a), int(sub_b) + 1] == 5)\n",
    "                elif sub_b <= 16:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b) - 8] + self.x[int(sub_a) + 1, int(sub_b) - 8] == 5)\n",
    "            elif sub_ == \"X\":\n",
    "                if sub_b <= 7:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b)] + self.x[int(sub_a), int(sub_b) + 1] == 10)\n",
    "                elif sub_b <= 16:\n",
    "                    self.model.Add(self.x[int(sub_a), int(sub_b) - 8] + self.x[int(sub_a) + 1, int(sub_b) - 8] == 10)\n",
    "    \n",
    "    def addEvenOddConstr(self):\n",
    "        for idx, sub_char in enumerate(self.evan_odd):\n",
    "            idx_a, idx_b = idx // self.X, idx % self.X\n",
    "            if sub_char == \"E\":\n",
    "                self.model.AddAllowedAssignments([self.x[idx_a, idx_b]], [[2], [4], [6], [8]])\n",
    "            elif sub_char == \"O\":\n",
    "                self.model.AddAllowedAssignments([self.x[idx_a, idx_b]], [[1], [3], [5], [7], [9]])\n",
    "        \n",
    "    def addKropkiConstr(self):\n",
    "        for idx, sub_ in enumerate(self.kropki):\n",
    "            if sub_ == \".\":\n",
    "                continue\n",
    "            sub_a, sub_b = idx // 17 , idx % 17 \n",
    "            if sub_ == \"B\":\n",
    "                if sub_b <= 7:\n",
    "                    self.model.AddAllowedAssignments([self.x[int(sub_a), int(sub_b)], self.x[int(sub_a), int(sub_b) + 1]], [[1,2], [2,4], [3,6], [4,8], [8,4], [6,3], [4,2], [2,1]])\n",
    "                elif sub_b <= 16:\n",
    "                    self.model.AddAllowedAssignments([self.x[int(sub_a), int(sub_b) - 8], self.x[int(sub_a) + 1, int(sub_b) - 8]], [[1,2], [2,4], [3,6], [4,8], [8,4], [6,3], [4,2], [2,1]])\n",
    "            elif sub_ == \"W\":\n",
    "                if sub_b <= 7:\n",
    "                    self.model.AddAbsEquality(1, self.x[int(sub_a), int(sub_b)] - self.x[int(sub_a), int(sub_b) + 1])\n",
    "                elif sub_b <= 16:\n",
    "                    self.model.AddAbsEquality(1, self.x[int(sub_a), int(sub_b) - 8] - self.x[int(sub_a) + 1, int(sub_b) - 8])\n",
    "    \n",
    "    \n",
    "    def solveall(self):\n",
    "\n",
    "        if self.std_rule and self.jigsaw == None:\n",
    "            self.addStandardConstr()\n",
    "        \n",
    "        if self.jigsaw != None:\n",
    "            self.addJigsawConstr()\n",
    "        \n",
    "        if self.diagonal:\n",
    "            self.addDiagonalConstr()\n",
    "        if self.killer != None:\n",
    "            self.addKillerConstr()\n",
    "        if self.petite_killer != None:\n",
    "            self.addPetiteKillerConstr()\n",
    "        if self.consecutive != None:\n",
    "            self.addConsecutiveConstr()\n",
    "        if self.sandwich != None:\n",
    "            self.addSandwichConstr()\n",
    "        if self.anti_knight != None and self.anti_knight == True:\n",
    "            self.addAntiKnightConstr()\n",
    "        if self.anti_king != None and self.anti_king == True:\n",
    "            self.addAntiKingConstr()\n",
    "        if self.thermo != None:\n",
    "            self.addThermoConstr()\n",
    "        if self.arrow != None:\n",
    "            self.addArrowConstr()\n",
    "        if self.greater_than != None:\n",
    "            self.addGreaterThanConstr()\n",
    "        if self.vudoku != None:\n",
    "            self.addVudokuConstr()\n",
    "        if self.all_nine != None:\n",
    "            self.addAllNineConstr()\n",
    "        if self.XV != None:\n",
    "            self.addXVConstr()\n",
    "        if self.evan_odd != None:\n",
    "            self.addEvenOddConstr()\n",
    "        if self.kropki != None:\n",
    "            self.addKropkiConstr()\n",
    "        \n",
    "        status = self.solver.Solve(self.model)\n",
    "\n",
    "        if status == cp.OPTIMAL:\n",
    "            self.printgrid()\n",
    "            return self.result\n",
    "\n",
    "        elif status == cp.INFEASIBLE:\n",
    "            print(\"模型不可行\")\n",
    "            return \"\"\n",
    "            # self.model.ExportToFile(\"./help.txt\")\n",
    "        else:\n",
    "            print(\"无法在规定时间内求解\")\n",
    "            return \"\"\n",
    "        # else:\n",
    "        #     print(\"没有找到可行方案\")\n",
    "        #     self.model.ExportToFile(\"./help.txt\")\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vudoku\n",
    "\n",
    "- 标准数独规则适用\n",
    "- 每个 “V”型包含的三个格子，边缘两个格子的数之和或者差，等于中间格子的数字。\n",
    "\n",
    "-----------\n",
    "\n",
    "- STD rules applied\n",
    "- The number at the vertex of each marked \"V\" must be either the sum or the difference of the other two numbers of the \"V\".\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 6 5 1 4 8 2 7 3 \n",
      "7 1 2 9 3 6 8 5 4 \n",
      "3 8 4 2 5 7 6 9 1 \n",
      "1 2 3 5 6 4 9 8 7 \n",
      "4 5 6 8 7 9 3 1 2 \n",
      "8 9 7 3 2 1 4 6 5 \n",
      "2 7 8 6 1 3 5 4 9 \n",
      "5 4 9 7 8 2 1 3 6 \n",
      "6 3 1 4 9 5 7 2 8 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.021150000000000002\n",
      "965148273712936854384257691123564987456879312897321465278613549549782136631495728\n"
     ]
    }
   ],
   "source": [
    "# 测试Vudoku数独 \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    test_vudoku_solver = \"960008003000000000000057000100004900000000000000001000000000040000700000000000000\"\n",
    "    vudoku = [\n",
    "        [7, 2],\n",
    "        [8, 2],\n",
    "        [10, 2],\n",
    "        [15, 0],\n",
    "        [22, 0],\n",
    "        [27, 1],\n",
    "        [28, 3],\n",
    "        [30, 2],\n",
    "        [35, 0],\n",
    "        [36, 1],\n",
    "        [37, 2],\n",
    "        [42, 3],\n",
    "        [49, 2],\n",
    "        [50, 3],\n",
    "        [51, 2],\n",
    "        [52, 1],\n",
    "        [54, 3],\n",
    "        [55, 0],\n",
    "        [57, 3],\n",
    "        [59, 2],\n",
    "        [59, 3],\n",
    "        [70, 0],\n",
    "        [70, 2],\n",
    "        [71, 0],\n",
    "        [73, 1],\n",
    "        [77, 1],\n",
    "    ]\n",
    "    css = CompoundSudokuSolver(grid = test_vudoku_solver, vudoku= vudoku)\n",
    "    result = css.solveall()\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/Vudoku.png)\n",
    "\n",
    "-------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Jigsaw Sudoku \n",
    "\n",
    "- 标准数独规则的行、列不重复规则依然适用\n",
    "- 取消原本3 x 3的宫的概念，而是不规则锯齿状，保证每个锯齿宫依然是9个数字不重复。\n",
    "\n",
    "---------\n",
    "\n",
    "- The difference is that instead of having 3x3 rectangular blocks these blocks have irregular shapes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 4 8 6 1 7 3 5 9 \n",
      "3 8 1 4 9 6 5 2 7 \n",
      "7 9 5 2 8 4 6 1 3 \n",
      "9 5 3 7 6 2 1 8 4 \n",
      "4 6 9 1 7 5 8 3 2 \n",
      "8 2 7 5 3 1 9 4 6 \n",
      "1 3 2 9 4 8 7 6 5 \n",
      "5 1 6 3 2 9 4 7 8 \n",
      "6 7 4 8 5 3 2 9 1 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.013172000000000001\n",
      "248617359381496527795284613953762184469175832827531946132948765516329478674853291\n"
     ]
    }
   ],
   "source": [
    "# 测试锯齿数独\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    test_jigsaw_solver = \"200007000300400000000284600000000000060000030000000000002948000000009008000800001\"\n",
    "    jigsaw = \"AAAAABBBCADBBBBCCCADDBBDCCCAADDDDECCFFFDGEEEEFFFGGGEHEFFGGGGEHHFIGIIIEHHIIIIIHHHH\"\n",
    "    css = CompoundSudokuSolver(grid = test_jigsaw_solver, jigsaw = jigsaw)\n",
    "    result = css.solveall()\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/Jigsaw1.png)\n",
    "\n",
    "-------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Greater-than Sudoku (不等式数独)\n",
    "\n",
    "- 标准数独规则适用\n",
    "- 某些数字之间存在不等式约束，所填入的格子需要满足这种不等式约束。\n",
    "\n",
    "\n",
    "-----------\n",
    "\n",
    "\n",
    "- STD rules applied.\n",
    "- All numbers must satisfy the Greater-Than Constraints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 5 4 7 6 9 2 1 8 \n",
      "2 9 6 5 1 8 4 3 7 \n",
      "1 7 8 3 4 2 9 5 6 \n",
      "7 2 1 9 5 6 3 8 4 \n",
      "5 4 3 8 2 7 1 6 9 \n",
      "6 8 9 4 3 1 5 7 2 \n",
      "4 6 7 1 9 5 8 2 3 \n",
      "8 3 5 2 7 4 6 9 1 \n",
      "9 1 2 6 8 3 7 4 5 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.019632\n"
     ]
    }
   ],
   "source": [
    "# 测试不等式数独\n",
    "if __name__ == \"__main__\":\n",
    "    test_greater_than_solver = \"000000000000000000000000000000000000000000000000000000000000000000000000000000000\"\n",
    "    greater_than = \"\"\n",
    "    css = CompoundSudokuSolver(grid = test_greater_than_solver, greater_than = \"<-<->--<<>-->----><---<>>--><>---<---><->>>>--<<-<-<>--<>->----->---><<-<--<<-->----->--<-->><--><----->---<\")\n",
    "    css.solveall()\n",
    "\n",
    "#  If the number below < the number above, the sign is \"<\", \n",
    "# If the number below > the number above, the sign is \">\",\n",
    "# For each cell, the sign is sequenced from left to right and from top to bottom.\n",
    "# and iterate cell from left to right and from top to bottom.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/GreaterThan1.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 箭头数独（Arrow Sudoku）\n",
    "\n",
    "- 标准数独规则适用\n",
    "- 规定每个Arrow起点的数字等于箭头经过的其他数字之和，注意箭头经过的数字可以是重复的\n",
    "\n",
    "-----------\n",
    "\n",
    "- STD rules applied\n",
    "- The number of origin of arrow = sum of rest numbers in the same arrow.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 9 3 7 8 4 1 6 5 \n",
      "6 4 8 1 3 5 7 2 9 \n",
      "1 7 5 6 2 9 4 8 3 \n",
      "5 6 4 2 7 3 8 9 1 \n",
      "7 1 2 9 4 8 5 3 6 \n",
      "3 8 9 5 1 6 2 7 4 \n",
      "4 3 7 8 6 1 9 5 2 \n",
      "9 2 6 4 5 7 3 1 8 \n",
      "8 5 1 3 9 2 6 4 7 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.027005\n"
     ]
    }
   ],
   "source": [
    "# 测试箭头数独\n",
    " \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    test_arrow_sudoku_grid = \"200000005000100000005020400060003090000040000080500070007060900000007000800000007\"\n",
    "    test_arrow_sudoku_arrow = [\n",
    "        [(0,4), (0,2), (1,1), (2,0)],\n",
    "        [(4,8),(2,8),(1,7),(0,6)],\n",
    "        [(4,0),(6,0),(7,1),(8,2)],\n",
    "        [(8,4),(8,6),(7,7),(6,8)]\n",
    "    ]\n",
    "    css = CompoundSudokuSolver(grid = test_arrow_sudoku_grid, arrow = test_arrow_sudoku_arrow)\n",
    "    css.solveall()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![](./assets/figures/Arrow%20Sudoku1.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "- [Ref:Bilibili article](https://www.bilibili.com/read/cv10214658)\n",
    "\n",
    "\n",
    "-------\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 无马数独(Anti Knight Sudoku)\n",
    "\n",
    "- 普通数独规则适用\n",
    "- 国际象棋中马能走到的格子和本格子的数字不能相同\n",
    "\n",
    "------------------\n",
    "\n",
    "![](./assets/figures/AntiKnight.png)\n",
    "\n",
    "--------\n",
    "\n",
    "Test Case:\n",
    "\n",
    "\n",
    "\n",
    "# 无缘数独(Anti King Sudoku)\n",
    "\n",
    "- 普通数独规则适用 \n",
    "- 国际象棋中King一步能走到的位置数字都不相同(也就是左上、上、右上、左、右、左下、下、右下)都不等于该格。\n",
    "\n",
    "\n",
    "\n",
    "参考B站大佬的讲解和介绍：[传送门](https://www.bilibili.com/read/cv10214643)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 8 9 4 6 3 1 2 7 \n",
      "4 2 3 9 7 1 5 6 8 \n",
      "6 7 1 8 2 5 4 3 9 \n",
      "8 1 5 6 3 4 7 9 2 \n",
      "9 3 2 5 1 7 6 8 4 \n",
      "7 6 4 2 8 9 3 5 1 \n",
      "1 4 6 3 9 8 2 7 5 \n",
      "3 9 7 1 5 2 8 4 6 \n",
      "2 5 8 7 4 6 9 1 3 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.012209000000000001\n",
      "4 2 1 5 9 3 6 7 8 \n",
      "3 5 8 6 2 7 4 1 9 \n",
      "6 9 7 4 8 1 5 3 2 \n",
      "2 8 6 1 3 9 7 4 5 \n",
      "7 1 9 8 5 4 3 2 6 \n",
      "5 4 3 2 7 6 8 9 1 \n",
      "8 7 5 9 4 2 1 6 3 \n",
      "1 3 2 7 6 8 9 5 4 \n",
      "9 6 4 3 1 5 2 8 7 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.005952000000000001\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    \n",
    "    # Test AntiKnight Sudoku\n",
    "    test_antiknight_grid = \"580400027000970000000005030005030000000000680060000300106000000097050000008000000\"\n",
    "    css = CompoundSudokuSolver(grid = test_antiknight_grid, anti_knight=True)\n",
    "    css.solveall()\n",
    "    \n",
    "    # Test Anti-King Sudoku\n",
    "    test_antiking_grid = \"001003070050007009600081000000000745009000300543000000000940003100700050060300200\"\n",
    "    css = CompoundSudokuSolver(grid = test_antiking_grid, anti_king=True)\n",
    "    css.solveall()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/Antiknight3.png)\n",
    "\n",
    "![](./assets/figures/AntiKing.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 三明治数独\n",
    "\n",
    "- 普通数独规则适用\n",
    "- 行列上的数字表示这一行/列在1和9之间的数字的和\n",
    "\n",
    "\n",
    "-----------\n",
    "\n",
    "- Standard Sudoku rules applied.\n",
    "- Number of row/ col repressent the sum of numbers between 1 and 9 of this col / row.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 1 2 3 9 8 5 6 4 \n",
      "3 4 5 2 7 6 1 9 8 \n",
      "8 6 9 1 5 4 2 3 7 \n",
      "5 3 6 8 4 1 9 7 2 \n",
      "1 9 4 7 2 3 8 5 6 \n",
      "2 8 7 5 6 9 3 4 1 \n",
      "4 5 3 6 8 2 7 1 9 \n",
      "9 2 1 4 3 7 6 8 5 \n",
      "6 7 8 9 1 5 4 2 3 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.017058\n"
     ]
    }
   ],
   "source": [
    "# 测试三明治数独\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    test_sandwich_grid = \"000090064000200100000104007006000000090000806000500000053682010920407005070010020\"\n",
    "    test_sandwich_nums = [\n",
    "        [\"R\", 6, 13, 20, 30, 35, 3, 2, 19, 0], \n",
    "        [\"C\", 5,0 ,0, 0, 0, 7, 0, 2, 0]\n",
    "    ]\n",
    "    \n",
    "    css = CompoundSudokuSolver(grid = test_sandwich_grid, sandwich = test_sandwich_nums)\n",
    "    css.solveall()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/Sandwich%20Sudoku1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Thermometer Sudoku (温度计数独)\n",
    "\n",
    "- 标准数独规则适用\n",
    "- 从水银球到顶部，其数字一定是递增的。就像温度计一样。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 8 5 3 1 4 2 9 6 \n",
      "9 4 6 2 5 7 3 1 8 \n",
      "2 1 3 9 6 8 4 7 5 \n",
      "6 7 1 5 4 2 8 3 9 \n",
      "4 9 8 6 3 1 7 5 2 \n",
      "3 5 2 7 8 9 1 6 4 \n",
      "8 2 7 1 9 6 5 4 3 \n",
      "5 6 4 8 7 3 9 2 1 \n",
      "1 3 9 4 2 5 6 8 7 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.011980000000000001\n"
     ]
    }
   ],
   "source": [
    "# 温度计数独\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    test_thermo_grid = \"785000200000000010000000000000000000000030000000000000000090000004070000100000607\"\n",
    "\n",
    "    test_thermo_cage = [\n",
    "        [ (0,4), (1,3), (2,2), (3,1) ], \n",
    "        [ (4, 8), (3,7), (2,6), (1,5)],\n",
    "        [(4,5), (3,5), (3,4), (3,3) ], \n",
    "        [(4, 3), (5,3), (5,4), (5,5)],\n",
    "        [ (4,0), (5,1), (6,2), (7,3)],\n",
    "        [(8,4), (7,5), (6,6), (5,7)]\n",
    "    ]\n",
    "    css = CompoundSudokuSolver(grid = test_thermo_grid, thermo = test_thermo_cage)\n",
    "    css.solveall()\n",
    "    # Check Completed\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/Thermo.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 4 9 2 6 1 7 3 8 \n",
      "3 6 7 4 9 8 5 2 1 \n",
      "2 1 8 5 7 3 6 4 9 \n",
      "4 7 6 9 3 2 8 1 5 \n",
      "8 9 2 7 1 5 4 6 3 \n",
      "1 3 5 8 4 6 9 7 2 \n",
      "6 5 4 1 2 9 3 8 7 \n",
      "7 8 1 3 5 4 2 9 6 \n",
      "9 2 3 6 8 7 1 5 4 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.003268\n"
     ]
    }
   ],
   "source": [
    "# 标准数独\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    test_std_solver = \"549001738367008001200073040000900005000705460135840070004000307780350006023080000\" \n",
    "    css = CompoundSudokuSolver(grid=test_std_solver, X = 9, Y = 9, std_rule = True)\n",
    "    css.solveall()\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 解谜游戏：杀手数独（Killer Sudoku）\n",
    "\n",
    "\n",
    "- 标准数独规则适用\n",
    "- 除了标准数独规则外，限制每个虚线框内的数字之和等于标记的数字。\n",
    "\n",
    "\n",
    "-------\n",
    "\n",
    "English Version:\n",
    "\n",
    "Killer Sudoku, Rules:\n",
    "\n",
    "- Standard Sudoku Applied.\n",
    "- Sum of numbers in cage equals the marked number.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 1 5 6 4 7 3 9 8 \n",
      "3 6 8 9 5 2 1 7 4 \n",
      "7 9 4 3 8 1 6 5 2 \n",
      "5 8 6 2 7 4 9 3 1 \n",
      "1 4 2 5 9 3 8 6 7 \n",
      "9 7 3 8 1 6 4 2 5 \n",
      "8 2 1 7 3 9 5 4 6 \n",
      "6 5 9 4 2 8 7 1 3 \n",
      "4 3 7 1 6 5 2 8 9 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.010554000000000001\n"
     ]
    }
   ],
   "source": [
    "# 测试杀手数独\n",
    "if __name__ == \"__main__\":\n",
    "    test_killer_solver = \"0\" * 81\n",
    "    test_killer_cages = [\n",
    "        [3, [[0, 0], [0, 1]]],\n",
    "        [15, [[0, 2], [0, 3], [0, 4]]],\n",
    "        [22, [[0, 5], [1, 4], [1, 5], [2, 4]]],\n",
    "        [4, [[0, 6], [1, 6]]],\n",
    "        [16, [[0, 7], [1, 7]]],\n",
    "        [15, [[0, 8], [1, 8], [2, 8], [3, 8]]],\n",
    "        [25, [[1, 0], [1, 1], [2, 0], [2, 1]]],\n",
    "        [17, [[1, 2], [1, 3]]],\n",
    "        [9, [[2, 2], [2, 3], [3, 3]]],\n",
    "        [8, [[2, 5], [3, 5], [4, 5]]],\n",
    "        [20, [[2, 6], [2, 7], [3, 6]]],\n",
    "        [6, [[3, 0], [4, 0]]],\n",
    "        [14, [[3, 1], [3, 2]]],\n",
    "        [17, [[3, 4], [4, 4], [5, 4]]],\n",
    "        [17, [[3, 7], [4, 6], [4, 7]]],\n",
    "        [13, [[4, 1], [4, 2], [5, 1]]],\n",
    "        [20, [[4, 3], [5, 3], [6, 3]]],\n",
    "        [12, [[4, 8], [5, 8]]],\n",
    "        [27, [[5, 0], [6, 0], [7, 0], [8, 0]]],\n",
    "        [6, [[5, 2], [6, 1], [6, 2]]],\n",
    "        [20, [[5, 5], [6, 5], [6, 6]]],\n",
    "        [6, [[5, 6], [5, 7]]],\n",
    "        [10, [[6, 4], [7, 3], [7, 4], [8, 3]]],\n",
    "        [14, [[6, 7], [6, 8], [7, 7], [7, 8]]],\n",
    "        [8, [[7, 1], [8, 1]]],\n",
    "        [16, [[7, 2], [8, 2]]],\n",
    "        [15, [[7, 5], [7, 6]]],\n",
    "        [13, [[8, 4], [8, 5], [8, 6]]],\n",
    "        [17, [[8, 7], [8, 8]]]\n",
    "    ]\n",
    "    \n",
    "    css = CompoundSudokuSolver(test_killer_solver, killer = test_killer_cages)\n",
    "    css.solveall()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![Killer Sudoku](./assets/figures/KillerSudoku.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 解决思维谜题：连续数独（Consecutive Sudoku）\n",
    "\n",
    "- 标准数独规则适用；\n",
    "- 有标记的相邻的两个格子数字必须是连续的（差的绝对值是1，因此在实现的时候用 `AllAbsEquality` 函数）\n",
    "\n",
    "------\n",
    "\n",
    "English Version:\n",
    "\n",
    "**Solve Consecutive Sudoku**\n",
    "\n",
    "- Standard Sudoku Rules applied.\n",
    "- Two adjacent cage with marker bust be integer-consecutive, (e.g. 1,2 or 2,3; 4,5 or 3,4)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8 1 5 7 3 9 2 4 6 \n",
      "2 7 4 1 8 6 9 5 3 \n",
      "3 6 9 2 5 4 1 8 7 \n",
      "7 9 3 5 4 2 8 6 1 \n",
      "4 2 6 9 1 8 3 7 5 \n",
      "5 8 1 6 7 3 4 9 2 \n",
      "6 4 8 3 2 5 7 1 9 \n",
      "9 3 7 4 6 1 5 2 8 \n",
      "1 5 2 8 9 7 6 3 4 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.014958\n",
      "815739246274186953369254187793542861426918375581673492648325719937461528152897634\n"
     ]
    }
   ],
   "source": [
    "test_consecutive_nums = \"000000040000000900000000000003000000000000000001000090000000000000000020000000000\"\n",
    "test_consecutive_constr = \"..........C....C.........CC.C.........C..C....C.......C...........C.........C.....C.....C.C..C...........C.....CCC...CC..............CC....C.C.C\"\n",
    "css = CompoundSudokuSolver(grid = test_consecutive_nums, consecutive = test_consecutive_constr )\n",
    "result = css.solveall()\n",
    "print(result)\n",
    "\n",
    "# Consecutive Sudoku(Evil) https://gridpuzzle.com/consecutive-sudoku/21229"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "144\n"
     ]
    }
   ],
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----------\n",
    "\n",
    "![](./assets/figures/ConsecutiveSudoku.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------\n",
    "\n",
    "# 解决思维谜题：小杀手数独（Petite Killer Sudoku）\n",
    "\n",
    "- 标准数独规则适用；\n",
    "- 斜对角线上的数字和等于小数字。注意一共有四个方向的斜对角线，分别用\"T\",\"B\",\"L\",\"R\" 标记“上(Top)”“下(Bottom)”“左(Left)”“右(Right)”，因此组成了“TL”、“RT”、“BR”、“LB” 四个方向来标记数字。\n",
    "\n",
    "\n",
    "> Numbers with arrows indicate sum of the numbers in each direction. Direction is shown in each arrow.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 9 5 6 3 1 7 8 4 \n",
      "1 8 3 7 4 9 2 6 5 \n",
      "6 7 4 8 5 2 1 9 3 \n",
      "7 2 6 4 9 3 8 5 1 \n",
      "3 1 8 5 7 6 9 4 2 \n",
      "5 4 9 2 1 8 3 7 6 \n",
      "8 3 7 1 6 5 4 2 9 \n",
      "9 6 2 3 8 4 5 1 7 \n",
      "4 5 1 9 2 7 6 3 8 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 1338\n",
      "WallTime: 0.107007\n"
     ]
    }
   ],
   "source": [
    "# 测试小杀手数独\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    test_petite_killer = \"005000000000000000000002000000000000000006040000000000000060000000300000000000008\"\n",
    "    test_petite_killer_cages = [ \n",
    "        [ \"TL\", 2, 10, 19, 23, 19, 25, 45, 47], # TL means \"Top to Left\" (digits from left to right)\n",
    "        [ \"RT\", 4, 13, 16, 13, 20, 30, 45, 47], # RT means \"Right to Top\" (digits from Top to bottom)\n",
    "        [ \"BR\", 37, 35, 30, 19, 20, 16, 10, 8], # BR means \"Bottom to Right\" (digits from left to right)\n",
    "        [ \"LB\", 33, 34, 33, 19, 19, 15, 14, 4] # LB means \"left to Bottom\" (digits from top to bottom)\n",
    "    ]\n",
    "\n",
    "    css = CompoundSudokuSolver(grid = test_petite_killer, petite_killer=test_petite_killer_cages )\n",
    "    css.solveall()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------\n",
    "\n",
    "\n",
    "![](./assets/figures/Petite%20Sudoku%201.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 窗口数独 （所有在给定区域内均为1～9不重复的数独）\n",
    "\n",
    "![](./assets/figures/WindowSudoku.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8 6 7 4 3 9 1 5 2 \n",
      "4 3 1 7 2 5 6 9 8 \n",
      "5 2 9 6 1 8 4 3 7 \n",
      "3 4 5 8 9 2 7 1 6 \n",
      "6 1 2 5 7 3 8 4 9 \n",
      "9 7 8 1 6 4 5 2 3 \n",
      "7 9 6 2 5 1 3 8 4 \n",
      "2 5 4 3 8 7 9 6 1 \n",
      "1 8 3 9 4 6 2 7 5 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.010362000000000001\n"
     ]
    }
   ],
   "source": [
    "# 测试窗口数独 窗口数独(中级) https://gridpuzzle.com/windoku/1n06k\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    test_window_sudoku = \"007430000000000690020600000300090006600000009900060003000001080054000000000046200\"\n",
    "    test_window_sudoku_windows = \"000000000011102220011102220011102220000000000033304440033304440033304440000000000\"\n",
    "\n",
    "    css = CompoundSudokuSolver(grid = test_window_sudoku, all_nine = test_window_sudoku_windows )\n",
    "    css.solveall()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  XV 数独\n",
    "\n",
    "- 标记了X的，两个格子的数字和为10，标记了V的，两个格子和为5.\n",
    "\n",
    "![](./assets/figures/XV_sudoku.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 3 8 4 2 7 1 5 6 \n",
      "6 2 5 1 3 8 4 9 7 \n",
      "7 4 1 9 5 6 2 8 3 \n",
      "2 1 3 5 6 4 8 7 9 \n",
      "8 5 9 3 7 1 6 4 2 \n",
      "4 6 7 2 8 9 3 1 5 \n",
      "1 8 2 7 9 3 5 6 4 \n",
      "3 9 4 6 1 5 7 2 8 \n",
      "5 7 6 8 4 2 9 3 1 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.009729\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    test_XV_sudoku = \"000000000000000000000000000000000000000000000000000000000000000090000008000000000\"\n",
    "    test_XV_example = \"---------V-VV-V-------------X----X-VX---X--V---XX------X---X----V------X--X----V-X-V-X--X----V---------X-----X----X------X----X--X-V--V---------\"\n",
    "# https://gridpuzzle.com/vx-sudoku/159j0\n",
    "    css = CompoundSudokuSolver(grid = test_XV_sudoku, XV = test_XV_example )\n",
    "    css.solveall()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "144\n"
     ]
    }
   ],
   "source": [
    "938427156625138497741956283213564879859371642467289315182793564394615728576842931\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "V, x[0, 1], x[1, 1]\n",
      "V, x[0, 3], x[1, 3]\n",
      "V, x[0, 4], x[1, 4]\n",
      "V, x[0, 6], x[1, 6]\n",
      "X, x[1, 3], x[2, 3]\n",
      "X, x[1, 8], x[2, 8]\n",
      "V, x[2, 1], x[2, 2]\n",
      "X, x[2, 2], x[2, 3]\n",
      "X, x[2, 6], x[2, 7]\n",
      "V, x[2, 1], x[3, 1]\n",
      "X, x[2, 5], x[3, 5]\n",
      "X, x[2, 6], x[3, 6]\n",
      "X, x[3, 4], x[3, 5]\n",
      "X, x[3, 0], x[4, 0]\n",
      "V, x[3, 5], x[4, 5]\n",
      "X, x[4, 3], x[4, 4]\n",
      "X, x[4, 6], x[4, 7]\n",
      "V, x[4, 3], x[5, 3]\n",
      "X, x[4, 5], x[5, 5]\n",
      "V, x[4, 7], x[5, 7]\n",
      "X, x[5, 0], x[5, 1]\n",
      "X, x[5, 3], x[5, 4]\n",
      "V, x[5, 0], x[6, 0]\n",
      "X, x[6, 1], x[6, 2]\n",
      "X, x[6, 7], x[6, 8]\n",
      "X, x[6, 4], x[7, 4]\n",
      "X, x[7, 2], x[7, 3]\n",
      "X, x[7, 7], x[7, 8]\n",
      "X, x[7, 2], x[8, 2]\n",
      "V, x[7, 4], x[8, 4]\n",
      "V, x[7, 7], x[8, 7]\n"
     ]
    }
   ],
   "source": [
    "a = \"---------V-VV-V-------------X----X-VX---X--V---XX------X---X----V------X--X----V-X-V-X--X----V---------X-----X----X------X----X--X-V--V---------\"\n",
    "\n",
    "for idx, sub_ in enumerate(a):\n",
    "    if sub_ == \"-\":\n",
    "        continue\n",
    "    sub_a, sub_b = idx // 17 , idx % 17 \n",
    "    if sub_b <= 7:\n",
    "        print(f\"{sub_}, x[{sub_a}, {sub_b}], x[{sub_a}, {int(sub_b) + 1}]\")\n",
    "    elif sub_b <= 16:\n",
    "        print(f\"{sub_}, x[{sub_a}, {int(sub_b) - 8}], x[{int(sub_a) + 1}, {int(sub_b) - 8}]\")\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "  \u001b[4m1 4 3 3 4 3 3 2 2\u001b[0m\n",
      "1|0 0 0 0 0 0 0 0 0|2\n",
      "4|0 0 0 0 0 0 0 0 0|2\n",
      "5|0 0 0 0 0 0 0 0 0|2\n",
      "2|0 0 0 0 0 0 0 0 0|3\n",
      "3|0 0 0 0 0 0 0 0 0|4\n",
      "2|0 0 0 0 0 0 0 0 0|3\n",
      "3|0 0 0 0 0 0 0 0 0|1\n",
      "2|0 0 0 0 0 0 0 0 0|3\n",
      "4|\u001b[4m0 0 0 0 0 0 0 0 0\u001b[0m|5\n",
      "  4 2 3 2 1 3 2 3 3\n",
      "\n",
      "\n",
      "\n",
      "starting solver with 1s time limit!\n",
      "\n",
      "done after 0.22s\n",
      "\n",
      "this many solutions found: 1\n",
      "\n",
      "solution #0:\n",
      "\n",
      "[[9 5 7 6 4 1 3 2 8]\n",
      " [3 7 8 2 5 4 1 9 6]\n",
      " [5 6 3 7 8 9 2 1 4]\n",
      " [6 1 9 3 7 2 8 4 5]\n",
      " [1 8 4 9 3 6 7 5 2]\n",
      " [8 4 6 1 2 5 9 7 3]\n",
      " [7 3 2 5 1 8 4 6 9]\n",
      " [2 9 1 4 6 3 5 8 7]\n",
      " [4 2 5 8 9 7 6 3 1]]\n"
     ]
    }
   ],
   "source": [
    "from __future__ import print_function\n",
    "\n",
    "import sys\n",
    "from ortools.constraint_solver import pywrapcp\n",
    "import numpy as np\n",
    "from time import time\n",
    "\n",
    "from random import randint\n",
    "import numpy as np\n",
    "from copy import copy,deepcopy\n",
    "\n",
    "\n",
    "class Skyscraper:\n",
    "\n",
    "    def __init__(self,N=4,see_list = [],const_list=[]):\n",
    "        pass\n",
    "        self.N = N\n",
    "        #self.state =  np.array([N*[i+1] for i in range(N)])\n",
    "\n",
    "        self.state = np.array([[0 for _ in range(self.N)] for i in range(self.N)])\n",
    "\n",
    "        #The way I'm gonna organize this is as a list of lists, where it goes\n",
    "        #left, right, top, down\n",
    "        self.see_list = np.array(see_list)\n",
    "\n",
    "        self.const_list = const_list\n",
    "        for const in self.const_list:\n",
    "            ind = const[0]\n",
    "            val = const[1]\n",
    "            self.state[ind[0],ind[1]] = val\n",
    "\n",
    "\n",
    "        self.const_list_indices = [x[0] for x in self.const_list]\n",
    "        #print(self.const_list)\n",
    "        #print(self.const_list_indices)\n",
    "\n",
    "        self.max_FF = 16*(self.N-1) + 8*(self.N)\n",
    "\n",
    "\n",
    "\n",
    "    def printState(self):\n",
    "        board = '\\n\\n'\n",
    "\n",
    "        #board = board + '  ' + ' '.join([str(x) for x in self.see_list[2]]) + '\\n'\n",
    "\n",
    "        #board = board + '  ' + '__'*(self.N-1) + '_' + ' ' + '\\n'\n",
    "\n",
    "        board = board + '  ' +  '\\033[4m' + ' '.join([str(x) for x in self.see_list[2]]) +  '\\033[0m' + '\\n'\n",
    "\n",
    "        \"\"\"for i in range(self.N):\n",
    "\n",
    "            board = board + str(self.see_list[0][i]) + '|'\n",
    "\n",
    "            board = board + ' '.join([str(x) for x in self.state[i,:]])\n",
    "\n",
    "            board = board + '|' + str(self.see_list[1][i])\n",
    "\n",
    "            board = board + '\\n'\"\"\"\n",
    "\n",
    "        for i in range(self.N-1):\n",
    "\n",
    "            board = board + str(self.see_list[0][i]) + '|'\n",
    "\n",
    "            board = board + ' '.join([str(x) for x in self.state[i,:]])\n",
    "\n",
    "            board = board + '|' + str(self.see_list[1][i])\n",
    "\n",
    "            board = board + '\\n'\n",
    "\n",
    "        board = board + str(self.see_list[0][self.N-1]) + '|'\n",
    "\n",
    "        board = board + '\\033[4m' + ' '.join([str(x) for x in self.state[self.N-1,:]]) + '\\033[0m'\n",
    "\n",
    "        board = board + '|' + str(self.see_list[1][self.N-1])\n",
    "\n",
    "        board = board + '\\n'\n",
    "\n",
    "        #board = board + '  ' + '‾‾'*(self.N-1) + '‾' + ' ' + '\\n'\n",
    "        board = board + '  ' + ' '.join([str(x) for x in self.see_list[3]]) + '\\n'\n",
    "\n",
    "        print(board)\n",
    "\n",
    "    def countSeen(self,sel,row_num):\n",
    "        #will return a tuple of what you see from the left and right if you pass it 'row',\n",
    "        #up and down if you pass it 'col'\n",
    "\n",
    "        if sel=='row':\n",
    "            row = self.state[row_num]\n",
    "        if sel=='col':\n",
    "            row = self.state[:,row_num]\n",
    "\n",
    "        #print(row)\n",
    "        max_left = max_right = -10000\n",
    "        seen_left = seen_right = 0\n",
    "\n",
    "        for i in range(self.N):\n",
    "            if row[i]>max_left:\n",
    "                max_left = row[i]\n",
    "                seen_left += 1\n",
    "                if row[i]==self.N:\n",
    "                    break\n",
    "\n",
    "        #and for from the other direction:\n",
    "        row = np.flip(row,axis=0)\n",
    "        #print(row)\n",
    "        for i in range(self.N):\n",
    "            if row[i]>max_right:\n",
    "                max_right = row[i]\n",
    "                seen_right += 1\n",
    "                if row[i]==self.N:\n",
    "                    break\n",
    "\n",
    "        #print([seen_left,seen_right])\n",
    "        return([seen_left,seen_right])\n",
    "\n",
    "\n",
    "\n",
    "    def countOccurrenceErrors(self):\n",
    "\n",
    "        base_occur = [-1]*self.N\n",
    "\n",
    "        error_sum = 0\n",
    "\n",
    "        for i in range(self.N):\n",
    "\n",
    "            occur_row = copy(base_occur)\n",
    "            occur_col = copy(base_occur)\n",
    "\n",
    "            for j in range(self.N):\n",
    "\n",
    "                occur_row[self.state[i,j]-1] += 1\n",
    "                occur_col[self.state[j,i]-1] += 1\n",
    "\n",
    "\n",
    "            #print('there are {} errors in row {}'.format(sum(np.absolute(occur_row)), i))\n",
    "            #print('there are {} errors in col {}'.format(sum(np.absolute(occur_col)), i))\n",
    "            error_sum += sum(np.absolute(occur_row)) + sum(np.absolute(occur_col))\n",
    "\n",
    "        return(error_sum)\n",
    "\n",
    "    def fitnessFunction(self):\n",
    "\n",
    "        occur_errors = self.countOccurrenceErrors()\n",
    "\n",
    "        seen_errors = 0\n",
    "\n",
    "        for i in range(self.N):\n",
    "            row_seen = self.countSeen('row',i)\n",
    "            col_seen = self.countSeen('col',i)\n",
    "\n",
    "            row_seen_error = sum(np.absolute(row_seen - self.see_list[[0,1],i]))\n",
    "            col_seen_error = sum(np.absolute(col_seen - self.see_list[[2,3],i]))\n",
    "\n",
    "            #print('row_seen_error',row_seen_error)\n",
    "            #print('col_seen_error',col_seen_error)\n",
    "            seen_errors += row_seen_error + col_seen_error\n",
    "\n",
    "        return(occur_errors + seen_errors)\n",
    "\n",
    "    def solFound(self):\n",
    "        if self.fitnessFunction()<1:\n",
    "            return(True)\n",
    "        else:\n",
    "            return(False)\n",
    "\n",
    "    def isSameState(self,other):\n",
    "        return((self.state==other.state).all())\n",
    "\n",
    "    def mutate(self):\n",
    "        row = randint(0,self.N-1)\n",
    "        col = randint(0,self.N-1)\n",
    "        if [row,col] not in self.const_list_indices:\n",
    "            self.state[row,col] = randint(1,self.N)\n",
    "\n",
    "\n",
    "    def mate(self,other):\n",
    "\n",
    "        new_1 = deepcopy(self)\n",
    "        new_2 = deepcopy(other)\n",
    "\n",
    "        r1 = randint(0,self.N-1)\n",
    "        r2 = randint(r1+1,self.N)\n",
    "\n",
    "        c1 = randint(0,self.N-1)\n",
    "        c2 = randint(c1+1,self.N)\n",
    "\n",
    "        temp_slice = copy(new_1.state[r1:r2,c1:c2])\n",
    "        new_1.state[r1:r2,c1:c2] = copy(new_2.state[r1:r2,c1:c2])\n",
    "        new_2.state[r1:r2,c1:c2] = temp_slice\n",
    "\n",
    "        return((new_1,new_2))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "med_88_SS = [[2,3,2,4,4,2,3,1],[1,3,5,3,2,3,2,4],[2,3,2,2,4,6,3,1],[1,2,3,4,3,2,2,4]]\n",
    "med_88_constlist = [([0,1],1),([1,3],1),([2,1],3),([3,2],3),([4,2],6),([4,3],3),([4,5],5),([5,0],4),([5,4],6),([6,1],2),([6,4],1),([7,4],5)]\n",
    "\n",
    "hard_88_ss = [[3,2,0,0,0,0,4,0],[3,0,2,4,4,2,0,0],[0,3,0,4,5,4,0,0],[0,3,4,0,2,1,4,2]]\n",
    "hard_88_constlist = [([1,1],2),([2,1],5),([2,3],3),([4,3],4),([3,7],2),([5,5],1),([6,1],3),([6,7],1),([7,4],3)]\n",
    "\n",
    "ss_99 = [[1,4,5,2,3,2,3,2,4],[2,2,2,3,4,3,1,3,5],[1,4,3,3,4,3,3,2,2],[4,2,3,2,1,3,2,3,3]]\n",
    "ss_99_constlist = [([0,3],6),([0,7],2),([1,0],3),([1,8],6),([2,0],5),([2,3],7),\n",
    "([2,6],2),([3,1],1),([3,5],2),([3,6],8),([4,6],7),([4,7],5),\n",
    "([5,1],4),([5,3],1),([5,7],7),([5,8],3),([6,1],3),([6,3],5),\n",
    "([6,4],1),([7,5],3),([7,7],8),([8,5],7)]\n",
    "\n",
    "see_list = ss_99\n",
    "const_list = ss_99_constlist\n",
    "#see_list=[[4,2,2,1],[1,2,2,4],[4,2,2,1],[1,2,2,4]]\n",
    "#left (t to b), right (t to b), top (l to r), down (l to r)\n",
    "#s = Skyscraper(4,see_list=[[2,1,3,4],[2,1,3,4],[2,1,3,4],[2,1,3,4]])\n",
    "size = len(see_list[0])\n",
    "s = Skyscraper(size,see_list=see_list)\n",
    "s.printState()\n",
    "\n",
    "\n",
    "# Creates the solver.\n",
    "solver = pywrapcp.Solver(\"simple_example\")\n",
    "\n",
    "#Create the variables we'll solve for\n",
    "ss_vars = np.array([[solver.IntVar(1, size, \"a_{}{}\".format(i,j)) for j in range(size)] for i in range(size)])\n",
    "\n",
    "#CONSTRAINTS\n",
    "\n",
    "# All rows and columns must be different.\n",
    "for i in range(len(ss_vars)):\n",
    "    solver.Add(solver.AllDifferent(ss_vars[i,:].tolist()))\n",
    "    solver.Add(solver.AllDifferent(ss_vars[:,i].tolist()))\n",
    "\n",
    "#Make the 'buildings seen' correct.\n",
    "#I'm going to do it in pairs, because the way it is, I have to reverse stuff.\n",
    "#'sidepair 0' are going to be the left and right sides, where the var list will have to be switched for the right.\n",
    "#similarly, sidepair 1 is for the top and bottom.\n",
    "for entry in range(size):\n",
    "    #left and right\n",
    "    sidepair = 0\n",
    "    left_top = 2*sidepair\n",
    "    right_bot = 2*sidepair + 1\n",
    "    #print('adding constraint for left/right sidepair {}, entry {}: {} and {}'.format(sidepair,entry,see_list[left_top][entry],see_list[right_bot][entry]))\n",
    "    if see_list[left_top][entry]!=0:\n",
    "        solver.Add(\n",
    "            (1 + solver.Sum(\n",
    "                [\n",
    "                    solver.Min(\n",
    "                        solver.Max(\n",
    "                            ss_vars[entry,:j+1].tolist()\n",
    "                            ) - solver.Max(ss_vars[entry,:j].tolist()),1) for j in range(1,size)]\n",
    "                ))\n",
    "            == see_list[left_top][entry]\n",
    "        )\n",
    "    if see_list[right_bot][entry]!=0:\n",
    "        solver.Add((1 + solver.Sum([solver.Min(solver.Max(ss_vars[entry,-(j+1):].tolist()) - solver.Max(ss_vars[entry,-j:].tolist()),1) for j in range(1,size)])) == see_list[right_bot][entry])\n",
    "    #top and bottom\n",
    "    sidepair = 1\n",
    "    left_top = 2*sidepair\n",
    "    right_bot = 2*sidepair + 1\n",
    "    #print('adding constraint for left/right sidepair {}, entry {}: {} and {}'.format(sidepair,entry,see_list[left_top][entry],see_list[right_bot][entry]))\n",
    "    if see_list[left_top][entry]!=0:\n",
    "        solver.Add((1 + solver.Sum([solver.Min(solver.Max(ss_vars[:j+1,entry].tolist()) - solver.Max(ss_vars[:j,entry].tolist()),1) for j in range(1,size)])) == see_list[left_top][entry])\n",
    "    if see_list[right_bot][entry]!=0:\n",
    "        solver.Add((1 + solver.Sum([solver.Min(solver.Max(ss_vars[-(j+1):,entry].tolist()) - solver.Max(ss_vars[-j:,entry].tolist()),1) for j in range(1,size)])) == see_list[right_bot][entry])\n",
    "\n",
    "#Add constraints for given constants, if there are any\n",
    "for const in const_list:\n",
    "    ind = const[0]\n",
    "    val = const[1]\n",
    "    solver.Add(ss_vars[ind[0],ind[1]] == val)\n",
    "\n",
    "\n",
    "#Soluion collector\n",
    "collector = solver.AllSolutionCollector()\n",
    "collector.Add(ss_vars.flatten().tolist())\n",
    "\n",
    "#The \"decision builder\". I just used the one from:\n",
    "#https://developers.google.com/optimization/cp/cp_tasks\n",
    "db = solver.Phase(ss_vars.flatten().tolist(), solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)\n",
    "\n",
    "#Solve it!\n",
    "time_limit_s = 1\n",
    "solver.TimeLimit(1000*time_limit_s)\n",
    "print('\\n\\nstarting solver with {}s time limit!'.format(time_limit_s))\n",
    "start_time = time()\n",
    "solver.Solve(db, [collector])\n",
    "print('\\ndone after {:.2f}s'.format(time()-start_time))\n",
    "\n",
    "#print solutions\n",
    "print('\\nthis many solutions found:',collector.SolutionCount())\n",
    "for sol_num in range(collector.SolutionCount()):\n",
    "    sol = np.array([[collector.Value(sol_num,ss_vars[i,j]) for j in range(size)] for i in range(size)])\n",
    "    print('\\nsolution #{}:\\n'.format(sol_num))\n",
    "    print(sol)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 4 7 9 6 3 8 2 5 \n",
      "5 6 9 2 7 8 4 1 3 \n",
      "3 2 8 1 4 5 7 6 9 \n",
      "9 3 6 7 1 2 5 8 4 \n",
      "8 5 1 6 3 4 9 7 2 \n",
      "2 7 4 5 8 9 1 3 6 \n",
      "6 9 3 8 5 1 2 4 7 \n",
      "4 8 2 3 9 7 6 5 1 \n",
      "7 1 5 4 2 6 3 9 8 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.006566000000000001\n",
      "147963825569278413328145769936712584851634972274589136693851247482397651715426398\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    grid = \"000900005000008000300000060000702000001004000074009100600801040402000000700000390\"\n",
    "\n",
    "    even_odd = \".E...OEE.O.O....O...E..OO..OOE......E...O..............OO...E...E.OO.E.......E...\"\n",
    "    \n",
    "    css = CompoundSudokuSolver(grid = grid, even_odd = even_odd)\n",
    "    result = css.solveall()\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/EvenOddSudoku.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 3 7 9 6 4 8 2 1 \n",
      "8 1 4 3 2 5 7 6 9 \n",
      "2 6 9 8 7 1 4 5 3 \n",
      "9 5 6 4 3 8 2 1 7 \n",
      "4 2 8 5 1 7 9 3 6 \n",
      "3 7 1 6 9 2 5 8 4 \n",
      "6 8 5 1 4 9 3 7 2 \n",
      "7 4 3 2 8 6 1 9 5 \n",
      "1 9 2 7 5 3 6 4 8 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 0\n",
      "WallTime: 0.022574\n",
      "537964821814325769269871453956438217428517936371692584685149372743286195192753648\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    grid = \"0\" * 81\n",
    "    kropki = \".....B.W.....WW....WW..W........W...WW..W..W.B..B...W.W..B....W.W..WB......BW..W............BBW.....WB........WB.BB.....WW.......W..B........B.B\"\n",
    "\n",
    "    css = CompoundSudokuSolver(grid = grid, kropki=kropki)\n",
    "    result = css.solveall()\n",
    "    print(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/KropkiSudoku.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./assets/figures/center-dotSudoku.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 6\\\n"
     ]
    }
   ],
   "source": [
    "a = [\"1\",\"2\",\"3\",\"4\",\"6\\\\\"]\n",
    "print(\" \".join(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py310_arm",
   "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.10.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}