examples/notebook/hidato_sat.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copyright 2010-2017 Google\n",
    "# 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",
    "\n",
    "from ortools.sat.python import cp_model\n",
    "from ortools.sat.python import visualization\n",
    "\n",
    "\n",
    "def BuildPairs(rows, cols):\n",
    "  \"\"\"Build closeness pairs for consecutive numbers.\n",
    "\n",
    "  Build set of allowed pairs such that two consecutive numbers touch\n",
    "  each other in the grid.\n",
    "\n",
    "  Returns:\n",
    "    A list of pairs for allowed consecutive position of numbers.\n",
    "\n",
    "  Args:\n",
    "    rows: the number of rows in the grid\n",
    "    cols: the number of columns in the grid\n",
    "  \"\"\"\n",
    "  return [\n",
    "      (x * cols + y, (x + dx) * cols + (y + dy)) for x in range(rows)\n",
    "      for y in range(cols) for dx in (-1, 0, 1)\n",
    "      for dy in (-1, 0, 1)\n",
    "      if (x + dx >= 0 and x + dx < rows and y + dy >= 0 and y + dy < cols and\n",
    "          (dx != 0 or dy != 0))\n",
    "  ]\n",
    "\n",
    "\n",
    "def PrintSolution(positions, rows, cols):\n",
    "  \"\"\"Print a current solution.\"\"\"\n",
    "  # Create empty board.\n",
    "  board = []\n",
    "  for _ in range(rows):\n",
    "    board.append([0] * cols)\n",
    "  # Fill board with solution value.\n",
    "  for k in range(rows * cols):\n",
    "    position = positions[k]\n",
    "    board[position // cols][position % cols] = k + 1\n",
    "  # Print the board.\n",
    "  print('Solution')\n",
    "  PrintMatrix(board)\n",
    "\n",
    "\n",
    "def PrintMatrix(game):\n",
    "  \"\"\"Pretty print of a matrix.\"\"\"\n",
    "  rows = len(game)\n",
    "  cols = len(game[0])\n",
    "  for i in range(rows):\n",
    "    line = ''\n",
    "    for j in range(cols):\n",
    "      if game[i][j] == 0:\n",
    "        line += '  .'\n",
    "      else:\n",
    "        line += '% 3s' % game[i][j]\n",
    "    print(line)\n",
    "\n",
    "\n",
    "def BuildPuzzle(problem):\n",
    "  #\n",
    "  # models, a 0 indicates an open cell which number is not yet known.\n",
    "  #\n",
    "  #\n",
    "  puzzle = None\n",
    "  if problem == 1:\n",
    "    # Simple problem\n",
    "    puzzle = [[6, 0, 9], [0, 2, 8], [1, 0, 0]]\n",
    "\n",
    "  elif problem == 2:\n",
    "    puzzle = [[0, 44, 41, 0, 0, 0, 0], [0, 43, 0, 28, 29, 0, 0],\n",
    "              [0, 1, 0, 0, 0, 33, 0], [0, 2, 25, 4, 34, 0, 36],\n",
    "              [49, 16, 0, 23, 0, 0, 0], [0, 19, 0, 0, 12, 7,\n",
    "                                         0], [0, 0, 0, 14, 0, 0, 0]]\n",
    "\n",
    "  elif problem == 3:\n",
    "    # Problems from the book:\n",
    "    # Gyora Bededek: \"Hidato: 2000 Pure Logic Puzzles\"\n",
    "    # Problem 1 (Practice)\n",
    "    puzzle = [[0, 0, 20, 0, 0], [0, 0, 0, 16, 18], [22, 0, 15, 0, 0],\n",
    "              [23, 0, 1, 14, 11], [0, 25, 0, 0, 12]]\n",
    "\n",
    "  elif problem == 4:\n",
    "    # problem 2 (Practice)\n",
    "    puzzle = [[0, 0, 0, 0, 14], [0, 18, 12, 0, 0], [0, 0, 17, 4, 5],\n",
    "              [0, 0, 7, 0, 0], [9, 8, 25, 1, 0]]\n",
    "\n",
    "  elif problem == 5:\n",
    "    # problem 3 (Beginner)\n",
    "    puzzle = [[0, 26, 0, 0, 0, 18], [0, 0, 27, 0, 0, 19], [31, 23, 0, 0, 14, 0],\n",
    "              [0, 33, 8, 0, 15, 1], [0, 0, 0, 5, 0, 0], [35, 36, 0, 10, 0, 0]]\n",
    "  elif problem == 6:\n",
    "    # Problem 15 (Intermediate)\n",
    "    puzzle = [[64, 0, 0, 0, 0, 0, 0, 0], [1, 63, 0, 59, 15, 57, 53, 0],\n",
    "              [0, 4, 0, 14, 0, 0, 0, 0], [3, 0, 11, 0, 20, 19, 0,\n",
    "                                          50], [0, 0, 0, 0, 22, 0, 48, 40],\n",
    "              [9, 0, 0, 32, 23, 0, 0, 41], [27, 0, 0, 0, 36, 0, 46,\n",
    "                                            0], [28, 30, 0, 35, 0, 0, 0, 0]]\n",
    "  return puzzle\n",
    "\n",
    "\n",
    "def SolveHidato(puzzle, index):\n",
    "  \"\"\"Solve the given hidato table.\"\"\"\n",
    "  # Create the model.\n",
    "  model = cp_model.CpModel()\n",
    "\n",
    "  r = len(puzzle)\n",
    "  c = len(puzzle[0])\n",
    "  if not visualization.RunFromIPython():\n",
    "    print('')\n",
    "    print('----- Solving problem %i -----' % index)\n",
    "    print('')\n",
    "    print(('Initial game (%i x %i)' % (r, c)))\n",
    "    PrintMatrix(puzzle)\n",
    "\n",
    "  #\n",
    "  # declare variables\n",
    "  #\n",
    "  positions = [model.NewIntVar(0, r * c - 1, 'p[%i]' % i) for i in range(r * c)]\n",
    "\n",
    "  #\n",
    "  # constraints\n",
    "  #\n",
    "  model.AddAllDifferent(positions)\n",
    "\n",
    "  #\n",
    "  # Fill in the clues\n",
    "  #\n",
    "  for i in range(r):\n",
    "    for j in range(c):\n",
    "      if puzzle[i][j] > 0:\n",
    "        model.Add(positions[puzzle[i][j] - 1] == i * c + j)\n",
    "\n",
    "  # Consecutive numbers much touch each other in the grid.\n",
    "  # We use an allowed assignment constraint to model it.\n",
    "  close_tuples = BuildPairs(r, c)\n",
    "  for k in range(0, r * c - 1):\n",
    "    model.AddAllowedAssignments([positions[k], positions[k + 1]], close_tuples)\n",
    "\n",
    "  #\n",
    "  # solution and search\n",
    "  #\n",
    "\n",
    "  solver = cp_model.CpSolver()\n",
    "  status = solver.Solve(model)\n",
    "\n",
    "  if status == cp_model.FEASIBLE:\n",
    "    if visualization.RunFromIPython():\n",
    "      output = visualization.SvgWrapper(10, r, 40.0)\n",
    "      for i in range(len(positions)):\n",
    "        val = solver.Value(positions[i])\n",
    "        x = val % c\n",
    "        y = val // c\n",
    "        color = 'white' if puzzle[y][x] == 0 else 'lightgreen'\n",
    "        value = solver.Value(positions[i])\n",
    "        output.AddRectangle(x, r - y - 1, 1, 1, color, 'black', str(i + 1))\n",
    "\n",
    "      output.AddTitle('Puzzle %i solved in %f s' % (index, solver.WallTime()))\n",
    "      output.Display()\n",
    "    else:\n",
    "      PrintSolution(\n",
    "          [solver.Value(x) for x in positions],\n",
    "          r,\n",
    "          c,\n",
    "      )\n",
    "      print('Statistics')\n",
    "      print('  - conflicts : %i' % solver.NumConflicts())\n",
    "      print('  - branches  : %i' % solver.NumBranches())\n",
    "      print('  - wall time : %f ms' % solver.WallTime())\n",
    "\n",
    "\n",
    "for i in range(1, 7):\n",
    "  SolveHidato(BuildPuzzle(i), i)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}