白駿#9663

問題のショートカット

質問する

N-Queen問題の大きさはN× これは,N個のチェス盤上のN個の皇后が互いに攻撃し合うことができない問題である.
Nが与えられた場合,解放後の方法の数を計算するプログラムを作成してください.

I/Oルール

1.入力
1行目はNです.(1 ≤ N < 15)
2.出力
1行目でN個の皇后が互いに攻撃できない場合は、数字を出力します.

質問へのアクセス

今回の問題はBacktrackingの代表的な問題N-Queen問題です.
1列の皇后は1つ置くことができて、各行には皇后が必要です.チェスクイーンの攻撃範囲から見ると、1マスの範囲内で攻撃可能で、すべての対角線が攻撃可能なので、上下左右および対角線の方向に重ならずに動線を構成すればよい.dfsアルゴリズムと再帰関数を用いて問題を近似して解くとよい.

問題解決(Python)

    
def queen(n, N) :
	global result 
    if n == N :
    result += 1 
    return
    
    else :
      for i in range(N) :
      	row[n] = i 
          for j in range(n): 
    	    if row[j] == row[n] or (row[n] - n) == (row[j] - j) or (row[n] + n) == (row[j] + j):
        	break
            else : queen(n+1, N) 
s = int(input()) 
 
result = 0 
row = [300] * s 
queen(0, s) 
 
print(result)