Puzzles/Buraitoraito.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Buraitoraito\n",
    "\n",
    "Buraitoraito (\"Bright Light\") is played on a rectangular or square grid. It contains black cells with numbers. The number in the cell represents how many stars can be seen from this cell. A star is visible from the black cell, if it is in the same row or column as this cell, but not behind other black cells.\n",
    "\n",
    "![](https://www.janko.at/Raetsel/Buraitoraito/Regeln-01.gif) ![](https://www.janko.at/Raetsel/Buraitoraito/Regeln-02.gif)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "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": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['2', '-', '-', '5', '-', '-', '1', '-']\n",
      "['-', '-', '4', '-', '-', '-', '-', '-']\n",
      "['-', '4', '-', '-', '-', '-', '4', '-']\n",
      "['1', '-', '-', '-', '-', '1', '-', '4']\n",
      "['-', '-', '5', '-', '6', '-', '-', '-']\n",
      "['3', '-', '-', '7', '-', '3', '-', '-']\n",
      "['-', '-', '-', '-', '-', '-', '5', '-']\n",
      "['-', '-', '2', '-', '-', '2', '-', '2']\n"
     ]
    }
   ],
   "source": [
    "def readGrid(path):\n",
    "    with open(f\"../assets/data/Buraitoraito/{path}.txt\") 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(\"problems/1_8x8\")\n",
    "    \n",
    "    for g in grid:\n",
    "        print(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 X X 5 O O 1 X \n",
      "O O 4 X X O O O \n",
      "O 4 X X O O 4 X \n",
      "1 O O O O 1 O 4 \n",
      "X X 5 X 6 X X X \n",
      "3 O X 7 X 3 O O \n",
      "X O O X O X 5 X \n",
      "O O 2 X O 2 O 2 \n",
      "\n",
      "NumConflicts: 0\n",
      "NumBranches: 48\n",
      "WallTime: 0.0040030000000000005\n"
     ]
    }
   ],
   "source": [
    "from ortools.sat.python import cp_model as cp\n",
    "def buraitoraito_solver(grid, X, Y):\n",
    "    model = cp.CpModel()\n",
    "    x = {}\n",
    "    for i in range(X):\n",
    "        for j in range(Y):\n",
    "            if grid[i][j] in [\"-\"]:\n",
    "                x[i, j] = model.NewBoolVar(name = f\"x[{i}, {j}]\")\n",
    "            else:\n",
    "                x[i, j] = 0\n",
    "    for i in range(X):\n",
    "        for j in range(Y):\n",
    "            if grid[i][j] not in [\"-\"]:\n",
    "                num_cnt = int(grid[i][j])\n",
    "                cand_pos = []\n",
    "                tmp_i, tmp_j = i + 1, j\n",
    "                while tmp_i < X:\n",
    "                    if grid[tmp_i][tmp_j] not in [\"-\"]:\n",
    "                        break\n",
    "                    cand_pos.append((tmp_i, tmp_j))\n",
    "                    tmp_i += 1\n",
    "                tmp_i, tmp_j = i, j + 1\n",
    "                while tmp_j < Y:\n",
    "                    if grid[tmp_i][tmp_j] not in [\"-\"]:\n",
    "                        break\n",
    "                    cand_pos.append((tmp_i, tmp_j))\n",
    "                    tmp_j += 1\n",
    "                tmp_i, tmp_j = i - 1, j\n",
    "                while tmp_i >= 0:\n",
    "                    if grid[tmp_i][tmp_j] not in [\"-\"]:\n",
    "                        break\n",
    "                    cand_pos.append((tmp_i, tmp_j))\n",
    "                    tmp_i -= 1\n",
    "\n",
    "                tmp_i, tmp_j = i, j - 1\n",
    "                while tmp_j >= 0:\n",
    "                    if grid[tmp_i][tmp_j] not in [\"-\"]:\n",
    "                        break\n",
    "                    cand_pos.append((tmp_i, tmp_j))\n",
    "                    tmp_j -= 1\n",
    "                model.Add(sum([x[p] for p in cand_pos]) == num_cnt)\n",
    "\n",
    "    \n",
    "    solver = cp.CpSolver()\n",
    "    status = solver.Solve(model)\n",
    "    if status == cp.OPTIMAL:\n",
    "        for i in range(X):\n",
    "            for j in range(Y):\n",
    "                if grid[i][j] not in \"0123456789\":\n",
    "                    if solver.Value(x[i, j]) > 1e-1:\n",
    "                        print(\"X\", end=\" \")\n",
    "                    else:\n",
    "                        print(\"O\", end=\" \")\n",
    "                else:\n",
    "                    print(grid[i][j], end=\" \")\n",
    "            print()\n",
    "        print()\n",
    "\n",
    "        print(\"NumConflicts:\", solver.NumConflicts())\n",
    "        print(\"NumBranches:\", solver.NumBranches())\n",
    "        print(\"WallTime:\", solver.WallTime())\n",
    "    else:\n",
    "        print(\"Something Wrong!\")\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    m, n, grid = readGrid(\"problems/1_8x8\")\n",
    "    buraitoraito_solver(grid, m, n)"
   ]
  },
  {
   "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
}