Lv3 N-Queen
1522 ワード
質問する
正方形のチェス盤があり、横、縦の長さはnです.チェス盤のn個の皇后を手配してお互いに攻撃できないと思います.
例えば、nが4であれば、Queenが配備され、n個のQueenが同時に互いを攻撃することはできない.
チェス盤の縦長nをパラメータとする場合、n個の後に条件を満たす方法の数を返す解関数を完了してください.
せいげんじょうけん
nresult42
I/O例説明
I/O例#1
問題の例.
に答える
最初の行にQueenを順番に配置し、Queenを配置するたびに次の利用可能な場所を格納して探索します.
コード#コード#
def solution(n):
answer = 0
available = set()
for i in range(1,n):
for j in range(n):
available.add((i,j))
for i in range(n):
stack = []
next,path = get_path(set()|available,0,i)
stack.append([(0,i),next,path])
while stack:
if len(stack[-1][1]) != 0:
next_ = stack[-1][1].pop()
next_next,path = get_path(stack[-1][2],next_[0],next_[1])
stack.append([next_,next_next,path])
else:
if stack[-1][0][0] == n-1:
answer += 1
stack.pop()
return answer
def get_path(s,i,j):
ns = set()
ns = ns | s
next_ = set()
for r,c in s:
if i+j == r+c or i-j == r-c or i == r or j == c:
ns.remove((r,c))
elif r == i+1:
next_.add((r,c))
return (next_,ns)Reference
この問題について(Lv3 N-Queen), 我々は、より多くの情報をここで見つけました https://velog.io/@du-du-zi/Lv.3-N-Queenテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol