[백준] 9663 N-Queen - 파이썬/백트래킹

https://www.acmicpc.net/problem/9663

N = int(input())

row = [0]*N
ans = 0

def is_promising(x):
    for i in range(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

    else:
        for i in range(N):
            row[x]=i
            if is_promising(x):
                n_queens(x+1)

n_queens(0)
print(ans)

pypy3으로 통과하였다.

N퀸은 대표적인 백트래킹 문제라고 한다.

문제를 풀지는 못했지만

체스판은 이차원 배열이지만 인덱스를 하나의 축으로 보는 방식으로 일차원 배열로 퀸의 위치를 기록하였다.

로직은 모든 경우의 수를 검증하는데, 경우의 수가 검증되었을때만 카운트 하는 방식이다.

이 검증과정이

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

    return True

이 부분이다.