9663: N-Queen

N-Queen의 규칙

• N*N 체스판에 N개의 Queen을 놓아야하는데, 이때 각 Queen당 좌우상하 대각선에 다른 Queen이 없어야함

구현 방식

• rows 리스트에 row 별로 어느 col에 Queen이 있는 지를 저장해둠
• 0번 row부터 시작하여 queen 함수 호출
  -> 만약 row 번호가 N이라면 N개의 queen을 서로 공격할 수 없게 놓기를 성공한 경우이므로 result += 1
  -> 그렇지 않다면 row의 모든 col을 순회하면서 탐색 진행
  -> -> adjacent(x)를 호출하여 주어진 조건을 만족하는 지 확인하고, x 행이 정상적이라면 다음 행으로 계속 진행

adjacent(x):

• x 행 이전의 행들 (0 ~ x-1)만큼 for문을 돌면서,
  1) 열이 같거나
  2) 대각선 상에 이전에 놓은 Queen이 있다면
  False를 반환
• 그렇지 않으면 True를 반환

import sys

def adjacent(x):
    for i in range(x):
        if rows[x] == rows[i] or abs(rows[x] - rows[i]) == x - i:
            return False #열이 같거나, 대각선상에 있으면 False (행-행 == 열-열 인 경우 두 개는 같은 대각선상에 있음)
    return True

def queen(x):
    global result

    if x == N: #N개의 queen을 서로 공격할 수 없게 놓기 성공 
        result += 1
    else:
        for i in range(N): 
            rows[x] = i #x는 행 번호, i는 열 번호
            if adjacent(x): #x 행이 정상적이라면 계속 진행
                queen(x+1)


N = int(input())
rows = [0] * N #row당 queen이 어디에 위치해있는지
result = 0
queen(0)
print(result)