Lv3 N-Queen

質問する

正方形のチェス盤があり、横、縦の長さはnです.チェス盤のn個の皇后を手配してお互いに攻撃できないと思います.
例えば、nが4であれば、Queenが配備され、n個のQueenが同時に互いを攻撃することはできない.


チェス盤の縦長nをパラメータとする場合、n個の後に条件を満たす方法の数を返す解関数を完了してください.
せいげんじょうけん

クイーン(Queen)は水平、垂直、対角線で移動できます.

nは12以下の自然数です.

I/O例
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)