[OR-Tools] Cryptarithmetic Puzzles

cryptarithmetic puzzle은 수학적인 exercise으로 여기서는 몇자리 숫자들이 글자 혹은 기호에 의해 표현된다.  

목표는 주어진 수학적 방정식을 검증할 수 있는 숫자를 찾는 것이다 : 

 

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

문자를 숫자에 한 번 할당하면 다음과 같은 방정식이 생성된다. 

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

이는 이 문제에 대한 또다른 정답이다. 모든 솔루션을 어떻게 찾는지를 다루어보자.

 

Modeling the problem

어떠한 최적화문제이건, 변수와 constraint들을 정의함으로써 시작된다. 변수는 문자들이며 이들은 어떠한 단일 숫자값을 가질 수 있다.

CP + IS + FUN = TRUE에 대해 constraint들은 다음과 같다 :

• the equation : CP + IS + FUN = TRUE
• Each of the ten letters must be a different digit.
• C, I, F, and T can't be zero (since we don't write leading zeros in numbers).

더 효과적인 new CP-SAT solver 혹은 original CP solver 둘 중 하나로 cryptarithmetic problem을 해결할 수 있다. 

아래에서는 CP-SAT을 시작으로 두가지 solver를 사용한 예제를 보여줄 것이다. 

 

CP-SAT Solution

#import the libraries
from ortools.sat.python import cp_model

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

    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0

    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            print('%s=%i' % (v, self.Value(v)), end=' ')
        print()

    def solution_count(self):
        return self.__solution_count
def CPSolver():
    #declare the model
    #문제를 위한 모델을 선언
    model = cp_model.CpModel()

    #defining the variables
    #CP-SAT을 사용할 때, 어떤 helper method가 있는데 이것은 선언에 있어서 매우 유용하다.
    #우리는 그것들 중 하나를 사용하는데 NewIntVar이다.
    #이것은 digit들을 선언하기 위해 사용된다.
    #잠재적으로 0이 될 수 있는 글자들과 0이 될 수 없는 글자들(C, I, F, T)을 구분한다.

    base = 10

    c = model.NewIntVar(1, base - 1, 'C')
    p = model.NewIntVar(0, base - 1, 'P')
    i = model.NewIntVar(1, base - 1, 'I')
    s = model.NewIntVar(0, base - 1, 'S')
    f = model.NewIntVar(1, base - 1, 'F')
    u = model.NewIntVar(0, base - 1, 'U')
    n = model.NewIntVar(0, base - 1, 'N')
    t = model.NewIntVar(1, base - 1, 'T')
    r = model.NewIntVar(0, base - 1, 'R')
    e = model.NewIntVar(0, base - 1, 'E')

    letters = [c, p, i, s, f, u, n, t, r, e]

    #assert : 가정 설정문으로 단순히 에러를 찾는 것이 아니라 값을 보증하기 위해 사용됨.
    assert base >= len(letters)


    #defining the constraints
    #우리는 AddAllDifferent helper method를 사용하여 모든 letter들이 다른 값을 가지고 있음을 보증한다.
    #그리고 우리는 AddEquality helper method를 사용하는데, 이는 CP+IS+FUN = TRUE에 동등성을 적용시키는 제약조건을 만든다.

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

    # invoking the solver
    # 마지막으로 문제를 푼 후 그에 대한 솔루션을 보여준다. 모든 magic은 operations_research::sat::SolveCpModel() method에 있다.

    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.StatusName(status)}')
    print(f'  conflicts: {solver.NumConflicts()}')
    print(f'  branches : {solver.NumBranches()}')
    print(f'  wall time: {solver.WallTime()} s')
    print(f'  sol found: {solution_printer.solution_count()}')

CPSolver()

 

Original CP Solution

이 케이스의 경우 base를 변수로 다루었기 때문에 더 높은 base에 대한 식도 풀 수 있다. 

(CP+IS+FUN=TRUE는 10개의 문자들이 모두 달랐어야했기에 lower base의 해결책이 없다. )

 

 

 

#import the libraries
from ortools.constraint_solver import pywrapcp

def OriginalCPSolution():
    #creating the solver
    solver = pywrapcp.Solver('CP is fun!')

    #defining the variables
    #각 글자들에 대해 IntVar로 생성하는 것이 첫번째 단계이다.
    #0이 될 수 있는 것과 없는 것을 구분한다.
    #그 후 각 단어별로 새로운 IntVar을 포함한 배열을 생성한다.
    #constraint들을 선언할 때 우리는 AllDifferent를 사용하기에 우리는 모든 element가 달라야하는 어떠한 배열이 필요하다.
    #마지막으로 우리의 base가 최소 문자의 숫자보다 큰지 확인해야한다.

    base = 10

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

    letters = [c, p, i, s, f, u, n, t, r, e]

    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)

    #invoking the solver
    #
    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}')

OriginalCPSolution()

 

Reference : 

https://developers.google.com/optimization/cp/cryptarithmetic