Ein kryptisches Rätsel ist eine mathematische Übung, bei der die Ziffern einiger Zahlen durch Buchstaben (oder Symbole) dargestellt werden. Jeder Buchstabe steht für eine eindeutige Ziffer. Das Ziel besteht darin, die Ziffern so zu finden, dass eine gegebene mathematische Gleichung bestätigt ist:
CP + IS + FUN -------- = TRUE
Eine Zuweisung von Buchstaben zu Ziffern ergibt folgende Gleichung:
23 + 74 + 968 -------- = 1065
Es gibt andere Antworten auf dieses Problem. Wir zeigen Ihnen, wie Sie alle Lösungen finden.
Modellieren des Problems
Wie bei jedem Optimierungsproblem beginnen wir mit der Identifizierung von Variablen und Einschränkungen. Die Variablen sind die Buchstaben, die einen beliebigen einstelligen Wert annehmen können.
Für CP + IS + FUN = TRUE gelten folgende Einschränkungen:
- Die Gleichung:
CP + IS + FUN = TRUE
. - Jeder der zehn Buchstaben muss eine andere Ziffer sein.
C
,I
,F
undT
dürfen nicht null sein (da keine führenden Nullen in Zahlen geschrieben werden).
Sie können kryptarithmetische Probleme entweder mit dem neuen, effizienteren CP-SAT-Alöser oder mit dem ursprünglichen CP-Resolver lösen. Wir zeigen Ihnen Beispiele, in denen beide Solver verwendet werden, beginnend mit CP-SAT.
CP-SAT-Lösung
Wir zeigen die Variablen, die Einschränkungen, den Solver-Aufruf und schließlich die vollständigen Programme.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
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;
Modell deklarieren
Mit dem folgenden Code wird das Modell für das Problem deklariert.
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()}"); } }
Variablen definieren
Bei der Verwendung des CP-SAT-Rechners gibt es bestimmte Hilfsmethoden, die definiert werden sollten.
Wir verwenden eine davon, NewIntVar
, um unsere Ziffern (Ganzzahl) zu deklarieren.
Wir unterscheiden zwischen den Buchstaben, die potenziell Null sein können, und den Buchstaben, die das nicht sind (C
, I
, F
und 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 };
Einschränkungen definieren
Als Nächstes die Einschränkungen. Zuerst sorgen wir mithilfe der Hilfsmethode AddAllDifferent
dafür, dass alle Buchstaben unterschiedliche Werte haben. Anschließend verwenden wir die Hilfsmethode AddEquality
, um Einschränkungen zu erstellen, die die CP + IS + FUN = TRUE
-Gleichheit erzwingen.
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);
Lösungsdrucker
Der Code für den Lösungsdrucker, der jede Lösung so anzeigt, wie der Solver sie findet, ist unten dargestellt.
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_; }
Löser aufrufen
Schließlich lösen wir das Problem und zeigen die Lösung an. Die gesamte Magie bietet die Methode operations_research::sat::SolveCpModel()
.
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);
Wenn Sie das Programm ausführen, zeigt es die folgende Ausgabe an, in der jede Zeile eine Lösung ist:
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
Abgeschlossene Programme
Hier sind die vollständigen Programme.
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()}"); } }
Ursprüngliche CP-Lösung
In diesem Fall behandeln wir die Basis als Variable, sodass Sie die Gleichung für höhere Basen lösen können. Für CP + IS + FUN = TRUE
darf es keine unteren Basislösungen geben, da die zehn Buchstaben alle unterschiedlich sein müssen.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
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;
Den Solver erstellen
Im ersten Schritt erstellen Sie die 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!");
Variablen definieren
Der erste Schritt besteht darin, eine IntVar
für jeden Buchstaben zu erstellen. Wir unterscheiden zwischen den Buchstaben, die potenziell Null sein können, und den Buchstaben, die das nicht sein können (C
, I
, F
und T
).
Als Nächstes erstellen wir ein Array, das für jeden Buchstaben eine neue IntVar
enthält. Dies ist nur erforderlich, weil wir beim Definieren unserer Einschränkungen AllDifferent
verwenden, also ein Array benötigen, bei dem sich jedes Element unterscheiden muss.
Schließlich überprüfen wir, ob unsere Basis mindestens so groß ist wie die Anzahl der Buchstaben. Andernfalls gibt es keine Lösung.
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"); }
Einschränkungen definieren
Nachdem wir die Variablen definiert haben, definieren wir als Nächstes Einschränkungen.
Zuerst fügen wir die Einschränkung AllDifferent
hinzu, sodass jeder Buchstabe eine andere Ziffer hat.
Als Nächstes fügen wir die Einschränkung CP + IS + FUN = TRUE
hinzu. In den Beispielprogrammen wird dies
auf unterschiedliche Weise ausgeführt.
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);
Löser aufrufen
Da wir nun unsere Variablen und Einschränkungen haben, können wir mit der Lösung beginnen.
Der Code für den Lösungsdrucker, der jede Lösung so anzeigt, wie der Solver sie findet, ist unten dargestellt.
Da es mehr als eine Lösung für unser Problem gibt, iterieren wir durch die Lösungen mit einer while solver.NextSolution()
-Schleife. Wenn wir nur eine einzige Lösung finden
möchten, würden wir diese Redewendung verwenden:
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}");
Abgeschlossene Programme
Hier sind die vollständigen Programme.
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}"); } }