[規格]9663:N-Queens

遡及アルゴリズム
- DFS
-可能なすべての子ノードをナビゲートし、続行できない場合は親ノードに戻ります.
アイデア
-n個のクイーンを配置するには、各行にクイーンを配置する必要があります.
-各行に対して解析関数を実行し、対角線または垂直かどうかを決定します.
-現在の行にQueenを配置できる場合は、次の行に対してソルバを呼び出します.そうでない場合は、前の行に戻ります.
-情報を3つのアレイに分割し、1つのアレイの上下のすべての状況の数を格納するのではなく

正しいコード

# BOJ 9663
import sys
input = sys.stdin.readline

def solve(i):
    global cnt
    
    if i == n:
        cnt += 1
        return
    
    for j in range(n):
        if not (a[j] or b[i+j] or c[i-j+n-1]):
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False
                
n, cnt = int(input()), 0
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

solve(0)
print(cnt)

ソース:https://rebas.kr/761