Cryptarithmetic Puzzles

Overview

A cryptarithmetic puzzle is a mathematical exercise where the digits of some numbers are represented by letters (or symbols). Each letter represents a unique digit. The goal is to find the digits such that a given mathematical equation is verified:

      CP
+     IS
+    FUN
--------
=   TRUE

One assignment of letters to digits yields the following equation:

      23
+     74
+    968
--------
=   1065

There are other answers to this problem. We'll show how to find all solutions.

Modeling the problem

As with any optimization problem, we'll start by identifying variables and constraints. The variables are the letters, which can take on any single digit value.

For CP + IS + FUN = TRUE, the constraints are as follows:

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

Implementing the solution

You can solve cryptarithmetic problems with either the new CP-SAT solver, which is more efficient, or the original CP solver. We'll show you examples using both solvers, starting with CP-SAT.

CP-SAT

We'll show the variables, the constraints, the solver invocation, and finally the complete programs.

Defining the variables

When using the CP-SAT solver, there are certain helper methods it's useful to define. We'll use two of them, new_variable and new_boolean_variable, to declare our (integer) digits and our (boolean) carry bits:

Python

    base = 10

    c = model.NewIntVar(1, base - 1, 'C')
    p = model.NewIntVar(0, base - 1, 'P')
    i = model.NewIntVar(1, base - 1, 'I')
    s = model.NewIntVar(0, base - 1, 'S')
    f = model.NewIntVar(1, base - 1, 'F')
    u = model.NewIntVar(0, base - 1, 'U')
    n = model.NewIntVar(0, base - 1, 'N')
    t = model.NewIntVar(1, base - 1, 'T')
    r = model.NewIntVar(0, base - 1, 'R')
    e = model.NewIntVar(0, base - 1, 'E')

    # We need to group variables in a list to use the constraint AllDifferent.
    letters = [c, p, i, s, f, u, n, t, r, e]

    # Verify that we have enough digits.
    assert base >= len(letters)

C++

  const int64 kBase = 10;

  // Define decision variables.
  Domain digit(0, kBase - 1);
  Domain non_zero_digit(1, kBase - 1);

  IntVar c = cp_model.NewIntVar(non_zero_digit).WithName("C");
  IntVar p = cp_model.NewIntVar(digit).WithName("P");
  IntVar i = cp_model.NewIntVar(non_zero_digit).WithName("I");
  IntVar s = cp_model.NewIntVar(digit).WithName("S");
  IntVar f = cp_model.NewIntVar(non_zero_digit).WithName("F");
  IntVar u = cp_model.NewIntVar(digit).WithName("U");
  IntVar n = cp_model.NewIntVar(digit).WithName("N");
  IntVar t = cp_model.NewIntVar(non_zero_digit).WithName("T");
  IntVar r = cp_model.NewIntVar(digit).WithName("R");
  IntVar e = cp_model.NewIntVar(digit).WithName("E");

Java

    int base = 10;
    IntVar c = model.newIntVar(1, base - 1, "C");
    IntVar p = model.newIntVar(0, base - 1, "P");
    IntVar i = model.newIntVar(1, base - 1, "I");
    IntVar s = model.newIntVar(0, base - 1, "S");
    IntVar f = model.newIntVar(1, base - 1, "F");
    IntVar u = model.newIntVar(0, base - 1, "U");
    IntVar n = model.newIntVar(0, base - 1, "N");
    IntVar t = model.newIntVar(1, base - 1, "T");
    IntVar r = model.newIntVar(0, base - 1, "R");
    IntVar e = model.newIntVar(0, base - 1, "E");

    // We need to group variables in a list to use the constraint AllDifferent.
    IntVar[] letters = new IntVar[] {c, p, i, s, f, u, n, t, r, e};

C#

    int kBase = 10;

    IntVar c = model.NewIntVar(1, kBase - 1, "C");
    IntVar p = model.NewIntVar(0, kBase - 1, "P");
    IntVar i = model.NewIntVar(1, kBase - 1, "I");
    IntVar s = model.NewIntVar(0, kBase - 1, "S");
    IntVar f = model.NewIntVar(1, kBase - 1, "F");
    IntVar u = model.NewIntVar(0, kBase - 1, "U");
    IntVar n = model.NewIntVar(0, kBase - 1, "N");
    IntVar t = model.NewIntVar(1, kBase - 1, "T");
    IntVar r = model.NewIntVar(0, kBase - 1, "R");
    IntVar e = model.NewIntVar(0, kBase - 1, "E");

    // We need to group variables in a list to use the constraint AllDifferent.
    IntVar[] letters = new IntVar[] {c, p, i, s, f, u, n, t, r, e};

Defining the constraints

Next, constraints. First, we ensure that all letters have different values, using the add_all_different helper method. Then we use the add_linear_constraint helper method to create constraints that enforce the add-and-carry operations.

Python

    # Define constraints.
    model.AddAllDifferent(letters)

    # CP + IS + FUN = TRUE
    model.Add(c * base + p + i * base + s + f * base * base + u * base + n ==
              t * base * base * base + r * base * base + u * base + e)

C++

  // Define constraints.
  cp_model.AddAllDifferent({c, p, i, s, f, u, n, t, r, e});

  // CP + IS + FUN = TRUE
  cp_model.AddEquality(
      LinearExpr::ScalProd({c, p, i, s, f, u, n},
                           {kBase, 1, kBase, 1, kBase * kBase, kBase, 1}),
      LinearExpr::ScalProd({t, r, u, e},
                           {kBase * kBase * kBase, kBase * kBase, kBase, 1}));

Java

    // Define constraints.
    model.addAllDifferent(letters);

    // CP + IS + FUN = TRUE
    model.addEquality(LinearExpr.scalProd(new IntVar[] {c, p, i, s, f, u, n, t, r, u, e},
                          new long[] {base, 1, base, 1, base * base, base, 1, -base * base * base,
                              -base * base, -base, -1}),
        0);

C#

    // Define constraints.
    model.AddAllDifferent(letters);

    // CP + IS + FUN = TRUE
    model.Add(c * kBase + p + i * kBase + s + f * kBase * kBase + u * kBase + n ==
              t * kBase * kBase * kBase + r * kBase * kBase + u * kBase + e);

Solution printer

The code for the solution printer, which displays each solution as the solver finds it, is shown below.

Python

class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0

    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            print('%s=%i' % (v, self.Value(v)), end=' ')
        print()

    def solution_count(self):
        return self.__solution_count 

C++

  Model model;
  int num_solutions = 0;
  model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) {
    LOG(INFO) << "Solution " << num_solutions;
    LOG(INFO) << "C=" << SolutionIntegerValue(response, c) << " "
              << "P=" << SolutionIntegerValue(response, p) << " "
              << "I=" << SolutionIntegerValue(response, i) << " "
              << "S=" << SolutionIntegerValue(response, s) << " "
              << "F=" << SolutionIntegerValue(response, f) << " "
              << "U=" << SolutionIntegerValue(response, u) << " "
              << "N=" << SolutionIntegerValue(response, n) << " "
              << "T=" << SolutionIntegerValue(response, t) << " "
              << "R=" << SolutionIntegerValue(response, r) << " "
              << "E=" << SolutionIntegerValue(response, e);
    num_solutions++;
  }));

Java

  static class VarArraySolutionPrinter extends CpSolverSolutionCallback {
    public VarArraySolutionPrinter(IntVar[] variables) {
      variableArray = variables;
    }

    @Override
    public void onSolutionCallback() {
      for (IntVar v : variableArray) {
        System.out.printf("  %s = %d", v.getName(), value(v));
      }
      System.out.println();
      solutionCount++;
    }

    public int getSolutionCount() {
      return solutionCount;
    }

    private int solutionCount;
    private final IntVar[] variableArray;
  }

C#

public class VarArraySolutionPrinter : CpSolverSolutionCallback
{
  public VarArraySolutionPrinter(IntVar[] variables)
  {
    variables_ = variables;
  }

  public override void OnSolutionCallback()
  {
    {
      foreach (IntVar v in variables_)
      {
        Console.Write(
            String.Format("  {0}={1}", v.ShortString(), Value(v)));
      }
      Console.WriteLine();
      solution_count_++;
    }
  }

  public int SolutionCount()
  {
    return solution_count_;
  }

  private int solution_count_;
  private IntVar[] variables_;
}

Invoking the solver

Finally we solve the problem and display the solution. All the magic is in the operations_research::sat::SolveCpModel() method.

Python

    ### Solve model.
    solver = cp_model.CpSolver()
    solution_printer = VarArraySolutionPrinter(letters)
    status = solver.SearchForAllSolutions(model, solution_printer)

C++

  // Tell the solver to enumerate all solutions.
  SatParameters parameters;
  parameters.set_enumerate_all_solutions(true);
  model.Add(NewSatParameters(parameters));

  const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
  LOG(INFO) << "Number of solutions found: " << num_solutions;

Java

    // Create a solver and solve the model.
    CpSolver solver = new CpSolver();
    VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters);
    solver.searchAllSolutions(model, cb);

C#

    // Creates a solver and solves the model.
    CpSolver solver = new CpSolver();
    VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters);
    solver.SearchAllSolutions(model, cb);

When you run the program, it diplays the following output, in which each row is a solution:

C=2 P=3 I=7 S=4 F=9 U=6 N=8 T=1 R=0 E=5
C=2 P=4 I=7 S=3 F=9 U=6 N=8 T=1 R=0 E=5
C=2 P=5 I=7 S=3 F=9 U=4 N=8 T=1 R=0 E=6
C=2 P=8 I=7 S=3 F=9 U=4 N=5 T=1 R=0 E=6
C=2 P=8 I=7 S=3 F=9 U=6 N=4 T=1 R=0 E=5
C=3 P=7 I=6 S=2 F=9 U=8 N=5 T=1 R=0 E=4
C=6 P=7 I=3 S=2 F=9 U=8 N=5 T=1 R=0 E=4
C=6 P=5 I=3 S=2 F=9 U=8 N=7 T=1 R=0 E=4
C=3 P=5 I=6 S=2 F=9 U=8 N=7 T=1 R=0 E=4
C=3 P=8 I=6 S=4 F=9 U=2 N=5 T=1 R=0 E=7
C=3 P=7 I=6 S=5 F=9 U=8 N=2 T=1 R=0 E=4
C=3 P=8 I=6 S=5 F=9 U=2 N=4 T=1 R=0 E=7
C=3 P=5 I=6 S=4 F=9 U=2 N=8 T=1 R=0 E=7
C=3 P=4 I=6 S=5 F=9 U=2 N=8 T=1 R=0 E=7
C=3 P=2 I=6 S=5 F=9 U=8 N=7 T=1 R=0 E=4
C=3 P=4 I=6 S=8 F=9 U=2 N=5 T=1 R=0 E=7
C=3 P=2 I=6 S=7 F=9 U=8 N=5 T=1 R=0 E=4
C=3 P=5 I=6 S=8 F=9 U=2 N=4 T=1 R=0 E=7
C=3 P=5 I=6 S=7 F=9 U=8 N=2 T=1 R=0 E=4
C=2 P=5 I=7 S=6 F=9 U=8 N=3 T=1 R=0 E=4
C=2 P=5 I=7 S=8 F=9 U=4 N=3 T=1 R=0 E=6
C=2 P=6 I=7 S=5 F=9 U=8 N=3 T=1 R=0 E=4
C=2 P=4 I=7 S=8 F=9 U=6 N=3 T=1 R=0 E=5
C=2 P=3 I=7 S=8 F=9 U=6 N=4 T=1 R=0 E=5
C=2 P=8 I=7 S=5 F=9 U=4 N=3 T=1 R=0 E=6
C=2 P=8 I=7 S=4 F=9 U=6 N=3 T=1 R=0 E=5
C=2 P=6 I=7 S=3 F=9 U=8 N=5 T=1 R=0 E=4
C=2 P=5 I=7 S=3 F=9 U=8 N=6 T=1 R=0 E=4
C=2 P=3 I=7 S=5 F=9 U=4 N=8 T=1 R=0 E=6
C=2 P=3 I=7 S=5 F=9 U=8 N=6 T=1 R=0 E=4
C=2 P=3 I=7 S=6 F=9 U=8 N=5 T=1 R=0 E=4
C=2 P=3 I=7 S=8 F=9 U=4 N=5 T=1 R=0 E=6
C=4 P=3 I=5 S=8 F=9 U=2 N=6 T=1 R=0 E=7
C=5 P=3 I=4 S=8 F=9 U=2 N=6 T=1 R=0 E=7
C=6 P=2 I=3 S=7 F=9 U=8 N=5 T=1 R=0 E=4
C=7 P=3 I=2 S=6 F=9 U=8 N=5 T=1 R=0 E=4
C=7 P=3 I=2 S=8 F=9 U=4 N=5 T=1 R=0 E=6
C=6 P=4 I=3 S=8 F=9 U=2 N=5 T=1 R=0 E=7
C=5 P=3 I=4 S=6 F=9 U=2 N=8 T=1 R=0 E=7
C=4 P=3 I=5 S=6 F=9 U=2 N=8 T=1 R=0 E=7
C=5 P=6 I=4 S=3 F=9 U=2 N=8 T=1 R=0 E=7
C=7 P=4 I=2 S=3 F=9 U=6 N=8 T=1 R=0 E=5
C=7 P=3 I=2 S=4 F=9 U=6 N=8 T=1 R=0 E=5
C=6 P=2 I=3 S=5 F=9 U=8 N=7 T=1 R=0 E=4
C=7 P=3 I=2 S=5 F=9 U=4 N=8 T=1 R=0 E=6
C=6 P=4 I=3 S=5 F=9 U=2 N=8 T=1 R=0 E=7
C=6 P=5 I=3 S=4 F=9 U=2 N=8 T=1 R=0 E=7
C=7 P=5 I=2 S=3 F=9 U=4 N=8 T=1 R=0 E=6
C=4 P=6 I=5 S=3 F=9 U=2 N=8 T=1 R=0 E=7
C=6 P=5 I=3 S=8 F=9 U=2 N=4 T=1 R=0 E=7
C=6 P=5 I=3 S=7 F=9 U=8 N=2 T=1 R=0 E=4
C=7 P=5 I=2 S=8 F=9 U=4 N=3 T=1 R=0 E=6
C=7 P=5 I=2 S=6 F=9 U=8 N=3 T=1 R=0 E=4
C=5 P=8 I=4 S=6 F=9 U=2 N=3 T=1 R=0 E=7
C=4 P=8 I=5 S=6 F=9 U=2 N=3 T=1 R=0 E=7
C=4 P=8 I=5 S=3 F=9 U=2 N=6 T=1 R=0 E=7
C=5 P=8 I=4 S=3 F=9 U=2 N=6 T=1 R=0 E=7
C=7 P=8 I=2 S=3 F=9 U=4 N=5 T=1 R=0 E=6
C=7 P=8 I=2 S=3 F=9 U=6 N=4 T=1 R=0 E=5
C=7 P=8 I=2 S=4 F=9 U=6 N=3 T=1 R=0 E=5
C=7 P=8 I=2 S=5 F=9 U=4 N=3 T=1 R=0 E=6
C=6 P=8 I=3 S=5 F=9 U=2 N=4 T=1 R=0 E=7
C=6 P=8 I=3 S=4 F=9 U=2 N=5 T=1 R=0 E=7
C=6 P=7 I=3 S=5 F=9 U=8 N=2 T=1 R=0 E=4
C=7 P=6 I=2 S=5 F=9 U=8 N=3 T=1 R=0 E=4
C=7 P=3 I=2 S=5 F=9 U=8 N=6 T=1 R=0 E=4
C=7 P=4 I=2 S=8 F=9 U=6 N=3 T=1 R=0 E=5
C=7 P=3 I=2 S=8 F=9 U=6 N=4 T=1 R=0 E=5
C=5 P=6 I=4 S=8 F=9 U=2 N=3 T=1 R=0 E=7
C=4 P=6 I=5 S=8 F=9 U=2 N=3 T=1 R=0 E=7
C=7 P=6 I=2 S=3 F=9 U=8 N=5 T=1 R=0 E=4
C=7 P=5 I=2 S=3 F=9 U=8 N=6 T=1 R=0 E=4

Statistics
  - status          : OPTIMAL
  - conflicts       : 110
  - branches        : 435
  - wall time       : 0.014934 ms
  - solutions found : 72

Complete programs

Here are the complete programs.

Python

"""Cryptarithmetic puzzle.

First attempt to solve equation CP + IS + FUN = TRUE
where each letter represents a unique digit.

This problem has 72 different solutions in base 10.
"""

from __future__ import print_function

from ortools.sat.python import cp_model


class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0

    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            print('%s=%i' % (v, self.Value(v)), end=' ')
        print()

    def solution_count(self):
        return self.__solution_count


def CPIsFunSat():
    """Solve the CP+IS+FUN==TRUE cryptarithm."""
    # Constraint programming engine
    model = cp_model.CpModel()

    base = 10

    c = model.NewIntVar(1, base - 1, 'C')
    p = model.NewIntVar(0, base - 1, 'P')
    i = model.NewIntVar(1, base - 1, 'I')
    s = model.NewIntVar(0, base - 1, 'S')
    f = model.NewIntVar(1, base - 1, 'F')
    u = model.NewIntVar(0, base - 1, 'U')
    n = model.NewIntVar(0, base - 1, 'N')
    t = model.NewIntVar(1, base - 1, 'T')
    r = model.NewIntVar(0, base - 1, 'R')
    e = model.NewIntVar(0, base - 1, 'E')

    # We need to group variables in a list to use the constraint AllDifferent.
    letters = [c, p, i, s, f, u, n, t, r, e]

    # Verify that we have enough digits.
    assert base >= len(letters)

    # Define constraints.
    model.AddAllDifferent(letters)

    # CP + IS + FUN = TRUE
    model.Add(c * base + p + i * base + s + f * base * base + u * base + n ==
              t * base * base * base + r * base * base + u * base + e)

    ### Solve model.
    solver = cp_model.CpSolver()
    solution_printer = VarArraySolutionPrinter(letters)
    status = solver.SearchForAllSolutions(model, solution_printer)

    print()
    print('Statistics')
    print('  - status          : %s' % solver.StatusName(status))
    print('  - conflicts       : %i' % solver.NumConflicts())
    print('  - branches        : %i' % solver.NumBranches())
    print('  - wall time       : %f s' % solver.WallTime())
    print('  - solutions found : %i' % solution_printer.solution_count())


if __name__ == '__main__':
    CPIsFunSat()

C++

// Cryptarithmetic puzzle
//
// First attempt to solve equation CP + IS + FUN = TRUE
// where each letter represents a unique digit.
//
// This problem has 72 different solutions in base 10.

#include <vector>

#include "ortools/sat/cp_model.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"

namespace operations_research {
namespace sat {

void CPIsFunSat() {
  // Instantiate the solver.
  CpModelBuilder cp_model;

  const int64 kBase = 10;

  // Define decision variables.
  Domain digit(0, kBase - 1);
  Domain non_zero_digit(1, kBase - 1);

  IntVar c = cp_model.NewIntVar(non_zero_digit).WithName("C");
  IntVar p = cp_model.NewIntVar(digit).WithName("P");
  IntVar i = cp_model.NewIntVar(non_zero_digit).WithName("I");
  IntVar s = cp_model.NewIntVar(digit).WithName("S");
  IntVar f = cp_model.NewIntVar(non_zero_digit).WithName("F");
  IntVar u = cp_model.NewIntVar(digit).WithName("U");
  IntVar n = cp_model.NewIntVar(digit).WithName("N");
  IntVar t = cp_model.NewIntVar(non_zero_digit).WithName("T");
  IntVar r = cp_model.NewIntVar(digit).WithName("R");
  IntVar e = cp_model.NewIntVar(digit).WithName("E");

  // Define constraints.
  cp_model.AddAllDifferent({c, p, i, s, f, u, n, t, r, e});

  // CP + IS + FUN = TRUE
  cp_model.AddEquality(
      LinearExpr::ScalProd({c, p, i, s, f, u, n},
                           {kBase, 1, kBase, 1, kBase * kBase, kBase, 1}),
      LinearExpr::ScalProd({t, r, u, e},
                           {kBase * kBase * kBase, kBase * kBase, kBase, 1}));

  Model model;
  int num_solutions = 0;
  model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) {
    LOG(INFO) << "Solution " << num_solutions;
    LOG(INFO) << "C=" << SolutionIntegerValue(response, c) << " "
              << "P=" << SolutionIntegerValue(response, p) << " "
              << "I=" << SolutionIntegerValue(response, i) << " "
              << "S=" << SolutionIntegerValue(response, s) << " "
              << "F=" << SolutionIntegerValue(response, f) << " "
              << "U=" << SolutionIntegerValue(response, u) << " "
              << "N=" << SolutionIntegerValue(response, n) << " "
              << "T=" << SolutionIntegerValue(response, t) << " "
              << "R=" << SolutionIntegerValue(response, r) << " "
              << "E=" << SolutionIntegerValue(response, e);
    num_solutions++;
  }));

  // Tell the solver to enumerate all solutions.
  SatParameters parameters;
  parameters.set_enumerate_all_solutions(true);
  model.Add(NewSatParameters(parameters));

  const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
  LOG(INFO) << "Number of solutions found: " << num_solutions;
}

}  // namespace sat
}  // namespace operations_research

// ----- MAIN -----
int main(int argc, char** argv) {
  operations_research::sat::CPIsFunSat();

  return EXIT_SUCCESS;
}

Java

import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverSolutionCallback;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;

/** Cryptarithmetic puzzle. */
public class CpIsFunSat {
  static {
    System.loadLibrary("jniortools");
  }

  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 {
    // Create the model.
    CpModel model = new CpModel();

    int base = 10;
    IntVar c = model.newIntVar(1, base - 1, "C");
    IntVar p = model.newIntVar(0, base - 1, "P");
    IntVar i = model.newIntVar(1, base - 1, "I");
    IntVar s = model.newIntVar(0, base - 1, "S");
    IntVar f = model.newIntVar(1, base - 1, "F");
    IntVar u = model.newIntVar(0, base - 1, "U");
    IntVar n = model.newIntVar(0, base - 1, "N");
    IntVar t = model.newIntVar(1, base - 1, "T");
    IntVar r = model.newIntVar(0, base - 1, "R");
    IntVar e = model.newIntVar(0, base - 1, "E");

    // We need to group variables in a list to use the constraint AllDifferent.
    IntVar[] letters = new IntVar[] {c, p, i, s, f, u, n, t, r, e};

    // Define constraints.
    model.addAllDifferent(letters);

    // CP + IS + FUN = TRUE
    model.addEquality(LinearExpr.scalProd(new IntVar[] {c, p, i, s, f, u, n, t, r, u, e},
                          new long[] {base, 1, base, 1, base * base, base, 1, -base * base * base,
                              -base * base, -base, -1}),
        0);

    // Create a solver and solve the model.
    CpSolver solver = new CpSolver();
    VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters);
    solver.searchAllSolutions(model, cb);

    System.out.println("Statistics");
    System.out.println("  - conflicts : " + solver.numConflicts());
    System.out.println("  - branches  : " + solver.numBranches());
    System.out.println("  - wall time : " + solver.wallTime() + " s");
    System.out.println("  - solutions : " + cb.getSolutionCount());
  }
}

C#

using System;
using Google.OrTools.Sat;

public class VarArraySolutionPrinter : CpSolverSolutionCallback
{
  public VarArraySolutionPrinter(IntVar[] variables)
  {
    variables_ = variables;
  }

  public override void OnSolutionCallback()
  {
    {
      foreach (IntVar v in variables_)
      {
        Console.Write(
            String.Format("  {0}={1}", v.ShortString(), Value(v)));
      }
      Console.WriteLine();
      solution_count_++;
    }
  }

  public int SolutionCount()
  {
    return solution_count_;
  }

  private int solution_count_;
  private IntVar[] variables_;
}

public class CpIsFunSat
{
  // Solve the CP+IS+FUN==TRUE cryptarithm.
  static void Main()
  {
    // Constraint programming engine
    CpModel model = new CpModel();

    int kBase = 10;

    IntVar c = model.NewIntVar(1, kBase - 1, "C");
    IntVar p = model.NewIntVar(0, kBase - 1, "P");
    IntVar i = model.NewIntVar(1, kBase - 1, "I");
    IntVar s = model.NewIntVar(0, kBase - 1, "S");
    IntVar f = model.NewIntVar(1, kBase - 1, "F");
    IntVar u = model.NewIntVar(0, kBase - 1, "U");
    IntVar n = model.NewIntVar(0, kBase - 1, "N");
    IntVar t = model.NewIntVar(1, kBase - 1, "T");
    IntVar r = model.NewIntVar(0, kBase - 1, "R");
    IntVar e = model.NewIntVar(0, kBase - 1, "E");

    // We need to group variables in a list to use the constraint AllDifferent.
    IntVar[] letters = new IntVar[] {c, p, i, s, f, u, n, t, r, e};

    // Define constraints.
    model.AddAllDifferent(letters);

    // CP + IS + FUN = TRUE
    model.Add(c * kBase + p + i * kBase + s + f * kBase * kBase + u * kBase + n ==
              t * kBase * kBase * kBase + r * kBase * kBase + u * kBase + e);

    // Creates a solver and solves the model.
    CpSolver solver = new CpSolver();
    VarArraySolutionPrinter cb = new VarArraySolutionPrinter(letters);
    solver.SearchAllSolutions(model, cb);

    Console.WriteLine("Statistics");
    Console.WriteLine($"  - conflicts : {solver.NumConflicts()}");
    Console.WriteLine($"  - branches  : {solver.NumBranches()}");
    Console.WriteLine($"  - wall time : {solver.WallTime()} s");
    Console.WriteLine($"  - number of solutions found: {cb.SolutionCount()}");
  }
}

Original CP

Next, we'll present the solution using the original CP solver.

In this case we'll treat the base as a variable, so you can solve the equation for higher bases. (There can be no lower base solutions for CP + IS + FUN = TRUE since the ten letters must all be different.)

Defining the variables

The first step is to create an IntVar for each letter. We distinguish between the letters that can potentially be zero and those that can't (C, I, F, and T).

Next, we create an array containing a new IntVar for each letter. This is only necessary because when we define our constraints, we're going to use AllDifferent, so we need some array for which every element needs to differ.

Finally, we verify that our base is at least as large as the number of letters; otherwise, there's no solution.

Python variables
  # Decision variables.
  digits = list(range(0, kBase))
  digits_without_zero = list(range(1, kBase))
  c = solver.IntVar(digits_without_zero, 'C');
  p = solver.IntVar(digits, 'P');
  i = solver.IntVar(digits_without_zero, 'I');
  s = solver.IntVar(digits, 'S');
  f = solver.IntVar(digits_without_zero, 'F');
  u = solver.IntVar(digits, 'U');
  n = solver.IntVar(digits, 'N');
  t = solver.IntVar(digits_without_zero, 'T');
  r = solver.IntVar(digits, 'R');
  e = solver.IntVar(digits, 'E');

  # We need to group variables in a list to use the constraint AllDifferent.
  letters = [c, p, i, s, f, u, n, t, r, e]

  # Verify that we have enough digits.
  assert kBase >= len(letters)
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.
  solver.Add(solver.AllDifferent(letters))

  # CP + IS + FUN = TRUE
  solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
              e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t)
C++ constraints
  // 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));
C# constraints
        // Define constraints.
        solver.Add (letters.AllDifferent ());

        // CP + IS + FUN = TRUE
        solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
               e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t);

Invoking the solver

Now that we have our variables and constraints, we're ready to solve. In Python, we call solver.Phase with our array of letters, and call solver.NewSearch.

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
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""
Cryptarithmetic puzzle

First attempt to solve equation CP + IS + FUN = TRUE
where each letter represents a unique digit.

This problem has 72 different solutions in base 10.
"""

from __future__ import print_function
from ortools.constraint_solver import pywrapcp
from os import abort

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

  kBase = 10

  # Decision variables.
  digits = list(range(0, kBase))
  digits_without_zero = list(range(1, kBase))
  c = solver.IntVar(digits_without_zero, 'C');
  p = solver.IntVar(digits, 'P');
  i = solver.IntVar(digits_without_zero, 'I');
  s = solver.IntVar(digits, 'S');
  f = solver.IntVar(digits_without_zero, 'F');
  u = solver.IntVar(digits, 'U');
  n = solver.IntVar(digits, 'N');
  t = solver.IntVar(digits_without_zero, 'T');
  r = solver.IntVar(digits, 'R');
  e = solver.IntVar(digits, 'E');

  # We need to group variables in a list to use the constraint AllDifferent.
  letters = [c, p, i, s, f, u, n, t, r, e]

  # Verify that we have enough digits.
  assert kBase >= len(letters)

  # Define constraints.
  solver.Add(solver.AllDifferent(letters))

  # CP + IS + FUN = TRUE
  solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
              e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t)

  db = solver.Phase(letters, solver.INT_VAR_DEFAULT,
                             solver.INT_VALUE_DEFAULT)
  solver.NewSearch(db)

  while solver.NextSolution():
    print(letters)
    # Is CP + IS + FUN = TRUE?
    assert (kBase*c.Value() +  p.Value() + kBase*i.Value() + s.Value() +
            kBase*kBase*f.Value() + kBase*u.Value() + n.Value() ==
            kBase*kBase*kBase*t.Value() + kBase*kBase*r.Value() +
            kBase*u.Value() + e.Value())

  solver.EndSearch()

  return


if __name__ == '__main__':
  CPIsFun()
C++ program
// Copyright 2011-2014 Google
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
//
// Cryptarithmetic puzzle
//
// First attempt to solve equation CP + IS + FUN = TRUE
// where each letter represents a unique digit.
//
// This problem has 72 different solutions in base 10.

#include <vector>

#include "base/logging.h"
#include "constraint_solver/constraint_solver.h"

namespace operations_research {

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

IntVar* const MakeBaseLine3(Solver* s,
                            IntVar* const v1,
                            IntVar* const v2,
                            IntVar* const v3,
                            const int64 base) {
  std::vector<IntVar*> tmp_vars;
  std::vector<int64> coefficients;
  tmp_vars.push_back(v1);
  coefficients.push_back(base * base);
  tmp_vars.push_back(v2);
  coefficients.push_back(base);
  tmp_vars.push_back(v3);
  coefficients.push_back(1);

  return s->MakeScalProd(tmp_vars, coefficients)->Var();
}

IntVar* const MakeBaseLine4(Solver* s,
                            IntVar* const v1,
                            IntVar* const v2,
                            IntVar* const v3,
                            IntVar* const v4,
                            const int64 base) {
  std::vector<IntVar*> tmp_vars;
  std::vector<int64> coefficients;
  tmp_vars.push_back(v1);
  coefficients.push_back(base * base * base);
  tmp_vars.push_back(v2);
  coefficients.push_back(base * base);
  tmp_vars.push_back(v3);
  coefficients.push_back(base);
  tmp_vars.push_back(v4);
  coefficients.push_back(1);

  return s->MakeScalProd(tmp_vars, coefficients)->Var();
}

void CPIsFun() {
  // Instantiate the solver.
  Solver solver("CP is fun!");

  const int64 kBase = 10;

  // Define decision variables.
  IntVar* const c = solver.MakeIntVar(1, kBase - 1, "C");
  IntVar* const p = solver.MakeIntVar(0, kBase - 1, "P");
  IntVar* const i = solver.MakeIntVar(1, kBase - 1, "I");
  IntVar* const s = solver.MakeIntVar(0, kBase - 1, "S");
  IntVar* const f = solver.MakeIntVar(1, kBase - 1, "F");
  IntVar* const u = solver.MakeIntVar(0, kBase - 1, "U");
  IntVar* const n = solver.MakeIntVar(0, kBase - 1, "N");
  IntVar* const t = solver.MakeIntVar(1, kBase - 1, "T");
  IntVar* const r = solver.MakeIntVar(0, kBase - 1, "R");
  IntVar* const e = solver.MakeIntVar(0, kBase - 1, "E");

  // We need to group variables in a vector to be able to use
  // the global constraint AllDifferent
  std::vector<IntVar*> letters;
  letters.push_back(c);
  letters.push_back(p);
  letters.push_back(i);
  letters.push_back(s);
  letters.push_back(f);
  letters.push_back(u);
  letters.push_back(n);
  letters.push_back(t);
  letters.push_back(r);
  letters.push_back(e);

  // Check if we have enough digits
  CHECK_GE(kBase, letters.size());
  // Define constraints.
  solver.AddConstraint(solver.MakeAllDifferent(letters));

  // CP + IS + FUN = TRUE
  IntVar* const term1 = MakeBaseLine2(&solver, c, p, kBase);
  IntVar* const term2 = MakeBaseLine2(&solver, i, s, kBase);
  IntVar* const term3 = MakeBaseLine3(&solver, f, u, n, kBase);
  IntVar* const sum_terms = solver.MakeSum(solver.MakeSum(term1,
                                                          term2),
                                           term3)->Var();

  IntVar* const sum   = MakeBaseLine4(&solver, t, r, u, e, kBase);

  solver.AddConstraint(solver.MakeEquality(sum_terms, sum));
  // Create decision builder to search for solutions.
  DecisionBuilder* const db = solver.MakePhase(letters,
                                               Solver::CHOOSE_FIRST_UNBOUND,
                                               Solver::ASSIGN_MIN_VALUE);
  solver.NewSearch(db);

  while (solver.NextSolution()) {
    LOG(INFO) << "C=" << c->Value() << " " << "P=" << p->Value() << " "
              << "I=" << i->Value() << " " << "S=" << s->Value() << " "
              << "F=" << f->Value() << " " << "U=" << u->Value() << " "
              << "N=" << n->Value() << " " << "T=" << t->Value() << " "
              << "R=" << r->Value() << " " << "E=" << e->Value();

  // Is CP + IS + FUN = TRUE?
  CHECK_EQ(p->Value() + s->Value() + n->Value() +
           kBase * (c->Value() + i->Value() + u->Value()) +
           kBase * kBase * f->Value(),
           e->Value() +
           kBase * u->Value() +
           kBase * kBase * r->Value() +
           kBase * kBase * kBase * t->Value());
  }

  solver.EndSearch();
}

}   // namespace operations_research

// ----- MAIN -----
int main(int argc, char **argv) {
  operations_research::CPIsFun();
  return 0;
}
C# program
// Copyright 2011-2014 Google
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
//
// Cryptarithmetic puzzle
//
// First attempt to solve equation CP + IS + FUN = TRUE
// where each letter represents a unique digit.
//
// This problem has 72 different solutions in base 10.

using System;
using Google.OrTools.ConstraintSolver;

public class cp_is_fun1 {
    private static void CPisFun () {
        // Instantiate the solver.
        Solver solver = new Solver ("CP is fun!");

        const int kBase = 10;

        // Decision variables.
        IntVar c = solver.MakeIntVar (1, kBase - 1, "C");
        IntVar p = solver.MakeIntVar (0, kBase - 1, "P");
        IntVar i = solver.MakeIntVar (1, kBase - 1, "I");
        IntVar s = solver.MakeIntVar (0, kBase - 1, "S");
        IntVar f = solver.MakeIntVar (1, kBase - 1, "F");
        IntVar u = solver.MakeIntVar (0, kBase - 1, "U");
        IntVar n = solver.MakeIntVar (0, kBase - 1, "N");
        IntVar t = solver.MakeIntVar (1, kBase - 1, "T");
        IntVar r = solver.MakeIntVar (0, kBase - 1, "R");
        IntVar e = solver.MakeIntVar (0, kBase - 1, "E");

        // Group variables in a vector so that we can use AllDifferent.
        IntVar[] letters = new IntVar[] { c, p, i, s, f, u, n, t, r, e};

        // Verify that we have enough digits.
        if (kBase < letters.Length) {
          throw new Exception("kBase < letters.Length");
        }

        // Define constraints.
        solver.Add (letters.AllDifferent ());

        // CP + IS + FUN = TRUE
        solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
               e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t);

        // Create the decision builder to search for solutions.
        DecisionBuilder db = solver.MakePhase (letters,
                                               Solver.CHOOSE_FIRST_UNBOUND,
                                               Solver.ASSIGN_MIN_VALUE);
        solver.NewSearch (db);

        while (solver.NextSolution ()) {
            Console.Write ("C=" + c.Value () + " P=" + p.Value ());
            Console.Write (" I=" + i.Value () + " S=" + s.Value ());
            Console.Write (" F=" + f.Value () + " U=" + u.Value ());
            Console.Write (" N=" + n.Value () + " T=" + t.Value ());
            Console.Write (" R=" + r.Value () + " E=" + e.Value ());
            Console.WriteLine ();

            // Is CP + IS + FUN = TRUE?
            if (p.Value () + s.Value () + n.Value() +
                kBase * (c.Value () + i.Value () + u.Value()) +
                kBase * kBase * f.Value () !=
                e.Value () + kBase * u.Value () +
                kBase * kBase * r.Value () +
                kBase * kBase * kBase * t.Value ()) {
              throw new Exception("CP + IS + FUN != TRUE");
            }
        }

        solver.EndSearch ();

    }

    public static void Main (String[] args) {
        CPisFun ();
    }
}

Send feedback about...