examples/notebook/cp_is_fun_sat.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copyright 2010-2011 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",
    "\"\"\"Cryptarithmetic puzzle\n",
    "\n",
    "First attempt to solve equation CP + IS + FUN = TRUE\n",
    "where each letter represents a unique digit.\n",
    "\n",
    "This problem has 72 different solutions in base 10.\n",
    "\"\"\"\n",
    "\n",
    "from __future__ import print_function\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
    "  \"\"\"Print intermediate solutions.\"\"\"\n",
    "\n",
    "  def __init__(self, variables):\n",
    "    cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "    self.__variables = variables\n",
    "    self.__solution_count = 0\n",
    "\n",
    "  def OnSolutionCallback(self):\n",
    "    self.__solution_count += 1\n",
    "    for v in self.__variables:\n",
    "      print('%s=%i' % (v, self.Value(v)), end=' ')\n",
    "    print()\n",
    "\n",
    "  def SolutionCount(self):\n",
    "    return self.__solution_count\n",
    "\n",
    "\n",
    "def CPIsFun():\n",
    "\n",
    "  kBase = 10\n",
    "\n",
    "  # Constraint programming engine\n",
    "  model = cp_model.CpModel()\n",
    "\n",
    "  c = model.NewIntVar(1, 9, 'C')\n",
    "  p = model.NewIntVar(0, 9, 'P')\n",
    "  i = model.NewIntVar(1, 9, 'I')\n",
    "  s = model.NewIntVar(0, 9, 'S')\n",
    "  f = model.NewIntVar(1, 9, 'F')\n",
    "  u = model.NewIntVar(0, 9, 'U')\n",
    "  n = model.NewIntVar(0, 9, 'N')\n",
    "  t = model.NewIntVar(1, 9, 'T')\n",
    "  r = model.NewIntVar(0, 9, 'R')\n",
    "  e = model.NewIntVar(0, 9, 'E')\n",
    "\n",
    "  # We need to group variables in a list to use the constraint AllDifferent.\n",
    "  letters = [c, p, i, s, f, u, n, t, r, e]\n",
    "\n",
    "  # Verify that we have enough digits.\n",
    "  assert kBase >= len(letters)\n",
    "\n",
    "  # Define constraints.\n",
    "  model.AddAllDifferent(letters)\n",
    "\n",
    "  # CP + IS + FUN = TRUE\n",
    "  model.Add(p + s + n + kBase * (c + i + u) + kBase * kBase * f == e +\n",
    "            kBase * u + kBase * kBase * r + kBase * kBase * kBase * t)\n",
    "\n",
    "  solver = cp_model.CpSolver()\n",
    "  status = solver.Solve(model)\n",
    "\n",
    "  ### Solve model.\n",
    "  solver = cp_model.CpSolver()\n",
    "  solution_printer = VarArraySolutionPrinter(letters)\n",
    "  status = solver.SearchForAllSolutions(model, solution_printer)\n",
    "\n",
    "  print()\n",
    "  print('Statistics')\n",
    "  print('  - conflicts       : %i' % solver.NumConflicts())\n",
    "  print('  - branches        : %i' % solver.NumBranches())\n",
    "  print('  - wall time       : %f ms' % solver.WallTime())\n",
    "  print('  - solutions found : %i' % solution_printer.SolutionCount())\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}