[파이썬 문제풀이] 체스판 경우의수 구하기

N-Queens 문제풀기

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

N-Queen 문제는 백트래킹(backtracking) 알고리즘을 사용하여 해결할 수 있습니다. 백트래킹은 가능한 모든 경우를 조사하면서 해를 찾는 방법으로, 불필요한 경우를 배제하여 탐색 시간을 단축하는 방법입니다.

 

def is_safe(board, row, col, N):
    # 같은 열에 퀸이 있는지 확인
    for i in range(row):
        if board[i][col] == 1:
            return False

    # 왼쪽 위 방향 대각선에 퀸이 있는지 확인
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # 오른쪽 위 방향 대각선에 퀸이 있는지 확인
    for i, j in zip(range(row, -1, -1), range(col, N)):
        if board[i][j] == 1:
            return False

    return True

def solve_n_queens_util(board, row, N, result):
    if row == N:
        result[0] += 1
        return

    for col in range(N):
        if is_safe(board, row, col, N):
            board[row][col] = 1
            solve_n_queens_util(board, row + 1, N, result)
            board[row][col] = 0

def solve_n_queens(N):
    board = [[0] * N for _ in range(N)]
    result = [0]
    solve_n_queens_util(board, 0, N, result)
    return result[0]

# 예시를 통한 테스트
N = 8
print(solve_n_queens(N))  # 출력: 92

 

위 코드에서 is_safe 함수는 현재 위치에 퀸을 놓을 수 있는지를 확인합니다. solve_n_queens_util 함수는 백트래킹을 사용하여 가능한 모든 경우를 탐색합니다. solve_n_queens 함수는 이러한 유틸리티 함수를 호출하고, 결과를 반환합니다.

위 코드를 실행하면 N-Queen 문제에 대한 답인 퀸을 놓는 방법의 수가 출력됩니다. 예를 들어, N이 8인 경우, 총 92가지 방법이 존재합니다.

 

1. is_safe(board, row, col, N): 현재 위치에 퀸을 놓을 수 있는지 확인하는 함수입니다.
   • board: 현재까지의 체스판 상태를 나타내는 2차원 리스트입니다.
   • row: 현재 검사 중인 행의 인덱스입니다.
   • col: 현재 검사 중인 열의 인덱스입니다.
   • N: 체스판의 크기입니다.
   • 함수는 같은 열, 왼쪽 위 대각선, 오른쪽 위 대각선에 퀸이 있는지를 확인하여 퀸을 놓을 수 있는지 여부를 판단합니다.
2. solve_n_queens_util(board, row, N, result): 백트래킹을 사용하여 가능한 모든 경우를 탐색하는 재귀 함수입니다.
   • board: 현재까지의 체스판 상태를 나타내는 2차원 리스트입니다.
   • row: 현재 검사 중인 행의 인덱스입니다.
   • N: 체스판의 크기입니다.
   • result: 가능한 퀸을 놓는 방법의 수를 저장하는 리스트입니다.
   • 함수는 현재 행에 퀸을 놓을 수 있는 모든 열을 시도하고, 가능한 경우에는 다음 행으로 넘어갑니다.
3. solve_n_queens(N): N-Queen 문제를 해결하는 함수입니다.
   • N: 체스판의 크기입니다.
   • 빈 체스판을 생성하고, 백트래킹을 시작하기 위해 solve_n_queens_util 함수를 호출합니다.
   • 가능한 퀸을 놓는 방법의 수를 반환합니다.
4. # 예시를 통한 테스트: 함수를 테스트하는 예시 코드입니다.
   • 이 예시에서는 N이 8일 때 가능한 퀸을 놓는 방법의 수를 출력하도록 합니다. 이 값을 반환하고 있으며, 예상대로면 92가 나와야 합니다.