# Cryptarithmetic Puzzles

## Overview

A cryptarithmetic puzzle is a mathematical game 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, and we'll use that fact to demonstrate how Google's CP solver can be used to iterate through multiple 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.

The constraints are as follows:

• The equation: CP + IS + FUN = TRUE.
• Each of the ten letter must be a different digit.
• C, I, F, and T can't be zero (since we don't write leading zeros in numbers).

Typical cryptarithmetic puzzles assume base 10, but in our solution we'll treat the base as a variable, just in case we want to solve our equation for higher bases. (There can be no lower base solutions for CP + IS + FUN = TRUE since the ten letters must all be different.)

## Implementing the solution

In this section, we'll walk through the implementation of this cryptarithmetic puzzle in three languages: Python, C++, and C#. With each, we'll show you the variables, the constraints, the solver invocation, and finally the entire programs.

### Defining the variables

Whatever language you choose, 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 variables
```  # Decision variables.
digits = range(0, kBase)
digits_without_zero = 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)
```
C++ variables
```  // 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());
```
C# variables
```        // 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 constraints
```  # Define constraints.

# 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)
```
C++ constraints
```  // Define constraints.

// 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);

```
C# constraints
```        // Define constraints.

// 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`.

Python solver
```  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()
```
C++ solver
```  // 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();
}
```
C# solver
```        // 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

Python program
```# Copyright 2010-2011 Google
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#
# Unless required by applicable law or agreed to in writing, software
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and

"""
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 constraint_solver import pywrapcp
from os import abort

def CPIsFun():
# Constraint programming engine
solver = pywrapcp.Solver('CP is fun!');

kBase = 10

# Decision variables.
digits = range(0, kBase)
digits_without_zero = 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.

# 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()
```
C++ program
```// Copyright 2011-2014 Google
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//
// Unless required by applicable law or agreed to in writing, software
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
//
//
// 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.

// 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);

// 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;
}
```
C# program
```// Copyright 2011-2014 Google
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//
// Unless required by applicable law or agreed to in writing, software
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
//
//
// 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;

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.

// 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 ();
}
}
```

## Running the programs

In this section, you'll see how to run the programs in the various languages. You should have already downloaded the OR-Tools suite and be in the top level `or-tools` directory.

These instructions assume that you're on Unix and installing from source code. For other situations consult the installation instructions.

### Running the Python program

First, the setup that you'll have to do, once, to use any OR-Tools Python code:

```\$ make third_party (this takes a long time)
\$ make install_python_modules
\$ make python
```

Once that's done, you can run the Python program (let's call it `cp_is_fun.py` and place it in the `examples/python` directory):

```\$ PYTHONPATH=src python examples/python/cp_is_fun.py
[C(2), P(3), I(7), S(4), F(9), U(6), N(8), T(1), R(0), E(5)]
[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)]
...
```

### Running the C++ program

First, the setup that you'll have to do, once, to use any OR-Tools C++ code:

```\$ make third_party (this takes a long time)
```

Now, the annoying part: makefiles. Let's call our C++ program `cp_is_fun.cc`:

1. Place `cp_is_fun.cc` in the `or-tools/examples/cpp` directory.
2. Create a `Makefile.user` file in the top-level `or-tools` directory with the following rules:
```\$(OBJ_DIR)/cp_is_fun.\$O:\$(EX_DIR)/cpp/cp_is_fun.cc \$(SRC_DIR)/constraint_solver/constraint_solver.h
\$(CCC) \$(CFLAGS) -c \$(EX_DIR)\$Scpp/cp_is_fun.cc \$(OBJ_OUT)\$(OBJ_DIR)\$Scp_is_fun.\$O

\$(BIN_DIR)/cp_is_fun\$E: \$(DYNAMIC_CP_DEPS) \$(OBJ_DIR)/cp_is_fun.\$O
\$(CCC) \$(CFLAGS) \$(OBJ_DIR)/cp_is_fun.\$O \$(DYNAMIC_CP_LNK) \$(DYNAMIC_LD_FLAGS) \$(EXE_OUT)\$(BIN_DIR)\$Scp_is_fun\$E
```

Once you've completed the above steps, you can compile and run your program as follows:

```\$ make bin/cp_is_fun
\$ bin/cp_is_fun
[11:37:23] examples/cpp/cp_is_fun.cc:131: C=2 P=3 I=7 S=4 F=9 U=6 N=8 T=1 R=0 E=5
[11:37:23] examples/cpp/cp_is_fun.cc:131: C=2 P=3 I=7 S=5 F=9 U=4 N=8 T=1 R=0 E=6
[11:37:23] examples/cpp/cp_is_fun.cc:131: C=2 P=3 I=7 S=5 F=9 U=8 N=6 T=1 R=0 E=4
...
```

### Running the C# program

First, the setup that you'll have to do, once, to use any OR-Tools C# code:

```\$ make third_party (this takes a long time)
```

On Unix, you'll have to install mono if you haven't already. (On Ubuntu, `sudo apt-get install mono-devel`.)

After placing `cp_is_fun.cs` in the `examples/csharp` directory, create a `Makefile.user` file in the top-level `or-tools` directory with the following rule:

```\$(BIN_DIR)/cp_is_fun.exe: \$(BIN_DIR)/Google.OrTools.dll \$(EX_DIR)/csharp/cp_is_fun.cs
\$(CSC) \$(SIGNING_FLAGS) /target:exe /out:\$(BIN_DIR)\$Scp_is_fun.exe /platform:\$(NETPLATFORM) /lib:\$(BIN_DIR) /r:Google.OrTools.dll \$(EX_DIR)\$Scsharp\$Scp_is_fun.cs
```

Now you can compile and run `cp_is_fun.cs` as follows:

```\$ make bin/cp_is_fun.exe
\$ LD_LIBRARY_PATH=./lib mono bin/cp_is_fun.exe
C=2 P=3 I=7 S=4 F=9 U=6 N=8 T=1 R=0 E=5
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
...
```