216 lines
6.7 KiB
Plaintext
216 lines
6.7 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": [
|
|
"# seseman"
|
|
]
|
|
},
|
|
{
|
|
"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/seseman.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/seseman.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": "markdown",
|
|
"id": "description",
|
|
"metadata": {},
|
|
"source": [
|
|
"\n",
|
|
"\n",
|
|
" Seseman Convent problem in Google CP Solver.\n",
|
|
"\n",
|
|
"\n",
|
|
" n is the length of a border\n",
|
|
" There are (n-2)^2 \"holes\", i.e.\n",
|
|
" there are n^2 - (n-2)^2 variables to find out.\n",
|
|
"\n",
|
|
" The simplest problem, n = 3 (n x n matrix)\n",
|
|
" which is represented by the following matrix:\n",
|
|
"\n",
|
|
" a b c\n",
|
|
" d e\n",
|
|
" f g h\n",
|
|
"\n",
|
|
" Where the following constraints must hold:\n",
|
|
"\n",
|
|
" a + b + c = border_sum\n",
|
|
" a + d + f = border_sum\n",
|
|
" c + e + h = border_sum\n",
|
|
" f + g + h = border_sum\n",
|
|
" a + b + c + d + e + f = total_sum\n",
|
|
"\n",
|
|
"\n",
|
|
" Compare with the following models:\n",
|
|
" * Tailor/Essence': http://hakank.org/tailor/seseman.eprime\n",
|
|
" * MiniZinc: http://hakank.org/minizinc/seseman.mzn\n",
|
|
" * SICStus: http://hakank.org/sicstus/seseman.pl\n",
|
|
" * Zinc: http://hakank.org/minizinc/seseman.zinc\n",
|
|
" * Choco: http://hakank.org/choco/Seseman.java\n",
|
|
" * Comet: http://hakank.org/comet/seseman.co\n",
|
|
" * ECLiPSe: http://hakank.org/eclipse/seseman.ecl\n",
|
|
" * Gecode: http://hakank.org/gecode/seseman.cpp\n",
|
|
" * Gecode/R: http://hakank.org/gecode_r/seseman.rb\n",
|
|
" * JaCoP: http://hakank.org/JaCoP/Seseman.java\n",
|
|
"\n",
|
|
"\n",
|
|
" This model was created by Hakan Kjellerstrand (hakank@gmail.com)\n",
|
|
" Also see my other Google CP Solver models:\n",
|
|
" http://www.hakank.org/google_or_tools/\n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "code",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from ortools.constraint_solver import pywrapcp\n",
|
|
"\n",
|
|
"\n",
|
|
"def main(unused_argv):\n",
|
|
" # Create the solver.\n",
|
|
" solver = pywrapcp.Solver(\"Seseman Convent problem\")\n",
|
|
"\n",
|
|
" # data\n",
|
|
" n = 3\n",
|
|
" border_sum = n * n\n",
|
|
"\n",
|
|
" # declare variables\n",
|
|
" total_sum = solver.IntVar(1, n * n * n * n, \"total_sum\")\n",
|
|
" # x[0..n-1,0..n-1]\n",
|
|
" x = {}\n",
|
|
" for i in range(n):\n",
|
|
" for j in range(n):\n",
|
|
" x[(i, j)] = solver.IntVar(0, n * n, \"x %i %i\" % (i, j))\n",
|
|
"\n",
|
|
" #\n",
|
|
" # constraints\n",
|
|
" #\n",
|
|
" # zero all middle cells\n",
|
|
" for i in range(1, n - 1):\n",
|
|
" for j in range(1, n - 1):\n",
|
|
" solver.Add(x[(i, j)] == 0)\n",
|
|
"\n",
|
|
" # all borders must be >= 1\n",
|
|
" for i in range(n):\n",
|
|
" for j in range(n):\n",
|
|
" if i == 0 or j == 0 or i == n - 1 or j == n - 1:\n",
|
|
" solver.Add(x[(i, j)] >= 1)\n",
|
|
"\n",
|
|
" # sum the borders (border_sum)\n",
|
|
" solver.Add(solver.Sum([x[(i, 0)] for i in range(n)]) == border_sum)\n",
|
|
" solver.Add(solver.Sum([x[(i, n - 1)] for i in range(n)]) == border_sum)\n",
|
|
" solver.Add(solver.Sum([x[(0, i)] for i in range(n)]) == border_sum)\n",
|
|
" solver.Add(solver.Sum([x[(n - 1, i)] for i in range(n)]) == border_sum)\n",
|
|
"\n",
|
|
" # total\n",
|
|
" solver.Add(\n",
|
|
" solver.Sum([x[(i, j)] for i in range(n) for j in range(n)]) == total_sum)\n",
|
|
"\n",
|
|
" #\n",
|
|
" # solution and search\n",
|
|
" #\n",
|
|
" solution = solver.Assignment()\n",
|
|
" solution.Add([x[(i, j)] for i in range(n) for j in range(n)])\n",
|
|
" solution.Add(total_sum)\n",
|
|
"\n",
|
|
" # all solutions\n",
|
|
" collector = solver.AllSolutionCollector(solution)\n",
|
|
" # search_log = solver.SearchLog(100, total_sum)\n",
|
|
" solver.Solve(\n",
|
|
" solver.Phase([x[(i, j)] for i in range(n) for j in range(n)],\n",
|
|
" solver.CHOOSE_PATH, solver.ASSIGN_MIN_VALUE), [collector])\n",
|
|
" #[collector, search_log])\n",
|
|
"\n",
|
|
" num_solutions = collector.SolutionCount()\n",
|
|
" # print \"x:\", x\n",
|
|
" print(\"num_solutions:\", num_solutions)\n",
|
|
" print()\n",
|
|
" for s in range(num_solutions):\n",
|
|
" # print [collector.Value(s, x[(i,j)])\n",
|
|
" # for i in range(n) for j in range(n)]\n",
|
|
" print(\"total_sum:\", collector.Value(s, total_sum))\n",
|
|
" for i in range(n):\n",
|
|
" for j in range(n):\n",
|
|
" print(collector.Value(s, x[(i, j)]), end=\" \")\n",
|
|
" print()\n",
|
|
" print()\n",
|
|
"\n",
|
|
" print(\"failures:\", solver.Failures())\n",
|
|
" print(\"branches:\", solver.Branches())\n",
|
|
" print(\"WallTime:\", solver.WallTime())\n",
|
|
" print(\"num_solutions:\", num_solutions)\n",
|
|
"\n",
|
|
"\n",
|
|
"main(\"cp sample\")\n",
|
|
"\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|