Cryptarithmetic Puzzles

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 <stdlib.h>

#include <cstdint>

#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/sorted_interval_list.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.weightedSum(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(f"{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.ToString(), 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(f"{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 <stdlib.h>

#include <cstdint>

#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/sorted_interval_list.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.weightedSum(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.ToString(), 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 "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#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{c, p, i, s, f, u, n, t, r, 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 "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/constraint_solver/constraint_solver.h"

namespace operations_research {

// Helper functions.
IntVar* MakeBaseLine2(Solver* s, IntVar* const v1, IntVar* const v2,
                      const int64_t base) {
  return s->MakeSum(s->MakeProd(v1, base), v2)->Var();
}

IntVar* 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* 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{c, p, i, s, f, u, n, t, r, 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) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  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}");
    }
}