암호화 퍼즐은 숫자의 숫자를 문자 (또는 기호)로 표시하는 수학적 연습입니다. 각 문자는 고유한 숫자를 나타냅니다. 목표는 주어진 수학 방정식을 확인하는 데 필요한 숫자를 찾는 것입니다.
CP
+ IS
+ FUN
--------
= TRUE
문자를 한 번 할당하면 다음 방정식이 됩니다.
23
+ 74
+ 968
--------
= 1065
이 문제에 대한 다른 답변이 있습니다. 모든 솔루션을 찾는 방법을 알려드립니다.
문제 모델링
여느 최적화 문제와 마찬가지로 먼저 변수와 제약 조건을 식별해 보겠습니다. 변수는 한 자릿수 값을 가질 수 있는 문자입니다.
CP + IS + FUN = TRUE의 경우 제약 조건은 다음과 같습니다.
- 방정식은
CP + IS + FUN = TRUE입니다. - 10개 문자가 각기 다른 숫자여야 합니다.
C,I,F,T는 0이 될 수 없습니다. 숫자에 선행 0을 쓰지 않기 때문입니다.
더 효율적인 새 CP-SAT 솔버 또는 원래 CP 솔버를 사용하여 암호 해독 문제를 해결할 수 있습니다. CP-SAT부터 두 솔버를 모두 사용한 예를 보여드리겠습니다.
CP-SAT 솔루션
변수, 제약 조건, 솔버 호출, 마지막으로 완전한 프로그램을 보여줍니다.
라이브러리 가져오기
다음 코드는 필요한 라이브러리를 가져옵니다.
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;
모델 선언
다음 코드는 문제의 모델을 선언합니다.
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()}");
}
}
변수 정의
CP-SAT 솔버를 사용할 때는 정의하는 것이 유용한 특정 도우미 메서드가 있습니다.
그중 하나인 NewIntVar를 사용하여 (정수) 자릿수를 선언합니다.
0이 될 수 있는 문자와 0이 될 수 없는 문자 (C, I, F, 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 };
제약조건 정의
다음은 제약 조건입니다 먼저 AddAllDifferent 도우미 메서드를 사용하여 모든 문자의 값이 서로 다른지 확인합니다. 그런 다음 AddEquality 도우미 메서드를 사용하여 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);
솔루션 프린터
다음은 문제 해결사가 찾을 때 각 솔루션을 표시하는 솔루션 프린터의 코드입니다.
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_;
}
솔버 호출
마지막으로 문제를 해결하고 솔루션을 표시합니다. 모든 매직은 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);
프로그램을 실행하면 다음 출력이 표시되며 여기서 각 행이 솔루션입니다.
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
프로그램 이수
전체 프로그램은 다음과 같습니다.
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()}");
}
}
기존 CP 솔루션
여기서는 밑을 변수로 취급하므로 더 높은 염기가 나오는 방정식을
해결할 수 있습니다. (10자가 모두 달라야 하므로 CP + IS + FUN = TRUE에 대해 하한 염기 해는 있을 수 없습니다.)
라이브러리 가져오기
다음 코드는 필요한 라이브러리를 가져옵니다.
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;
솔버 만들기
첫 번째 단계는 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!");
변수 정의
첫 번째 단계는 각 문자의 IntVar를 만드는 것입니다. 0이 될 수 있는 문자와 0이 될 수 없는 문자 (C, I, F, T)를 구분합니다.
다음으로, 각 문자에 새로운 IntVar가 포함된 배열을 만듭니다. 이는 제약 조건을 정의할 때 AllDifferent를 사용하므로 모든 요소가 달라야 하는 배열이 필요하기 때문에 필요한 것입니다.
마지막으로 밑이 적어도 문자 수만큼 크다는 것을 확인합니다. 그렇지 않으면 해결책이 없습니다.
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");
}
제약조건 정의
변수를 정의했으니 다음 단계는 제약 조건을 정의하는 것입니다.
먼저 AllDifferent 제약 조건을 추가하여 각 문자가 서로 다른 숫자를 갖도록 강제합니다.
다음으로 CP + IS + FUN = TRUE 제약 조건을 추가합니다. 샘플 프로그램은 다양한 방법으로 이 작업을 수행합니다.
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);
솔버 호출
이제 변수와 제약 조건이 생겼으므로 해결할 준비가 되었습니다.
다음은 문제 해결사가 찾을 때 각 솔루션을 표시하는 솔루션 프린터의 코드입니다.
문제에 관한 솔루션이 두 개 이상 있으므로 while solver.NextSolution() 루프를 사용하여 솔루션을 반복합니다. 하나의 해결책을 찾으려는 경우라면 이 관용구를 사용할 것입니다.:\
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}");
프로그램 이수
전체 프로그램은 다음과 같습니다.
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}");
}
}