Zählen der Anzahl der Lösungen von N Queens Funktion erzeugt.

Question

Ich habe eine Funktion geschrieben, die alle möglichen Lösungen für das N Königinnen Problem erzeugt. Es nimmt eine ganzzahlige Eingabe vom Benutzer, die die Dimensionen der Tabelle ist. Wenn der Benutzer beispielsweise 4 eingibt, werden alle möglichen Lösungen für eine 4x4-Tabelle aufgelistet. Die Ausgabe sieht wie folgt aus, wenn n = 4 ist der Eingang:

[1, 3, 0, 2] 
[2, 0, 3, 1] 

Dies ist die Funktion, die ich verwendet:

def nQueens(partialSolution, n): 
    allPositions = getPositions(partialSolution, n) 
    if len(partialSolution) == n: 
     print(partialSolution) 
    else: 
     for item in allPositions: 
      partialSolution.append(item) 
      nQueens(partialSolution, n) 
      partialSolution.pop() 
nQueens([], n) 

Irgendwo in dieser Funktion Ich brauche eine Zählvariable zu implementieren am Ende das wird gib die Anzahl der Lösungen aus. Wenn zum Beispiel 4 eingegeben wird, dann wird es Ausgabe 2, weil es zwei Lösungen:

[1, 3, 0, 2] 
[2, 0, 3, 1] 
2 

habe ich versucht, die folgenden, aber es hat nicht funktioniert:

count = 0 
for i in partialSolution: 
    count+=1 
print(count) 

Weil es nicht in der Funktion selbst, ich bekomme einen Fehler, der besagt, dass PartialSolution nicht definiert ist. Ich bin mir nicht sicher, wie ich sowas in die Funktion selbst implementieren soll.

Answer 1

Angenommen, Ihr Code korrekt ist, könnten Sie versuchen, die Zählung auf der Funktion zurückzukehren, würde die Basis Fall sein, wenn es tatsächlich eine Lösung druckt, wie folgt aus (vorsichtig sein, nicht getesteten Code):

def nQueens(partialSolution, n): 
    allPositions = getPositions(partialSolution, n) 
    if len(partialSolution) == n: 
     print(partialSolution) 
     return 1 
    else: 
     ctr = 0 
     for item in allPositions: 
      partialSolution.append(item) 
      ctr += nQueens(partialSolution, n) 
      partialSolution.pop() 

     return ctr 

Der Basisfall gibt eins zurück, weil er eine gültige Lösung ausgibt, und nach dem rekursiven Aufruf summieren Sie die Anzahl der gefundenen Lösungen, bevor Sie zum nächsten Zweig der Rekursion gehen.