Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 N-Queens 퍼즐 해결 가능 여부 확인하는 프로그램

0은 빈 칸을, 1은 그 자리에 놓인 체스 퀸을 나타내는 이진 행렬이 주어졌다고 가정해 보겠습니다. 이때 현재 보드 상태에서 퀸을 추가로 배치하여 유효한 N-Queens 해답을 완성할 수 있는지 확인해야 합니다.

N-Queens 퍼즐은 n × n 체스판에 n개의 퀸을 배치하되, 어떤 두 퀸도 서로 공격할 수 없도록 만드는 고전적인 문제입니다. 퀸은 가로, 세로, 대각선 어느 방향으로든 움직일 수 있기 때문에, 모든 퀸은 서로 다른 행, 서로 다른 열, 서로 다른 대각선 위에 위치해야 합니다.

예를 들어 입력이 다음과 같다면,

10000
00000
00001
00000
00010

출력은 True입니다. 아래처럼 보드를 완성했을 때 유효한 해답 중 하나가 되기 때문입니다.

10000
00100
00001
01000
00010

해결 접근 방법

이 문제는 백트래킹(backtracking) 기법과 스택(stack)을 활용하여 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.

1단계: isSafe() 함수 정의

isSafe() 함수는 보드(board)와 좌표 (i, j)를 인자로 받아, 해당 위치에 퀸을 놓아도 충돌이 없는지 검사합니다.

  • 열 검사: 행 r을 0부터 보드 크기까지 순회하면서, r이 i가 아니고 board[r][j]가 1이면 False를 반환합니다.
  • 대각선 검사: 네 개의 대각선 방향(우하, 좌하, 우상, 좌상)으로 각각 이동하면서 퀸이 있는지 확인하고, 발견되면 False를 반환합니다.
  • 모든 검사를 통과하면 True를 반환합니다.

2단계: 메인 로직 구현

  • r과 c를 0으로 초기화하고 빈 스택을 준비합니다.
  • r이 보드의 행 개수보다 작은 동안 다음 과정을 반복합니다.
  • 현재 행 board[r]에 이미 퀸(1)이 있다면 해당 행은 건너뛰고 r을 1 증가시킵니다.
  • 그렇지 않다면 found를 False로 설정하고, c가 열 개수보다 작은 동안 각 위치에 대해 isSafe()를 호출합니다.
  • 안전한 위치를 찾으면 board[r][c]를 1로 설정하고 [r, c]를 스택에 저장한 뒤 found를 True로 바꾸고 내부 반복문을 종료합니다.
  • found가 True라면 c를 0으로 초기화하고 r을 1 증가시켜 다음 행으로 넘어갑니다.
  • found가 False라면(현재 행에 놓을 곳이 없다면) 백트래킹을 수행합니다. 스택이 비어 있으면 False를 반환하고, 그렇지 않으면 스택에서 마지막 위치를 꺼내 r과 c를 복원하며(c는 한 칸 앞으로), 직전에 놓았던 퀸을 제거합니다.
  • 모든 행을 성공적으로 처리하면 True를 반환합니다.

구현 예제

아래 구현을 통해 더 자세히 이해해 보겠습니다.

class Solution:
    def solve(self, board):
        def isSafe(board, i, j):
            for r in range(len(board)):
                if r != i and board[r][j] == 1:
                    return False
            r, c = i + 1, j + 1
            while r < len(board) and c < len(board[0]):
                if board[r][c] == 1:
                    return False
                r += 1
                c += 1
            r, c = i + 1, j - 1
            while r < len(board) and c >= 0:
                if board[r][c] == 1:
                    return False
                r += 1
                c -= 1
            r, c = i - 1, j + 1
            while r >= 0 and c < len(board[0]):
                if board[r][c] == 1:
                    return False
                r -= 1
                c += 1
            r, c = i - 1, j - 1
            while r >= 0 and c >= 0:
                if board[r][c] == 1:
                    return False
                r -= 1
                c -= 1
            return True
        r = c = 0
        stack = []
        while r < len(board):
            if 1 in board[r]:
                r += 1
                continue
            else:
                found = False
                while c < len(board[0]):
                    if isSafe(board, r, c):
                        board[r][c] = 1
                        stack.append([r, c])
                        found = True
                        break
                    c += 1
                if found:
                    c = 0
                    r += 1
                else:
                    if not stack:
                        return False
                    m = stack.pop()
                    r, c = m[0], m[1] + 1
                    board[r][c - 1] = 0
        return True
ob = Solution()
matrix = [
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0]
]
print(ob.solve(matrix))

입력

[ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1],
[0, 0, 0, 0, 0], [0, 0, 0, 1, 0] ]

출력

True

마무리

이 알고리즘은 최악의 경우 지수적으로 많은 경우를 살펴봐야 하지만, 백트래킹 덕분에 실제 탐색 공간은 크게 줄어듭니다. 기존에 퀸이 배치된 행은 건너뛰고, 안전한 위치를 찾지 못하면 즉시 이전 상태로 되돌아가므로 해답의 존재 여부를 효율적으로 판별할 수 있습니다.