teka-teki kriptografis adalah latihan matematika yang melibatkan angka beberapa angka yang diwakili oleh huruf (atau simbol). Setiap huruf mewakili digit unik. Tujuannya adalah untuk menemukan angka sehingga persamaan matematika tertentu diverifikasi:
CP + IS + FUN -------- = TRUE
Satu penetapan huruf ke angka menghasilkan persamaan berikut:
23 + 74 + 968 -------- = 1065
Ada jawaban lain untuk masalah ini. Kami akan menunjukkan cara menemukan semua solusi.
Membuat model masalah
Seperti halnya masalah pengoptimalan lainnya, kita akan mulai dengan mengidentifikasi variabel dan batasan. Variabelnya adalah huruf, yang dapat berisi nilai satu digit mana pun.
Untuk CP + IS + FUN = TRUE, batasannya adalah sebagai berikut:
- Persamaan:
CP + IS + FUN = TRUE
. - Masing-masing dari sepuluh huruf harus berupa digit yang berbeda.
C
,I
,F
, danT
tidak boleh nol (karena kita tidak menuliskan angka nol di awal dalam angka).
Anda dapat menyelesaikan masalah kriptografis dengan pemecah CP-SAT baru, yang lebih efisien, atau pemecah CP asli. Kami akan menampilkan contoh menggunakan kedua pemecah masalah, dimulai dengan CP-SAT.
Solusi CP-SAT
Kita akan menampilkan variabel, batasan, pemanggilan pemecah, dan terakhir program lengkap.
Mengimpor library
Kode berikut mengimpor library yang diperlukan.
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;
Mendeklarasikan model
Kode berikut mendeklarasikan model untuk masalah.
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()}"); } }
Menentukan variabel
Saat menggunakan pemecah CP-SAT, ada metode bantuan tertentu yang perlu
ditentukan.
Kita akan menggunakan salah satunya, NewIntVar
, untuk mendeklarasikan digit (bilangan bulat).
Kita membedakan huruf yang berpotensi nol dan huruf yang tidak
bisa (C
, I
, F
, dan 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 };
Menentukan batasan
Selanjutnya, batasan. Pertama, kami memastikan bahwa semua huruf memiliki nilai yang berbeda,
menggunakan metode helper AddAllDifferent
. Kemudian, kita menggunakan metode helper AddEquality
untuk membuat batasan yang menerapkan kesetaraan 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);
Printer solusi
Kode untuk printer solusi, yang menampilkan setiap solusi sebagai pemecah masalah, ditunjukkan di bawah ini.
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_; }
Memanggil pemecah masalah
Terakhir, kita selesaikan masalah dan tampilkan solusinya. Semua keajaibannya ada dalam
metode
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);
Saat Anda menjalankannya, program akan menampilkan output berikut, yang setiap barisnya berisi solusi:
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
Selesaikan program
Berikut program lengkapnya.
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()}"); } }
Solusi CP Asli
Dalam hal ini kita akan memperlakukan basis sebagai variabel sehingga Anda dapat menyelesaikan persamaan
untuk basis yang lebih tinggi. (Tidak ada solusi dasar yang lebih rendah untuk
CP + IS + FUN = TRUE
karena semua hurufnya harus berbeda.)
Mengimpor library
Kode berikut mengimpor library yang diperlukan.
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;
Membuat pemecah masalah
Langkah pertama adalah membuat 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!");
Menentukan variabel
Langkah pertama adalah membuat IntVar
untuk setiap huruf. Kita membedakan huruf-huruf yang berpotensi nol dan yang tidak (C
, I
, F
, dan T
).
Selanjutnya, kita membuat array yang berisi IntVar
baru untuk setiap huruf. Ini hanya
diperlukan karena saat menentukan batasan, kita akan menggunakan
AllDifferent
, jadi kita memerlukan beberapa array yang setiap elemennya perlu dibedakan.
Terakhir, kita memverifikasi bahwa basis kita setidaknya sebesar jumlah huruf; jika tidak, tidak ada solusi.
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"); }
Menentukan batasan
Setelah kita menentukan variabel, langkah berikutnya adalah menentukan batasan.
Pertama, kita tambahkan batasan AllDifferent
, yang memaksa setiap huruf memiliki
digit yang berbeda.
Selanjutnya, tambahkan batasan CP + IS + FUN = TRUE
. Program-program sampel melakukannya
dengan cara yang berbeda.
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);
Memanggil pemecah masalah
Sekarang setelah kita memiliki variabel dan batasan, kita siap untuk mengatasinya.
Kode untuk printer solusi, yang menampilkan setiap solusi sebagai pemecah masalah, ditunjukkan di bawah ini.
Karena ada lebih dari satu solusi untuk masalah ini, kita melakukan iterasi solusi dengan loop while solver.NextSolution()
. Jika kita hanya mencoba untuk menemukan
solusi tunggal, kita akan menggunakan idiom ini:
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}");
Selesaikan program
Berikut program lengkapnya.
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}"); } }