Puzzles/Heyawake.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Heyawake\n",
    "\n",
    "Rules can be found [here](https://www.janko.at/Raetsel/Heyawake/).\n",
    "\n",
    "- Blacken some cells of the grid.\n",
    "- A number in a region indicates how many cells in this region must be blackened. In regions without a number any amount of cells may be blackened (maybe none).\n",
    "- Black cells may not be orthogonally adjacent (diagonally is allowed).\n",
    "- Stripes of adjacent white cells may not span across more than one region border horizontally or vertically.\n",
    "- All white cells must form a single orthogonally contiguous area.\n",
    "\n",
    "----------\n",
    "\n",
    "\n",
    "- 将网格的某些单元格涂黑。\n",
    "- 区域中的数字表示此区域中有多少单元格必须被涂黑。在没有数字的区域中，任何数量的细胞都可能变黑（可能没有格被涂黑）。\n",
    "- 黑格不能正交相邻（允许对角线相邻）。\n",
    "- 相邻白细胞的条纹不能跨越水平或垂直边界的多个区域。\n",
    "- 所有白细胞必须形成一个正交连续的区域。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from collections import deque\n",
    "from itertools import chain\n",
    "# ===== vsualzie ===== \n",
    "import matplotlib.pyplot as plt\n",
    "from matplotlib.patches import Rectangle, Circle\n",
    "from matplotlib.pyplot import MultipleLocator\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['-', '2', '-', '-', '-', '2', '-', '-', '-', '1', '-', '-', '-', '2', '-', '1', '-', '-', '-', '-', '1', '-', '3', '-']\n",
      "['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-']\n",
      "['-', '3', '-', '-', '-', '-', '-', '-', '-', '2', '-', '-', '-', '-', '-', '-', '-', '-', '1', '-', '-', '-', '-', '-']\n",
      "['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '2', '-', '-', '1', '-', '-', '-', '-', '-', '-', '-', '-']\n",
      "['-', '1', '-', '-', '3', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '5', '-', '-', '-', '-', '-', '2']\n",
      "['-', '-', '-', '-', '3', '-', '-', '-', '-', '-', '-', '-', '-', '1', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-']\n",
      "['-', '1', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '2', '-', '-', '-', '-', '3', '-', '-', '-']\n",
      "['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '1', '-', '-', '-', '-', '-', '-']\n",
      "['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-']\n",
      "['4', '-', '-', '2', '-', '-', '3', '-', '-', '-', '-', '-', '-', '-', '-', '3', '-', '-', '-', '-', '3', '-', '-', '-']\n",
      "['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-']\n",
      "['-', '-', '-', '1', '-', '-', '-', '-', '-', '-', '-', '-', '3', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-']\n",
      "['2', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-']\n",
      "['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '2', '-', '-', '-', '-', '-', '-', '2', '-', '-', '-', '-']\n",
      "['1', '2', '2', '2', '13', '14', '14', '15', '15', '21', '21', '37', '37', '38', '38', '39', '39', '40', '40', '40', '41', '41', '42', '42']\n",
      "['1', '2', '2', '2', '13', '14', '14', '15', '15', '21', '21', '37', '37', '38', '38', '39', '39', '40', '40', '40', '41', '41', '42', '42']\n",
      "['1', '3', '3', '3', '16', '16', '17', '15', '15', '22', '22', '37', '37', '43', '43', '39', '39', '50', '52', '52', '41', '41', '42', '42']\n",
      "['1', '3', '3', '3', '16', '16', '18', '19', '20', '22', '22', '44', '45', '43', '43', '49', '49', '51', '52', '52', '41', '41', '42', '42']\n",
      "['1', '4', '4', '4', '23', '23', '23', '23', '23', '23', '23', '23', '45', '46', '47', '49', '49', '53', '53', '53', '54', '54', '54', '55']\n",
      "['1', '4', '4', '4', '24', '24', '24', '24', '25', '25', '99', '97', '45', '48', '48', '49', '49', '53', '53', '53', '54', '54', '54', '55']\n",
      "['1', '5', '5', '5', '24', '24', '24', '24', '25', '25', '98', '98', '45', '48', '48', '61', '61', '53', '53', '53', '57', '57', '56', '55']\n",
      "['1', '6', '8', '8', '8', '26', '26', '26', '25', '25', '98', '98', '62', '62', '62', '61', '61', '60', '59', '59', '57', '57', '56', '55']\n",
      "['7', '7', '8', '8', '8', '27', '27', '28', '28', '28', '28', '28', '28', '28', '28', '61', '61', '60', '59', '59', '57', '57', '56', '55']\n",
      "['9', '9', '9', '11', '11', '11', '29', '29', '29', '29', '29', '36', '36', '36', '36', '63', '63', '63', '59', '59', '58', '58', '56', '55']\n",
      "['9', '9', '9', '11', '11', '11', '30', '30', '30', '30', '30', '36', '36', '36', '36', '63', '63', '63', '65', '65', '58', '58', '56', '55']\n",
      "['9', '9', '9', '12', '12', '31', '31', '31', '31', '31', '31', '31', '35', '35', '35', '63', '63', '63', '65', '65', '58', '58', '56', '55']\n",
      "['10', '10', '10', '10', '32', '32', '32', '33', '34', '34', '34', '34', '35', '35', '35', '64', '67', '67', '67', '67', '67', '67', '67', '66']\n",
      "['10', '10', '10', '10', '32', '32', '32', '33', '34', '34', '34', '34', '68', '68', '68', '68', '68', '68', '68', '69', '69', '69', '69', '69']\n"
     ]
    }
   ],
   "source": [
    "def readGrid(path):\n",
    "    with open(f\"../assets/data/Heyawake/problems/{path}\") as f:\n",
    "        num = f.readline()\n",
    "        m, n = num.split(\" \")[0], num.split(\" \")[1]\n",
    "        grid = f.readlines()\n",
    "        res = [g.strip().split(\" \") for g in grid]\n",
    "        return int(m), int(n), res\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    m, n, grid = readGrid(\"20_14x24.txt\")\n",
    "    num_grid, maze_grid = grid[:m], grid[m:]\n",
    "    for g in num_grid:\n",
    "        print(g)\n",
    "    for g in maze_grid:\n",
    "        print(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SCIP solver (Verified!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/var/folders/wp/zfkgqzvj2lq6fk2gy0rbmq6m0000gn/T/ipykernel_17983/1826740586.py:9: UserWarning: linked SCIP 9.02 is not recommended for this version of PySCIPOpt - use version 9.2.1\n",
      "  Heyawake = Model('Heyawake')\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". . . X . . X . . . X . . . X . X . . . . . X .\n",
      ". X . . . X . . X . . . . X . . . X . X . . . .\n",
      ". . X . . . X . . X . X . . X . . . X . . . X .\n",
      ". X . X . . . X . . X . X . . . X . . . X . . X\n",
      ". . . . X . X . X . . . . X . . . X . X . . . .\n",
      ". X . . . X . . . X . X . . X . . . X . . . X .\n",
      ". . X . X . X . . . X . X . . X . X . X . X . .\n",
      ". X . X . . . X . X . . . X . . X . . . X . . X\n",
      ". . . . . X . . . . . X . . X . . X . . . X . .\n",
      "X . X . . . X . X . X . X . . . X . . . X . . X\n",
      ". . . X . X . X . X . . . . . X . . X . . X . .\n",
      "X . X . X . . . . . . X . X . . . X . . X . X .\n",
      ". X . . . . X . X . X . X . X . X . . X . . . .\n",
      ". . . X . . . X . . . . . . . X . . X . . X . X\n"
     ]
    }
   ],
   "source": [
    "from pyscipopt import Model, quicksum\n",
    "\n",
    "def has_two_or_fewer_unique_elements(lst):\n",
    "    return len(set(lst)) <= 2\n",
    "\n",
    "def HeyawakeSolverWithSCIP(m, n, grid):\n",
    "    num_grid, maze_grid = grid[:m], grid[m:]\n",
    "    \n",
    "    Heyawake = Model('Heyawake')\n",
    "    Heyawake.setMinimize()  # 替代modelSense设置\n",
    "\n",
    "    x = {}\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            x[i, j] = Heyawake.addVar(\n",
    "                name=f\"x[{i},{j}]\",\n",
    "                vtype=\"B\",  # 二进制类型标识符变更\n",
    "                obj=1.0     # 目标系数设置保持\n",
    "            )\n",
    "\n",
    "    cell_coord = {}\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            cell_id = maze_grid[i][j]\n",
    "            if cell_id not in cell_coord:\n",
    "                cell_coord[cell_id] = []\n",
    "            cell_coord[cell_id].append((i, j))\n",
    "\n",
    "    \n",
    "    for cell_id, positions in cell_coord.items():\n",
    "        i, j = positions[0]  \n",
    "        if num_grid[i][j] != '-':\n",
    "            Heyawake.addCons(\n",
    "                quicksum(x[pos] for pos in positions) == int(num_grid[i][j]),\n",
    "                name=f\"cell_{cell_id}\"\n",
    "            )\n",
    "\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            for k in range(j+1, n+1):\n",
    "                if not has_two_or_fewer_unique_elements(maze_grid[i][j:k]):\n",
    "                    Heyawake.addCons(\n",
    "                        quicksum(x[i,g] for g in range(j,k)) >= 1,\n",
    "                        name=f\"row_{i}_{j}_{k}\"\n",
    "                    )\n",
    "\n",
    "\n",
    "    for j in range(n):\n",
    "        for i in range(m):\n",
    "            for k in range(i+1, m+1):\n",
    "                temp = [maze_grid[g][j] for g in range(i,k)]\n",
    "                if not has_two_or_fewer_unique_elements(temp):\n",
    "                    Heyawake.addCons(\n",
    "                        quicksum(x[g,j] for g in range(i,k)) >= 1,\n",
    "                        name=f\"col_{i}_{j}_{k}\"\n",
    "                    )\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if j+1 < n:\n",
    "                Heyawake.addCons(\n",
    "                    x[i,j] + x[i,j+1] <= 1,\n",
    "                    name=f\"SMALL1_{i}_{j}_1\"\n",
    "                )\n",
    "            if i+1 < m:\n",
    "                Heyawake.addCons(\n",
    "                    x[i,j] + x[i+1,j] <= 1,\n",
    "                    name=f\"SMALL1_{i}_{j}_2\"\n",
    "                )\n",
    "\n",
    "    Heyawake.setObjective(quicksum(x[i,j] for i in range(m) for j in range(n)), \"minimize\")\n",
    "    # Heyawake.optimize()\n",
    "    def find_surrounding_black_cells(grid):\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, down, left, right movements\n",
    "        total_white = sum(chain.from_iterable(grid))\n",
    "        # Find the first unvisited white cell\n",
    "        def find_unvisited_white():\n",
    "            for i in range(rows):\n",
    "                for j in range(cols):\n",
    "                    if grid[i][j] == 1 and (i, j) not in visited:\n",
    "                        return (i, j)\n",
    "            return None\n",
    "        borders_cut = [] # record cells that formulate the border: list(tuple)\n",
    "        cells_inside_borders = [] # record all cells inside the border: list(tuple)\n",
    "        cnt_white = 0\n",
    "        while len(visited) < total_white:\n",
    "            start = find_unvisited_white()\n",
    "            if not start:\n",
    "                break\n",
    "            # Use BFS to find all connected white cells and record the surrounding black cells\n",
    "            queue = deque([start])\n",
    "            surrounding_black_cells = set()  # Use a set to avoid duplicates\n",
    "            current_inside_cells = [] # record cells in current border\n",
    "            while queue:\n",
    "                x, y = queue.popleft()\n",
    "                if (x, y) in visited:\n",
    "                    continue\n",
    "                visited.add((x, y))\n",
    "                current_inside_cells.append((x, y))\n",
    "                cnt_white += 1\n",
    "                # Check all four adjacent directions\n",
    "                for dx, dy in directions:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < rows and 0 <= ny < cols:\n",
    "                        if grid[nx][ny] == 1 and (nx, ny) not in visited:\n",
    "                            queue.append((nx, ny))\n",
    "                        elif grid[nx][ny] == 0:\n",
    "                            surrounding_black_cells.add((nx, ny))\n",
    "            borders_cut.append(list(surrounding_black_cells))\n",
    "            cells_inside_borders.append(current_inside_cells)\n",
    "            \n",
    "        assert len(borders_cut) == len(cells_inside_borders)\n",
    "\n",
    "        if cnt_white == sum(chain.from_iterable(grid)) and len(borders_cut) == 1:\n",
    "            return [], []\n",
    "        # borders_cut.sort(key = lambda x: len(x), reverse = True)\n",
    "        return borders_cut, cells_inside_borders\n",
    "    iteration = 0\n",
    "    max_iterations = 1e6  # 安全阀值\n",
    "    Heyawake.hideOutput()\n",
    "    while True:\n",
    "        Heyawake.optimize()\n",
    "        \n",
    "        if Heyawake.getStatus() != 'optimal':\n",
    "            break\n",
    "            \n",
    "        curr_grid = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                curr_grid[i][j] = 0 if Heyawake.getVal(x[i,j]) >= 0.5 else 1\n",
    "        \n",
    "\n",
    "        borders_cut, cells_inside = find_surrounding_black_cells(curr_grid)\n",
    "        \n",
    "        if not borders_cut:\n",
    "            break  # 收敛条件\n",
    "            \n",
    "        for border, inside_cells in zip(borders_cut, cells_inside):\n",
    "            for (cell_x, cell_y) in inside_cells:\n",
    "                if len(inside_cells) < m * n // 2:\n",
    "                    Heyawake.freeTransform()\n",
    "                    Heyawake.addCons(\n",
    "                        quicksum(x[subx, suby] for (subx, suby) in border) \n",
    "                        <= len(border) - 1 + x[cell_x, cell_y],\n",
    "                        name=f\"heyawake_cut_{iteration}\"\n",
    "                    )\n",
    "        iteration += 1\n",
    "\n",
    "\n",
    "    result = [[\".\"]*n for _ in range(m)]\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if Heyawake.getVal(x[i,j]) > 1e-6:\n",
    "                result[i][j] = \"X\"\n",
    "    for row in result:\n",
    "        print(\" \".join(row))\n",
    "    return result\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    m, n, grid = readGrid(\"20_14x24.txt\")\n",
    "    result = HeyawakeSolverWithSCIP(m, n, grid)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gurobi solver (Verified!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Set parameter LazyConstraints to value 1\n",
      "Gurobi Optimizer version 11.0.2 build v11.0.2rc0 (mac64[arm] - Darwin 23.5.0 23F79)\n",
      "\n",
      "CPU model: Apple M3 Pro\n",
      "Thread count: 11 physical cores, 11 logical processors, using up to 11 threads\n",
      "\n",
      "Optimize a model with 4831 rows, 336 columns and 43859 nonzeros\n",
      "Model fingerprint: 0x39590deb\n",
      "Variable types: 0 continuous, 336 integer (336 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 5e+00]\n",
      "Presolve removed 4322 rows and 119 columns\n",
      "Presolve time: 0.03s\n",
      "Presolved: 509 rows, 217 columns, 1321 nonzeros\n",
      "Variable types: 0 continuous, 217 integer (217 binary)\n",
      "\n",
      "Root relaxation: objective 9.811111e+01, 166 iterations, 0.00 seconds (0.00 work units)\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0   98.11111    0   40          -   98.11111      -     -    0s\n",
      "     0     0  100.00000    0    -          -  100.00000      -     -    0s\n",
      "     0     0  100.00000    0   17          -  100.00000      -     -    0s\n",
      "H    0     0                     100.0000000  100.00000  0.00%     -    0s\n",
      "     0     0  100.00000    0   10  100.00000  100.00000  0.00%     -    0s\n",
      "\n",
      "Cutting planes:\n",
      "  Lazy constraints: 228\n",
      "\n",
      "Explored 1 nodes (376 simplex iterations) in 0.08 seconds (0.13 work units)\n",
      "Thread count was 11 (of 11 available processors)\n",
      "\n",
      "Solution count 1: 100 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.000000000000e+02, best bound 1.000000000000e+02, gap 0.0000%\n",
      "\n",
      "User-callback calls 690, time in user-callback 0.02 sec\n",
      ". . . X . . X . . . X . . . X . X . . . . . X . \n",
      ". X . . . X . . X . . . . X . . . X . X . . . . \n",
      ". . X . . . X . . X . X . . X . . . X . . . X . \n",
      ". X . X . . . X . . X . X . . . X . . . X . . X \n",
      ". . . . X . X . X . . . . X . . . X . X . . . . \n",
      ". X . . . X . . . X . X . . X . . . X . . . X . \n",
      ". . X . X . X . . . X . X . . X . X . X . X . . \n",
      ". X . X . . . X . X . . . X . . X . . . X . . X \n",
      ". . . . . X . . . . . X . . X . . X . . . X . . \n",
      "X . X . . . X . X . X . X . . . X . . . X . . X \n",
      ". . . X . X . X . X . . . . . X . . X . . X . . \n",
      "X . X . X . . . . . . X . X . . . X . . X . X . \n",
      ". X . . . . X . X . X . X . X . X . . X . . . . \n",
      ". . . X . . . X . . . . . . . X . . X . . X . X \n",
      "\n"
     ]
    }
   ],
   "source": [
    "def has_two_or_fewer_unique_elements(lst):\n",
    "    # 使用set去重并检查不同元素的数量是否小于等于2\n",
    "    return len(set(lst)) <= 2\n",
    "\n",
    "def HeyawakeSolver(m, n, grid):\n",
    "    num_grid, maze_grid = grid[:m], grid[m:]\n",
    "    \n",
    "    Heyawake = gp.Model('Heyawake')\n",
    "    Heyawake.modelSense = gp.GRB.MINIMIZE\n",
    "    Heyawake.Params.lazyConstraints = 1\n",
    "    Heyawake.update()\n",
    "\n",
    "    x = dict() # 存储决策变量\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            x[i, j] = Heyawake.addVar(\n",
    "                vtype = gp.GRB.BINARY,\n",
    "                obj = 1,\n",
    "                name = f\"x[{i},{j}]\"\n",
    "            ) # 声明决策变量\n",
    "    \n",
    "    cell_coord = dict()\n",
    "    # 记录每个宫对应的坐标的情况\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if maze_grid[i][j] not in cell_coord:\n",
    "                cell_coord[maze_grid[i][j]] = [[i, j]]\n",
    "            else:\n",
    "                cell_coord[maze_grid[i][j]].append([i, j])\n",
    "    \n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if num_grid[i][j] not in ['-']:\n",
    "                cur_cell = maze_grid[i][j]\n",
    "                cur_cell_pos = cell_coord[cur_cell]\n",
    "                Heyawake.addConstr(gp.quicksum(x[subx, suby] for (subx, suby) in cur_cell_pos) == int(num_grid[i][j]), name = f'cell_{cur_cell}')\n",
    "    \n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            for k in range(j + 1, n + 1):\n",
    "                if not has_two_or_fewer_unique_elements(maze_grid[i][j : k]):\n",
    "                    Heyawake.addConstr(gp.quicksum(x[i, g] for g in range(j, k) ) >= 1, name = f'row_{i}_{j}_{k}')\n",
    "    \n",
    "    for j in range(n):\n",
    "        for i in range(m):\n",
    "            for k in range(i + 1, m + 1):\n",
    "                temp = [maze_grid[g][j] for g in range(i, k)]\n",
    "                if not has_two_or_fewer_unique_elements(temp):\n",
    "                    Heyawake.addConstr(gp.quicksum(x[g, j] for g in range(i, k) ) >= 1, name = f'col_{i}_{j}_{k}')\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if j + 1 < n:\n",
    "                Heyawake.addConstr(gp.quicksum([x[i,j] , x[i, j + 1]]) <= 1, name = f\"SMALL1_{i}_{j}_1\")\n",
    "            if i + 1 < m:\n",
    "                Heyawake.addConstr(gp.quicksum([x[i,j] , x[i + 1, j]]) <= 1, name = f\"SMALL1_{i}_{j}_2\")\n",
    "    \n",
    "    Heyawake.setObjective(gp.quicksum(x[i, j] for i in range(m) for j in range(n)), gp.GRB.MINIMIZE)\n",
    "    \n",
    "    def border_elim(model, where):\n",
    "        if (where == gp.GRB.Callback.MIPSOL):\n",
    "            x_sol = model.cbGetSolution(model._x)\n",
    "            curr_grid = [[0] * n for _ in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if int(x_sol[i, j]) == 0:\n",
    "                        curr_grid[i][j] = 1\n",
    "                        # 所有白色格子都被涂白了!\n",
    "\n",
    "            def find_surrounding_black_cells(grid):\n",
    "                rows, cols = len(grid), len(grid[0])\n",
    "                visited = set()\n",
    "                directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, down, left, right movements\n",
    "                total_white = sum(chain.from_iterable(grid))\n",
    "                # Find the first unvisited white cell\n",
    "                def find_unvisited_white():\n",
    "                    for i in range(rows):\n",
    "                        for j in range(cols):\n",
    "                            if grid[i][j] == 1 and (i, j) not in visited:\n",
    "                                return (i, j)\n",
    "                    return None\n",
    "                borders_cut = [] # record cells that formulate the border: list(tuple)\n",
    "                cells_inside_borders = [] # record all cells inside the border: list(tuple)\n",
    "                cnt_white = 0\n",
    "                while len(visited) < total_white:\n",
    "                    start = find_unvisited_white()\n",
    "                    if not start:\n",
    "                        break\n",
    "                    # Use BFS to find all connected white cells and record the surrounding black cells\n",
    "                    queue = deque([start])\n",
    "                    surrounding_black_cells = set()  # Use a set to avoid duplicates\n",
    "                    current_inside_cells = [] # record cells in current border\n",
    "                    while queue:\n",
    "                        x, y = queue.popleft()\n",
    "                        if (x, y) in visited:\n",
    "                            continue\n",
    "                        visited.add((x, y))\n",
    "                        current_inside_cells.append((x, y))\n",
    "                        cnt_white += 1\n",
    "                        # Check all four adjacent directions\n",
    "                        for dx, dy in directions:\n",
    "                            nx, ny = x + dx, y + dy\n",
    "                            if 0 <= nx < rows and 0 <= ny < cols:\n",
    "                                if grid[nx][ny] == 1 and (nx, ny) not in visited:\n",
    "                                    queue.append((nx, ny))\n",
    "                                elif grid[nx][ny] == 0:\n",
    "                                    surrounding_black_cells.add((nx, ny))\n",
    "                    borders_cut.append(list(surrounding_black_cells))\n",
    "                    cells_inside_borders.append(current_inside_cells)\n",
    "                    \n",
    "                assert len(borders_cut) == len(cells_inside_borders)\n",
    "\n",
    "                if cnt_white == sum(chain.from_iterable(grid)) and len(borders_cut) == 1:\n",
    "                    return [], []\n",
    "                # borders_cut.sort(key = lambda x: len(x), reverse = True)\n",
    "                return borders_cut, cells_inside_borders\n",
    "\n",
    "            borders_cut, cells_inside_borders = find_surrounding_black_cells(curr_grid)\n",
    "\n",
    "            for borders, cells_inside in zip(borders_cut, cells_inside_borders):\n",
    "                if len(cells_inside) < m * n // 2:\n",
    "                    for (cell_x, cell_y) in cells_inside:\n",
    "                        model.cbLazy(gp.quicksum(model._x[subx, suby] for (subx, suby) in borders ) <= len(borders) - 1 + model._x[cell_x, cell_y])\n",
    "                    \n",
    "                \n",
    "    \n",
    "    Heyawake._x = x\n",
    "    Heyawake.optimize(border_elim)\n",
    "    # Creek.computeIIS()\n",
    "    # Creek.write(\"Creek.ilp\")\n",
    "    result = [[\".\"] * n for _ in range(m)]\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if x[i, j].x > 1e-6:\n",
    "                print(f\"X\", end = \" \")\n",
    "                result[i][j] = \"X\"\n",
    "            else:\n",
    "                print(f\".\", end = \" \")\n",
    "        print()\n",
    "    print()\n",
    "    return result\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    m, n, grid = readGrid(\"problems/20_14x24\")\n",
    "    result = HeyawakeSolver(m, n, grid)\n",
    "    "
   ]
  }
 ],
 "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
}