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, and in the Original CP section below we'll use that fact to demonstrate how 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.

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 two OR-Tools solvers: the original CP solver, or the newer and more efficient CP-SAT solver. We'll show you both, starting with CP-SAT.

CP-SAT

We'll show a C++ implementation of SEND + MORE = MONEY, which has only one solution. We'll show the variables, the constraints, the solver invocation, and finally the entire program.

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:

C++ variables

  // Create variables.
  const int s = new_variable(0, 9);
  const int e = new_variable(0, 9);
  const int n = new_variable(0, 9);
  const int d = new_variable(0, 9);
  // Since m is a leading digit, it can't be 0.
  const int m = new_variable(1, 9);
  const int o = new_variable(0, 9);
  const int r = new_variable(0, 9);
  const int y = new_variable(0, 9);

  // Create carry variables. c0 is true if the first column of addends carries
  // a 1, c2 is true if the second column carries a 1, and so on.
  const int c0 = new_boolean_variable();
  const int c1 = new_boolean_variable();
  const int c2 = new_boolean_variable();
  const int c3 = new_boolean_variable();

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.

C++ constraints

  // Force all letters to take on different values.
  std::vector<int> vars = {s, e, n, d, m, o, r, y};
  add_all_different(vars);

  // Column 0: Force c0 - m to be 0.
  add_linear_constraint({c0, m}, {1, -1}, 0, 0);
  // Column 1: Force c1 + s + m + o - 10*c0 to be 0.
  add_linear_constraint({c1, s, m, o, c0}, {1, 1, 1, -1, -10}, 0, 0);
  // Column 2: Force c2 + e + o - n - 10*c1 to be 0.
  add_linear_constraint({c2, e, o, n, c1}, {1, 1, 1, -1, -10}, 0, 0);
  // Column 3: Force c3 + n + r - e - 10*c2 to be 0.
  add_linear_constraint({c3, n, r, e, c2}, {1, 1, 1, -1, -10}, 0, 0);
  // Column 4: Force d + e - y - 10*c3 to be 0.
  add_linear_constraint({d, e, y, c3}, {1, 1, -1, -10}, 0, 0);

Invoking the solver

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

C++ solve

  // Declare the model, solve it, and display the results.
  Model model;
  LOG(INFO) << CpModelStats(cp_model);
  const operations_research::sat::CpSolverResponse response =
      operations_research::sat::SolveCpModel(cp_model, &model);
  LOG(INFO) << CpSolverResponseStats(response);
  LOG(INFO) << "s: " << response.solution(s);
  LOG(INFO) << "e: " << response.solution(e);
  LOG(INFO) << "n: " << response.solution(n);
  LOG(INFO) << "d: " << response.solution(d);
  LOG(INFO) << "m: " << response.solution(m);
  LOG(INFO) << "o: " << response.solution(o);
  LOG(INFO) << "r: " << response.solution(r);
  LOG(INFO) << "y: " << response.solution(y);
}

Complete program

C++ program

// Use CP-SAT to solve a simple cryptarithmetic problem: SEND+MORE=MONEY.
#include "util/operations_research/sat/all_different.h"
#include "util/operations_research/sat/cp_model.proto.h"
#include "util/operations_research/sat/cp_model_solver.h"
#include "util/operations_research/sat/cp_model_utils.h"
#include "util/operations_research/sat/model.h"

namespace operations_research {
namespace sat {

void SendMoreMoney() {
  CpModelProto cp_model;

  // First, define four helper methods that will be used to create our
  // variables and constraints. You may find them useful for your own programs.
  auto add_linear_constraint = [&cp_model](const std::vector<int>& vars,
                                           const std::vector<int64>& coeffs,
                                           int64 lb, int64 ub) {
    LinearConstraintProto* const lin =
        cp_model.add_constraints()->mutable_linear();
    for (const int v : vars) {
      lin->add_vars(v);
    }
    for (const int64 c : coeffs) {
      lin->add_coeffs(c);
    }
    lin->add_domain(lb);
    lin->add_domain(ub);
  };

  auto new_variable = [&cp_model](int64 lb, int64 ub) {
    CHECK_LE(lb, ub);
    const int index = cp_model.variables_size();
    IntegerVariableProto* const var = cp_model.add_variables();
    var->add_domain(lb);
    var->add_domain(ub);
    return index;
  };

  auto new_boolean_variable = [&new_variable]() { return new_variable(0, 1); };

  auto add_all_different = [&cp_model](const std::vector<int>& vars) {
    AllDifferentConstraintProto* const alldiff =
        cp_model.add_constraints()->mutable_all_diff();
    for (int v : vars) {
      alldiff->add_vars(v);
    }
  };

  // Create variables.
  const int s = new_variable(0, 9);
  const int e = new_variable(0, 9);
  const int n = new_variable(0, 9);
  const int d = new_variable(0, 9);
  // Since m is a leading digit, it can't be 0.
  const int m = new_variable(1, 9);
  const int o = new_variable(0, 9);
  const int r = new_variable(0, 9);
  const int y = new_variable(0, 9);

  // Create carry variables. c0 is true if the first column of addends carries
  // a 1, c2 is true if the second column carries a 1, and so on.
  const int c0 = new_boolean_variable();
  const int c1 = new_boolean_variable();
  const int c2 = new_boolean_variable();
  const int c3 = new_boolean_variable();


  // Force all letters to take on different values.
  std::vector<int> vars = {s, e, n, d, m, o, r, y};
  add_all_different(vars);

  // Column 0: Force c0 - m to be 0.
  add_linear_constraint({c0, m}, {1, -1}, 0, 0);
  // Column 1: Force c1 + s + m + o - 10*c0 to be 0.
  add_linear_constraint({c1, s, m, o, c0}, {1, 1, 1, -1, -10}, 0, 0);
  // Column 2: Force c2 + e + o - n - 10*c1 to be 0.
  add_linear_constraint({c2, e, o, n, c1}, {1, 1, 1, -1, -10}, 0, 0);
  // Column 3: Force c3 + n + r - e - 10*c2 to be 0.
  add_linear_constraint({c3, n, r, e, c2}, {1, 1, 1, -1, -10}, 0, 0);
  // Column 4: Force d + e - y - 10*c3 to be 0.
  add_linear_constraint({d, e, y, c3}, {1, 1, -1, -10}, 0, 0);

  // Declare the model, solve it, and display the results.
  Model model;
  LOG(INFO) << CpModelStats(cp_model);
  const operations_research::sat::CpSolverResponse response =
      operations_research::sat::SolveCpModel(cp_model, &model);
  LOG(INFO) << CpSolverResponseStats(response);
  LOG(INFO) << "s: " << response.solution(s);
  LOG(INFO) << "e: " << response.solution(e);
  LOG(INFO) << "n: " << response.solution(n);
  LOG(INFO) << "d: " << response.solution(d);
  LOG(INFO) << "m: " << response.solution(m);
  LOG(INFO) << "o: " << response.solution(o);
  LOG(INFO) << "r: " << response.solution(r);
  LOG(INFO) << "y: " << response.solution(y);
}

}  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::SendMoreMoney();
  return EXIT_SUCCESS;
}

Original CP

We'll walk through the implementation of CP + IS + FUN = TRUE in three languages: Python, C++, and C#. With each, we'll show you the variables, the constraints, the solver invocation, and finally the entire program.

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.)

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.
  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 awhile 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 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 = 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.
  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 ();
    }
}

Overview

Modeling the problem

Implementing the solution

CP-SAT

Defining the variables

Defining the constraints

Invoking the solver

Complete program

Original CP

Defining the variables

Defining the constraints

Invoking the solver

Complete programs

Send feedback about...