giải đố số học là một bài tập toán học trong đó các chữ số của một số số được biểu thị bằng chữ cái (hoặc ký hiệu). Mỗi chữ cái đại diện cho một chữ số duy nhất. Mục tiêu là tìm các chữ số sao cho một phương trình toán học cho trước được xác minh:
CP + IS + FUN -------- = TRUE
Một phép gán chữ cái thành chữ số cho ra phương trình sau:
23 + 74 + 968 -------- = 1065
Có nhiều câu trả lời khác cho bài toán này. Chúng tôi sẽ trình bày cách tìm tất cả giải pháp.
Lập mô hình cho vấn đề
Giống như mọi vấn đề tối ưu hoá, chúng ta sẽ bắt đầu bằng cách xác định các biến và quy tắc ràng buộc. Biến là các chữ cái có thể nhận bất kỳ giá trị chỉ có một chữ số nào.
Với CP + IS + FUN = TRUE, các điều kiện ràng buộc sẽ được áp dụng như sau:
- Phương trình:
CP + IS + FUN = TRUE
. - Mỗi chữ cái trong số mười chữ cái phải là một chữ số khác nhau.
C
,I
,F
vàT
không được bằng 0 (vì chúng tôi không viết các số 0 đứng đầu bằng số).
Bạn có thể giải các bài toán mật mã bằng trình giải CP-SAT mới (hiệu quả hơn hoặc trình giải CP ban đầu). Chúng tôi sẽ đưa ra các ví dụ dùng cả hai trình phân giải, bắt đầu bằng CP-SAT.
Giải pháp CP-SAT
Chúng tôi sẽ trình bày các biến, các điều kiện ràng buộc, lệnh gọi trình giải và cuối cùng là chương trình hoàn chỉnh.
Nhập thư viện
Mã sau đây nhập thư viện bắt buộc.
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;
Khai báo mô hình
Đoạn mã sau đây khai báo mô hình cho bài toán.
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()}"); } }
Xác định các biến
Khi sử dụng trình giải CP-SAT, bạn cần xác định một số phương thức trợ giúp nhất định.
Chúng ta sẽ dùng một trong số đó là NewIntVar
để khai báo các chữ số (số nguyên).
Chúng tôi phân biệt giữa các chữ cái có thể bằng 0 và các chữ cái không thể (C
, I
, F
và 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 };
Xác định các quy tắc ràng buộc
Tiếp theo là các quy tắc ràng buộc. Trước tiên, chúng ta đảm bảo rằng tất cả chữ cái đều có giá trị khác nhau bằng cách sử dụng phương thức trợ giúp AddAllDifferent
. Sau đó, chúng ta sẽ sử dụng phương thức trợ giúp AddEquality
để tạo các quy tắc ràng buộc thực thi đẳng thức 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);
Máy in giải pháp
Mã cho máy in giải pháp, hiển thị từng giải pháp khi trình giải tìm tìm thấy, được hiển thị bên dưới.
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_; }
Gọi trình giải
Cuối cùng, chúng ta giải bài toán và xem lời giải. Tất cả điều kỳ diệu ấy đều nằm trong phương thức
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);
Khi chạy chương trình, chương trình sẽ hiển thị kết quả sau, trong đó mỗi hàng là một giải pháp:
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
Hoàn thành chương trình
Sau đây là các chương trình đầy đủ.
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()}"); } }
Giải pháp CP gốc
Trong trường hợp này, chúng ta sẽ coi cơ số là một biến để bạn có thể giải phương trình cho các cơ số cao hơn. (Không thể có nghiệm cơ sở thấp hơn cho CP + IS + FUN = TRUE
vì 10 chữ cái phải khác nhau.)
Nhập thư viện
Mã sau đây nhập thư viện bắt buộc.
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;
Tạo trình giải
Bước đầu tiên là tạo 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!");
Xác định các biến
Bước đầu tiên là tạo một IntVar
cho mỗi chữ cái. Chúng tôi phân biệt giữa các chữ cái có thể bằng 0 và những chữ cái không thể (C
, I
, F
và T
).
Tiếp theo, chúng ta tạo một mảng chứa IntVar
mới cho mỗi chữ cái. Điều này chỉ cần thiết vì khi xác định các quy tắc ràng buộc, chúng ta sẽ sử dụng AllDifferent
. Vì vậy, chúng ta cần một số mảng mà mỗi phần tử cần phải khác nhau.
Cuối cùng, chúng ta xác minh rằng cơ sở của chúng ta ít nhất bằng số chữ cái; nếu không, không có giải pháp.
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"); }
Xác định các quy tắc ràng buộc
Hiện tại, chúng ta đã xác định được biến, bước tiếp theo là xác định các điều kiện ràng buộc.
Trước tiên, chúng ta thêm quy tắc ràng buộc AllDifferent
, buộc mỗi chữ cái phải có một chữ số khác nhau.
Tiếp theo, chúng ta thêm điều kiện ràng buộc CP + IS + FUN = TRUE
. Các chương trình mẫu thực hiện việc này theo nhiều cách.
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);
Gọi trình giải
Giờ đây, khi đã có các biến và quy tắc ràng buộc, chúng ta đã sẵn sàng giải quyết.
Mã cho máy in giải pháp, hiển thị từng giải pháp khi trình giải tìm tìm thấy, được hiển thị bên dưới.
Vì có nhiều giải pháp cho bài toán, nên chúng ta lặp lại các giải pháp bằng vòng lặp while solver.NextSolution()
. Nếu chúng ta chỉ đang cố gắng
tìm một giải pháp duy nhất, chúng ta sẽ sử dụng thành ngữ này:\
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}");
Hoàn thành chương trình
Sau đây là các chương trình đầy đủ.
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}"); } }