Overview
A cryptarithmetic puzzle is a mathematical exercise where the digits of some numbers are represented by letters (or symbols). Each letter represents a unique digit. The goal is to find the digits such that a given mathematical equation is verified:
CP
+ IS
+ FUN
--------
= TRUE
One assignment of letters to digits yields the following equation:
23
+ 74
+ 968
--------
= 1065
There are other answers to this problem. We'll show how to find all solutions.
Modeling the problem
As with any optimization problem, we'll start by identifying variables and constraints. The variables are the letters, which can take on any single digit value.
For CP + IS + FUN = TRUE, the constraints are as follows:
- The equation: CP + IS + FUN = TRUE.
- Each of the ten letters must be a different digit.
- C, I, F, and T can't be zero (since we don't write leading zeros in numbers).
Implementing the solution
You can solve cryptarithmetic problems with either the new CP-SAT solver, which is more efficient, or the original CP solver. We'll show you examples using both solvers, starting with CP-SAT.
CP-SAT
We'll show the variables, the constraints, the solver invocation, and finally the complete programs.
Defining the variables
When using the CP-SAT solver, there are certain helper methods it's
useful to define. We'll use two of them, new_variable
and new_boolean_variable, to declare our (integer) digits
and our (boolean) carry bits:
Python
base = 10
c = model.NewIntVar(1, base - 1, 'C')
p = model.NewIntVar(0, base - 1, 'P')
i = model.NewIntVar(1, base - 1, 'I')
s = model.NewIntVar(0, base - 1, 'S')
f = model.NewIntVar(1, base - 1, 'F')
u = model.NewIntVar(0, base - 1, 'U')
n = model.NewIntVar(0, base - 1, 'N')
t = model.NewIntVar(1, base - 1, 'T')
r = model.NewIntVar(0, base - 1, 'R')
e = model.NewIntVar(0, base - 1, 'E')
# We need to group variables in a list to use the constraint AllDifferent.
letters = [c, p, i, s, f, u, n, t, r, e]
# Verify that we have enough digits.
assert base >= len(letters)
C++
const int64 kBase = 10;
// Define decision variables.
Domain digit(0, kBase - 1);
Domain non_zero_digit(1, kBase - 1);
IntVar c = cp_model.NewIntVar(non_zero_digit).WithName("C");
IntVar p = cp_model.NewIntVar(digit).WithName("P");
IntVar i = cp_model.NewIntVar(non_zero_digit).WithName("I");
IntVar s = cp_model.NewIntVar(digit).WithName("S");
IntVar f = cp_model.NewIntVar(non_zero_digit).WithName("F");
IntVar u = cp_model.NewIntVar(digit).WithName("U");
IntVar n = cp_model.NewIntVar(digit).WithName("N");
IntVar t = cp_model.NewIntVar(non_zero_digit).WithName("T");
IntVar r = cp_model.NewIntVar(digit).WithName("R");
IntVar e = cp_model.NewIntVar(digit).WithName("E");
Java
int base = 10;
IntVar c = model.newIntVar(1, base - 1, "C");
IntVar p = model.newIntVar(0, base - 1, "P");
IntVar i = model.newIntVar(1, base - 1, "I");
IntVar s = model.newIntVar(0, base - 1, "S");
IntVar f = model.newIntVar(1, base - 1, "F");
IntVar u = model.newIntVar(0, base - 1, "U");
IntVar n = model.newIntVar(0, base - 1, "N");
IntVar t = model.newIntVar(1, base - 1, "T");
IntVar r = model.newIntVar(0, base - 1, "R");
IntVar e = model.newIntVar(0, base - 1, "E");
// We need to group variables in a list to use the constraint AllDifferent.
IntVar[] letters = new IntVar[] {c, p, i, s, f, u, n, t, r, e};
C#
int kBase = 10;
IntVar c = model.NewIntVar(1, kBase - 1, "C");
IntVar p = model.NewIntVar(0, kBase - 1, "P");
IntVar i = model.NewIntVar(1, kBase - 1, "I");
IntVar s = model.NewIntVar(0, kBase - 1, "S");
IntVar f = model.NewIntVar(1, kBase - 1, "F");
IntVar u = model.NewIntVar(0, kBase - 1, "U");
IntVar n = model.NewIntVar(0, kBase - 1, "N");
IntVar t = model.NewIntVar(1, kBase - 1, "T");
IntVar r = model.NewIntVar(0, kBase - 1, "R");
IntVar e = model.NewIntVar(0, kBase - 1, "E");
// We need to group variables in a list to use the constraint AllDifferent.
IntVar[] letters = new IntVar[] { c, p, i, s, f, u, n, t, r, e };
Defining the constraints
Next, constraints. First, we ensure that all letters have different
values, using the add_all_different helper method. Then
we use the add_linear_constraint helper method to create
constraints that enforce the add-and-carry operations.
Python
# Define constraints.
model.AddAllDifferent(letters)
# CP + IS + FUN = TRUE
model.Add(c * base + p + i * base + s + f * base * base + u * base +
n == t * base * base * base + r * base * base + u * base + e)
C++
// Define constraints.
cp_model.AddAllDifferent({c, p, i, s, f, u, n, t, r, e});
// CP + IS + FUN = TRUE
cp_model.AddEquality(
LinearExpr::ScalProd({c, p, i, s, f, u, n},
{kBase, 1, kBase, 1, kBase * kBase, kBase, 1}),
LinearExpr::ScalProd({t, r, u, e},
{kBase * kBase * kBase, kBase * kBase, kBase, 1}));
Java
// Define constraints.
model.addAllDifferent(letters);
// CP + IS + FUN = TRUE
model.addEquality(LinearExpr.scalProd(new IntVar[] {c, p, i, s, f, u, n, t, r, u, e},
new long[] {base, 1, base, 1, base * base, base, 1, -base * base * base,
-base * base, -base, -1}),
0);
C#
// Define constraints.
model.AddAllDifferent(letters);
// CP + IS + FUN = TRUE
model.Add(c * kBase + p + i * kBase + s + f * kBase * kBase + u * kBase + n ==
t * kBase * kBase * kBase + r * kBase * kBase + u * kBase + e);
Solution printer
The code for the solution printer, which displays each solution as the solver finds it, is shown below.
Python
class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def on_solution_callback(self):
self.__solution_count += 1
for v in self.__variables:
print('%s=%i' % (v, self.Value(v)), end=' ')
print()
def solution_count(self):
return self.__solution_count
C++
Model model;
int num_solutions = 0;
model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) {
LOG(INFO) << "Solution " << num_solutions;
LOG(INFO) << "C=" << SolutionIntegerValue(response, c) << " "
<< "P=" << SolutionIntegerValue(response, p) << " "
<< "I=" << SolutionIntegerValue(response, i) << " "
<< "S=" << SolutionIntegerValue(response, s) << " "
<< "F=" << SolutionIntegerValue(response, f) << " "
<< "U=" << SolutionIntegerValue(response, u) << " "
<< "N=" << SolutionIntegerValue(response, n) << " "
<< "T=" << SolutionIntegerValue(response, t) << " "
<< "R=" << SolutionIntegerValue(response, r) << " "
<< "E=" << SolutionIntegerValue(response, e);
num_solutions++;
}));
Java
static class VarArraySolutionPrinter extends CpSolverSolutionCallback {
public VarArraySolutionPrinter(IntVar[] variables) {
variableArray = variables;
}
@Override
public void onSolutionCallback() {
for (IntVar v : variableArray) {
System.out.printf(" %s = %d", v.getName(), value(v));
}
System.out.println();
solutionCount++;
}
public int getSolutionCount() {
return solutionCount;
}
private int solutionCount;
private final IntVar[] variableArray;
}
C#
public class VarArraySolutionPrinter : CpSolverSolutionCallback
{
public VarArraySolutionPrinter(IntVar[] variables)
{
variables_ = variables;
}
public override void OnSolutionCallback()
{
{
foreach (IntVar v in variables_)
{
Console.Write(String.Format(" {0}={1}", v.ShortString(), Value(v)));
}
Console.WriteLine();
solution_count_++;
}
}
public int SolutionCount()
{
return solution_count_;
}
private int solution_count_;
private IntVar[] variables_;
}
Invoking the solver
Finally we solve the problem and display the solution. All the magic is in the operations_research::sat::SolveCpModel() method.
Python
### Solve model.
solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinter(letters)
status = solver.SearchForAllSolutions(model, solution_printer)
C++
// Tell the solver to enumerate all solutions. SatParameters parameters; parameters.set_enumerate_all_solutions(true); model.Add(NewSatParameters(parameters)); const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model); LOG(INFO) << "Number of solutions found: " << num_solutions;
Java
// Create a solver and solve the model.
CpSolver solver = new CpSolver();
VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters);
solver.searchAllSolutions(model, cb);
C#
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters);
solver.SearchAllSolutions(model, cb);
When you run the program, it diplays the following output, in which each row is a solution:
C=2 P=3 I=7 S=4 F=9 U=6 N=8 T=1 R=0 E=5 C=2 P=4 I=7 S=3 F=9 U=6 N=8 T=1 R=0 E=5 C=2 P=5 I=7 S=3 F=9 U=4 N=8 T=1 R=0 E=6 C=2 P=8 I=7 S=3 F=9 U=4 N=5 T=1 R=0 E=6 C=2 P=8 I=7 S=3 F=9 U=6 N=4 T=1 R=0 E=5 C=3 P=7 I=6 S=2 F=9 U=8 N=5 T=1 R=0 E=4 C=6 P=7 I=3 S=2 F=9 U=8 N=5 T=1 R=0 E=4 C=6 P=5 I=3 S=2 F=9 U=8 N=7 T=1 R=0 E=4 C=3 P=5 I=6 S=2 F=9 U=8 N=7 T=1 R=0 E=4 C=3 P=8 I=6 S=4 F=9 U=2 N=5 T=1 R=0 E=7 C=3 P=7 I=6 S=5 F=9 U=8 N=2 T=1 R=0 E=4 C=3 P=8 I=6 S=5 F=9 U=2 N=4 T=1 R=0 E=7 C=3 P=5 I=6 S=4 F=9 U=2 N=8 T=1 R=0 E=7 C=3 P=4 I=6 S=5 F=9 U=2 N=8 T=1 R=0 E=7 C=3 P=2 I=6 S=5 F=9 U=8 N=7 T=1 R=0 E=4 C=3 P=4 I=6 S=8 F=9 U=2 N=5 T=1 R=0 E=7 C=3 P=2 I=6 S=7 F=9 U=8 N=5 T=1 R=0 E=4 C=3 P=5 I=6 S=8 F=9 U=2 N=4 T=1 R=0 E=7 C=3 P=5 I=6 S=7 F=9 U=8 N=2 T=1 R=0 E=4 C=2 P=5 I=7 S=6 F=9 U=8 N=3 T=1 R=0 E=4 C=2 P=5 I=7 S=8 F=9 U=4 N=3 T=1 R=0 E=6 C=2 P=6 I=7 S=5 F=9 U=8 N=3 T=1 R=0 E=4 C=2 P=4 I=7 S=8 F=9 U=6 N=3 T=1 R=0 E=5 C=2 P=3 I=7 S=8 F=9 U=6 N=4 T=1 R=0 E=5 C=2 P=8 I=7 S=5 F=9 U=4 N=3 T=1 R=0 E=6 C=2 P=8 I=7 S=4 F=9 U=6 N=3 T=1 R=0 E=5 C=2 P=6 I=7 S=3 F=9 U=8 N=5 T=1 R=0 E=4 C=2 P=5 I=7 S=3 F=9 U=8 N=6 T=1 R=0 E=4 C=2 P=3 I=7 S=5 F=9 U=4 N=8 T=1 R=0 E=6 C=2 P=3 I=7 S=5 F=9 U=8 N=6 T=1 R=0 E=4 C=2 P=3 I=7 S=6 F=9 U=8 N=5 T=1 R=0 E=4 C=2 P=3 I=7 S=8 F=9 U=4 N=5 T=1 R=0 E=6 C=4 P=3 I=5 S=8 F=9 U=2 N=6 T=1 R=0 E=7 C=5 P=3 I=4 S=8 F=9 U=2 N=6 T=1 R=0 E=7 C=6 P=2 I=3 S=7 F=9 U=8 N=5 T=1 R=0 E=4 C=7 P=3 I=2 S=6 F=9 U=8 N=5 T=1 R=0 E=4 C=7 P=3 I=2 S=8 F=9 U=4 N=5 T=1 R=0 E=6 C=6 P=4 I=3 S=8 F=9 U=2 N=5 T=1 R=0 E=7 C=5 P=3 I=4 S=6 F=9 U=2 N=8 T=1 R=0 E=7 C=4 P=3 I=5 S=6 F=9 U=2 N=8 T=1 R=0 E=7 C=5 P=6 I=4 S=3 F=9 U=2 N=8 T=1 R=0 E=7 C=7 P=4 I=2 S=3 F=9 U=6 N=8 T=1 R=0 E=5 C=7 P=3 I=2 S=4 F=9 U=6 N=8 T=1 R=0 E=5 C=6 P=2 I=3 S=5 F=9 U=8 N=7 T=1 R=0 E=4 C=7 P=3 I=2 S=5 F=9 U=4 N=8 T=1 R=0 E=6 C=6 P=4 I=3 S=5 F=9 U=2 N=8 T=1 R=0 E=7 C=6 P=5 I=3 S=4 F=9 U=2 N=8 T=1 R=0 E=7 C=7 P=5 I=2 S=3 F=9 U=4 N=8 T=1 R=0 E=6 C=4 P=6 I=5 S=3 F=9 U=2 N=8 T=1 R=0 E=7 C=6 P=5 I=3 S=8 F=9 U=2 N=4 T=1 R=0 E=7 C=6 P=5 I=3 S=7 F=9 U=8 N=2 T=1 R=0 E=4 C=7 P=5 I=2 S=8 F=9 U=4 N=3 T=1 R=0 E=6 C=7 P=5 I=2 S=6 F=9 U=8 N=3 T=1 R=0 E=4 C=5 P=8 I=4 S=6 F=9 U=2 N=3 T=1 R=0 E=7 C=4 P=8 I=5 S=6 F=9 U=2 N=3 T=1 R=0 E=7 C=4 P=8 I=5 S=3 F=9 U=2 N=6 T=1 R=0 E=7 C=5 P=8 I=4 S=3 F=9 U=2 N=6 T=1 R=0 E=7 C=7 P=8 I=2 S=3 F=9 U=4 N=5 T=1 R=0 E=6 C=7 P=8 I=2 S=3 F=9 U=6 N=4 T=1 R=0 E=5 C=7 P=8 I=2 S=4 F=9 U=6 N=3 T=1 R=0 E=5 C=7 P=8 I=2 S=5 F=9 U=4 N=3 T=1 R=0 E=6 C=6 P=8 I=3 S=5 F=9 U=2 N=4 T=1 R=0 E=7 C=6 P=8 I=3 S=4 F=9 U=2 N=5 T=1 R=0 E=7 C=6 P=7 I=3 S=5 F=9 U=8 N=2 T=1 R=0 E=4 C=7 P=6 I=2 S=5 F=9 U=8 N=3 T=1 R=0 E=4 C=7 P=3 I=2 S=5 F=9 U=8 N=6 T=1 R=0 E=4 C=7 P=4 I=2 S=8 F=9 U=6 N=3 T=1 R=0 E=5 C=7 P=3 I=2 S=8 F=9 U=6 N=4 T=1 R=0 E=5 C=5 P=6 I=4 S=8 F=9 U=2 N=3 T=1 R=0 E=7 C=4 P=6 I=5 S=8 F=9 U=2 N=3 T=1 R=0 E=7 C=7 P=6 I=2 S=3 F=9 U=8 N=5 T=1 R=0 E=4 C=7 P=5 I=2 S=3 F=9 U=8 N=6 T=1 R=0 E=4 Statistics - status : OPTIMAL - conflicts : 110 - branches : 435 - wall time : 0.014934 ms - solutions found : 72
Complete programs
Here are the complete programs.
Python
"""Cryptarithmetic puzzle.
First attempt to solve equation CP + IS + FUN = TRUE
where each letter represents a unique digit.
This problem has 72 different solutions in base 10.
"""
from ortools.sat.python import cp_model
class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def on_solution_callback(self):
self.__solution_count += 1
for v in self.__variables:
print('%s=%i' % (v, self.Value(v)), end=' ')
print()
def solution_count(self):
return self.__solution_count
def CPIsFunSat():
"""Solve the CP+IS+FUN==TRUE cryptarithm."""
# Constraint programming engine
model = cp_model.CpModel()
base = 10
c = model.NewIntVar(1, base - 1, 'C')
p = model.NewIntVar(0, base - 1, 'P')
i = model.NewIntVar(1, base - 1, 'I')
s = model.NewIntVar(0, base - 1, 'S')
f = model.NewIntVar(1, base - 1, 'F')
u = model.NewIntVar(0, base - 1, 'U')
n = model.NewIntVar(0, base - 1, 'N')
t = model.NewIntVar(1, base - 1, 'T')
r = model.NewIntVar(0, base - 1, 'R')
e = model.NewIntVar(0, base - 1, 'E')
# We need to group variables in a list to use the constraint AllDifferent.
letters = [c, p, i, s, f, u, n, t, r, e]
# Verify that we have enough digits.
assert base >= len(letters)
# Define constraints.
model.AddAllDifferent(letters)
# CP + IS + FUN = TRUE
model.Add(c * base + p + i * base + s + f * base * base + u * base +
n == t * base * base * base + r * base * base + u * base + e)
### Solve model.
solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinter(letters)
status = solver.SearchForAllSolutions(model, solution_printer)
print()
print('Statistics')
print(' - status : %s' % solver.StatusName(status))
print(' - conflicts : %i' % solver.NumConflicts())
print(' - branches : %i' % solver.NumBranches())
print(' - wall time : %f s' % solver.WallTime())
print(' - solutions found : %i' % solution_printer.solution_count())
if __name__ == '__main__':
CPIsFunSat()
C++
// Cryptarithmetic puzzle
//
// First attempt to solve equation CP + IS + FUN = TRUE
// where each letter represents a unique digit.
//
// This problem has 72 different solutions in base 10.
#include <vector>
#include "ortools/sat/cp_model.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
namespace operations_research {
namespace sat {
void CPIsFunSat() {
// Instantiate the solver.
CpModelBuilder cp_model;
const int64 kBase = 10;
// Define decision variables.
Domain digit(0, kBase - 1);
Domain non_zero_digit(1, kBase - 1);
IntVar c = cp_model.NewIntVar(non_zero_digit).WithName("C");
IntVar p = cp_model.NewIntVar(digit).WithName("P");
IntVar i = cp_model.NewIntVar(non_zero_digit).WithName("I");
IntVar s = cp_model.NewIntVar(digit).WithName("S");
IntVar f = cp_model.NewIntVar(non_zero_digit).WithName("F");
IntVar u = cp_model.NewIntVar(digit).WithName("U");
IntVar n = cp_model.NewIntVar(digit).WithName("N");
IntVar t = cp_model.NewIntVar(non_zero_digit).WithName("T");
IntVar r = cp_model.NewIntVar(digit).WithName("R");
IntVar e = cp_model.NewIntVar(digit).WithName("E");
// Define constraints.
cp_model.AddAllDifferent({c, p, i, s, f, u, n, t, r, e});
// CP + IS + FUN = TRUE
cp_model.AddEquality(
LinearExpr::ScalProd({c, p, i, s, f, u, n},
{kBase, 1, kBase, 1, kBase * kBase, kBase, 1}),
LinearExpr::ScalProd({t, r, u, e},
{kBase * kBase * kBase, kBase * kBase, kBase, 1}));
Model model;
int num_solutions = 0;
model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) {
LOG(INFO) << "Solution " << num_solutions;
LOG(INFO) << "C=" << SolutionIntegerValue(response, c) << " "
<< "P=" << SolutionIntegerValue(response, p) << " "
<< "I=" << SolutionIntegerValue(response, i) << " "
<< "S=" << SolutionIntegerValue(response, s) << " "
<< "F=" << SolutionIntegerValue(response, f) << " "
<< "U=" << SolutionIntegerValue(response, u) << " "
<< "N=" << SolutionIntegerValue(response, n) << " "
<< "T=" << SolutionIntegerValue(response, t) << " "
<< "R=" << SolutionIntegerValue(response, r) << " "
<< "E=" << SolutionIntegerValue(response, e);
num_solutions++;
}));
// Tell the solver to enumerate all solutions.
SatParameters parameters;
parameters.set_enumerate_all_solutions(true);
model.Add(NewSatParameters(parameters));
const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
LOG(INFO) << "Number of solutions found: " << num_solutions;
}
} // namespace sat
} // namespace operations_research
// ----- MAIN -----
int main(int argc, char** argv) {
operations_research::sat::CPIsFunSat();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverSolutionCallback;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;
/** Cryptarithmetic puzzle. */
public class CpIsFunSat {
static class VarArraySolutionPrinter extends CpSolverSolutionCallback {
public VarArraySolutionPrinter(IntVar[] variables) {
variableArray = variables;
}
@Override
public void onSolutionCallback() {
for (IntVar v : variableArray) {
System.out.printf(" %s = %d", v.getName(), value(v));
}
System.out.println();
solutionCount++;
}
public int getSolutionCount() {
return solutionCount;
}
private int solutionCount;
private final IntVar[] variableArray;
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Create the model.
CpModel model = new CpModel();
int base = 10;
IntVar c = model.newIntVar(1, base - 1, "C");
IntVar p = model.newIntVar(0, base - 1, "P");
IntVar i = model.newIntVar(1, base - 1, "I");
IntVar s = model.newIntVar(0, base - 1, "S");
IntVar f = model.newIntVar(1, base - 1, "F");
IntVar u = model.newIntVar(0, base - 1, "U");
IntVar n = model.newIntVar(0, base - 1, "N");
IntVar t = model.newIntVar(1, base - 1, "T");
IntVar r = model.newIntVar(0, base - 1, "R");
IntVar e = model.newIntVar(0, base - 1, "E");
// We need to group variables in a list to use the constraint AllDifferent.
IntVar[] letters = new IntVar[] {c, p, i, s, f, u, n, t, r, e};
// Define constraints.
model.addAllDifferent(letters);
// CP + IS + FUN = TRUE
model.addEquality(LinearExpr.scalProd(new IntVar[] {c, p, i, s, f, u, n, t, r, u, e},
new long[] {base, 1, base, 1, base * base, base, 1, -base * base * base,
-base * base, -base, -1}),
0);
// Create a solver and solve the model.
CpSolver solver = new CpSolver();
VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters);
solver.searchAllSolutions(model, cb);
System.out.println("Statistics");
System.out.println(" - conflicts : " + solver.numConflicts());
System.out.println(" - branches : " + solver.numBranches());
System.out.println(" - wall time : " + solver.wallTime() + " s");
System.out.println(" - solutions : " + cb.getSolutionCount());
}
}
C#
using System;
using Google.OrTools.Sat;
public class VarArraySolutionPrinter : CpSolverSolutionCallback
{
public VarArraySolutionPrinter(IntVar[] variables)
{
variables_ = variables;
}
public override void OnSolutionCallback()
{
{
foreach (IntVar v in variables_)
{
Console.Write(String.Format(" {0}={1}", v.ShortString(), Value(v)));
}
Console.WriteLine();
solution_count_++;
}
}
public int SolutionCount()
{
return solution_count_;
}
private int solution_count_;
private IntVar[] variables_;
}
public class CpIsFunSat
{
// Solve the CP+IS+FUN==TRUE cryptarithm.
static void Main()
{
// Constraint programming engine
CpModel model = new CpModel();
int kBase = 10;
IntVar c = model.NewIntVar(1, kBase - 1, "C");
IntVar p = model.NewIntVar(0, kBase - 1, "P");
IntVar i = model.NewIntVar(1, kBase - 1, "I");
IntVar s = model.NewIntVar(0, kBase - 1, "S");
IntVar f = model.NewIntVar(1, kBase - 1, "F");
IntVar u = model.NewIntVar(0, kBase - 1, "U");
IntVar n = model.NewIntVar(0, kBase - 1, "N");
IntVar t = model.NewIntVar(1, kBase - 1, "T");
IntVar r = model.NewIntVar(0, kBase - 1, "R");
IntVar e = model.NewIntVar(0, kBase - 1, "E");
// We need to group variables in a list to use the constraint AllDifferent.
IntVar[] letters = new IntVar[] { c, p, i, s, f, u, n, t, r, e };
// Define constraints.
model.AddAllDifferent(letters);
// CP + IS + FUN = TRUE
model.Add(c * kBase + p + i * kBase + s + f * kBase * kBase + u * kBase + n ==
t * kBase * kBase * kBase + r * kBase * kBase + u * kBase + e);
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters);
solver.SearchAllSolutions(model, cb);
Console.WriteLine("Statistics");
Console.WriteLine($" - conflicts : {solver.NumConflicts()}");
Console.WriteLine($" - branches : {solver.NumBranches()}");
Console.WriteLine($" - wall time : {solver.WallTime()} s");
Console.WriteLine($" - number of solutions found: {cb.SolutionCount()}");
}
}
Original CP
Next, we'll present the solution using the original CP solver.
In this case we'll treat the base as a variable, so you can solve the equation for higher bases. (There can be no lower base solutions for CP + IS + FUN = TRUE since the ten letters must all be different.)
Defining the variables
The first step is to create
an IntVar for each letter. We distinguish between the
letters that can potentially be zero and those that can't (C, I, F,
and T).
Next, we create an array containing a new IntVar for
each letter. This is only necessary because when we define our
constraints, we're going to use AllDifferent, so we need
some array for which every element needs to differ.
Finally, we verify that our base is at least as large as the number of letters; otherwise, there's no solution.
# Decision variables. digits = list(range(0, kBase)) digits_without_zero = list(range(1, kBase)) c = solver.IntVar(digits_without_zero, 'C'); p = solver.IntVar(digits, 'P'); i = solver.IntVar(digits_without_zero, 'I'); s = solver.IntVar(digits, 'S'); f = solver.IntVar(digits_without_zero, 'F'); u = solver.IntVar(digits, 'U'); n = solver.IntVar(digits, 'N'); t = solver.IntVar(digits_without_zero, 'T'); r = solver.IntVar(digits, 'R'); e = solver.IntVar(digits, 'E'); # We need to group variables in a list to use the constraint AllDifferent. letters = [c, p, i, s, f, u, n, t, r, e] # Verify that we have enough digits. assert kBase >= len(letters)
// Define decision variables. IntVar* const c = solver.MakeIntVar(1, kBase - 1, "C"); IntVar* const p = solver.MakeIntVar(0, kBase - 1, "P"); IntVar* const i = solver.MakeIntVar(1, kBase - 1, "I"); IntVar* const s = solver.MakeIntVar(0, kBase - 1, "S"); IntVar* const f = solver.MakeIntVar(1, kBase - 1, "F"); IntVar* const u = solver.MakeIntVar(0, kBase - 1, "U"); IntVar* const n = solver.MakeIntVar(0, kBase - 1, "N"); IntVar* const t = solver.MakeIntVar(1, kBase - 1, "T"); IntVar* const r = solver.MakeIntVar(0, kBase - 1, "R"); IntVar* const e = solver.MakeIntVar(0, kBase - 1, "E"); // We need to group variables in a vector to be able to use // the global constraint AllDifferent std::vector<IntVar*> letters; letters.push_back(c); letters.push_back(p); letters.push_back(i); letters.push_back(s); letters.push_back(f); letters.push_back(u); letters.push_back(n); letters.push_back(t); letters.push_back(r); letters.push_back(e); // Check if we have enough digits CHECK_GE(kBase, letters.size());
// Decision variables.
IntVar c = solver.MakeIntVar (1, kBase - 1, "C");
IntVar p = solver.MakeIntVar (0, kBase - 1, "P");
IntVar i = solver.MakeIntVar (1, kBase - 1, "I");
IntVar s = solver.MakeIntVar (0, kBase - 1, "S");
IntVar f = solver.MakeIntVar (1, kBase - 1, "F");
IntVar u = solver.MakeIntVar (0, kBase - 1, "U");
IntVar n = solver.MakeIntVar (0, kBase - 1, "N");
IntVar t = solver.MakeIntVar (1, kBase - 1, "T");
IntVar r = solver.MakeIntVar (0, kBase - 1, "R");
IntVar e = solver.MakeIntVar (0, kBase - 1, "E");
// Group variables in a vector so that we can use AllDifferent.
IntVar[] letters = new IntVar[] { c, p, i, s, f, u, n, t, r, e};
// Verify that we have enough digits.
if (kBase < letters.Length) {
throw new Exception("kBase < letters.Length");
}
Defining the constraints
Now that we've defined our variables, the next step is to define
constraints. First, we add the AllDifferent constraint,
forcing each letter to have a different digit.
Next, we add the CP + IS + FUN = TRUE constraint. The sample programs do this in different ways.
# Define constraints.
solver.Add(solver.AllDifferent(letters))
# CP + IS + FUN = TRUE
solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t)
// Define constraints.
solver.AddConstraint(solver.MakeAllDifferent(letters));
// CP + IS + FUN = TRUE
IntVar* const term1 = MakeBaseLine2(&solver, c, p, kBase);
IntVar* const term2 = MakeBaseLine2(&solver, i, s, kBase);
IntVar* const term3 = MakeBaseLine3(&solver, f, u, n, kBase);
IntVar* const sum_terms = solver.MakeSum(solver.MakeSum(term1,
term2),
term3)->Var();
IntVar* const sum = MakeBaseLine4(&solver, t, r, u, e, kBase);
solver.AddConstraint(solver.MakeEquality(sum_terms, sum));
// Define constraints.
solver.Add (letters.AllDifferent ());
// CP + IS + FUN = TRUE
solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t);
Invoking the solver
Now that we have our variables and constraints, we're ready to
solve. In Python, we call solver.Phase with our array of
letters, and call solver.NewSearch.
db = solver.Phase(letters, solver.INT_VAR_DEFAULT,
solver.INT_VALUE_DEFAULT)
solver.NewSearch(db)
while solver.NextSolution():
print(letters)
# Is CP + IS + FUN = TRUE?
assert (kBase*c.Value() + p.Value() + kBase*i.Value() + s.Value() +
kBase*kBase*f.Value() + kBase*u.Value() + n.Value() ==
kBase*kBase*kBase*t.Value() + kBase*kBase*r.Value() +
kBase*u.Value() + e.Value())
solver.EndSearch()
// Create decision builder to search for solutions.
DecisionBuilder* const db = solver.MakePhase(letters,
Solver::CHOOSE_FIRST_UNBOUND,
Solver::ASSIGN_MIN_VALUE);
solver.NewSearch(db);
while (solver.NextSolution()) {
LOG(INFO) << "C=" << c->Value() << " " << "P=" << p->Value() << " "
<< "I=" << i->Value() << " " << "S=" << s->Value() << " "
<< "F=" << f->Value() << " " << "U=" << u->Value() << " "
<< "N=" << n->Value() << " " << "T=" << t->Value() << " "
<< "R=" << r->Value() << " " << "E=" << e->Value();
// Is CP + IS + FUN = TRUE?
CHECK_EQ(p->Value() + s->Value() + n->Value() +
kBase * (c->Value() + i->Value() + u->Value()) +
kBase * kBase * f->Value(),
e->Value() +
kBase * u->Value() +
kBase * kBase * r->Value() +
kBase * kBase * kBase * t->Value());
}
solver.EndSearch();
}
// Create the decision builder to search for solutions.
DecisionBuilder db = solver.MakePhase (letters,
Solver.CHOOSE_FIRST_UNBOUND,
Solver.ASSIGN_MIN_VALUE);
solver.NewSearch (db);
while (solver.NextSolution ()) {
Console.Write ("C=" + c.Value () + " P=" + p.Value ());
Console.Write (" I=" + i.Value () + " S=" + s.Value ());
Console.Write (" F=" + f.Value () + " U=" + u.Value ());
Console.Write (" N=" + n.Value () + " T=" + t.Value ());
Console.Write (" R=" + r.Value () + " E=" + e.Value ());
Console.WriteLine ();
// Is CP + IS + FUN = TRUE?
if (p.Value () + s.Value () + n.Value() +
kBase * (c.Value () + i.Value () + u.Value()) +
kBase * kBase * f.Value () !=
e.Value () + kBase * u.Value () +
kBase * kBase * r.Value () +
kBase * kBase * kBase * t.Value ()) {
throw new Exception("CP + IS + FUN != TRUE");
}
}
solver.EndSearch ();
Because there's more than one solution to our problem, we iterate
through the solutions with a while
solver.NextSolution() loop. If we were just trying to find a
single solution, we'd use this idiom:
if (solver.NextSolution()) {
// Print solution.
} else {
// Print that no solution could be found.
}
Complete programs
# Copyright 2010-2011 Google
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""
Cryptarithmetic puzzle
First attempt to solve equation CP + IS + FUN = TRUE
where each letter represents a unique digit.
This problem has 72 different solutions in base 10.
"""
from __future__ import print_function
from ortools.constraint_solver import pywrapcp
from os import abort
def CPIsFun():
# Constraint programming engine
solver = pywrapcp.Solver('CP is fun!');
kBase = 10
# Decision variables.
digits = list(range(0, kBase))
digits_without_zero = list(range(1, kBase))
c = solver.IntVar(digits_without_zero, 'C');
p = solver.IntVar(digits, 'P');
i = solver.IntVar(digits_without_zero, 'I');
s = solver.IntVar(digits, 'S');
f = solver.IntVar(digits_without_zero, 'F');
u = solver.IntVar(digits, 'U');
n = solver.IntVar(digits, 'N');
t = solver.IntVar(digits_without_zero, 'T');
r = solver.IntVar(digits, 'R');
e = solver.IntVar(digits, 'E');
# We need to group variables in a list to use the constraint AllDifferent.
letters = [c, p, i, s, f, u, n, t, r, e]
# Verify that we have enough digits.
assert kBase >= len(letters)
# Define constraints.
solver.Add(solver.AllDifferent(letters))
# CP + IS + FUN = TRUE
solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t)
db = solver.Phase(letters, solver.INT_VAR_DEFAULT,
solver.INT_VALUE_DEFAULT)
solver.NewSearch(db)
while solver.NextSolution():
print(letters)
# Is CP + IS + FUN = TRUE?
assert (kBase*c.Value() + p.Value() + kBase*i.Value() + s.Value() +
kBase*kBase*f.Value() + kBase*u.Value() + n.Value() ==
kBase*kBase*kBase*t.Value() + kBase*kBase*r.Value() +
kBase*u.Value() + e.Value())
solver.EndSearch()
return
if __name__ == '__main__':
CPIsFun()
// Copyright 2011-2014 Google
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
//
// Cryptarithmetic puzzle
//
// First attempt to solve equation CP + IS + FUN = TRUE
// where each letter represents a unique digit.
//
// This problem has 72 different solutions in base 10.
#include <vector>
#include "base/logging.h"
#include "constraint_solver/constraint_solver.h"
namespace operations_research {
// Helper functions.
IntVar* const MakeBaseLine2(Solver* s,
IntVar* const v1,
IntVar* const v2,
const int64 base) {
return s->MakeSum(s->MakeProd(v1, base), v2)->Var();
}
IntVar* const MakeBaseLine3(Solver* s,
IntVar* const v1,
IntVar* const v2,
IntVar* const v3,
const int64 base) {
std::vector<IntVar*> tmp_vars;
std::vector<int64> coefficients;
tmp_vars.push_back(v1);
coefficients.push_back(base * base);
tmp_vars.push_back(v2);
coefficients.push_back(base);
tmp_vars.push_back(v3);
coefficients.push_back(1);
return s->MakeScalProd(tmp_vars, coefficients)->Var();
}
IntVar* const MakeBaseLine4(Solver* s,
IntVar* const v1,
IntVar* const v2,
IntVar* const v3,
IntVar* const v4,
const int64 base) {
std::vector<IntVar*> tmp_vars;
std::vector<int64> coefficients;
tmp_vars.push_back(v1);
coefficients.push_back(base * base * base);
tmp_vars.push_back(v2);
coefficients.push_back(base * base);
tmp_vars.push_back(v3);
coefficients.push_back(base);
tmp_vars.push_back(v4);
coefficients.push_back(1);
return s->MakeScalProd(tmp_vars, coefficients)->Var();
}
void CPIsFun() {
// Instantiate the solver.
Solver solver("CP is fun!");
const int64 kBase = 10;
// Define decision variables.
IntVar* const c = solver.MakeIntVar(1, kBase - 1, "C");
IntVar* const p = solver.MakeIntVar(0, kBase - 1, "P");
IntVar* const i = solver.MakeIntVar(1, kBase - 1, "I");
IntVar* const s = solver.MakeIntVar(0, kBase - 1, "S");
IntVar* const f = solver.MakeIntVar(1, kBase - 1, "F");
IntVar* const u = solver.MakeIntVar(0, kBase - 1, "U");
IntVar* const n = solver.MakeIntVar(0, kBase - 1, "N");
IntVar* const t = solver.MakeIntVar(1, kBase - 1, "T");
IntVar* const r = solver.MakeIntVar(0, kBase - 1, "R");
IntVar* const e = solver.MakeIntVar(0, kBase - 1, "E");
// We need to group variables in a vector to be able to use
// the global constraint AllDifferent
std::vector<IntVar*> letters;
letters.push_back(c);
letters.push_back(p);
letters.push_back(i);
letters.push_back(s);
letters.push_back(f);
letters.push_back(u);
letters.push_back(n);
letters.push_back(t);
letters.push_back(r);
letters.push_back(e);
// Check if we have enough digits
CHECK_GE(kBase, letters.size());
// Define constraints.
solver.AddConstraint(solver.MakeAllDifferent(letters));
// CP + IS + FUN = TRUE
IntVar* const term1 = MakeBaseLine2(&solver, c, p, kBase);
IntVar* const term2 = MakeBaseLine2(&solver, i, s, kBase);
IntVar* const term3 = MakeBaseLine3(&solver, f, u, n, kBase);
IntVar* const sum_terms = solver.MakeSum(solver.MakeSum(term1,
term2),
term3)->Var();
IntVar* const sum = MakeBaseLine4(&solver, t, r, u, e, kBase);
solver.AddConstraint(solver.MakeEquality(sum_terms, sum));
// Create decision builder to search for solutions.
DecisionBuilder* const db = solver.MakePhase(letters,
Solver::CHOOSE_FIRST_UNBOUND,
Solver::ASSIGN_MIN_VALUE);
solver.NewSearch(db);
while (solver.NextSolution()) {
LOG(INFO) << "C=" << c->Value() << " " << "P=" << p->Value() << " "
<< "I=" << i->Value() << " " << "S=" << s->Value() << " "
<< "F=" << f->Value() << " " << "U=" << u->Value() << " "
<< "N=" << n->Value() << " " << "T=" << t->Value() << " "
<< "R=" << r->Value() << " " << "E=" << e->Value();
// Is CP + IS + FUN = TRUE?
CHECK_EQ(p->Value() + s->Value() + n->Value() +
kBase * (c->Value() + i->Value() + u->Value()) +
kBase * kBase * f->Value(),
e->Value() +
kBase * u->Value() +
kBase * kBase * r->Value() +
kBase * kBase * kBase * t->Value());
}
solver.EndSearch();
}
} // namespace operations_research
// ----- MAIN -----
int main(int argc, char **argv) {
operations_research::CPIsFun();
return 0;
}
// Copyright 2011-2014 Google
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
//
// Cryptarithmetic puzzle
//
// First attempt to solve equation CP + IS + FUN = TRUE
// where each letter represents a unique digit.
//
// This problem has 72 different solutions in base 10.
using System;
using Google.OrTools.ConstraintSolver;
public class cp_is_fun1 {
private static void CPisFun () {
// Instantiate the solver.
Solver solver = new Solver ("CP is fun!");
const int kBase = 10;
// Decision variables.
IntVar c = solver.MakeIntVar (1, kBase - 1, "C");
IntVar p = solver.MakeIntVar (0, kBase - 1, "P");
IntVar i = solver.MakeIntVar (1, kBase - 1, "I");
IntVar s = solver.MakeIntVar (0, kBase - 1, "S");
IntVar f = solver.MakeIntVar (1, kBase - 1, "F");
IntVar u = solver.MakeIntVar (0, kBase - 1, "U");
IntVar n = solver.MakeIntVar (0, kBase - 1, "N");
IntVar t = solver.MakeIntVar (1, kBase - 1, "T");
IntVar r = solver.MakeIntVar (0, kBase - 1, "R");
IntVar e = solver.MakeIntVar (0, kBase - 1, "E");
// Group variables in a vector so that we can use AllDifferent.
IntVar[] letters = new IntVar[] { c, p, i, s, f, u, n, t, r, e};
// Verify that we have enough digits.
if (kBase < letters.Length) {
throw new Exception("kBase < letters.Length");
}
// Define constraints.
solver.Add (letters.AllDifferent ());
// CP + IS + FUN = TRUE
solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t);
// Create the decision builder to search for solutions.
DecisionBuilder db = solver.MakePhase (letters,
Solver.CHOOSE_FIRST_UNBOUND,
Solver.ASSIGN_MIN_VALUE);
solver.NewSearch (db);
while (solver.NextSolution ()) {
Console.Write ("C=" + c.Value () + " P=" + p.Value ());
Console.Write (" I=" + i.Value () + " S=" + s.Value ());
Console.Write (" F=" + f.Value () + " U=" + u.Value ());
Console.Write (" N=" + n.Value () + " T=" + t.Value ());
Console.Write (" R=" + r.Value () + " E=" + e.Value ());
Console.WriteLine ();
// Is CP + IS + FUN = TRUE?
if (p.Value () + s.Value () + n.Value() +
kBase * (c.Value () + i.Value () + u.Value()) +
kBase * kBase * f.Value () !=
e.Value () + kBase * u.Value () +
kBase * kBase * r.Value () +
kBase * kBase * kBase * t.Value ()) {
throw new Exception("CP + IS + FUN != TRUE");
}
}
solver.EndSearch ();
}
public static void Main (String[] args) {
CPisFun ();
}
}