[伯俊]9663号:N-Queen

今回の問題は後追跡の代表的な問題n-queenである.チェスでは、クイーンは所属する横線、縦線、対角線内のすべての格子を攻撃することができる.
N*Nチェス盤にN個の皇后がいるのは攻撃不可だと考えれば、横線を基準に1行ずつ載せることができる.今回の問題は,再帰関数で1行1行にQueenを配置し,配置できない行を排除するプロセスである(backtrack:以前にQueenを配置した行ではQueenを配置できなかった).コードを見てください.

N = int(input())
cols = [-1 for _ in range(N)]

def solve(row, N):
    global ans
    if row == N:
        ans += 1
        return
    for col in range(N):
        can = True
        
        # 백트래킹
        for preRow in range(row):
            if col == cols[preRow] or abs(preRow - row) == abs(cols[preRow] - col):
                can = False
                break
                
        if can:
            cols[row] = col
            solve(row+1, N)
ans = 0
solve(0, N)
print(ans)

2つの除外条件

col == cols[preRow]:0からrow-1まで、colsに格納されている数字は、この行にqueenを配置できない列のidxです.(同じ一直線)

abs(preRow - row) == abs(cols[preRow] - col):すでに対角線上に置かれていると、その格子の上に置くことができません.

この質問は以前の答えを順番に参照し続ける必要があるので、答えをBoolean値に保存するよりも、答え自体を保存します.裏通りの問題がすべてそうなのか、他のことをしなければ分からない.