Questa pagina è stata tradotta dall'API Cloud Translation.

Puzzle criptaritmetici

un rompicapo crittotmetico è un esercizio matematico in cui le cifre di alcuni numeri sono rappresentate da lettere (o simboli). Ogni lettera rappresenta una cifra univoca. L'obiettivo è trovare le cifre in modo da verificare una determinata equazione matematica:

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

Un'assegnazione di lettere alle cifre produce la seguente equazione:

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

Esistono altre risposte a questo problema. Ti mostreremo come trovare tutte le soluzioni.

Modellazione del problema

Come per qualsiasi problema di ottimizzazione, inizieremo identificando variabili e vincoli. Le variabili sono le lettere, che possono assumere qualsiasi valore a una sola cifra.

Per CP + IS + FUN = TRUE, i vincoli sono i seguenti:

L'equazione: CP + IS + FUN = TRUE.
Ciascuna delle dieci lettere deve essere una cifra diversa.
C, I, F e T non possono essere zero (poiché non scriviamo zero iniziali nei numeri).

Puoi risolvere problemi di crittotmetica con il nuovo risolutore CP-SAT, più efficiente, o con il risolutore CP originale. Ti mostreremo esempi che utilizzano entrambi i risolutori, a partire da CP-SAT.

Soluzione CP-SAT

Mostreremo le variabili, i vincoli, la chiamata del risolutore e infine i programmi completi.

Importa le librerie

Il seguente codice importa la libreria richiesta.

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;

Dichiara il modello

Il codice seguente dichiara il modello per il problema.

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

Definizione delle variabili

Quando utilizzi il risolutore CP-SAT, è utile definire alcuni metodi helper. Utilizzeremo NewIntVar, per dichiarare le nostre cifre (numero intero). Distinguiamo tra le lettere che possono potenzialmente essere zero e quelle che non possono farlo (C, I, F e T).

Python

base = 10

c = model.new_int_var(1, base - 1, "C")
p = model.new_int_var(0, base - 1, "P")
i = model.new_int_var(1, base - 1, "I")
s = model.new_int_var(0, base - 1, "S")
f = model.new_int_var(1, base - 1, "F")
u = model.new_int_var(0, base - 1, "U")
n = model.new_int_var(0, base - 1, "N")
t = model.new_int_var(1, base - 1, "T")
r = model.new_int_var(0, base - 1, "R")
e = model.new_int_var(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 };

Definizione dei vincoli

Passiamo ora ai vincoli. Innanzitutto, ci assicuriamo che tutte le lettere abbiano valori diversi, utilizzando il metodo helper AddAllDifferent. Quindi usiamo il metodo helper AddEquality per creare vincoli che applichino l'uguaglianza di CP + IS + FUN = TRUE.

Python

model.add_all_different(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);

Stampante di soluzioni

Di seguito è mostrato il codice della stampante della soluzione, che mostra ogni soluzione man mano che il risolutore la trova.

Python

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

    def __init__(self, variables: list[cp_model.IntVar]):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0

    def on_solution_callback(self) -> None:
        self.__solution_count += 1
        for v in self.__variables:
            print(f"{v}={self.value(v)}", end=" ")
        print()

    @property
    def solution_count(self) -> int:
        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_;
}

Richiamo del risolutore

Infine risolviamo il problema e mostriamo la soluzione. Il metodo operations_research::sat::SolveCpModel() sta tutto al grande.

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

Quando esegui il programma, viene visualizzato il seguente output, in cui ogni riga rappresenta una soluzione:

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

Completa i programmi

Ecco i programmi completi.

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: list[cp_model.IntVar]):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0

    def on_solution_callback(self) -> None:
        self.__solution_count += 1
        for v in self.__variables:
            print(f"{v}={self.value(v)}", end=" ")
        print()

    @property
    def solution_count(self) -> int:
        return self.__solution_count


def main() -> None:
    """solve the CP+IS+FUN==TRUE cryptarithm."""
    # Constraint programming engine
    model = cp_model.CpModel()

    base = 10

    c = model.new_int_var(1, base - 1, "C")
    p = model.new_int_var(0, base - 1, "P")
    i = model.new_int_var(1, base - 1, "I")
    s = model.new_int_var(0, base - 1, "S")
    f = model.new_int_var(1, base - 1, "F")
    u = model.new_int_var(0, base - 1, "U")
    n = model.new_int_var(0, base - 1, "N")
    t = model.new_int_var(1, base - 1, "T")
    r = model.new_int_var(0, base - 1, "R")
    e = model.new_int_var(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.add_all_different(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.status_name(status)}")
    print(f"  conflicts: {solver.num_conflicts}")
    print(f"  branches : {solver.num_branches}")
    print(f"  wall time: {solver.wall_time} 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()}");
    }
}

Soluzione CP originale

In questo caso tratteremo la base come variabile, in modo da poter risolvere l'equazione per basi più elevate. (Non possono esistere soluzioni di base inferiori per CP + IS + FUN = TRUE poiché le dieci lettere devono essere tutte diverse.)

Importa le librerie

Il seguente codice importa la libreria richiesta.

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;

Creazione del risolutore

Il primo passaggio consiste nel creare 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!");

Definizione delle variabili

Il primo passaggio consiste nel creare un IntVar per ogni lettera. Distinguiamo tra le lettere che possono potenzialmente essere pari a zero e quelle che non possono esserlo (C, I, F e T).

Successivamente, creiamo un array contenente un nuovo IntVar per ogni lettera. Questo è necessario solo perché quando definiamo i nostri vincoli, useremo AllDifferent, quindi abbiamo bisogno di un array per il quale ogni elemento deve differire.

Infine, verifichiamo che la nostra base sia grande almeno quanto il numero di lettere; in caso contrario, non c'è soluzione.

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");
}

Definizione dei vincoli

Ora che abbiamo definito le variabili, il passaggio successivo è definire i vincoli. Innanzitutto, aggiungiamo il vincolo AllDifferent, forzando ogni lettera ad avere una cifra diversa.

Quindi, aggiungiamo il vincolo CP + IS + FUN = TRUE. I programmi di esempio lo fanno in modi diversi.

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

Richiamo del risolutore

Ora che abbiamo le nostre variabili e i nostri vincoli, possiamo risolvere il problema.

Di seguito è mostrato il codice della stampante della soluzione, che mostra ogni soluzione man mano che il risolutore la trova.

Poiché esistono più soluzioni al nostro problema, eseguiamo l'iterazione delle soluzioni con un loop while solver.NextSolution(). Se stessimo solo cercando di trovare un'unica soluzione, useremmo questo idioma:\

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}");

Completa i programmi

Ecco i programmi completi.

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}");
    }
}