문제

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

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

입력

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

출력

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

풀이

row = i행에 들어간 위치
dfs를 이용해서 하나씩 입력을 하면서
유효성 검사를 한다
-> 들어있는 값이 같거나 -> ( 행-행 == 열-열) 이면 대각선에 위치한다.

import sys
sys.stdin = open('input.txt')

N = int(input())
row =[0]*N  # i번째 행에 든 위치
result =0   # 결과

def check(n):   # 유효성 검사
    for i in range(n):  # 끝까지 다할 필요없고 n까지만 하면된다.
                        # n번째 들어간 숫자가 이미 들어가 있는 숫자다?
                        # 행끼리의 차이 == 열끼리의 차이가 같으면 대각선에 있다
        if row[n]==row[i] or abs(row[i]-row[n])==n-i:
            return False
    return True

def dfs(n): # dfs를 이용해 들어간다
    global result
    if n==N:    # n이 하나씩 올라가서 N과 같아지면
        result +=1  # 결과 +1
        return

    for i in range(N): # n번째 줄에 들어갈 숫자를 0~N까지 다 넣어 본다
        row[n]= i
        if check(n):   # 그 숫자가 유효성 검사를 통과하면?
            dfs(n+1)   # dfs가 하나 늘어난다.


dfs(0)
print(result)