#1 OrTools로 n-Queens 해답 찾기

N-Queens 문제는 가로, 세로 칸의 수가 동일한 체스판 모든 행에 서로 공격할 수 없는 퀸을 배치하는 문제입니다. 이 문제에 대한 자세한 정보는 위키백과에서 확인 할 수 있습니다.

아래는 OrTools 최적화 도구를 이용해 N-Queens 문제를 푸는 python 소스입니다.

import sys
# CP-SAT 솔버
from ortools.sat.python import cp_model

def main(board_size):
  model = cp_model.CpModel()
  # 변수 생성
  # 배열의 인덱스는 열(column), 값은 행(Row)
  queens = [model.NewIntVar(0, board_size - 1, 'x%i' % i) for i in range(board_size)]
  
  # 제약조건 생성
  # 모든 여왕은 다른 행에 있어야 한다는 조건
  model.AddAllDifferent(queens)
  # 참고: 배열은 인덱스가 모두 다르므로 기본적으로 모든 여왕은 다른 열에 있고,
  #       배열의 값을 모두 다르게 지정하면 여왕은 모두 다른 행에 위치 하게 됨

  # 두 개의 여왕이 동일한 대각선에 있을 수 없다는 제약 조건 설정
  diag1 = []
  for i in range(board_size):
    q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i)
    diag1.append(q1)
    model.Add(q1 == queens[i] + i)
      
  diag2 = []
  for i in range(board_size):
    q2 = model.NewIntVar(-board_size, board_size, 'diag2_%i' % i)
    diag2.append(q2)
    model.Add(q2 == queens[i] - i)

  model.AddAllDifferent(diag1)
  model.AddAllDifferent(diag2)
  
  ### 모델 해결
  solver = cp_model.CpSolver()
  ### 모델 다이어그램 출력
  printer = DiagramPrinter(queens)
  ### 모델 다이어그램 출력
  status = solver.SearchForAllSolutions(model, printer)
  print()
  print('찾은 솔루션 개수 : %i' % printer.SolutionCount())
  print("걸린 시간: ", solver.WallTime(), "ms")

아래처럼 9번째 라인에 queens라는 배열을 생성합니다. 이 배열의 인덱스는 체스판의 열(column)을 의미하고, 값은 체스판의 행(row)을 의미합니다. 그래서 배열의 인덱스는 동일한 값이 없으므로 모든 다른 열에 퀸이 존재하게 됩니다. 

queens = [model.NewIntVar(0, board_size - 1, 'x%i' % i) for i in range(board_size)]

python 문법에 따르면 for 이하 문장으로 0에서 board_size-1의 만큼 반복해서 for 앞에 있는 변수를 반복 생성해 배열값을 만듭니다. model.NewIntVar(min, max, 이름) 의미는 최적화 과정에서 해당 변수가 갖을 수 있는 값의 범위를 지정한다고 보시면 됩니다. 각 배열의 값은(행 위치) 0행부터 board_size-1만큼의 값을 갖는다는 의미입니다. 그런데 이렇게하면 배열의 값은 중복된 값을 갖을 수 있게 됩니다. 이를 제약하는 제약조건을 아래와 같이(소스에서 13행) 추가합니다.

model.AddAllDifferent(queens)

이렇게 하면 queens 배열의 최적화 계산 과정에서 모든 값이 다른 조건에서 진행하라고 최적화 엔진에게 알려줍니다. 이 제약조건을 걸면 같은 행에 2개 이상의 퀸이 존재하지 않게 됩니다. 

또 다른 체스 퀸의 제약 조건은 대각선에 동시에 2개 이상의 퀸이 있으면 안된다는 것입니다. 대각선에 여왕이 존재하는지 체크하는 방식은 약간 수학적인 규칙이 있습니다.

같은 ↗방향 대각선에 존재하는 여왕들은 예외없이 행번호와 열번호를 더한 값이 같다는 것입니다.

또, ↘방향 대각선에 존재하는 여왕들은 예외없이 행번호에서 열번호를 뺀 값이 같다는 것입니다.

소스 18-22행에 model.Add(q1 == queens[i] + i) 같은 ↗방향 대각선에 위치해야 한다는 제약조건이고, 24-28행은 같은 ↘방향 대각선에 존재한다는 제약조건을 추가한 것입니다. 그리고, 소스 30, 31행을 보면 이 값이 모두 달라야 한다는 조건을 추가해서 같은 대각선에 동시에 존재하지 않게 됩니다.

board_size = 4
main(board_size)

위 소스와 같은 조건으로 실행하면 board 크기가 4인 경우로 실행 결과를 확인할 수 있습니다.

N-Queens 보드 크기가 4인 경우 결과

다음 글에서는 이 글는 빠져있는 DiagramPrinter와 python 문법으로 소스를 좀더 축약한 버전을 소개할 예정입니다.

 

ps. 반말과 높임말을 번갈아 쓴 이유는 조금이라도 타이핑을 적게 하려다가 좀 이상해 보여서 오락가락했네요. 앞으로는 높임말로 통일 하도록 하겠습니다.