白準-9663(Python)-N-Queen

4914 ワード
algo_study テキストリンク
N-Queen
質問する
N-Queen問題の大きさはN× これは,N個のチェス盤上のN個の皇后が互いに攻撃し合うことができない問題である.
Nが与えられた場合,解放後の方法の数を計算するプログラムを作成してください.
入力
1行目はNです.(1 ≤ N < 15)
しゅつりょく
1行目でN個の皇后が互いに攻撃できない場合は、数字を出力します.
コード#コード#
解法
N×Nサイズのチェス盤にN個のクイーンを重ねずに置くことができる場合,出力数の問題は,遡及アルゴリズムの中で最も代表的な問題である.
各列に皇后を1人置くことができます.したがって、Queenを1列目からN列目に配置すると、i列中のQueenの行の値をrow[i]と表すことができる.
dfsアルゴリズムを実行し、最初のif文は無限ループから逃れるための機能であり、関数を限定する条件を満たすと再帰関数に入る.再帰関数は次の列に進み、for j in range(N)セクションは次の行に進みます.
  • プール
    • 
# 퀸 놓아보기 함수

def build_queen(n, N) :
	global result # 글로벌로 생성
    # 재귀 빠져나가기 
    if n == N :
    result += 1 
    return
    # 재귀 빠져나갈 수 없을 때 퀸을 놓아보고 이전 퀸들과 비교. 
    
    else :
      for i in range(N) :
      	row[n] = i 
      # for문이 break 걸리지 않고 다 돌면 else(재귀) 실행
          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 : build_queen(n+1, N) 
# 입력 
s = int(input()) 
 
# 초기값 설정
result = 0 
row = [300] * s 
 
# 퀸 놓아보기 함수 
build_queen(0, s) 
 
# 출력
print(result)
    [swiftベース]関数
    Asp.Netのデータフィルタリングの浅い分析