[アルゴリズム]Backjun 9663 N-Queen、Backtracking代表質問に答えてください🧐


前回の授業で遡及テクニックを学びました!
だからこの授業では、PythonでBackTracking代表問題N-Queenを解決したいと思います.
開~始~始~😎
📌 バックグラウンド解答N-Queen

🤔 方法

  • 列では、皇后は1つ置くことができ、各行に皇后が必要です.
  • チェスの皇后が攻撃できる範囲は上下左右および対角線方向である.
  • この点を考慮して、
  • は、行および列の1つを基準として遡及技術を使用する.
  • では、動作基準で、行ごとに異なるQueenが攻撃できるかどうかをチェックし、Queenが攻撃できない場合は、dfs(n+1)を呼び出して次の行に対して同じ操作を繰り返す.
  • 💡 コード#コード#

    from sys import stdin
    
    def check(n):
        for i in range(n):
        	# 열 혹은 대각선이 같다면 0 리턴
            if row[n] == row[i] or abs(row[n]-row[i]) == n-i:
                return 0
        return 1
            
    def find(n):
        global res
        if n == N:
            res += 1
        else:
        	# 각 행에 퀸 놓기
            for i in range(N):
                row[n] = i
                # 행과 열, 대각선을 체크
                # 리턴값이 1이면 백트래킹 과정X
                if check(n):
                    find(1)
    
    N = int(stdin.readline())
    row = [0] * N
    res = 0
    find(0)
    print(res)
    📌
    熱確認対角線の確認