274 lines
8.1 KiB
Plaintext
274 lines
8.1 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": [
|
|
"# kenken2"
|
|
]
|
|
},
|
|
{
|
|
"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/kenken2.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/kenken2.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",
|
|
" KenKen puzzle in Google CP Solver.\n",
|
|
"\n",
|
|
" http://en.wikipedia.org/wiki/KenKen\n",
|
|
" '''\n",
|
|
" KenKen or KEN-KEN is a style of arithmetic and logical puzzle sharing\n",
|
|
" several characteristics with sudoku. The name comes from Japanese and\n",
|
|
" is translated as 'square wisdom' or 'cleverness squared'.\n",
|
|
" ...\n",
|
|
" The objective is to fill the grid in with the digits 1 through 6 such that:\n",
|
|
"\n",
|
|
" * Each row contains exactly one of each digit\n",
|
|
" * Each column contains exactly one of each digit\n",
|
|
" * Each bold-outlined group of cells is a cage containing digits which\n",
|
|
" achieve the specified result using the specified mathematical operation:\n",
|
|
" addition (+),\n",
|
|
" subtraction (-),\n",
|
|
" multiplication (x),\n",
|
|
" and division (/).\n",
|
|
" (Unlike in Killer sudoku, digits may repeat within a group.)\n",
|
|
"\n",
|
|
" ...\n",
|
|
" More complex KenKen problems are formed using the principles described\n",
|
|
" above but omitting the symbols +, -, x and /, thus leaving them as\n",
|
|
" yet another unknown to be determined.\n",
|
|
" '''\n",
|
|
"\n",
|
|
"\n",
|
|
" The solution is:\n",
|
|
"\n",
|
|
" 5 6 3 4 1 2\n",
|
|
" 6 1 4 5 2 3\n",
|
|
" 4 5 2 3 6 1\n",
|
|
" 3 4 1 2 5 6\n",
|
|
" 2 3 6 1 4 5\n",
|
|
" 1 2 5 6 3 4\n",
|
|
"\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": [
|
|
"import sys\n",
|
|
"\n",
|
|
"from ortools.constraint_solver import pywrapcp\n",
|
|
"from functools import reduce\n",
|
|
"\n",
|
|
"#\n",
|
|
"# Ensure that the sum of the segments\n",
|
|
"# in cc == res\n",
|
|
"#\n",
|
|
"\n",
|
|
"\n",
|
|
"def calc(cc, x, res):\n",
|
|
"\n",
|
|
" solver = list(x.values())[0].solver()\n",
|
|
"\n",
|
|
" if len(cc) == 2:\n",
|
|
"\n",
|
|
" # for two operands there may be\n",
|
|
" # a lot of variants\n",
|
|
"\n",
|
|
" c00, c01 = cc[0]\n",
|
|
" c10, c11 = cc[1]\n",
|
|
" a = x[c00 - 1, c01 - 1]\n",
|
|
" b = x[c10 - 1, c11 - 1]\n",
|
|
"\n",
|
|
" r1 = solver.IsEqualCstVar(a + b, res)\n",
|
|
" r2 = solver.IsEqualCstVar(a * b, res)\n",
|
|
" r3 = solver.IsEqualVar(a * res, b)\n",
|
|
" r4 = solver.IsEqualVar(b * res, a)\n",
|
|
" r5 = solver.IsEqualCstVar(a - b, res)\n",
|
|
" r6 = solver.IsEqualCstVar(b - a, res)\n",
|
|
" solver.Add(r1 + r2 + r3 + r4 + r5 + r6 >= 1)\n",
|
|
"\n",
|
|
" else:\n",
|
|
"\n",
|
|
" # res is either sum or product of the segment\n",
|
|
"\n",
|
|
" xx = [x[i[0] - 1, i[1] - 1] for i in cc]\n",
|
|
"\n",
|
|
" # Sum\n",
|
|
" # # SumEquality don't work:\n",
|
|
" # this_sum = solver.SumEquality(xx, res)\n",
|
|
" this_sum = solver.IsEqualCstVar(solver.Sum(xx), res)\n",
|
|
"\n",
|
|
" # Product\n",
|
|
" # # Prod (or MakeProd) don't work:\n",
|
|
" # this_prod = solver.IsEqualCstVar(solver.Prod(xx), res)\n",
|
|
" this_prod = solver.IsEqualCstVar(reduce(lambda a, b: a * b, xx), res)\n",
|
|
" solver.Add(this_sum + this_prod >= 1)\n",
|
|
"\n",
|
|
"\n",
|
|
"def main():\n",
|
|
"\n",
|
|
" # Create the solver.\n",
|
|
" solver = pywrapcp.Solver(\"KenKen\")\n",
|
|
"\n",
|
|
" #\n",
|
|
" # data\n",
|
|
" #\n",
|
|
"\n",
|
|
" # size of matrix\n",
|
|
" n = 6\n",
|
|
"\n",
|
|
" # For a better view of the problem, see\n",
|
|
" # http://en.wikipedia.org/wiki/File:KenKenProblem.svg\n",
|
|
"\n",
|
|
" # hints\n",
|
|
" # [sum, [segments]]\n",
|
|
" # Note: 1-based\n",
|
|
" problem = [[11, [[1, 1], [2, 1]]], [2, [[1, 2], [1, 3]]],\n",
|
|
" [20, [[1, 4], [2, 4]]], [6, [[1, 5], [1, 6], [2, 6], [3, 6]]],\n",
|
|
" [3, [[2, 2], [2, 3]]], [3, [[2, 5], [3, 5]]],\n",
|
|
" [240, [[3, 1], [3, 2], [4, 1], [4, 2]]], [6, [[3, 3], [3, 4]]],\n",
|
|
" [6, [[4, 3], [5, 3]]], [7, [[4, 4], [5, 4], [5, 5]]],\n",
|
|
" [30, [[4, 5], [4, 6]]], [6, [[5, 1], [5, 2]]],\n",
|
|
" [9, [[5, 6], [6, 6]]], [8, [[6, 1], [6, 2], [6, 3]]],\n",
|
|
" [2, [[6, 4], [6, 5]]]]\n",
|
|
"\n",
|
|
" num_p = len(problem)\n",
|
|
"\n",
|
|
" #\n",
|
|
" # variables\n",
|
|
" #\n",
|
|
"\n",
|
|
" # the set\n",
|
|
" x = {}\n",
|
|
" for i in range(n):\n",
|
|
" for j in range(n):\n",
|
|
" x[i, j] = solver.IntVar(1, n, \"x[%i,%i]\" % (i, j))\n",
|
|
"\n",
|
|
" x_flat = [x[i, j] for i in range(n) for j in range(n)]\n",
|
|
"\n",
|
|
" #\n",
|
|
" # constraints\n",
|
|
" #\n",
|
|
"\n",
|
|
" # all rows and columns must be unique\n",
|
|
" for i in range(n):\n",
|
|
" row = [x[i, j] for j in range(n)]\n",
|
|
" solver.Add(solver.AllDifferent(row))\n",
|
|
"\n",
|
|
" col = [x[j, i] for j in range(n)]\n",
|
|
" solver.Add(solver.AllDifferent(col))\n",
|
|
"\n",
|
|
" # calculate the segments\n",
|
|
" for (res, segment) in problem:\n",
|
|
" calc(segment, x, res)\n",
|
|
"\n",
|
|
" #\n",
|
|
" # search and solution\n",
|
|
" #\n",
|
|
" db = solver.Phase(x_flat, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT)\n",
|
|
"\n",
|
|
" solver.NewSearch(db)\n",
|
|
"\n",
|
|
" num_solutions = 0\n",
|
|
" while solver.NextSolution():\n",
|
|
" for i in range(n):\n",
|
|
" for j in range(n):\n",
|
|
" print(x[i, j].Value(), end=\" \")\n",
|
|
" print()\n",
|
|
"\n",
|
|
" print()\n",
|
|
" num_solutions += 1\n",
|
|
"\n",
|
|
" solver.EndSearch()\n",
|
|
"\n",
|
|
" print()\n",
|
|
" print(\"num_solutions:\", num_solutions)\n",
|
|
" print(\"failures:\", solver.Failures())\n",
|
|
" print(\"branches:\", solver.Branches())\n",
|
|
" print(\"WallTime:\", solver.WallTime())\n",
|
|
"\n",
|
|
"\n",
|
|
"main()\n",
|
|
"\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|