276 lines
8.4 KiB
Plaintext
276 lines
8.4 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": [
|
|
"# crossword2"
|
|
]
|
|
},
|
|
{
|
|
"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/crossword2.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/crossword2.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",
|
|
" Crosswords in Google CP Solver.\n",
|
|
"\n",
|
|
" This is a standard example for constraint logic programming. See e.g.\n",
|
|
"\n",
|
|
" http://www.cis.temple.edu/~ingargio/cis587/readings/constraints.html\n",
|
|
" '''\n",
|
|
" We are to complete the puzzle\n",
|
|
"\n",
|
|
" 1 2 3 4 5\n",
|
|
" +---+---+---+---+---+ Given the list of words:\n",
|
|
" 1 | 1 | | 2 | | 3 | AFT LASER\n",
|
|
" +---+---+---+---+---+ ALE LEE\n",
|
|
" 2 | # | # | | # | | EEL LINE\n",
|
|
" +---+---+---+---+---+ HEEL SAILS\n",
|
|
" 3 | # | 4 | | 5 | | HIKE SHEET\n",
|
|
" +---+---+---+---+---+ HOSES STEER\n",
|
|
" 4 | 6 | # | 7 | | | KEEL TIE\n",
|
|
" +---+---+---+---+---+ KNOT\n",
|
|
" 5 | 8 | | | | |\n",
|
|
" +---+---+---+---+---+\n",
|
|
" 6 | | # | # | | # | The numbers 1,2,3,4,5,6,7,8 in the crossword\n",
|
|
" +---+---+---+---+---+ puzzle correspond to the words\n",
|
|
" that will start at those locations.\n",
|
|
" '''\n",
|
|
"\n",
|
|
" The model was inspired by Sebastian Brand's Array Constraint cross word\n",
|
|
" example\n",
|
|
" http://www.cs.mu.oz.au/~sbrand/project/ac/\n",
|
|
" http://www.cs.mu.oz.au/~sbrand/project/ac/examples.pl\n",
|
|
"\n",
|
|
"\n",
|
|
" Also, see the following models:\n",
|
|
" * MiniZinc: http://www.hakank.org/minizinc/crossword.mzn\n",
|
|
" * Comet: http://www.hakank.org/comet/crossword.co\n",
|
|
" * ECLiPSe: http://hakank.org/eclipse/crossword2.ecl\n",
|
|
" * Gecode: http://hakank.org/gecode/crossword2.cpp\n",
|
|
" * SICStus: http://hakank.org/sicstus/crossword2.pl\n",
|
|
" * Zinc: http://hakank.org/minizinc/crossword2.zinc\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():\n",
|
|
" # Create the solver.\n",
|
|
" solver = pywrapcp.Solver(\"Problem\")\n",
|
|
"\n",
|
|
" #\n",
|
|
" # data\n",
|
|
" #\n",
|
|
" alpha = \"_abcdefghijklmnopqrstuvwxyz\"\n",
|
|
" a = 1\n",
|
|
" b = 2\n",
|
|
" c = 3\n",
|
|
" d = 4\n",
|
|
" e = 5\n",
|
|
" f = 6\n",
|
|
" g = 7\n",
|
|
" h = 8\n",
|
|
" i = 9\n",
|
|
" j = 10\n",
|
|
" k = 11\n",
|
|
" l = 12\n",
|
|
" m = 13\n",
|
|
" n = 14\n",
|
|
" o = 15\n",
|
|
" p = 16\n",
|
|
" q = 17\n",
|
|
" r = 18\n",
|
|
" s = 19\n",
|
|
" t = 20\n",
|
|
" u = 21\n",
|
|
" v = 22\n",
|
|
" w = 23\n",
|
|
" x = 24\n",
|
|
" y = 25\n",
|
|
" z = 26\n",
|
|
"\n",
|
|
" num_words = 15\n",
|
|
" word_len = 5\n",
|
|
" AA = [\n",
|
|
" [h, o, s, e, s], # HOSES\n",
|
|
" [l, a, s, e, r], # LASER\n",
|
|
" [s, a, i, l, s], # SAILS\n",
|
|
" [s, h, e, e, t], # SHEET\n",
|
|
" [s, t, e, e, r], # STEER\n",
|
|
" [h, e, e, l, 0], # HEEL\n",
|
|
" [h, i, k, e, 0], # HIKE\n",
|
|
" [k, e, e, l, 0], # KEEL\n",
|
|
" [k, n, o, t, 0], # KNOT\n",
|
|
" [l, i, n, e, 0], # LINE\n",
|
|
" [a, f, t, 0, 0], # AFT\n",
|
|
" [a, l, e, 0, 0], # ALE\n",
|
|
" [e, e, l, 0, 0], # EEL\n",
|
|
" [l, e, e, 0, 0], # LEE\n",
|
|
" [t, i, e, 0, 0] # TIE\n",
|
|
" ]\n",
|
|
"\n",
|
|
" num_overlapping = 12\n",
|
|
" overlapping = [\n",
|
|
" [0, 2, 1, 0], # s\n",
|
|
" [0, 4, 2, 0], # s\n",
|
|
" [3, 1, 1, 2], # i\n",
|
|
" [3, 2, 4, 0], # k\n",
|
|
" [3, 3, 2, 2], # e\n",
|
|
" [6, 0, 1, 3], # l\n",
|
|
" [6, 1, 4, 1], # e\n",
|
|
" [6, 2, 2, 3], # e\n",
|
|
" [7, 0, 5, 1], # l\n",
|
|
" [7, 2, 1, 4], # s\n",
|
|
" [7, 3, 4, 2], # e\n",
|
|
" [7, 4, 2, 4] # r\n",
|
|
" ]\n",
|
|
"\n",
|
|
" n = 8\n",
|
|
"\n",
|
|
" # declare variables\n",
|
|
" A = {}\n",
|
|
" for I in range(num_words):\n",
|
|
" for J in range(word_len):\n",
|
|
" A[(I, J)] = solver.IntVar(0, 26, \"A(%i,%i)\" % (I, J))\n",
|
|
"\n",
|
|
" A_flat = [A[(I, J)] for I in range(num_words) for J in range(word_len)]\n",
|
|
" E = [solver.IntVar(0, num_words, \"E%i\" % I) for I in range(n)]\n",
|
|
"\n",
|
|
" #\n",
|
|
" # constraints\n",
|
|
" #\n",
|
|
" solver.Add(solver.AllDifferent(E))\n",
|
|
"\n",
|
|
" for I in range(num_words):\n",
|
|
" for J in range(word_len):\n",
|
|
" solver.Add(A[(I, J)] == AA[I][J])\n",
|
|
"\n",
|
|
" for I in range(num_overlapping):\n",
|
|
" # This is what I would do:\n",
|
|
" # solver.Add(A[(E[overlapping[I][0]], overlapping[I][1])] == A[(E[overlapping[I][2]], overlapping[I][3])])\n",
|
|
"\n",
|
|
" # But we must use Element explicitly\n",
|
|
" solver.Add(\n",
|
|
" solver.Element(A_flat, E[overlapping[I][0]] * word_len +\n",
|
|
" overlapping[I][1]) == solver\n",
|
|
" .Element(A_flat, E[overlapping[I][2]] * word_len + overlapping[I][3]))\n",
|
|
"\n",
|
|
" #\n",
|
|
" # solution and search\n",
|
|
" #\n",
|
|
" solution = solver.Assignment()\n",
|
|
" solution.Add(E)\n",
|
|
"\n",
|
|
" # db: DecisionBuilder\n",
|
|
" db = solver.Phase(E + A_flat, solver.INT_VAR_SIMPLE, solver.ASSIGN_MIN_VALUE)\n",
|
|
"\n",
|
|
" solver.NewSearch(db)\n",
|
|
" num_solutions = 0\n",
|
|
" while solver.NextSolution():\n",
|
|
" print(E)\n",
|
|
" print_solution(A, E, alpha, n, word_len)\n",
|
|
" num_solutions += 1\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",
|
|
"def print_solution(A, E, alpha, n, word_len):\n",
|
|
" for ee in range(n):\n",
|
|
" print(\"%i: (%2i)\" % (ee, E[ee].Value()), end=\" \")\n",
|
|
" print(\"\".join(\n",
|
|
" [\"%s\" % (alpha[A[ee, ii].Value()]) for ii in range(word_len)]))\n",
|
|
"\n",
|
|
"\n",
|
|
"main()\n",
|
|
"\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|