246 lines
7.5 KiB
Plaintext
246 lines
7.5 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": [
|
|
"# pandigital_numbers"
|
|
]
|
|
},
|
|
{
|
|
"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/pandigital_numbers.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/pandigital_numbers.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",
|
|
" Pandigital numbers in Google CP Solver.\n",
|
|
"\n",
|
|
" From Albert H. Beiler 'Recreations in the Theory of Numbers',\n",
|
|
" quoted from http://www.worldofnumbers.com/ninedig1.htm\n",
|
|
" '''\n",
|
|
" Chapter VIII : Digits - and the magic of 9\n",
|
|
"\n",
|
|
" The following curious table shows how to arrange the 9 digits so that\n",
|
|
" the product of 2 groups is equal to a number represented by the\n",
|
|
" remaining digits.\n",
|
|
"\n",
|
|
" 12 x 483 = 5796\n",
|
|
" 42 x 138 = 5796\n",
|
|
" 18 x 297 = 5346\n",
|
|
" 27 x 198 = 5346\n",
|
|
" 39 x 186 = 7254\n",
|
|
" 48 x 159 = 7632\n",
|
|
" 28 x 157 = 4396\n",
|
|
" 4 x 1738 = 6952\n",
|
|
" 4 x 1963 = 7852\n",
|
|
" '''\n",
|
|
"\n",
|
|
" See also MathWorld http://mathworld.wolfram.com/PandigitalNumber.html\n",
|
|
" '''\n",
|
|
" A number is said to be pandigital if it contains each of the digits\n",
|
|
" from 0 to 9 (and whose leading digit must be nonzero). However,\n",
|
|
" 'zeroless' pandigital quantities contain the digits 1 through 9.\n",
|
|
" Sometimes exclusivity is also required so that each digit is\n",
|
|
" restricted to appear exactly once.\n",
|
|
" '''\n",
|
|
"\n",
|
|
" * Wikipedia http://en.wikipedia.org/wiki/Pandigital_number\n",
|
|
"\n",
|
|
"\n",
|
|
" Compare with the following models:\n",
|
|
" * MiniZinc: http://www.hakank.org/minizinc/pandigital_numbers.mzn\n",
|
|
" * Comet : http://www.hakank.org/comet/pandigital_numbers.co\n",
|
|
" * ECLiPSe : http://www.hakank.org/eclipse/pandigital_numbers.ecl\n",
|
|
" * Gecode/R: http://www.hakank.org/gecoder/pandigital_numbers.rb\n",
|
|
" * ECLiPSe : http://hakank.org/eclipse/pandigital_numbers.ecl\n",
|
|
" * SICStus : http://hakank.org/sicstus/pandigital_numbers.pl\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",
|
|
"\n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "code",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"import sys\n",
|
|
"\n",
|
|
"from ortools.constraint_solver import pywrapcp\n",
|
|
"\n",
|
|
"#\n",
|
|
"# converts a number (s) <-> an array of integers (t) in the specific base.\n",
|
|
"#\n",
|
|
"\n",
|
|
"\n",
|
|
"def toNum(solver, t, s, base):\n",
|
|
" tlen = len(t)\n",
|
|
" solver.Add(\n",
|
|
" s == solver.Sum([(base**(tlen - i - 1)) * t[i] for i in range(tlen)]))\n",
|
|
"\n",
|
|
"\n",
|
|
"def main(base=10, start=1, len1=1, len2=4):\n",
|
|
"\n",
|
|
" # Create the solver.\n",
|
|
" solver = pywrapcp.Solver(\"Pandigital numbers\")\n",
|
|
"\n",
|
|
" #\n",
|
|
" # data\n",
|
|
" #\n",
|
|
" max_d = base - 1\n",
|
|
" x_len = max_d + 1 - start\n",
|
|
" max_num = base**4 - 1\n",
|
|
"\n",
|
|
" #\n",
|
|
" # declare variables\n",
|
|
" #\n",
|
|
" num1 = solver.IntVar(0, max_num, \"num1\")\n",
|
|
" num2 = solver.IntVar(0, max_num, \"num2\")\n",
|
|
" res = solver.IntVar(0, max_num, \"res\")\n",
|
|
"\n",
|
|
" x = [solver.IntVar(start, max_d, \"x[%i]\" % i) for i in range(x_len)]\n",
|
|
"\n",
|
|
" #\n",
|
|
" # constraints\n",
|
|
" #\n",
|
|
" solver.Add(solver.AllDifferent(x))\n",
|
|
"\n",
|
|
" toNum(solver, [x[i] for i in range(len1)], num1, base)\n",
|
|
" toNum(solver, [x[i] for i in range(len1, len1 + len2)], num2, base)\n",
|
|
" toNum(solver, [x[i] for i in range(len1 + len2, x_len)], res, base)\n",
|
|
"\n",
|
|
" solver.Add(num1 * num2 == res)\n",
|
|
"\n",
|
|
" # no number must start with 0\n",
|
|
" solver.Add(x[0] > 0)\n",
|
|
" solver.Add(x[len1] > 0)\n",
|
|
" solver.Add(x[len1 + len2] > 0)\n",
|
|
"\n",
|
|
" # symmetry breaking\n",
|
|
" solver.Add(num1 < num2)\n",
|
|
"\n",
|
|
" #\n",
|
|
" # solution and search\n",
|
|
" #\n",
|
|
" solution = solver.Assignment()\n",
|
|
" solution.Add(x)\n",
|
|
" solution.Add(num1)\n",
|
|
" solution.Add(num2)\n",
|
|
" solution.Add(res)\n",
|
|
"\n",
|
|
" db = solver.Phase(x, solver.INT_VAR_SIMPLE, solver.INT_VALUE_DEFAULT)\n",
|
|
"\n",
|
|
" solver.NewSearch(db)\n",
|
|
" num_solutions = 0\n",
|
|
" solutions = []\n",
|
|
" while solver.NextSolution():\n",
|
|
" print_solution([x[i].Value() for i in range(x_len)], len1, len2, x_len)\n",
|
|
" num_solutions += 1\n",
|
|
"\n",
|
|
" solver.EndSearch()\n",
|
|
"\n",
|
|
" if 0 and num_solutions > 0:\n",
|
|
" print()\n",
|
|
" print(\"num_solutions:\", num_solutions)\n",
|
|
" print(\"failures:\", solver.Failures())\n",
|
|
" print(\"branches:\", solver.Branches())\n",
|
|
" print(\"WallTime:\", solver.WallTime())\n",
|
|
" print()\n",
|
|
"\n",
|
|
"\n",
|
|
"def print_solution(x, len1, len2, x_len):\n",
|
|
" print(\"\".join([str(x[i]) for i in range(len1)]), \"*\", end=\" \")\n",
|
|
" print(\"\".join([str(x[i]) for i in range(len1, len1 + len2)]), \"=\", end=\" \")\n",
|
|
" print(\"\".join([str(x[i]) for i in range(len1 + len2, x_len)]))\n",
|
|
"\n",
|
|
"\n",
|
|
"base = 10\n",
|
|
"start = 1\n",
|
|
"if len(sys.argv) > 1:\n",
|
|
" base = int(sys.argv[1])\n",
|
|
"if len(sys.argv) > 2:\n",
|
|
" start = int(sys.argv[2])\n",
|
|
"\n",
|
|
"x_len = base - 1 + 1 - start\n",
|
|
"for len1 in range(1 + (x_len)):\n",
|
|
" for len2 in range(1 + (x_len)):\n",
|
|
" if x_len > len1 + len2:\n",
|
|
" main(base, start, len1, len2)\n",
|
|
"\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|