문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
문제 풀이
import sys
input = sys.stdin.readline
n = int(input())
cnt = 0
isused_col = [0] * (n + 1) # 열에 대응되는 값 -> (x, y) => isused[y] = True
isused_dia1 = [0] * (2 * n) # 왼쪽 아래에서 우측 위로 가는 대각선
isused_dia2 = [0] * (2 * n) # 왼쪽 위에서 우측 아래로 가는 대각선
def func(curr):
global cnt
if curr == n: # 퀸 n개를 놓는데 성공
cnt += 1
return
# 한 행에 2개인지는 생각할 필요가 없음 -> 열과 대각선만 생각
# 같은 열 : 같은 y를 가지는 가
# 같은 대각선 : x + y나 x - y가 같을 때
for i in range(n):
if isused_col[i] or isused_dia1[i + curr] or isused_dia2[curr - i + (n - 1)]:
continue
isused_col[i] = True
isused_dia1[i + curr] = True # (x, y)에 퀸이 있을 경우, isused_dia1[x+y]을 true
isused_dia2[curr - i + n - 1] = True # (x, y)에 퀸이 있으면 isused_dia2[x-y+n-1]을 true
func(curr + 1)
isused_col[i] = False
isused_dia1[i + curr] = False
isused_dia2[curr - i + n - 1] = False
func(0)
print(cnt)다른 풀이 코드
n = int(input())
ans = 0
row = [0] * n
def is_promising(x):
for i in range(x):
# 같은 열번호를 가지는 경우 : row[i] == row[x]
# (행번호 차이) = (열번호 차이) 이면 같은 대각선상에 있는 것
if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
return False
return True
def n_queens(x):
global ans
if x == n:
ans += 1
return
else:
for i in range(n):
# [x, i]에 퀸을 놓겠다.
row[x] = i
if is_promising(x):
n_queens(x+1)
n_queens(0)
print(ans)