파이썬으로 여덟 개의 퀸 배치 문제 풀기

이 포스트에서는 파이썬으로 여덟 개의 퀸을 배치하는 문제를 푸는 프로그램을 만드는 방법을 설명합니다.
여덟 개의 퀸 배치 문제에 대한 위키백과 설명은 다음과 같습니다: [한국어], [영어]

여덟 개의 퀸 배치 문제는 1848년 막스 베첼(Max Bezzel)이 고안한 체스 퍼즐로, 다음과 같은 규칙을 가지고 있습니다.

• 8×8 크기의 체스판과 8개의 퀸을 준비합니다.
• 퀸이 움직일 수 있는 경로는 실제 체스와 동일합니다(전후좌우 또는 대각선의 8방향 중 한 방향으로 원하는 만큼 이동).
• 8개의 퀸은 색에 관계없이 서로가 서로를 공격할 수 있습니다.
• 8개의 퀸을 모두 다른 퀸을 한 번의 이동으로 바로 공격할 수 없도록 배치해야 합니다.

8개가 아닌 경우에도 n×n 크기의 체스판에서 n개의 퀸을 배열하는 문제는 n이 2이거나 3인 경우를 제외하고는 하나 이상의 해가 존재하며, 8개의 경우는 92개의 해가 존재합니다. 단, 대칭을 같은 해로 간주할 경우는 12개의 해가 존재합니다.

파이썬 코드로 나타내 보면 다음과 같습니다.

BOARD_SIZE = 8  # 체스판 크기를 8로 설정

board = [None] * BOARD_SIZE

def set_queen(row):
    global board
    for col in range(BOARD_SIZE):
        noset = False
        if row > 0:
            for i in range(row):
                dif = row - i
                if board[i] == col or board[i] == col + dif or board[i] == col - dif:
                    # 윗줄 수직 또는 대각선으로 이미 놓여있을 경우
                    noset = True
                    break
        if noset: continue
        board[row] = col
        if row + 1 >= BOARD_SIZE:
            # 마지막 줄까지 배치에 성공하였을 경우
            return True
        else:
            # 다음 줄 재귀호출
            if set_queen(row + 1): return True
            # 마지막 줄 배치 성공시 연쇄적으로 종료
            
if __name__ == "__main__":
    # 첫 줄부터 배치 시작
    if set_queen(0):
        for b in board:
            print("+---" * BOARD_SIZE + "+")
            for i in range(BOARD_SIZE):
                if b == i: print("| Q ", end="")
                else:      print("|   ", end="")
            print("|")
        print("+---" * BOARD_SIZE + "+")

보는 바와 같이 배열을 2차원이 아닌 1차원 구조로 선언하였습니다. 상하좌우 자유이동이 가능한 특성상 당연히 한 줄에는 단 하나의 퀸만이 있을 수 있기 때문입니다. 줄을 나타내는 배열에는 그 줄에서 몇 번째 열에 퀸이 배치될지를 대입하게 됩니다.

1번째 이후(실제로는 2번째 이후)의 줄에 퀸을 배치하기 전, 0번째 줄(실제로는 1번째 줄)부터 배치할 줄의 바로 윗줄까지 검사해서 수직 또는 대각선 방향에 이미 퀸이 있을 경우 배치를 하지 않고 다음 줄로 넘깁니다.

이 과정을 통해 마지막 줄까지 배치에 성공하면, 연쇄적으로 참값을 돌려주고 함수를 빠져나와 그 결과를 화면에 표시합니다. 위의 코드는 다음과 같이 됩니다.

+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | Q |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | Q |   |   |
+---+---+---+---+---+---+---+---+
|   |   | Q |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | Q |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   | Q |   |   |   |   |
+---+---+---+---+---+---+---+---+

이와 같이 8개의 퀸이 모두 서로를 공격할 수 없는 위치에 배치된 결과를 볼 수 있습니다.

이 코드는 항상 위와 같은 결과를 출력합니다. 그 이유는 항상 왼쪽 열부터 검사해서 배치하기 때문입니다. 만약에 실행할 때마다 랜덤으로 배치되게 하고 싶다면,

import random

BOARD_SIZE = 8  # 체스판 크기를 8로 설정

board = [None] * BOARD_SIZE

def set_queen(row):
    global board
    tmp_arr = list(range(BOARD_SIZE))
    random.shuffle(tmp_arr)
    for col in tuple(tmp_arr):
        noset = False
        if row > 0:
            for i in range(row):
                dif = row - i
                if board[i] == col or board[i] == col + dif or board[i] == col - dif:
                    # 윗줄 수직 또는 대각선으로 이미 놓여있을 경우
                    noset = True
                    break
        if noset: continue
        board[row] = col
        if row + 1 >= BOARD_SIZE:
            # 마지막 줄까지 배치에 성공하였을 경우
            return True
        else:
            # 다음 줄 재귀호출
            if set_queen(row + 1): return True
            # 마지막 줄 배치 성공시 연쇄적으로 종료
            
if __name__ == "__main__":
    # 첫 줄부터 배치 시작
    if set_queen(0):
        for b in board:
            print("+---" * BOARD_SIZE + "+")
            for i in range(BOARD_SIZE):
                if b == i: print("| Q ", end="")
                else:      print("|   ", end="")
            print("|")
        print("+---" * BOARD_SIZE + "+")

위와 같이 random 모듈의 shuffle 메소드를 이용해서 검사 후 배치할 열의 순서를 무작위로 하게 하면 실행할 때마다 랜덤하게 배치될 것입니다.