376 lines
14 KiB
Plaintext
376 lines
14 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "google",
|
|
"metadata": {},
|
|
"source": [
|
|
"##### Copyright 2025 Google LLC."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "apache",
|
|
"metadata": {},
|
|
"source": [
|
|
"Licensed under the Apache License, Version 2.0 (the \"License\");\n",
|
|
"you may not use this file except in compliance with the License.\n",
|
|
"You may obtain a copy of the License at\n",
|
|
"\n",
|
|
" http://www.apache.org/licenses/LICENSE-2.0\n",
|
|
"\n",
|
|
"Unless required by applicable law or agreed to in writing, software\n",
|
|
"distributed under the License is distributed on an \"AS IS\" BASIS,\n",
|
|
"WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
|
|
"See the License for the specific language governing permissions and\n",
|
|
"limitations under the License.\n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "basename",
|
|
"metadata": {},
|
|
"source": [
|
|
"# slitherlink"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "link",
|
|
"metadata": {},
|
|
"source": [
|
|
"<table align=\"left\">\n",
|
|
"<td>\n",
|
|
"<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/contrib/slitherlink.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
|
|
"</td>\n",
|
|
"<td>\n",
|
|
"<a href=\"https://github.com/google/or-tools/blob/main/examples/contrib/slitherlink.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
|
|
"</td>\n",
|
|
"</table>"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "doc",
|
|
"metadata": {},
|
|
"source": [
|
|
"First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "install",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"%pip install ortools"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "code",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from ortools.constraint_solver import pywrapcp\n",
|
|
"from collections import deque\n",
|
|
"\n",
|
|
"small = [[3, 2, -1, 3], [-1, -1, -1, 2], [3, -1, -1, -1], [3, -1, 3, 1]]\n",
|
|
"\n",
|
|
"medium = [[-1, 0, -1, 1, -1, -1, 1, -1], [-1, 3, -1, -1, 2, 3, -1, 2],\n",
|
|
" [-1, -1, 0, -1, -1, -1, -1, 0], [-1, 3, -1, -1, 0, -1, -1, -1],\n",
|
|
" [-1, -1, -1, 3, -1, -1, 0, -1], [1, -1, -1, -1, -1, 3, -1, -1],\n",
|
|
" [3, -1, 1, 3, -1, -1, 3, -1], [-1, 0, -1, -1, 3, -1, 3, -1]]\n",
|
|
"\n",
|
|
"big = [[3, -1, -1, -1, 2, -1, 1, -1, 1, 2], [1, -1, 0, -1, 3, -1, 2, 0, -1, -1],\n",
|
|
" [-1, 3, -1, -1, -1, -1, -1, -1, 3, -1],\n",
|
|
" [2, 0, -1, 3, -1, 2, 3, -1, -1, -1], [-1, -1, -1, 1, 1, 1, -1, -1, 3, 3],\n",
|
|
" [2, 3, -1, -1, 2, 2, 3, -1, -1, -1], [-1, -1, -1, 1, 2, -1, 2, -1, 3, 3],\n",
|
|
" [-1, 2, -1, -1, -1, -1, -1, -1, 2, -1],\n",
|
|
" [-1, -1, 1, 1, -1, 2, -1, 1, -1, 3], [3, 3, -1, 1, -1, 2, -1, -1, -1, 2]]\n",
|
|
"\n",
|
|
"\n",
|
|
"def NeighboringArcs(i, j, h_arcs, v_arcs):\n",
|
|
" tmp = []\n",
|
|
" if j > 0:\n",
|
|
" tmp.append(h_arcs[i][j - 1])\n",
|
|
" if j < len(v_arcs) - 1:\n",
|
|
" tmp.append(h_arcs[i][j])\n",
|
|
" if i > 0:\n",
|
|
" tmp.append(v_arcs[j][i - 1])\n",
|
|
" if i < len(h_arcs) - 1:\n",
|
|
" tmp.append(v_arcs[j][i])\n",
|
|
" return tmp\n",
|
|
"\n",
|
|
"\n",
|
|
"def PrintSolution(data, h_arcs, v_arcs):\n",
|
|
" num_rows = len(data)\n",
|
|
" num_columns = len(data[0])\n",
|
|
"\n",
|
|
" for i in range(num_rows):\n",
|
|
" first_line = ''\n",
|
|
" second_line = ''\n",
|
|
" third_line = ''\n",
|
|
" for j in range(num_columns):\n",
|
|
" h_arc = h_arcs[i][j].Value()\n",
|
|
" v_arc = v_arcs[j][i].Value()\n",
|
|
" cnt = data[i][j]\n",
|
|
" first_line += ' ---' if h_arc else ' '\n",
|
|
" second_line += '|' if v_arc else ' '\n",
|
|
" second_line += ' ' if cnt == -1 else ' %i ' % cnt\n",
|
|
" third_line += '| ' if v_arc == 1 else ' '\n",
|
|
" termination = v_arcs[num_columns][i].Value()\n",
|
|
" second_line += '|' if termination else ' '\n",
|
|
" third_line += '|' if termination else ' '\n",
|
|
" print(first_line)\n",
|
|
" print(third_line)\n",
|
|
" print(second_line)\n",
|
|
" print(third_line)\n",
|
|
" last_line = ''\n",
|
|
" for j in range(num_columns):\n",
|
|
" h_arc = h_arcs[num_rows][j].Value()\n",
|
|
" last_line += ' ---' if h_arc else ' '\n",
|
|
" print(last_line)\n",
|
|
"\n",
|
|
"\n",
|
|
"class BooleanSumEven(pywrapcp.PyConstraint):\n",
|
|
"\n",
|
|
" def __init__(self, solver, vars):\n",
|
|
" pywrapcp.PyConstraint.__init__(self, solver)\n",
|
|
" self.__vars = vars\n",
|
|
" self.__num_possible_true_vars = pywrapcp.NumericalRevInteger(0)\n",
|
|
" self.__num_always_true_vars = pywrapcp.NumericalRevInteger(0)\n",
|
|
"\n",
|
|
" def Post(self):\n",
|
|
" for i in range(len(self.__vars)):\n",
|
|
" v = self.__vars[i]\n",
|
|
" if not v.Bound():\n",
|
|
" demon = self.Demon(BooleanSumEven.Update, i)\n",
|
|
" v.WhenBound(demon)\n",
|
|
"\n",
|
|
" def InitialPropagate(self):\n",
|
|
" num_always_true = 0\n",
|
|
" num_possible_true = 0\n",
|
|
" possible_true_index = -1\n",
|
|
" for i in range(len(self.__vars)):\n",
|
|
" var = self.__vars[i]\n",
|
|
" if var.Min() == 1:\n",
|
|
" num_always_true += 1\n",
|
|
" num_possible_true += 1\n",
|
|
" elif var.Max() == 1:\n",
|
|
" num_possible_true += 1\n",
|
|
" possible_true_index = i\n",
|
|
"\n",
|
|
" if num_always_true == num_possible_true and num_possible_true % 2 == 1:\n",
|
|
" self.solver().Fail()\n",
|
|
"\n",
|
|
" if num_possible_true == num_always_true + 1:\n",
|
|
" self.__vars[possible_true_index].SetValue(num_always_true % 2)\n",
|
|
"\n",
|
|
" self.__num_possible_true_vars.SetValue(self.solver(), num_possible_true)\n",
|
|
" self.__num_always_true_vars.SetValue(self.solver(), num_always_true)\n",
|
|
"\n",
|
|
" def Update(self, index):\n",
|
|
" solver = self.solver()\n",
|
|
" value = self.__vars[index].Value()\n",
|
|
" if value == 0:\n",
|
|
" self.__num_possible_true_vars.Decr(solver)\n",
|
|
" else:\n",
|
|
" self.__num_always_true_vars.Incr(solver)\n",
|
|
"\n",
|
|
" num_possible = self.__num_possible_true_vars.Value()\n",
|
|
" num_always = self.__num_always_true_vars.Value()\n",
|
|
"\n",
|
|
" if num_always == num_possible and num_possible % 2 == 1:\n",
|
|
" solver.Fail()\n",
|
|
"\n",
|
|
" if num_possible == num_always + 1:\n",
|
|
" possible_true_index = -1\n",
|
|
" for i in range(len(self.__vars)):\n",
|
|
" if not self.__vars[i].Bound():\n",
|
|
" possible_true_index = i\n",
|
|
" break\n",
|
|
"\n",
|
|
" if possible_true_index != -1:\n",
|
|
" self.__vars[possible_true_index].SetValue(num_always % 2)\n",
|
|
"\n",
|
|
" def DebugString(self):\n",
|
|
" return 'BooleanSumEven'\n",
|
|
"\n",
|
|
"\n",
|
|
"# Dedicated constraint: There is a single path on the grid.\n",
|
|
"# This constraint does not enforce the non-crossing, this is done\n",
|
|
"# by the constraint on the degree of each node.\n",
|
|
"class GridSinglePath(pywrapcp.PyConstraint):\n",
|
|
"\n",
|
|
" def __init__(self, solver, h_arcs, v_arcs):\n",
|
|
" pywrapcp.PyConstraint.__init__(self, solver)\n",
|
|
" self.__h_arcs = h_arcs\n",
|
|
" self.__v_arcs = v_arcs\n",
|
|
"\n",
|
|
" def Post(self):\n",
|
|
" demon = self.DelayedInitialPropagateDemon()\n",
|
|
" for row in self.__h_arcs:\n",
|
|
" for var in row:\n",
|
|
" var.WhenBound(demon)\n",
|
|
"\n",
|
|
" for column in self.__v_arcs:\n",
|
|
" for var in column:\n",
|
|
" var.WhenBound(demon)\n",
|
|
"\n",
|
|
" # This constraint implements a single propagation.\n",
|
|
" # If one point is on the path, it checks the reachability of all possible\n",
|
|
" # nodes, and zero out the unreachable parts.\n",
|
|
" def InitialPropagate(self):\n",
|
|
" num_rows = len(self.__h_arcs)\n",
|
|
" num_columns = len(self.__v_arcs)\n",
|
|
"\n",
|
|
" num_points = num_rows * num_columns\n",
|
|
" root_node = -1\n",
|
|
" possible_points = set()\n",
|
|
" neighbors = [[] for _ in range(num_points)]\n",
|
|
"\n",
|
|
" for i in range(num_rows):\n",
|
|
" for j in range(num_columns - 1):\n",
|
|
" h_arc = self.__h_arcs[i][j]\n",
|
|
" if h_arc.Max() == 1:\n",
|
|
" head = i * num_columns + j\n",
|
|
" tail = i * num_columns + j + 1\n",
|
|
" neighbors[head].append(tail)\n",
|
|
" neighbors[tail].append(head)\n",
|
|
" possible_points.add(head)\n",
|
|
" possible_points.add(tail)\n",
|
|
" if root_node == -1 and h_arc.Min() == 1:\n",
|
|
" root_node = head\n",
|
|
"\n",
|
|
" for i in range(num_rows - 1):\n",
|
|
" for j in range(num_columns):\n",
|
|
" v_arc = self.__v_arcs[j][i]\n",
|
|
" if v_arc.Max() == 1:\n",
|
|
" head = i * num_columns + j\n",
|
|
" tail = (i + 1) * num_columns + j\n",
|
|
" neighbors[head].append(tail)\n",
|
|
" neighbors[tail].append(head)\n",
|
|
" possible_points.add(head)\n",
|
|
" possible_points.add(tail)\n",
|
|
" if root_node == -1 and v_arc.Min() == 1:\n",
|
|
" root_node = head\n",
|
|
"\n",
|
|
" if root_node == -1:\n",
|
|
" return\n",
|
|
"\n",
|
|
" visited_points = set()\n",
|
|
" to_process = deque()\n",
|
|
"\n",
|
|
" # Compute reachable points\n",
|
|
" to_process.append(root_node)\n",
|
|
" while to_process:\n",
|
|
" candidate = to_process.popleft()\n",
|
|
" visited_points.add(candidate)\n",
|
|
" for neighbor in neighbors[candidate]:\n",
|
|
" if not neighbor in visited_points:\n",
|
|
" to_process.append(neighbor)\n",
|
|
" visited_points.add(neighbor)\n",
|
|
"\n",
|
|
" if len(visited_points) < len(possible_points):\n",
|
|
" for point in visited_points:\n",
|
|
" possible_points.remove(point)\n",
|
|
"\n",
|
|
" # Loop on unreachable points and zero all neighboring arcs.\n",
|
|
" for point in possible_points:\n",
|
|
" i = point // num_columns\n",
|
|
" j = point % num_columns\n",
|
|
" neighbors = NeighboringArcs(i, j, self.__h_arcs, self.__v_arcs)\n",
|
|
" for var in neighbors:\n",
|
|
" var.SetMax(0)\n",
|
|
"\n",
|
|
"\n",
|
|
"def SlitherLink(data):\n",
|
|
" num_rows = len(data)\n",
|
|
" num_columns = len(data[0])\n",
|
|
"\n",
|
|
" solver = pywrapcp.Solver('slitherlink')\n",
|
|
" h_arcs = [[\n",
|
|
" solver.BoolVar('h_arcs[%i][%i]' % (i, j)) for j in range(num_columns)\n",
|
|
" ] for i in range(num_rows + 1)]\n",
|
|
"\n",
|
|
" v_arcs = [[\n",
|
|
" solver.BoolVar('v_arcs[%i][%i]' % (i, j)) for j in range(num_rows)\n",
|
|
" ] for i in range(num_columns + 1)]\n",
|
|
"\n",
|
|
" # Constraint on the sum or arcs\n",
|
|
" for i in range(num_rows):\n",
|
|
" for j in range(num_columns):\n",
|
|
" if data[i][j] != -1:\n",
|
|
" sq = [h_arcs[i][j], h_arcs[i + 1][j], v_arcs[j][i], v_arcs[j + 1][i]]\n",
|
|
" solver.Add(solver.SumEquality(sq, data[i][j]))\n",
|
|
"\n",
|
|
" # Single loop: each node has a degree 0 or 2\n",
|
|
" zero_or_two = [0, 2]\n",
|
|
" for i in range(num_rows + 1):\n",
|
|
" for j in range(num_columns + 1):\n",
|
|
" neighbors = NeighboringArcs(i, j, h_arcs, v_arcs)\n",
|
|
" solver.Add(solver.Sum(neighbors).Member(zero_or_two))\n",
|
|
"\n",
|
|
" # Single loop: sum or arcs on row or column is even\n",
|
|
" for i in range(num_columns):\n",
|
|
" column = [h_arcs[j][i] for j in range(num_rows + 1)]\n",
|
|
" solver.Add(BooleanSumEven(solver, column))\n",
|
|
"\n",
|
|
" for i in range(num_rows):\n",
|
|
" row = [v_arcs[j][i] for j in range(num_columns + 1)]\n",
|
|
" solver.Add(BooleanSumEven(solver, row))\n",
|
|
"\n",
|
|
" # Single loop: main constraint\n",
|
|
" solver.Add(GridSinglePath(solver, h_arcs, v_arcs))\n",
|
|
"\n",
|
|
" # Special rule on corners: value == 3 implies 2 border arcs used.\n",
|
|
" if data[0][0] == 3:\n",
|
|
" h_arcs[0][0].SetMin(1)\n",
|
|
" v_arcs[0][0].SetMin(1)\n",
|
|
" if data[0][num_columns - 1] == 3:\n",
|
|
" h_arcs[0][num_columns - 1].SetMin(1)\n",
|
|
" v_arcs[num_columns][0].SetMin(1)\n",
|
|
" if data[num_rows - 1][0] == 3:\n",
|
|
" h_arcs[num_rows][0].SetMin(1)\n",
|
|
" v_arcs[0][num_rows - 1].SetMin(1)\n",
|
|
" if data[num_rows - 1][num_columns - 1] == 3:\n",
|
|
" h_arcs[num_rows][num_columns - 1].SetMin(1)\n",
|
|
" v_arcs[num_columns][num_rows - 1].SetMin(1)\n",
|
|
"\n",
|
|
" # Search\n",
|
|
" all_vars = []\n",
|
|
" for row in h_arcs:\n",
|
|
" all_vars.extend(row)\n",
|
|
" for column in v_arcs:\n",
|
|
" all_vars.extend(column)\n",
|
|
"\n",
|
|
" db = solver.Phase(all_vars, solver.CHOOSE_FIRST_UNBOUND,\n",
|
|
" solver.ASSIGN_MAX_VALUE)\n",
|
|
"\n",
|
|
" log = solver.SearchLog(1000000)\n",
|
|
"\n",
|
|
" solver.NewSearch(db, log)\n",
|
|
" while solver.NextSolution():\n",
|
|
" PrintSolution(data, h_arcs, v_arcs)\n",
|
|
" solver.EndSearch()\n",
|
|
"\n",
|
|
"\n",
|
|
"SlitherLink(small)\n",
|
|
"SlitherLink(medium)\n",
|
|
"SlitherLink(big)\n",
|
|
"\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|