N-Königinnen in Scala

Question

def queens(n: Int): List[List[(Int, Int)]] = { 
    def placeQueens(k: Int): List[List[(Int, Int)]] = 
     if (k == 0) 
     List(List()) 
     else 
     for { 
      queens <- placeQueens(k - 1) 
      column <- 1 to n 
      queen = (k, column) 
      if isSafe(queen, queens) 
     } yield queen :: queens 
    placeQueens(n) 
    } 

Ich verstehe nicht, wie dieser Code funktioniert, auch wenn ich in Eclipse debuggte. Kannst du diesen Code Schritt für Schritt erklären? Übrigens funktioniert Code richtig. Ich verstehe auch den n-Queens-Algorithmus, aber ich verstehe den Mechanismus dieses Codes nicht.

Answer 1

Lassen Sie uns es brechen.

def queens(n: Int): List[List[(Int, Int)]] = { 
    def placeQueens(k: Int): List[List[(Int, Int)]] = 
    if (k == 0) 
     List(List()) 
    else 
     for { 
     queens <- placeQueens(k - 1) 
     column <- 1 to n 
     queen = (k, column) 
     if isSafe(queen, queens) 
     } yield queen :: queens 
    placeQueens(n) 
} 

Wir definieren eine Funktion queens(n: Int), die jede mögliche Platzierung von n Damen auf einem n * n Schachbrett zurückgibt. Die Funktionen queens selbst sind sehr einfach; Es delegiert nur an eine innere Funktion namens placeQueens.

placeQueens hat einen Basisfall zuerst aufgelistet: Wenn wir auf einem 0 * 0 Schachbrett operieren und 0 Königinnen platzieren, gibt es genau einen (sehr trivialen) Weg es zu tun. Jetzt ist das Fleisch dieser Funktion in der For-Schleife.

Teile davon können wie eine "traditionelle" for-Schleife gelesen werden, aber einige davon sind nicht so einfach. Die For-Schleife von Scala basiert auf der Haskell-Do-Loop-Syntax, die wahrscheinlich einige Ihrer Verwirrung erklärt. Der Weg dies zu lesen ist:

// We're starting a for-loop 
for { 
    // Call placeQueens recursively. placeQueens returns a list of 
    // all possible results, so iterate over them. 
    queens <- placeQueens(k - 1) 
    // Iterate over each column that the kth queen could go in. 
    column <- 1 to n 
    // Assign the queen to that position. 
    queen = (k, column) 
    // If the position is safe, keep going. More precisely, if the position 
    // is NOT safe, stop. 
    if isSafe(queen, queens) 
// Put our new queen assignment at the beginning of the recursively computed list. 
} yield queen :: queens 

Diese Schleifen sind gewöhnungsbedürftig. Es kann lehrreich sein, die Schleife (die der Compiler sowieso macht) manuell zu entziffern, um zu sehen, was es bedeutet. Sie können die Übersetzungsregeln on the Scala website finden.