Puzzles/Starbattle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Starbattle (星战)\n",
    "\n",
    "> Rules \n",
    "\n",
    "\n",
    "The rules of Star Battle are simple:\n",
    "You have to place stars on the grid according to the rules:\n",
    "- 2 stars cannot be adjacent horizontally, vertically or diagonally.\n",
    "- For 1★ puzzles, you have to place 1 star on each row, column and shape.\n",
    "- For 2★ puzzles, the stars per row, column and shape must be 2, etc.\n",
    "\n",
    "-------------\n",
    "\n",
    "> 游戏规则\n",
    "\n",
    "按如下要求在格子上放置星星：\n",
    "- 任意两颗星星不能在横向、纵向或对角上相邻。\n",
    "- 对于1★谜题，每行、每列及每个区块（黑色粗线条标识）上需放置1颗星星。\n",
    "- 对于2★谜题, 每行、每列及每个区块（黑色粗线条标识）上需放置2颗星星，以此类推。\n",
    "\n",
    "<https://www.puzzle-star-battle.com>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.sat.python import cp_model as cp\n",
    "\n",
    "def StarbattleSolver(X, Y, grid, star):\n",
    "    model = cp.CpModel()\n",
    "    solver = cp.CpSolver()\n",
    "    cells = dict()\n",
    "    x = dict()\n",
    "    aux_starbattle = {}\n",
    "    for i in range(Y):\n",
    "        for j in range(X):\n",
    "            x[i, j] = model.NewBoolVar(name = f\"x[{i}, {j}]\")\n",
    "            if grid[i * X + j] not in cells:\n",
    "                cells[grid[i * X + j]] = []\n",
    "            cells[grid[i * X + j]].append([i, j])\n",
    "            aux_starbattle[i, j, \"aux\"] = model.NewBoolVar(f\"x[{i}, {j}, aux]\")\n",
    "    \n",
    "    for _, val in cells.items():\n",
    "        model.Add(sum(x[i[0], i[1]] for i in val) == star)\n",
    "    for i in range(Y):\n",
    "        model.Add(sum(x[i, j] for j in range(X)) == star)\n",
    "    for j in range(X):\n",
    "        model.Add(sum(x[i, j] for i in range(Y)) == star)\n",
    "    \n",
    "    directions = [\n",
    "        [-1,-1], [-1,0], [-1,1],\n",
    "        [0, -1], [0, 0], [0, 1],\n",
    "        [1, -1], [1, 0], [1, 1]\n",
    "    ]\n",
    "    for i in range(Y):\n",
    "        for j in range(X):\n",
    "            \n",
    "            model.Add(x[i, j] == 1).OnlyEnforceIf(aux_starbattle[i, j, \"aux\"])\n",
    "            model.Add(x[i, j] == 0).OnlyEnforceIf(aux_starbattle[i, j, \"aux\"].Not())\n",
    "            \n",
    "            temp_node = []\n",
    "            for direct in directions:\n",
    "                if i + direct[0] >= 0 and i + direct[0] < Y and \\\n",
    "                    j + direct[1] >= 0 and j + direct[1] < X:\n",
    "                        temp_node.append(x[i + direct[0], j + direct[1]])\n",
    "                        # print(f\"{i + direct[0]} - {j + direct[1]}\")\n",
    "            model.Add(sum(temp_node) <= 1).OnlyEnforceIf(aux_starbattle[i, j, \"aux\"])\n",
    "            # print(f\"ADDD {len(temp_node)}\")\n",
    "\n",
    "    status = solver.Solve(model)\n",
    "    if status == cp.OPTIMAL:\n",
    "        print(\"FOUND OPTIMAL\")\n",
    "        outputline = \"\"\n",
    "        for idx in range(len(grid)):\n",
    "            if solver.Value(x[idx // X, idx % X]) == 1:\n",
    "                outputline += \"# \"\n",
    "            else:\n",
    "                outputline += \". \"\n",
    "            if idx % X == X - 1:\n",
    "                print(outputline)\n",
    "                outputline = \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "FOUND OPTIMAL\n",
      ". . # . . . # . . . . . # . \n",
      "# . . . # . . . . . # . . . \n",
      ". . # . . . # . # . . . . . \n",
      "# . . . . . . . . . # . # . \n",
      ". . . # . # . . # . . . . . \n",
      ". # . . . . . . . . # . # . \n",
      ". . . . # . # . # . . . . . \n",
      ". . # . . . . . . . . # . # \n",
      ". . . . # . . # . # . . . . \n",
      ". # . . . . . . . . . # . # \n",
      ". . . # . # . # . . . . . . \n",
      "# . . . . . . . . # . # . . \n",
      ". . . # . # . . . . . . . # \n",
      ". # . . . . . # . # . . . . \n",
      "196\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    grid = \"AAAAAAABBBBBBCAADABBBBBBEBCCFADAAGGBEEEBBCFDDDAGGGEHEBBCFDDDFFIGGHHBBCFDFFFIIIGGHBHCFFFIIIJJGHHHHCKKFFFIJJGJJHHCKIIIIIIJJJJJCCKIKKKKIIJLLLCCKKKKKKKKJLLLLCMKMMKNNNJLLLCCMKKMKNLLLLLCCCMMMMNNNNNNLLCC\"\n",
    "    # grid = \"ABBBBAACDDCCCDDEEEDDEEEDD\"\n",
    "    StarbattleSolver(X = 14,Y=  14,grid =  grid, star = 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](../assets/figures/Starbattle1.png)\n",
    "\n",
    "![](../assets/figures/Starbattle2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py310",
   "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}