[伯俊]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)col == cols[preRow]:0からrow-1まで、colsに格納されている数字は、この行にqueenを配置できない列のidxです.(同じ一直線)abs(preRow - row) == abs(cols[preRow] - col):すでに対角線上に置かれていると、その格子の上に置くことができません.Reference
この問題について([伯俊]9663号:N-Queen), 我々は、より多くの情報をここで見つけました https://velog.io/@kyy00n/백준-9663번-N-Queenテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol