SW Expert Academy

2086번 N-Queen / Python

문제

풀이과정

N * N 보드에서 N개의 퀸이 있을 수 있는 경우의 수 구하기
N개의 퀸의 서로 같은 행과 열, 대각선에 위치할 수 없다.
rows 리스트의 인덱스는 행의 번호(x좌표), 해당 인덱스의 값은 열의 번호(y좌표)
같은 열에 위치하는 경우(y좌표) rows[x] == rows[i]
대각선에 위치하는 경우 abs(rows[x] - rows[i]) == abs(x - i)
퀸이 위치할 수 있는지 여부를 확인하는 함수 is_promising(x)

경우의 수를 계산할 전역 변수 global result
마지막 행 까지 검사한 경우 x == n 경우의 수 추가, 재귀 종료
(0, 0)부터 퀸을 위치 시키고 다음 행부터 퀸이 올 수 있는 경우를 재귀적으로 찾는다.

소스코드

T = int(input())

testcase = []

for i in range(T):
  testcase.append(int(input()))

def is_promising(x):
  for i in range(x):
    if rows[x] == rows[i] or abs(rows[x] - rows[i]) == abs(x - i):
      return False
  return True

def solve(x):
  global result
  if x == n:
    result += 1
    return
    
  for i in range(n):
    rows[x] = i
    if is_promising(x):
      solve(x+1)
    
for i in range(T):
  n = testcase[i]
  rows = [0] * n
  result = 0
  solve(0)
  print("#%d %d"%((i+1), result))