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).
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 Solution
We'll show the variables, the constraints, the solver invocation, and finally the complete programs.
Import the libraries
The following code imports the required library.
Python
from ortools.sat.python import cp_model
C++
#include <cstdint> #include <vector> #include "ortools/sat/cp_model.h" #include "ortools/sat/model.h" #include "ortools/sat/sat_parameters.pb.h"
Java
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;
C#
using System; using Google.OrTools.Sat;
Declare the model
The following code declares the model for the problem.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
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);
// Search for all solutions.
solver.StringParameters = "enumerate_all_solutions:true";
// And solve.
solver.Solve(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()}");
}
}
Defining the variables
When using the CP-SAT solver, there are certain helper methods it's useful to define.
We'll use one of them, NewIntVar, to declare our (integer) digits.
We distinguish between the letters that can potentially be zero and those that can't
(C, I, F, and T).
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_t 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
AddAllDifferent helper method. Then we use the AddEquality helper
method to create constraints that enforce the CP + IS + FUN = TRUE equality.
Python
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(
c * kBase + p + i * kBase + s + f * kBase * kBase + u * kBase + n,
kBase * kBase * kBase * t + kBase * kBase * r + kBase * u + e);
Java
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
solver = cp_model.CpSolver() solution_printer = VarArraySolutionPrinter(letters) # Enumerate all solutions. solver.parameters.enumerate_all_solutions = True # Solve. status = solver.Solve(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
CpSolver solver = new CpSolver(); VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters); // Tell the solver to enumerate all solutions. solver.getParameters().setEnumerateAllSolutions(true); // And solve. solver.solve(model, cb);
C#
// Creates a solver and solves the model. CpSolver solver = new CpSolver(); VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters); // Search for all solutions. solver.StringParameters = "enumerate_all_solutions:true"; // And solve. solver.Solve(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 main():
"""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)
# Creates a solver and solves the model.
solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinter(letters)
# Enumerate all solutions.
solver.parameters.enumerate_all_solutions = True
# Solve.
status = solver.Solve(model, solution_printer)
# Statistics.
print('\nStatistics')
print(f' status : {solver.StatusName(status)}')
print(f' conflicts: {solver.NumConflicts()}')
print(f' branches : {solver.NumBranches()}')
print(f' wall time: {solver.WallTime()} s')
print(f' sol found: {solution_printer.solution_count()}')
if __name__ == '__main__':
main()
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 <cstdint>
#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_t 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(
c * kBase + p + i * kBase + s + f * kBase * kBase + u * kBase + n,
kBase * kBase * kBase * t + kBase * kBase * r + kBase * u + e);
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;
// Statistics.
LOG(INFO) << "Statistics";
LOG(INFO) << CpSolverResponseStats(response);
}
} // namespace sat
} // namespace operations_research
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 final 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);
// Tell the solver to enumerate all solutions.
solver.getParameters().setEnumerateAllSolutions(true);
// And solve.
solver.solve(model, cb);
// Statistics.
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());
}
private 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.
using System;
using Google.OrTools.Sat;
public class CpIsFunSat
{
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_;
}
// 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);
// Search for all solutions.
solver.StringParameters = "enumerate_all_solutions:true";
// And solve.
solver.Solve(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 Solution
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.)
Import the libraries
The following code imports the required library.
Python
from ortools.constraint_solver import pywrapcp
C++
#include <cstdint> #include <vector> #include "ortools/constraint_solver/constraint_solver.h"
Java
C#
using System; using Google.OrTools.ConstraintSolver;
Creating the solver
The first step is to create the Solver.
Python
solver = pywrapcp.Solver('CP is fun!')
C++
Solver solver("CP is fun!");
Java
Solver solver = new Solver("CP is fun!");
C#
Solver solver = new Solver("CP is fun!");
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.
Python
base = 10 # Decision variables. digits = list(range(0, base)) digits_without_zero = list(range(1, base)) 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 base >= len(letters)
C++
const int64_t 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());
Java
final int base = 10;
// Decision variables.
final IntVar c = solver.makeIntVar(1, base - 1, "C");
final IntVar p = solver.makeIntVar(0, base - 1, "P");
final IntVar i = solver.makeIntVar(1, base - 1, "I");
final IntVar s = solver.makeIntVar(0, base - 1, "S");
final IntVar f = solver.makeIntVar(1, base - 1, "F");
final IntVar u = solver.makeIntVar(0, base - 1, "U");
final IntVar n = solver.makeIntVar(0, base - 1, "N");
final IntVar t = solver.makeIntVar(1, base - 1, "T");
final IntVar r = solver.makeIntVar(0, base - 1, "R");
final IntVar e = solver.makeIntVar(0, base - 1, "E");
// Group variables in a vector so that we can use AllDifferent.
final IntVar[] letters = new IntVar[] {c, p, i, s, f, u, n, t, r, e};
// Verify that we have enough digits.
if (base < letters.length) {
throw new Exception("base < letters.Length");
}
C#
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");
}
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.
Python
solver.Add(solver.AllDifferent(letters))
# CP + IS + FUN = TRUE
solver.Add(p + s + n + base * (c + i + u) + base * base * f == e +
base * u + base * base * r + base * base * base * t)
C++
// 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));
Java
solver.addConstraint(solver.makeAllDifferent(letters));
// CP + IS + FUN = TRUE
final IntVar sum1 =
solver.makeSum(new IntVar[] {
p, s, n,
solver.makeProd(solver.makeSum(new IntVar[]{c, i, u}).var(), base).var(),
solver.makeProd(f, base * base).var()}).var();
final IntVar sum2 =
solver.makeSum(new IntVar[] {
e,
solver.makeProd(u, base).var(),
solver.makeProd(r, base * base).var(),
solver.makeProd(t, base * base * base).var()}).var();
solver.addConstraint(solver.makeEquality(sum1, sum2));
C#
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.
The code for the solution printer, which displays each solution as the solver finds it, is shown below.
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.
}
Python
solution_count = 0
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 (base * c.Value() + p.Value() + base * i.Value() + s.Value() +
base * base * f.Value() + base * u.Value() +
n.Value() == base * base * base * t.Value() +
base * base * r.Value() + base * u.Value() + e.Value())
solution_count += 1
solver.EndSearch()
print(f'Number of solutions found: {solution_count}')
C++
int num_solutions = 0;
// 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());
num_solutions++;
}
solver.EndSearch();
LOG(INFO) << "Number of solutions found: " << num_solutions;
Java
int countSolution = 0;
// Create the decision builder to search for solutions.
final DecisionBuilder db =
solver.makePhase(letters, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
solver.newSearch(db);
while (solver.nextSolution()) {
System.out.println("C=" + c.value() + " P=" + p.value());
System.out.println(" I=" + i.value() + " S=" + s.value());
System.out.println(" F=" + f.value() + " U=" + u.value());
System.out.println(" N=" + n.value() + " T=" + t.value());
System.out.println(" R=" + r.value() + " E=" + e.value());
// Is CP + IS + FUN = TRUE?
if (p.value() + s.value() + n.value() + base * (c.value() + i.value() + u.value())
+ base * base * f.value()
!= e.value() + base * u.value() + base * base * r.value()
+ base * base * base * t.value()) {
throw new Exception("CP + IS + FUN != TRUE");
}
countSolution++;
}
solver.endSearch();
System.out.println("Number of solutions found: " + countSolution);
C#
int SolutionCount = 0;
// 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");
}
SolutionCount++;
}
solver.EndSearch();
Console.WriteLine($"Number of solutions found: {SolutionCount}");
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.constraint_solver import pywrapcp
def main():
# Constraint programming engine
solver = pywrapcp.Solver('CP is fun!')
base = 10
# Decision variables.
digits = list(range(0, base))
digits_without_zero = list(range(1, base))
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 base >= len(letters)
# Define constraints.
solver.Add(solver.AllDifferent(letters))
# CP + IS + FUN = TRUE
solver.Add(p + s + n + base * (c + i + u) + base * base * f == e +
base * u + base * base * r + base * base * base * t)
solution_count = 0
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 (base * c.Value() + p.Value() + base * i.Value() + s.Value() +
base * base * f.Value() + base * u.Value() +
n.Value() == base * base * base * t.Value() +
base * base * r.Value() + base * u.Value() + e.Value())
solution_count += 1
solver.EndSearch()
print(f'Number of solutions found: {solution_count}')
if __name__ == '__main__':
main()
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 <cstdint>
#include <vector>
#include "ortools/constraint_solver/constraint_solver.h"
namespace operations_research {
// Helper functions.
IntVar* const MakeBaseLine2(Solver* s, IntVar* const v1, IntVar* const v2,
const int64_t 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_t base) {
std::vector<IntVar*> tmp_vars;
std::vector<int64_t> 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_t base) {
std::vector<IntVar*> tmp_vars;
std::vector<int64_t> 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 CPIsFunCp() {
// Instantiate the solver.
Solver solver("CP is fun!");
const int64_t 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));
int num_solutions = 0;
// 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());
num_solutions++;
}
solver.EndSearch();
LOG(INFO) << "Number of solutions found: " << num_solutions;
}
} // namespace operations_research
int main(int argc, char** argv) {
operations_research::CPIsFunCp();
return EXIT_SUCCESS;
}
Java
// 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.
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
/** Cryptarithmetic puzzle. */
public final class CpIsFunCp {
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate the solver.
Solver solver = new Solver("CP is fun!");
final int base = 10;
// Decision variables.
final IntVar c = solver.makeIntVar(1, base - 1, "C");
final IntVar p = solver.makeIntVar(0, base - 1, "P");
final IntVar i = solver.makeIntVar(1, base - 1, "I");
final IntVar s = solver.makeIntVar(0, base - 1, "S");
final IntVar f = solver.makeIntVar(1, base - 1, "F");
final IntVar u = solver.makeIntVar(0, base - 1, "U");
final IntVar n = solver.makeIntVar(0, base - 1, "N");
final IntVar t = solver.makeIntVar(1, base - 1, "T");
final IntVar r = solver.makeIntVar(0, base - 1, "R");
final IntVar e = solver.makeIntVar(0, base - 1, "E");
// Group variables in a vector so that we can use AllDifferent.
final IntVar[] letters = new IntVar[] {c, p, i, s, f, u, n, t, r, e};
// Verify that we have enough digits.
if (base < letters.length) {
throw new Exception("base < letters.Length");
}
// Define constraints.
solver.addConstraint(solver.makeAllDifferent(letters));
// CP + IS + FUN = TRUE
final IntVar sum1 =
solver.makeSum(new IntVar[] {
p, s, n,
solver.makeProd(solver.makeSum(new IntVar[]{c, i, u}).var(), base).var(),
solver.makeProd(f, base * base).var()}).var();
final IntVar sum2 =
solver.makeSum(new IntVar[] {
e,
solver.makeProd(u, base).var(),
solver.makeProd(r, base * base).var(),
solver.makeProd(t, base * base * base).var()}).var();
solver.addConstraint(solver.makeEquality(sum1, sum2));
int countSolution = 0;
// Create the decision builder to search for solutions.
final DecisionBuilder db =
solver.makePhase(letters, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
solver.newSearch(db);
while (solver.nextSolution()) {
System.out.println("C=" + c.value() + " P=" + p.value());
System.out.println(" I=" + i.value() + " S=" + s.value());
System.out.println(" F=" + f.value() + " U=" + u.value());
System.out.println(" N=" + n.value() + " T=" + t.value());
System.out.println(" R=" + r.value() + " E=" + e.value());
// Is CP + IS + FUN = TRUE?
if (p.value() + s.value() + n.value() + base * (c.value() + i.value() + u.value())
+ base * base * f.value()
!= e.value() + base * u.value() + base * base * r.value()
+ base * base * base * t.value()) {
throw new Exception("CP + IS + FUN != TRUE");
}
countSolution++;
}
solver.endSearch();
System.out.println("Number of solutions found: " + countSolution);
}
private CpIsFunCp() {}
}
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.
using System;
using Google.OrTools.ConstraintSolver;
public class CpIsFunCp
{
public static void Main(String[] args)
{
// 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);
int SolutionCount = 0;
// 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");
}
SolutionCount++;
}
solver.EndSearch();
Console.WriteLine($"Number of solutions found: {SolutionCount}");
}
}