[OR-Tools 스터디] The N-queens Problem

이번 섹션에서는 체스게임에 기반을 둔 combinational problem에 의한 constraint programming(CP)를 기술할 예정이다.

체스에서 queen은 수평, 수직, 대각선으로 모두 공격 가능하다. 

N-queens 문제에서 다음과 같이 물어본다:

How can N queens be placed on an NxN chessboard so that not two of them attack each other?

 

즉, NxN크기의 체스판에 N개의 queen들이 위치할 때, 두 queen이 서로를 공격하지 않도록 위치하는 방법은?

=> 가능한 솔루션은 한가지로 N=4이다. 

이 경우 두 퀸이 같은 행, 열, 대각선에 위치하지 않음을 볼 수 있다. 

 

이것은 optimization problem이 아니다  :  우리는 하나의 optimal solution보다는 가능한 모든 solution을 찾길 원한다

이는 constraint programming을 위한 natural candidate를 만든다.  

 

다음의 섹션에서는 N-queens problem에 대한 CP approach를 기술할 것이며, CP-SAT solver와 original CP solver를 둘다 사용하여 문제를 푼 program을 보여줄 것이다. 

 

CP approach to the N-queens problem

CP solver는 적용가능한 해결책을 찾기 위해 시스템적으로 가능한 모든 값을 변수에 대입함으로써 동작한다. 

4-queens 문제에서, solver는 왼쪽 제일 끝 열에서 시작하여 각 열에 하나의 퀸들을 성공적으로 위치시킨다. 각 장소들은 이전에 위치한 퀸들에게 공격을 받지 않는 곳이다.

 

Propagation and backtracking

constraint programming search에는 두가지 key element가 있다. 

• Propagation : solver가 변수에 값을 할당할 때, constraint들은 부여받지않은 변수들의 가능한 값들에 제약을 더한다. 그 제약들은 향후 변수 할당으로 이어진다. 예를 들어 4-queens 문제에서 매번 solver가 퀸을 위치시키는데 최근에 퀸을 위치시킨 행과 대각선에는 어떠한 퀸도 위치시킬 수 없다. Propagation은 solver가 탐색해야하는 변수값들의 set들이 줄어드는 것에 따라 탐색 속도가 상당히 빨라질 수 있다.
• Backtracking : 이것은 solver가 constraint들 때문에 다음 변수에 값을 할당할 수 없는 경우이거나 솔루션을 찾았을 경우에 발생한다. 이 둘의 경우, solver는 이전 스테이지를 backtrack하게되며 전에 시도되지 않았던 값으로 변수의 값을 바꾼다. 4-queens 예제에서는, 이것이 최근 열에 새로운 공간으로 퀸을 옮긴다는 것을 의미한다. 

다음으로는 4-queens 문제를 풀기 위해 constraint programming이 propagation과 backtracking을 어떻게 사용하는지를 다루자.

 

solver가 임의로 왼쪽 상단 모서리에 퀸을 위치시킨다고 가정하자. 이것은 일종의 가설이다; 아마 왼쪽 상단 모서리에 퀸이 있으면 답이 없다고 나올 것이다.  

 

주어진 이 가설에 있어서 우리가 제시할 수 있는 constraint들은 무엇일까? 첫번째 constraint는 한 열에 오직 하나의 퀸만 위치할 수 있다는 것이다 (그림에서 회색 X). 그리고 다른 constraint는 두 퀸이 같은 대각선상에 위치하면 안된다. (그림에서 빨간 X)

세번째 constraint는 같은 행에 퀸을 위치시키면 안된다는 것이다. 

우리의 constraint들이 제시되었는데, 우리는 다른 가설들도 테스트해볼 수 있다. 그리고 가능한 남은 공간들 중 하나에 두번째 퀸을 위치시킬 수 있다. 우리의 solver는 두번째 열에 첫번째 가능한 공간에 위치시키도록 결정할 것이다. 

대각의 constraint를 제시한 후, 우리는 세번째 열 혹은 마지막 행에 가능한 공간이 없음을 볼 수 있다. 

이 스테이지에서 가능한 솔루션 없이 우리는 backtrack을 할 필요가 있다. 한가지 옵션은 solver가 두번째 열에 다른 가능한 공간을 선택하는 것이다. 그러나 constraint propagation에서는 퀸을 세번째 행에 두번째 열에 강제로 넣음으로써 네번째 퀸이 들어갈 자리를 남기지 않는다.

그리고 solver가 반드시 다시 backtrack해야하며, 이때는 첫번째 퀸의 자리까지 거슬러올라가야한다. 우리는 이제 퀸 문제에 대한 어떠한 해결책도 코너 공간을 차지하지 않을 것임을 볼 수 있다.

 

코너에 퀸이 있을 수 없기 때문에, solver는 첫번째 퀸을 한칸 밑으로 이동시켰으며, 두번째 퀸을 위한 오직 한자리만 남겨두고 propagate한다.  

다시 propagate하면 세번째 퀸에게 남은 자리는 단 한곳 뿐이다. 

그리고 네번째 퀸은 다음에 위치할 수 있다:

우리는 첫번째 솔루션을 찾았다. 만약 첫번째 솔루션을 찾은 후 우리의 solver가 멈추도록 지시했다면, 여기서 끝났을 것이다. 그렇게하지 않는다면 한번 더 backtrack을 하고, 이를 통해 첫번째 열의 세번째 행에 첫번째 퀸이 위치한다. 

 

Solution using CP-SAT

N-queens 문제는 constraint programming에 이상적으로 적합하다. 이번 섹션에서 우리는 CP-SAT solver를 사용하여 짧은 파이썬 프로그램을 통해 이 문제에 대한 모든 해답을 찾을 것이다. 

 

"""OR-Tools solution to the N-queens problem."""
import sys
import time
from ortools.sat.python import cp_model


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

    def __init__(self, queens):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__queens = queens
        self.__solution_count = 0
        self.__start_time = time.time()

    def solution_count(self):
        return self.__solution_count

    def on_solution_callback(self):
        current_time = time.time()
        print('Solution %i, time = %f s' %
              (self.__solution_count, current_time - self.__start_time))
        self.__solution_count += 1

        all_queens = range(len(self.__queens))
        for i in all_queens:
            for j in all_queens:
                if self.Value(self.__queens[j]) == i:
                    # There is a queen in column j, row i.
                    print('Q', end=' ')
                else:
                    print('_', end=' ')
            print()
        print()



def main(board_size):
    # Creates the solver.
    model = cp_model.CpModel()

    # Creates the variables.
    # The array index is the column, and the value is the row.
    queens = [
        model.NewIntVar(0, board_size - 1, 'x%i' % i) for i in range(board_size)
    ]

    # Creates the constraints.
    # All rows must be different.
    model.AddAllDifferent(queens)

    # All columns must be different because the indices of queens are all
    # different.

    # No two queens can be on the same diagonal.
    model.AddAllDifferent(queens[i] + i for i in range(board_size))
    model.AddAllDifferent(queens[i] - i for i in range(board_size))

    # Solve the model.
    solver = cp_model.CpSolver()
    solution_printer = NQueenSolutionPrinter(queens)
    solver.parameters.enumerate_all_solutions = True
    solver.Solve(model, solution_printer)

    # Statistics.
    print('\nStatistics')
    print(f'  conflicts      : {solver.NumConflicts()}')
    print(f'  branches       : {solver.NumBranches()}')
    print(f'  wall time      : {solver.WallTime()} s')
    print(f'  solutions found: {solution_printer.solution_count()}')


if __name__ == '__main__':
    # By default, solve the 8x8 problem.
    size = 8
    if len(sys.argv) > 1:
        size = int(sys.argv[1])
    main(size)

 

Solution using the original CP solver

 

import sys
from ortools.constraint_solver import pywrapcp

def NQueen2(board_size):
    solver = pywrapcp.Solver('n-queens')
    queens = [
        solver.IntVar(0, board_size - 1, f'x{i}') for i in range(board_size)
    ]
    solver.Add(solver.AllDifferent(queens))

    solver.Add(solver.AllDifferent([queens[i] + i for i in range(board_size)]))
    solver.Add(solver.AllDifferent([queens[i] - i for i in range(board_size)]))

    #solver의 Phase method를 사용하여 decision builder를 만든다.
    db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
    #어떻게 동작하는것인가?
    #solver는 CHOOSE_FIRST_UNBOUND에 따라 queens[0]에서 시작하는데 이는 배열에서 첫번째 변수이다.
    #solver는 이전에 시도되지 않았던 가장 작은 값을 queens[0]에 할당한다. 이는 ASSIGN_MIN_VALUE에 따라 0이 할당된다.
    #이곳은 첫번째 퀸이 위치한 곳으로, 보드의 좌측 상단 모서리이다.
    #다음으로 solver는 queens[1]을 선택하는데, queens에서 첫번째 무한 변수이다.
    #constraint를 제시한 후, 퀸에게는 1번 열:2번 행 혹은 3번 행으로 가능한 행이 두가지가 있다
    #ASSIGN_MIN_VALUE 옵션은 solver에게 queens[1] = 2로 할당하도록 지시한다.


    #call the solver and display the results
    #iterates through the solutions, displaying each.
    num_solutions = 0
    solver.NewSearch(db)
    while solver.NextSolution():
        #displays the solution just computed.
        for i in range(board_size):
            for j in range(board_size):
                if queens[j].Value() == i:
                    print('Q', end = ' ')
                else:
                    print('_', end = ' ')
            print()
        print()
        num_solutions += 1
    solver.EndSearch()

    print('\nStatistics')
    print(f'  failures: {solver.Failures()}')
    print(f'  branches: {solver.Branches()}')
    print(f'  wall time: {solver.WallTime()} ms')
    print(f'  Solutions found: {num_solutions}')

size = 8
if len(sys.argv) > 1:
    size = int(sys.argv[1])
NQueen2(size)

 

 

 

 

 

 

 

Reference : 

https://developers.google.com/optimization/cp/queens#import_the_libraries

N-퀸즈 문제  |  OR-Tools  |  Google Developers