Lösen Sie das 8-Königinnen-Problem in Python basierend auf der Teilmengenbaumvorlage der Backtracking-Methode

In diesem Artikel wird hauptsächlich die Python-Implementierung des 8-Königin-Problems basierend auf der Teilmengenbaumvorlage der Backtracking-Methode vorgestellt. Er erläutert kurz das Prinzip des 8-Königinnen-Problems und analysiert die spezifischen Implementierungstechniken der zu lösenden Backtracking-Methoden-Teilbaumvorlage Das 8-Königinnen-Problem in Form von Beispielen. Freunde in Not können sich auf

beziehen. Dieser Artikel beschreibt das Beispiel der Python-Implementierung des 8-Königinnen-Problems basierend auf der Teilmengenbaumvorlage der Backtracking-Methode. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Problem

Platzieren Sie acht Damen auf einem 8×8-Raster, damit sie sich nicht gegenseitig angreifen können , das heißt, es dürfen keine zwei Damen in derselben Reihe, Spalte oder Diagonale stehen. Wie viele Möglichkeiten gibt es, sie zu platzieren?

Analyse

Um das Problem zu vereinfachen, wird unter Berücksichtigung der Tatsache, dass sich die 8 Königinnen in verschiedenen Reihen befinden, eine Königin eingesetzt Jede Zeile und die Königin können in den Spalten 0, 1, 2, ..., 7 platziert werden. Wir glauben, dass die Königin in jeder Zeile 8 Zustände hat. Dann müssen wir nur noch die Teilmengenbaumvorlage anwenden, beginnend bei Zeile 0, von oben nach unten und die 8 Zustände der Königin in jeder Zeile durchlaufen.

Code:

'''
8皇后问题
'''
n = 8 
x = [] # 一个解（n元数组）
X = [] # 一组解
# 冲突检测：判断 x[k] 是否与前 x[0~k-1] 冲突
def conflict(k):
 global x
 for i in range(k):        # 遍历前 x[0~k-1]
  if x[i]==x[k] or abs(x[i]-x[k])==abs(i-k): # 判断是否与 x[k] 冲突
   return True
 return False
# 套用子集树模板
def queens(k): # 到达第k行
 global n, x, X
 if k >= n:   # 超出最底行
  #print(x)
  X.append(x[:]) # 保存（一个解），注意x[:]
 else:
  for i in range(n): # 遍历第 0~n-1 列（即n个状态）
   x.append(i)  # 皇后置于第i列，入栈
   if not conflict(k): # 剪枝
    queens(k+1)
   x.pop()   # 回溯，出栈
# 解的可视化（根据一个解x，复原棋盘。'X'表示皇后）
def show(x):
 global n
 for i in range(n):
  print('. ' * (x[i]) + 'X ' + '. '*(n-x[i]-1))
# 测试
queens(0) # 从第0行开始
print(X[-1], '\n')
show(X[-1])

Rendering

Das obige ist der detaillierte Inhalt vonLösen Sie das 8-Königinnen-Problem in Python basierend auf der Teilmengenbaumvorlage der Backtracking-Methode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!