문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

풀이과정

• 퀸이 움직이는 법칙 : 상하좌우 대각선 거리제한없이 움직임
  → 행, 열, 대각선이 모두 겹치지않는 경우의 수
• 이중배열로 풀어보려했는데 시간이 엄청 오래 걸림
  →일차원 배열로 수정

★중요개념★ 대각선 : 행차이 == 열차이

코드

def attack(x):
    # row[x] : 현재 놓인 행, x: 현재 놓인 열
    # row[i] : 이제 놓일 행, i: 이제 놓일 열
    for i in range(x):
        if row[x] == row[i] or abs(row[x]-row[i]) == abs(x-i):
            return True
    return False

def dfs(queen):
    global cnt
    if queen == n:
        cnt += 1
        return

    for i in range(n):
        row[queen] = i
        if not attack(queen):
            dfs(queen+1)


n = int(input())
row = [0]*n
cnt = 0
dfs(0)
print(cnt)