Python Backtracking (Königinnen-Checkboard)

Question

Ok, endlich habe ich nach stundenlangem Kampf mit meinem Kopf endlich verstanden, wie Backtracking funktioniert. Obwohl ich immer noch denke, dass es noch Geheimnisse gibt, die es zu verstehen gibt. Wie auch immer, ich versuche das 4-Königinnen Problem auf dem Checkboard zu erstellen. Praktisch gebe ich mir ein leeres Checkboard (es ist tatsächlich 4x4) und ich muss 4 Orte finden, an denen diese Königinnen sich nicht selbst angreifen. Eine Königin greift die Reihe, Spalte und Diagonale an, zu der sie gehört. hier ist, was ich bisher getan habe (Die gültige Funktion ist noch nicht vollständig, aber es ist nicht wirklich wichtig. Ich brauche nur die Backtrack-Funktion zu arbeiten).

def findNextCell(grid,i,j): 

    for index in range(i,4): 
     for jindex in range(j,4): 
      return index, jindex 

    for index in range(0,4): 
     for jindex in range(0,4): 
      if grid[index][jindex] == 0: 
       return index, jindex 

    return -1,-1 


def isValid(grid, index, jindex, queen): 

    rowOk = all([queen != grid[index][x] for x in range(4)]) 
    if rowOk: 
     columnOk = all([queen != grid[x][jindex] for x in range(4)]) 
     if columnOk: 
      return True 
    return False 

def queenSolve(grid, i=0, j=0, num_queens = 0): 

    i, j = findNextCell(grid, i, j) 
    print grid 
    if num_queens == 4: 
     return True 
    if isValid(grid, i, j, 1): 
     grid[i][j]=1 
     num_queens += 1 
     if (queenSolve(grid, i, j, num_queens)): 
      return True 
     grid[i][j]=0 
    return False 

input = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] 

print queenSolve(input) 

Answer 1

Das erste Problem, das ich sehe, ist die anfänglichen verschachtelten Schleifen in dieser Routine:

def findNextCell(grid,i,j): 

    for index in range(i,4): 
     for jindex in range(j,4): 
      return index, jindex 

    for index in range(0,4): 
     for jindex in range(0,4): 
      if grid[index][jindex] == 0: 
       return index, jindex 

    return -1,-1 

Dies scheint einigen frühen Testcode zu sein, wurde nie ausgeräumt:

for index in range(i,4): 
     for jindex in range(j,4): 
      return index, jindex 

Aber leider verursacht es findNextCell(), immer die i und j es wurde übergeben, nichts mehr:

>>> findNextCell(0, 1, 2) 
(1, 2) 
>>> findNextCell(0, 3, 2) 
(3, 2) 
>>> findNextCell(0, 1, 1) 
(1, 1) 
>>> 

Das nächste Problem, das ich sehe, ist das Paar von Leitungen:

num_queens += 1 
if (queenSolve(grid, i, j, num_queens)): 

Dadurch wird die Anzahl der Damen wird vermehren, Erfolg oder Misserfolg! Stattdessen wollen Sie wahrscheinlich nur eine Zeile:

if (queenSolve(grid, i, j, num_queens + 1)): 

dass die Zahl der Königinnen auf Rekursion erhöhen, aber keine aktuelle Zahl für den Fall beeinflusst dies nicht gelingt.

Das dritte Problem, das ich sehe, ist, dass dies nicht eine Schleife ist:

i, j = findNextCell(grid, i, j) 
... 
if isValid(grid, i, j, 1): 
    grid[i][j]=1 
    num_queens += 1 
    if (queenSolve(grid, i, j, num_queens)): 
     return True 
    grid[i][j]=0 

Sie sollten die aktuelle Königin in allen gültigen Räumen zu platzieren versuchen, bis Sie aus gültigen Räumen laufen, findNextCell() Renditen negativ, oder bis die Rekursion erfolgreich ist. Sie versuchen einen Ort für die aktuelle Königin und geben dann auf. Dieses Problem ist bei der aktuellen Königin iterativ und bei den folgenden rekursiv.