In den folgenden Abschnitten wird die Constraint-Programmierung (CP) anhand eines kombinatorischen Problems auf Basis des Schachspiels veranschaulicht. Beim Schach kann eine Königin horizontal, vertikal und diagonal angreifen. Das N-Quens-Problem stellt die Frage:
Wie können N Quens auf ein NxN-Schachbrett gesetzt werden, damit sich keine zwei von ihnen gegenseitig angreifen?
Unten sehen Sie eine mögliche Lösung für das n-Queens-Problem mit N = 4.
Keine zwei Königinnen stehen in derselben Zeile, Spalte oder Diagonale.
Beachten Sie, dass dies keine Optimierungsproblematik ist: Wir möchten alle möglichen Lösungen finden und nicht nur eine optimale Lösung, die sie zu einem natürlichen Kandidaten für die Einschränkungsprogrammierung macht. In den folgenden Abschnitten wird der CP-Ansatz für das N-Quens-Problem beschrieben. Außerdem werden Programme vorgestellt, die dieses mit dem CP-SAT-Resolver und dem ursprünglichen CP-Resolver lösen.
CP-Ansatz zur Bewältigung des N-Quens-Problems
Ein CP-Resolver versucht systematisch alle möglichen Zuweisungen von Werten zu den Variablen in einem Problem, um eine mögliche Lösung zu finden. Beim 4-Quenen-Problem beginnt der Solver in der Spalte ganz links und platziert nacheinander eine Königin in jeder Spalte an einer Stelle, die nicht von zuvor platzierten Queens angegriffen wird.
Weitergabe und Backtracking
Es gibt zwei wichtige Elemente einer Einschränkungs-Programmiersuche:
- Propagation: Jedes Mal, wenn der Matherechner einer Variablen einen Wert zuweist, werden durch die Einschränkungen die möglichen Werte der nicht zugewiesenen Variablen eingeschränkt. Diese Einschränkungen gelten für zukünftige Variablenzuweisungen. Beispielsweise kann bei der 4-Queens-Aufgabe jedes Mal, wenn der Matherechner eine Königin platziert, keine anderen Königinnen in die Zeile und Diagonalen der aktuellen Königin aufgenommen werden. Durch die Weitergabe kann die Suche erheblich beschleunigt werden, da die Menge der Variablenwerte reduziert wird, die der Solver untersuchen muss.
- Backtracking tritt auf, wenn der Solver der nächsten Variablen aufgrund der Einschränkungen keinen Wert zuweisen kann oder eine Lösung findet. In beiden Fällen kehrt der Löser zu einer vorherigen Phase zurück und ändert den Wert der Variablen in dieser Phase in einen Wert, der noch nicht versucht wurde. Im Beispiel mit den 4 Queens bedeutet dies, dass eine Königin in ein neues Quadrat in der aktuellen Spalte verschoben wird.
Als Nächstes sehen Sie, wie die Einschränkungsprogrammierung Propagation und Backtracking zur Lösung des 4-Quens-Problems nutzt.
Angenommen, der Matherechner setzt zuerst willkürlich eine Königin in die obere linke Ecke. Das ist eine Hypothese. Vielleicht stellt sich heraus, dass es keine Lösung mit einer Königin in der oberen linken Ecke gibt.
Welche Einschränkungen können wir unter Berücksichtigung dieser Hypothese propagieren? Eine Einschränkung besteht darin, dass es nur eine Königin in einer Spalte geben kann (die grauen X-Werte unten) und eine andere verhindert zwei Königinnen auf derselben Diagonale (die roten X-Symbole unten).
Unsere dritte Einschränkung unterbindet Queens in derselben Zeile:
Unsere Einschränkungen haben sich verbreitet. Wir können eine weitere Hypothese testen und eine zweite Königin auf eines der verfügbaren verbleibenden Quadrate setzen. Unser Matherechner könnte das erste verfügbare Quadrat in der zweiten Spalte platzieren:
Nachdem die diagonale Einschränkung übertragen wurde, sehen wir, dass sie keine verfügbaren Quadrate in der dritten oder letzten Zeile zurücklässt:
Da in dieser Phase keine Lösungen möglich sind, müssen wir einen Rückschritt verfolgen. Eine Möglichkeit besteht darin, dass der Matherechner das andere verfügbare Quadrat in der zweiten Spalte auswählt. Die Einschränkungsverbreitung zwingt dann jedoch eine Queen in die zweite Zeile der dritten Spalte, sodass keine gültigen Plätze für die vierte Königin übrig bleiben:
Der Matherechner muss also noch einmal zurückverfolgt werden, diesmal bis zum Platz der ersten Königin. Wir haben gezeigt, dass keine Lösung für das Queens-Quadrat ein Eckquadrat ist.
Da es keine Königin in der Ecke geben kann, bewegt der Solver die erste Königin um eins nach unten und propagiert, sodass nur ein Punkt für die zweite Königin übrig bleibt:
Durch erneutes Verbreiten bleibt nur noch ein Platz für die dritte Königin frei:
Und für die vierte und letzte Königin:
Wir haben unsere erste Lösung! Wenn wir den Matherechner angewiesen hätten, nach der ersten Lösung aufzuhören, würde er hier enden. Andernfalls würde sie wieder zurückgehen und die erste Königin in der dritten Zeile der ersten Spalte platzieren.
Lösung mit CP-SAT
Das N-Quens-Problem eignet sich ideal für die Constraint-Programmierung. In diesem Abschnitt geht es um ein kurzes Python-Programm, das den CP-SAT-Belöser verwendet, um alle Lösungen für das Problem zu finden.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
Python
import sys import time from ortools.sat.python import cp_model
C++
#include <stdlib.h> #include <sstream> #include <string> #include <vector> #include "absl/strings/numbers.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h" #include "ortools/sat/model.h" #include "ortools/sat/sat_parameters.pb.h" #include "ortools/util/sorted_interval_list.h"
Java
import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverSolutionCallback; import com.google.ortools.sat.IntVar; import com.google.ortools.sat.LinearExpr;
C#
using System; using Google.OrTools.Sat;
Modell deklarieren
Mit dem folgenden Code wird das CP-SAT-Modell deklariert.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel(); int BoardSize = 8; // There are `BoardSize` number of variables, one for a queen in each // column of the board. The value of each variable is the row that the // queen is in. IntVar[] queens = new IntVar[BoardSize]; for (int i = 0; i < BoardSize; ++i) { queens[i] = model.NewIntVar(0, BoardSize - 1, $"x{i}"); } // Define constraints. // All rows must be different. model.AddAllDifferent(queens); // No two queens can be on the same diagonal. LinearExpr[] diag1 = new LinearExpr[BoardSize]; LinearExpr[] diag2 = new LinearExpr[BoardSize]; for (int i = 0; i < BoardSize; ++i) { diag1[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/i); diag2[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/-i); } model.AddAllDifferent(diag1); model.AddAllDifferent(diag2); // Creates a solver and solves the model. CpSolver solver = new CpSolver(); SolutionPrinter cb = new SolutionPrinter(queens); // Search for all solutions. solver.StringParameters = "enumerate_all_solutions:true"; // And solve. solver.Solve(model, cb); Console.WriteLine("Statistics"); Console.WriteLine($" conflicts : {solver.NumConflicts()}"); Console.WriteLine($" branches : {solver.NumBranches()}"); Console.WriteLine($" wall time : {solver.WallTime()} s"); Console.WriteLine($" number of solutions found: {cb.SolutionCount()}"); } }
Variablen erstellen
Der Matherechner erstellt die Variablen für das Problem als Array mit dem Namen queens
.
Python
# There are `board_size` number of variables, one for a queen in each column # of the board. The value of each variable is the row that the queen is in. queens = [model.new_int_var(0, board_size - 1, f"x_{i}") for i in range(board_size)]
C++
// There are `board_size` number of variables, one for a queen in each column // of the board. The value of each variable is the row that the queen is in. std::vector<IntVar> queens; queens.reserve(board_size); Domain range(0, board_size - 1); for (int i = 0; i < board_size; ++i) { queens.push_back( cp_model.NewIntVar(range).WithName("x" + std::to_string(i))); }
Java
int boardSize = 8; // There are `BoardSize` number of variables, one for a queen in each column of the board. The // value of each variable is the row that the queen is in. IntVar[] queens = new IntVar[boardSize]; for (int i = 0; i < boardSize; ++i) { queens[i] = model.newIntVar(0, boardSize - 1, "x" + i); }
C#
int BoardSize = 8; // There are `BoardSize` number of variables, one for a queen in each // column of the board. The value of each variable is the row that the // queen is in. IntVar[] queens = new IntVar[BoardSize]; for (int i = 0; i < BoardSize; ++i) { queens[i] = model.NewIntVar(0, BoardSize - 1, $"x{i}"); }
Hier wird angenommen, dass queens[j]
die Zeilennummer der Queen in Spalte j
ist.
Mit anderen Worten: queens[j] = i
bedeutet, dass in Zeile i
und Spalte j
eine Königin vorhanden ist.
Einschränkungen erstellen
Hier ist der Code, der die Einschränkungen für das Problem erstellt.
Python
# All rows must be different. model.add_all_different(queens) # No two queens can be on the same diagonal. model.add_all_different(queens[i] + i for i in range(board_size)) model.add_all_different(queens[i] - i for i in range(board_size))
C++
// The following sets the constraint that all queens are in different rows. cp_model.AddAllDifferent(queens); // No two queens can be on the same diagonal. std::vector<LinearExpr> diag_1; diag_1.reserve(board_size); std::vector<LinearExpr> diag_2; diag_2.reserve(board_size); for (int i = 0; i < board_size; ++i) { diag_1.push_back(queens[i] + i); diag_2.push_back(queens[i] - i); } cp_model.AddAllDifferent(diag_1); cp_model.AddAllDifferent(diag_2);
Java
// All rows must be different. model.addAllDifferent(queens); // No two queens can be on the same diagonal. LinearExpr[] diag1 = new LinearExpr[boardSize]; LinearExpr[] diag2 = new LinearExpr[boardSize]; for (int i = 0; i < boardSize; ++i) { diag1[i] = LinearExpr.newBuilder().add(queens[i]).add(i).build(); diag2[i] = LinearExpr.newBuilder().add(queens[i]).add(-i).build(); } model.addAllDifferent(diag1); model.addAllDifferent(diag2);
C#
// All rows must be different. model.AddAllDifferent(queens); // No two queens can be on the same diagonal. LinearExpr[] diag1 = new LinearExpr[BoardSize]; LinearExpr[] diag2 = new LinearExpr[BoardSize]; for (int i = 0; i < BoardSize; ++i) { diag1[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/i); diag2[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/-i); } model.AddAllDifferent(diag1); model.AddAllDifferent(diag2);
Im Code wird die Methode AddAllDifferent
verwendet, bei der sich alle Elemente eines variablen Arrays unterscheiden müssen.
Sehen wir uns an, wie diese Einschränkungen die drei Bedingungen für das N-Quenen-Problem garantieren (Königinnen in verschiedenen Zeilen, Spalten und Diagonalen).
Zwei Königinnen in einer Reihe
Wenn die Methode AllDifferent
des Solver auf queens
angewendet wird, werden die Werte von queens[j]
für jeden j
unterschiedlich festgelegt. Das bedeutet, dass sich alle Queens in verschiedenen Zeilen befinden müssen.
Keine zwei Königinnen auf derselben Säule
Diese Einschränkung ist in der Definition von queens
implizit enthalten.
Da keine zwei Elemente von queens
denselben Index haben können, dürfen sich nicht zwei Queens in derselben Spalte befinden.
Zwei Königinnen auf derselben Diagonale
Die Diagonale ist etwas schwieriger als die Zeilen- und Spalteneinschränkungen. Wenn zwei Königinnen auf derselben Diagonale liegen, muss eine der folgenden Bedingungen erfüllt sein:
- Für jede der beiden Queens sind die Zeilennummer plus die Spaltennummer gleich.
Mit anderen Worten:
queens(j) + j
hat denselben Wert für zwei verschiedene Indexej
. - Die Zeilennummer abzüglich der Spaltennummer ist für jede der beiden Queens gleich.
In diesem Fall hat
queens(j) - j
denselben Wert für zwei verschiedene Indexej
.
Eine dieser Bedingungen bedeutet, dass die Königinnen auf derselben aufsteigenden Diagonalen (von links nach rechts) liegen, während die andere bedeutet, dass sie auf derselben absteigenden Diagonalen liegen. Welche Bedingung aufsteigend und welche absteigend entspricht, hängt davon ab, wie Sie die Zeilen und Spalten sortieren. Wie im vorherigen Abschnitt erwähnt, hat die Reihenfolge keine Auswirkungen auf die Lösungen, sondern nur darauf, wie sie visualisiert werden.
Die diagonale Einschränkung besteht also darin, dass die Werte von queens(j) + j
alle unterschiedlich sein müssen und die Werte von queens(j) - j
für unterschiedliche j
unterschiedlich sein müssen.
Um die Methode AddAllDifferent
auf queens(j) + j
anzuwenden, fügen wir die N Instanzen der Variable für j
von 0
bis N-1
wie folgt in das Array diag1
ein:
q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i) diag1.append(q1) model.Add(q1 == queens[j] + j)
Dann wenden wir AddAllDifferent
auf diag1
an.
model.AddAllDifferent(diag1)
Die Einschränkung für queens(j) - j
wird ähnlich erstellt.
Lösungsdrucker erstellen
Wenn Sie alle Lösungen für das N-Quens-Problem ausgeben möchten, müssen Sie einen Callback, auch als Lösungsdrucker bezeichnet, an den CP-SAT-Resolver übergeben. Der Callback gibt jede neue Lösung aus, sobald der Matherechner sie gefunden hat. Mit dem folgenden Code wird ein Lösungsdrucker erstellt.
Python
class NQueenSolutionPrinter(cp_model.CpSolverSolutionCallback): """Print intermediate solutions.""" def __init__(self, queens: list[cp_model.IntVar]): cp_model.CpSolverSolutionCallback.__init__(self) self.__queens = queens self.__solution_count = 0 self.__start_time = time.time() @property def solution_count(self) -> int: return self.__solution_count def on_solution_callback(self): current_time = time.time() print( f"Solution {self.__solution_count}, " f"time = {current_time - self.__start_time} s" ) self.__solution_count += 1 all_queens = range(len(self.__queens)) for i in all_queens: for j in all_queens: if self.value(self.__queens[j]) == i: # There is a queen in column j, row i. print("Q", end=" ") else: print("_", end=" ") print() print()
C++
int num_solutions = 0; Model model; model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) { LOG(INFO) << "Solution " << num_solutions; for (int i = 0; i < board_size; ++i) { std::stringstream ss; for (int j = 0; j < board_size; ++j) { if (SolutionIntegerValue(response, queens[j]) == i) { // There is a queen in column j, row i. ss << "Q"; } else { ss << "_"; } if (j != board_size - 1) ss << " "; } LOG(INFO) << ss.str(); } num_solutions++; }));
Java
static class SolutionPrinter extends CpSolverSolutionCallback { public SolutionPrinter(IntVar[] queensIn) { solutionCount = 0; queens = queensIn; } @Override public void onSolutionCallback() { System.out.println("Solution " + solutionCount); for (int i = 0; i < queens.length; ++i) { for (int j = 0; j < queens.length; ++j) { if (value(queens[j]) == i) { System.out.print("Q"); } else { System.out.print("_"); } if (j != queens.length - 1) { System.out.print(" "); } } System.out.println(); } solutionCount++; } public int getSolutionCount() { return solutionCount; } private int solutionCount; private final IntVar[] queens; }
C#
public class SolutionPrinter : CpSolverSolutionCallback { public SolutionPrinter(IntVar[] queens) { queens_ = queens; } public override void OnSolutionCallback() { Console.WriteLine($"Solution {SolutionCount_}"); for (int i = 0; i < queens_.Length; ++i) { for (int j = 0; j < queens_.Length; ++j) { if (Value(queens_[j]) == i) { Console.Write("Q"); } else { Console.Write("_"); } if (j != queens_.Length - 1) Console.Write(" "); } Console.WriteLine(""); } SolutionCount_++; } public int SolutionCount() { return SolutionCount_; } private int SolutionCount_; private IntVar[] queens_; }
Beachten Sie, dass der Lösungsdrucker aufgrund der Python-Schnittstelle zum zugrunde liegenden C++-Resolver als Python-Klasse geschrieben werden muss.
Die Lösungen werden durch die folgenden Zeilen im Lösungsdrucker gedruckt.
for v in self.__variables: print('%s = %i' % (v, self.Value(v)), end = ' ')
In diesem Beispiel ist self.__variables
die Variable queens
und jede v
entspricht einem der acht Einträge von queens
. Dadurch wird eine Lösung in der folgenden Form ausgegeben: x0 = queens(0) x1 = queens(1) ... x7 = queens(7)
, wobei xi
die Spaltennummer der Queen in Zeile i
ist.
Im nächsten Abschnitt wird ein Beispiel für eine Lösung gezeigt.
Den Matherechner aufrufen und die Ergebnisse anzeigen
Mit dem folgenden Code wird der Solver ausgeführt und die Lösungen angezeigt.
Python
solver = cp_model.CpSolver() solution_printer = NQueenSolutionPrinter(queens) solver.parameters.enumerate_all_solutions = True solver.solve(model, solution_printer)
C++
// Tell the solver to enumerate all solutions. SatParameters parameters; parameters.set_enumerate_all_solutions(true); model.Add(NewSatParameters(parameters)); const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model); LOG(INFO) << "Number of solutions found: " << num_solutions;
Java
CpSolver solver = new CpSolver(); SolutionPrinter cb = new SolutionPrinter(queens); // Tell the solver to enumerate all solutions. solver.getParameters().setEnumerateAllSolutions(true); // And solve. solver.solve(model, cb);
C#
// Creates a solver and solves the model. CpSolver solver = new CpSolver(); SolutionPrinter cb = new SolutionPrinter(queens); // Search for all solutions. solver.StringParameters = "enumerate_all_solutions:true"; // And solve. solver.Solve(model, cb);
Im Rahmen des Programms werden 92 verschiedene Lösungen für ein 8x8-Board gefunden. Hier ist deine erste Frage.
Q _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ ...91 other solutions displayed... Solutions found: 92
Sie können das Problem für ein Board einer anderen Größe lösen, indem Sie N als Befehlszeilenargument übergeben. Wenn das Programm beispielsweise den Namen queens
hat, löst python nqueens_sat.py 6
das Problem für ein 6x6-Board.
Das gesamte Programm
Hier ist das gesamte Programm des N-Quens-Programms.
Python
"""OR-Tools solution to the N-queens problem.""" import sys import time from ortools.sat.python import cp_model class NQueenSolutionPrinter(cp_model.CpSolverSolutionCallback): """Print intermediate solutions.""" def __init__(self, queens: list[cp_model.IntVar]): cp_model.CpSolverSolutionCallback.__init__(self) self.__queens = queens self.__solution_count = 0 self.__start_time = time.time() @property def solution_count(self) -> int: return self.__solution_count def on_solution_callback(self): current_time = time.time() print( f"Solution {self.__solution_count}, " f"time = {current_time - self.__start_time} s" ) self.__solution_count += 1 all_queens = range(len(self.__queens)) for i in all_queens: for j in all_queens: if self.value(self.__queens[j]) == i: # There is a queen in column j, row i. print("Q", end=" ") else: print("_", end=" ") print() print() def main(board_size: int) -> None: # Creates the solver. model = cp_model.CpModel() # Creates the variables. # There are `board_size` number of variables, one for a queen in each column # of the board. The value of each variable is the row that the queen is in. queens = [model.new_int_var(0, board_size - 1, f"x_{i}") for i in range(board_size)] # Creates the constraints. # All rows must be different. model.add_all_different(queens) # No two queens can be on the same diagonal. model.add_all_different(queens[i] + i for i in range(board_size)) model.add_all_different(queens[i] - i for i in range(board_size)) # Solve the model. solver = cp_model.CpSolver() solution_printer = NQueenSolutionPrinter(queens) solver.parameters.enumerate_all_solutions = True solver.solve(model, solution_printer) # Statistics. print("\nStatistics") print(f" conflicts : {solver.num_conflicts}") print(f" branches : {solver.num_branches}") print(f" wall time : {solver.wall_time} s") print(f" solutions found: {solution_printer.solution_count}") if __name__ == "__main__": # By default, solve the 8x8 problem. size = 8 if len(sys.argv) > 1: size = int(sys.argv[1]) main(size)
C++
// OR-Tools solution to the N-queens problem. #include <stdlib.h> #include <sstream> #include <string> #include <vector> #include "absl/strings/numbers.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h" #include "ortools/sat/model.h" #include "ortools/sat/sat_parameters.pb.h" #include "ortools/util/sorted_interval_list.h" namespace operations_research { namespace sat { void NQueensSat(const int board_size) { // Instantiate the solver. CpModelBuilder cp_model; // There are `board_size` number of variables, one for a queen in each column // of the board. The value of each variable is the row that the queen is in. std::vector<IntVar> queens; queens.reserve(board_size); Domain range(0, board_size - 1); for (int i = 0; i < board_size; ++i) { queens.push_back( cp_model.NewIntVar(range).WithName("x" + std::to_string(i))); } // Define constraints. // The following sets the constraint that all queens are in different rows. cp_model.AddAllDifferent(queens); // No two queens can be on the same diagonal. std::vector<LinearExpr> diag_1; diag_1.reserve(board_size); std::vector<LinearExpr> diag_2; diag_2.reserve(board_size); for (int i = 0; i < board_size; ++i) { diag_1.push_back(queens[i] + i); diag_2.push_back(queens[i] - i); } cp_model.AddAllDifferent(diag_1); cp_model.AddAllDifferent(diag_2); int num_solutions = 0; Model model; model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) { LOG(INFO) << "Solution " << num_solutions; for (int i = 0; i < board_size; ++i) { std::stringstream ss; for (int j = 0; j < board_size; ++j) { if (SolutionIntegerValue(response, queens[j]) == i) { // There is a queen in column j, row i. ss << "Q"; } else { ss << "_"; } if (j != board_size - 1) ss << " "; } LOG(INFO) << ss.str(); } num_solutions++; })); // Tell the solver to enumerate all solutions. SatParameters parameters; parameters.set_enumerate_all_solutions(true); model.Add(NewSatParameters(parameters)); const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model); LOG(INFO) << "Number of solutions found: " << num_solutions; // Statistics. LOG(INFO) << "Statistics"; LOG(INFO) << CpSolverResponseStats(response); } } // namespace sat } // namespace operations_research int main(int argc, char** argv) { int board_size = 8; if (argc > 1) { if (!absl::SimpleAtoi(argv[1], &board_size)) { LOG(INFO) << "Cannot parse '" << argv[1] << "', using the default value of 8."; board_size = 8; } } operations_research::sat::NQueensSat(board_size); return EXIT_SUCCESS; }
Java
package com.google.ortools.sat.samples; import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverSolutionCallback; import com.google.ortools.sat.IntVar; import com.google.ortools.sat.LinearExpr; /** OR-Tools solution to the N-queens problem. */ public final class NQueensSat { static class SolutionPrinter extends CpSolverSolutionCallback { public SolutionPrinter(IntVar[] queensIn) { solutionCount = 0; queens = queensIn; } @Override public void onSolutionCallback() { System.out.println("Solution " + solutionCount); for (int i = 0; i < queens.length; ++i) { for (int j = 0; j < queens.length; ++j) { if (value(queens[j]) == i) { System.out.print("Q"); } else { System.out.print("_"); } if (j != queens.length - 1) { System.out.print(" "); } } System.out.println(); } solutionCount++; } public int getSolutionCount() { return solutionCount; } private int solutionCount; private final IntVar[] queens; } public static void main(String[] args) { Loader.loadNativeLibraries(); // Create the model. CpModel model = new CpModel(); int boardSize = 8; // There are `BoardSize` number of variables, one for a queen in each column of the board. The // value of each variable is the row that the queen is in. IntVar[] queens = new IntVar[boardSize]; for (int i = 0; i < boardSize; ++i) { queens[i] = model.newIntVar(0, boardSize - 1, "x" + i); } // Define constraints. // All rows must be different. model.addAllDifferent(queens); // No two queens can be on the same diagonal. LinearExpr[] diag1 = new LinearExpr[boardSize]; LinearExpr[] diag2 = new LinearExpr[boardSize]; for (int i = 0; i < boardSize; ++i) { diag1[i] = LinearExpr.newBuilder().add(queens[i]).add(i).build(); diag2[i] = LinearExpr.newBuilder().add(queens[i]).add(-i).build(); } model.addAllDifferent(diag1); model.addAllDifferent(diag2); // Create a solver and solve the model. CpSolver solver = new CpSolver(); SolutionPrinter cb = new SolutionPrinter(queens); // Tell the solver to enumerate all solutions. solver.getParameters().setEnumerateAllSolutions(true); // And solve. solver.solve(model, cb); // Statistics. System.out.println("Statistics"); System.out.println(" conflicts : " + solver.numConflicts()); System.out.println(" branches : " + solver.numBranches()); System.out.println(" wall time : " + solver.wallTime() + " s"); System.out.println(" solutions : " + cb.getSolutionCount()); } private NQueensSat() {} }
C#
// OR-Tools solution to the N-queens problem. using System; using Google.OrTools.Sat; public class NQueensSat { public class SolutionPrinter : CpSolverSolutionCallback { public SolutionPrinter(IntVar[] queens) { queens_ = queens; } public override void OnSolutionCallback() { Console.WriteLine($"Solution {SolutionCount_}"); for (int i = 0; i < queens_.Length; ++i) { for (int j = 0; j < queens_.Length; ++j) { if (Value(queens_[j]) == i) { Console.Write("Q"); } else { Console.Write("_"); } if (j != queens_.Length - 1) Console.Write(" "); } Console.WriteLine(""); } SolutionCount_++; } public int SolutionCount() { return SolutionCount_; } private int SolutionCount_; private IntVar[] queens_; } static void Main() { // Constraint programming engine CpModel model = new CpModel(); int BoardSize = 8; // There are `BoardSize` number of variables, one for a queen in each // column of the board. The value of each variable is the row that the // queen is in. IntVar[] queens = new IntVar[BoardSize]; for (int i = 0; i < BoardSize; ++i) { queens[i] = model.NewIntVar(0, BoardSize - 1, $"x{i}"); } // Define constraints. // All rows must be different. model.AddAllDifferent(queens); // No two queens can be on the same diagonal. LinearExpr[] diag1 = new LinearExpr[BoardSize]; LinearExpr[] diag2 = new LinearExpr[BoardSize]; for (int i = 0; i < BoardSize; ++i) { diag1[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/i); diag2[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/-i); } model.AddAllDifferent(diag1); model.AddAllDifferent(diag2); // Creates a solver and solves the model. CpSolver solver = new CpSolver(); SolutionPrinter cb = new SolutionPrinter(queens); // Search for all solutions. solver.StringParameters = "enumerate_all_solutions:true"; // And solve. solver.Solve(model, cb); Console.WriteLine("Statistics"); Console.WriteLine($" conflicts : {solver.NumConflicts()}"); Console.WriteLine($" branches : {solver.NumBranches()}"); Console.WriteLine($" wall time : {solver.WallTime()} s"); Console.WriteLine($" number of solutions found: {cb.SolutionCount()}"); } }
Lösung mit dem ursprünglichen CP Solver
In den folgenden Abschnitten wird ein Python-Programm vorgestellt, das N-Quenen mit dem ursprünglichen CP-Belöser löst. Wir empfehlen jedoch die Verwendung des neueren CP-SAT-Rechners.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
Python
import sys from ortools.constraint_solver import pywrapcp
C++
#include <cstdint> #include <cstdlib> #include <sstream> #include <vector> #include "ortools/base/logging.h" #include "ortools/constraint_solver/constraint_solver.h"
Java
import com.google.ortools.Loader; import com.google.ortools.constraintsolver.DecisionBuilder; import com.google.ortools.constraintsolver.IntVar; import com.google.ortools.constraintsolver.Solver;
C#
using System; using Google.OrTools.ConstraintSolver;
Löser deklarieren
Mit dem folgenden Code wird der ursprüngliche CP-Resolver deklariert.
Python
solver = pywrapcp.Solver("n-queens")
C++
Solver solver("N-Queens");
Java
Solver solver = new Solver("N-Queens");
C#
Solver solver = new Solver("N-Queens");
Variablen erstellen
Die Methode IntVar
des Matherechners erstellt die Variablen für das Problem als Array mit dem Namen queens
.
Python
# The array index is the column, and the value is the row. queens = [solver.IntVar(0, board_size - 1, f"x{i}") for i in range(board_size)]
C++
std::vector<IntVar*> queens; queens.reserve(board_size); for (int i = 0; i < board_size; ++i) { queens.push_back( solver.MakeIntVar(0, board_size - 1, absl::StrCat("x", i))); }
Java
int boardSize = 8; IntVar[] queens = new IntVar[boardSize]; for (int i = 0; i < boardSize; ++i) { queens[i] = solver.makeIntVar(0, boardSize - 1, "x" + i); }
C#
const int BoardSize = 8; IntVar[] queens = new IntVar[BoardSize]; for (int i = 0; i < BoardSize; ++i) { queens[i] = solver.MakeIntVar(0, BoardSize - 1, $"x{i}"); }
Für jede Lösung bedeutet queens[j] = i
, dass in Spalte j
und Zeile i
eine Königin vorhanden ist.
Einschränkungen erstellen
Hier ist der Code, der die Einschränkungen für das Problem erstellt.
Python
# All rows must be different. solver.Add(solver.AllDifferent(queens)) # No two queens can be on the same diagonal. solver.Add(solver.AllDifferent([queens[i] + i for i in range(board_size)])) solver.Add(solver.AllDifferent([queens[i] - i for i in range(board_size)]))
C++
// The following sets the constraint that all queens are in different rows. solver.AddConstraint(solver.MakeAllDifferent(queens)); // All columns must be different because the indices of queens are all // different. No two queens can be on the same diagonal. std::vector<IntVar*> diag_1; diag_1.reserve(board_size); std::vector<IntVar*> diag_2; diag_2.reserve(board_size); for (int i = 0; i < board_size; ++i) { diag_1.push_back(solver.MakeSum(queens[i], i)->Var()); diag_2.push_back(solver.MakeSum(queens[i], -i)->Var()); } solver.AddConstraint(solver.MakeAllDifferent(diag_1)); solver.AddConstraint(solver.MakeAllDifferent(diag_2));
Java
// All rows must be different. solver.addConstraint(solver.makeAllDifferent(queens)); // All columns must be different because the indices of queens are all different. // No two queens can be on the same diagonal. IntVar[] diag1 = new IntVar[boardSize]; IntVar[] diag2 = new IntVar[boardSize]; for (int i = 0; i < boardSize; ++i) { diag1[i] = solver.makeSum(queens[i], i).var(); diag2[i] = solver.makeSum(queens[i], -i).var(); } solver.addConstraint(solver.makeAllDifferent(diag1)); solver.addConstraint(solver.makeAllDifferent(diag2));
C#
// All rows must be different. solver.Add(queens.AllDifferent()); // All columns must be different because the indices of queens are all different. // No two queens can be on the same diagonal. IntVar[] diag1 = new IntVar[BoardSize]; IntVar[] diag2 = new IntVar[BoardSize]; for (int i = 0; i < BoardSize; ++i) { diag1[i] = solver.MakeSum(queens[i], i).Var(); diag2[i] = solver.MakeSum(queens[i], -i).Var(); } solver.Add(diag1.AllDifferent()); solver.Add(diag2.AllDifferent());
Diese Einschränkungen garantieren die drei Bedingungen für das n-Queens-Problem (Königinnen auf verschiedenen Zeilen, Spalten und Diagonalen).
Zwei Königinnen in einer Reihe
Wenn die Methode AllDifferent
des Solver auf queens
angewendet wird, werden die Werte von queens[j]
für jede j
unterschiedlich. Das bedeutet, dass sich alle Queens in verschiedenen Zeilen befinden müssen.
Keine zwei Königinnen auf derselben Säule
Diese Einschränkung ist in der Definition von queens
implizit enthalten.
Da keine zwei Elemente von queens
denselben Index haben können, dürfen sich nicht zwei Queens in derselben Spalte befinden.
Zwei Königinnen auf derselben Diagonale
Die Diagonale ist etwas schwieriger als die Zeilen- und Spalteneinschränkungen. Wenn zwei Königinnen auf derselben Diagonale liegen, muss eine der folgenden Aussagen zutreffen:
- Wenn die Diagonale absteigend (von links nach rechts) ist, sind die Zeilennummer plus die Spaltennummer für jede der beiden Queens gleich. Daher hat
queens(i) + i
denselben Wert für zwei verschiedene Indexei
. - Wenn die Diagonale aufsteigend ist, sind die Zeilennummer abzüglich der Spaltennummer für jede der beiden Queens gleich. In diesem Fall hat
queens(i) - i
denselben Wert für zwei verschiedene Indexei
.
Die diagonale Einschränkung besteht also darin, dass die Werte von queens(i) + i
unterschiedlich sein müssen und auch die Werte von queens(i) - i
für verschiedene i
unterschiedlich sein müssen.
Mit dem Code oben wird diese Einschränkung hinzugefügt. Dazu wird die Methode AllDifferent
für jeden i
auf queens[j] + j
und queens[j] - j
angewendet.
Entscheidungstool hinzufügen
Im nächsten Schritt erstellen Sie einen Entscheidungsgenerator, der die Suchstrategie für das Problem festlegt. Die Suchstrategie kann aufgrund der Verbreitung von Einschränkungen erhebliche Auswirkungen auf die Suchzeit haben, wodurch die Anzahl der Variablenwerte reduziert wird, die der Matherechner untersuchen muss. Ein entsprechendes Beispiel haben Sie bereits unter 4-Queens-Beispiel gesehen.
Mit dem folgenden Code wird ein Entscheidungsgenerator mithilfe der Methode Phase
des Solver erstellt.
Python
db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
C++
DecisionBuilder* const db = solver.MakePhase( queens, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);
Java
// Create the decision builder to search for solutions. final DecisionBuilder db = solver.makePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
C#
// Create the decision builder to search for solutions. DecisionBuilder db = solver.MakePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
Weitere Informationen zu den Eingabeargumenten für die Methode Phase
finden Sie in Entscheidungserstellung.
Funktionsweise des Entscheidungstools im 4-Queens-Beispiel
Sehen wir uns an, wie der Entscheidungserstellungs-Builder die Suche im 4-Quenen-Beispiel leitet.
Der Matherechner beginnt mit queens[0]
, der ersten Variablen im Array, wie in CHOOSE_FIRST_UNBOUND
angegeben. Der Solver weist dann queens[0]
den kleinsten Wert zu, der noch nicht versucht wurde, d. h. in dieser Phase 0, wie von ASSIGN_MIN_VALUE
vorgegeben. Dadurch wird die erste Queen in der oberen linken Ecke des Boards platziert.
Als Nächstes wählt der Matherechner queens[1]
aus. Dies ist jetzt die erste ungebundene Variable in queens
. Nach der Weitergabe der Einschränkungen gibt es zwei mögliche Zeilen für eine Queen in Spalte 1: Zeile 2 oder Zeile 3. Die Option ASSIGN_MIN_VALUE
weist den Solver an, queens[1] = 2
zuzuweisen. Wenn du stattdessen IntValueStrategy
auf ASSIGN_MAX_VALUE
setzt, weist der Matherechner queens[1] = 3
zu.
Sie können überprüfen, ob für den Rest der Suche dieselben Regeln gelten.
Den Matherechner aufrufen und die Ergebnisse anzeigen
Mit dem folgenden Code wird der Solver ausgeführt und die Lösung angezeigt.
Python
# Iterates through the solutions, displaying each. num_solutions = 0 solver.NewSearch(db) while solver.NextSolution(): # Displays the solution just computed. for i in range(board_size): for j in range(board_size): if queens[j].Value() == i: # There is a queen in column j, row i. print("Q", end=" ") else: print("_", end=" ") print() print() num_solutions += 1 solver.EndSearch()
C++
// Iterates through the solutions, displaying each. int num_solutions = 0; solver.NewSearch(db); while (solver.NextSolution()) { // Displays the solution just computed. LOG(INFO) << "Solution " << num_solutions; for (int i = 0; i < board_size; ++i) { std::stringstream ss; for (int j = 0; j < board_size; ++j) { if (queens[j]->Value() == i) { // There is a queen in column j, row i. ss << "Q"; } else { ss << "_"; } if (j != board_size - 1) ss << " "; } LOG(INFO) << ss.str(); } num_solutions++; } solver.EndSearch();
Java
int solutionCount = 0; solver.newSearch(db); while (solver.nextSolution()) { System.out.println("Solution " + solutionCount); for (int i = 0; i < boardSize; ++i) { for (int j = 0; j < boardSize; ++j) { if (queens[j].value() == i) { System.out.print("Q"); } else { System.out.print("_"); } if (j != boardSize - 1) { System.out.print(" "); } } System.out.println(); } solutionCount++; } solver.endSearch();
C#
// Iterates through the solutions, displaying each. int SolutionCount = 0; solver.NewSearch(db); while (solver.NextSolution()) { Console.WriteLine("Solution " + SolutionCount); for (int i = 0; i < BoardSize; ++i) { for (int j = 0; j < BoardSize; ++j) { if (queens[j].Value() == i) { Console.Write("Q"); } else { Console.Write("_"); } if (j != BoardSize - 1) Console.Write(" "); } Console.WriteLine(""); } SolutionCount++; } solver.EndSearch();
Hier ist die erste Lösung des Programms für ein 8x8-Board.
Q _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ ...91 other solutions displayed... Statistics failures: 304 branches: 790 wall time: 5 ms Solutions found: 92
Sie können das Problem für ein Board einer anderen Größe lösen, indem Sie N als Befehlszeilenargument übergeben. Beispielsweise löst python nqueens_cp.py 6
das Problem bei einem 6x6-Board.
Das gesamte Programm
Das vollständige Programm sehen Sie unten.
Python
"""OR-Tools solution to the N-queens problem.""" import sys from ortools.constraint_solver import pywrapcp def main(board_size): # Creates the solver. solver = pywrapcp.Solver("n-queens") # Creates the variables. # The array index is the column, and the value is the row. queens = [solver.IntVar(0, board_size - 1, f"x{i}") for i in range(board_size)] # Creates the constraints. # All rows must be different. solver.Add(solver.AllDifferent(queens)) # No two queens can be on the same diagonal. solver.Add(solver.AllDifferent([queens[i] + i for i in range(board_size)])) solver.Add(solver.AllDifferent([queens[i] - i for i in range(board_size)])) db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) # Iterates through the solutions, displaying each. num_solutions = 0 solver.NewSearch(db) while solver.NextSolution(): # Displays the solution just computed. for i in range(board_size): for j in range(board_size): if queens[j].Value() == i: # There is a queen in column j, row i. print("Q", end=" ") else: print("_", end=" ") print() print() num_solutions += 1 solver.EndSearch() # Statistics. print("\nStatistics") print(f" failures: {solver.Failures()}") print(f" branches: {solver.Branches()}") print(f" wall time: {solver.WallTime()} ms") print(f" Solutions found: {num_solutions}") if __name__ == "__main__": # By default, solve the 8x8 problem. size = 8 if len(sys.argv) > 1: size = int(sys.argv[1]) main(size)
C++
// OR-Tools solution to the N-queens problem. #include <cstdint> #include <cstdlib> #include <sstream> #include <vector> #include "ortools/base/logging.h" #include "ortools/constraint_solver/constraint_solver.h" namespace operations_research { void NQueensCp(const int board_size) { // Instantiate the solver. Solver solver("N-Queens"); std::vector<IntVar*> queens; queens.reserve(board_size); for (int i = 0; i < board_size; ++i) { queens.push_back( solver.MakeIntVar(0, board_size - 1, absl::StrCat("x", i))); } // Define constraints. // The following sets the constraint that all queens are in different rows. solver.AddConstraint(solver.MakeAllDifferent(queens)); // All columns must be different because the indices of queens are all // different. No two queens can be on the same diagonal. std::vector<IntVar*> diag_1; diag_1.reserve(board_size); std::vector<IntVar*> diag_2; diag_2.reserve(board_size); for (int i = 0; i < board_size; ++i) { diag_1.push_back(solver.MakeSum(queens[i], i)->Var()); diag_2.push_back(solver.MakeSum(queens[i], -i)->Var()); } solver.AddConstraint(solver.MakeAllDifferent(diag_1)); solver.AddConstraint(solver.MakeAllDifferent(diag_2)); DecisionBuilder* const db = solver.MakePhase( queens, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE); // Iterates through the solutions, displaying each. int num_solutions = 0; solver.NewSearch(db); while (solver.NextSolution()) { // Displays the solution just computed. LOG(INFO) << "Solution " << num_solutions; for (int i = 0; i < board_size; ++i) { std::stringstream ss; for (int j = 0; j < board_size; ++j) { if (queens[j]->Value() == i) { // There is a queen in column j, row i. ss << "Q"; } else { ss << "_"; } if (j != board_size - 1) ss << " "; } LOG(INFO) << ss.str(); } num_solutions++; } solver.EndSearch(); // Statistics. LOG(INFO) << "Statistics"; LOG(INFO) << " failures: " << solver.failures(); LOG(INFO) << " branches: " << solver.branches(); LOG(INFO) << " wall time: " << solver.wall_time() << " ms"; LOG(INFO) << " Solutions found: " << num_solutions; } } // namespace operations_research int main(int argc, char** argv) { int board_size = 8; if (argc > 1) { board_size = std::atoi(argv[1]); } operations_research::NQueensCp(board_size); return EXIT_SUCCESS; }
Java
// OR-Tools solution to the N-queens problem. package com.google.ortools.constraintsolver.samples; import com.google.ortools.Loader; import com.google.ortools.constraintsolver.DecisionBuilder; import com.google.ortools.constraintsolver.IntVar; import com.google.ortools.constraintsolver.Solver; /** N-Queens Problem. */ public final class NQueensCp { public static void main(String[] args) { Loader.loadNativeLibraries(); // Instantiate the solver. Solver solver = new Solver("N-Queens"); int boardSize = 8; IntVar[] queens = new IntVar[boardSize]; for (int i = 0; i < boardSize; ++i) { queens[i] = solver.makeIntVar(0, boardSize - 1, "x" + i); } // Define constraints. // All rows must be different. solver.addConstraint(solver.makeAllDifferent(queens)); // All columns must be different because the indices of queens are all different. // No two queens can be on the same diagonal. IntVar[] diag1 = new IntVar[boardSize]; IntVar[] diag2 = new IntVar[boardSize]; for (int i = 0; i < boardSize; ++i) { diag1[i] = solver.makeSum(queens[i], i).var(); diag2[i] = solver.makeSum(queens[i], -i).var(); } solver.addConstraint(solver.makeAllDifferent(diag1)); solver.addConstraint(solver.makeAllDifferent(diag2)); // Create the decision builder to search for solutions. final DecisionBuilder db = solver.makePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); int solutionCount = 0; solver.newSearch(db); while (solver.nextSolution()) { System.out.println("Solution " + solutionCount); for (int i = 0; i < boardSize; ++i) { for (int j = 0; j < boardSize; ++j) { if (queens[j].value() == i) { System.out.print("Q"); } else { System.out.print("_"); } if (j != boardSize - 1) { System.out.print(" "); } } System.out.println(); } solutionCount++; } solver.endSearch(); // Statistics. System.out.println("Statistics"); System.out.println(" failures: " + solver.failures()); System.out.println(" branches: " + solver.branches()); System.out.println(" wall time: " + solver.wallTime() + "ms"); System.out.println(" Solutions found: " + solutionCount); } private NQueensCp() {} }
C#
// OR-Tools solution to the N-queens problem. using System; using Google.OrTools.ConstraintSolver; public class NQueensCp { public static void Main(String[] args) { // Instantiate the solver. Solver solver = new Solver("N-Queens"); const int BoardSize = 8; IntVar[] queens = new IntVar[BoardSize]; for (int i = 0; i < BoardSize; ++i) { queens[i] = solver.MakeIntVar(0, BoardSize - 1, $"x{i}"); } // Define constraints. // All rows must be different. solver.Add(queens.AllDifferent()); // All columns must be different because the indices of queens are all different. // No two queens can be on the same diagonal. IntVar[] diag1 = new IntVar[BoardSize]; IntVar[] diag2 = new IntVar[BoardSize]; for (int i = 0; i < BoardSize; ++i) { diag1[i] = solver.MakeSum(queens[i], i).Var(); diag2[i] = solver.MakeSum(queens[i], -i).Var(); } solver.Add(diag1.AllDifferent()); solver.Add(diag2.AllDifferent()); // Create the decision builder to search for solutions. DecisionBuilder db = solver.MakePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); // Iterates through the solutions, displaying each. int SolutionCount = 0; solver.NewSearch(db); while (solver.NextSolution()) { Console.WriteLine("Solution " + SolutionCount); for (int i = 0; i < BoardSize; ++i) { for (int j = 0; j < BoardSize; ++j) { if (queens[j].Value() == i) { Console.Write("Q"); } else { Console.Write("_"); } if (j != BoardSize - 1) Console.Write(" "); } Console.WriteLine(""); } SolutionCount++; } solver.EndSearch(); // Statistics. Console.WriteLine("Statistics"); Console.WriteLine($" failures: {solver.Failures()}"); Console.WriteLine($" branches: {solver.Branches()}"); Console.WriteLine($" wall time: {solver.WallTime()} ms"); Console.WriteLine($" Solutions found: {SolutionCount}"); } }
Anzahl der Lösungen
Die Anzahl der Lösungen steigt mit der Größe der Tafel etwa exponentiell an:
Board-Größe | Lösungen | Zeit bis zum Finden aller Lösungen (ms) |
---|---|---|
1 | 1 | 0 |
2 | 0 | 0 |
3 | 0 | 0 |
4 | 2 | 0 |
5 | 10 | 0 |
6 | 4 | 0 |
7 | 40 | 3 |
8 | 92 | 9 |
9 | 352 | 35 |
10 | 724 | 95 |
11 | 2680 | 378 |
12 | 14200 | 2198 |
13 | 73712 | 11628 |
14 | 365596 | 62427 |
15 | 2279184 | 410701 |
Viele Lösungen sind nur Drehungen von anderen und eine Technik namens Symmetriebruch kann verwendet werden, um den Rechenaufwand zu reduzieren. Das verwenden wir hier nicht. Die obige Lösung ist nicht schnell, sondern einfach. Natürlich könnten wir es viel schneller machen, wenn wir nur eine Lösung anstelle von allen finden wollten: nicht mehr als ein paar Millisekunden für Board-Größen bis zu 50.