[アルゴリズム]Backjun 9663 N-Queen、Backtracking代表質問に答えてください🧐
4371 ワード
前回の授業で遡及テクニックを学びました!
だからこの授業では、PythonでBackTracking代表問題N-Queenを解決したいと思います.
開~始~始~😎
📌 バックグラウンド解答N-Queen
列では、皇后は1つ置くことができ、各行に皇后が必要です. チェスの皇后が攻撃できる範囲は上下左右および対角線方向である. この点を考慮して、は、行および列の1つを基準として遡及技術を使用する. では、動作基準で、行ごとに異なるQueenが攻撃できるかどうかをチェックし、Queenが攻撃できない場合は、
熱確認対角線の確認
だからこの授業では、PythonでBackTracking代表問題N-Queenを解決したいと思います.
開~始~始~😎
📌 バックグラウンド解答N-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)
📌熱確認対角線の確認
Reference
この問題について([アルゴリズム]Backjun 9663 N-Queen、Backtracking代表質問に答えてください🧐), 我々は、より多くの情報をここで見つけました https://velog.io/@sorzzzzy/Algorithm-백준-9663-N-Queen-백트래킹-대표-문제-풀어보기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol