W kolejnych sekcjach omówimy programowanie ograniczeń (CP) za pomocą zadania kombinacyjnego opartego na grze w szachy. W szachach królowa może atakować w poziomie, w pionie i po przekątnej. Zadanie N-queens ma na celu:
Jak można umieścić N Królów na szachownicy NxN, aby żadna z nich nie atakowała siebie?
Poniżej przedstawiliśmy jedno z możliwych rozwiązań problemu z n = 4.
Żadne dwie królowe nie znajdują się w tym samym wierszu, w tej samej kolumnie czy po przekątnej.
Pamiętaj, że nie jest to problem z optymalizacją – chcemy znaleźć wszystkie możliwe rozwiązania, a nie jedno, co czyni go naturalnym kandydatem do programowania z ograniczeniami. W kolejnych sekcjach opisujemy podejście CP do problemu N queens i przedstawiamy programy, które rozwiązują ten problem przy użyciu zarówno rozwiązania CP-SAT, jak i pierwotnego rozwiązania CP-SAT.
Podejście CP do problemu N-queens
Narzędzie do rozwiązywania problemów CP systematycznie próbuje przypisać wszystkie możliwe wartości do zmiennych w danym problemie, aby znaleźć wykonalne rozwiązania. W problemie z 4 queens rozwiązanie zaczyna się od kolumny po lewej stronie i stopniowo umieszcza 1 kręgę w każdej kolumnie, w miejscu, w którym żadna z nich nie jest atakowana.
Propagacja i śledzenie wsteczne
Istnieją 2 główne elementy wyszukiwania związanego z programowaniem ograniczeń:
- Propagacja – za każdym razem, gdy rozwiązanie przypisuje wartość do zmiennej, ograniczenia dodają ograniczenia dotyczące możliwych wartości nieprzypisanych zmiennych. Te ograniczenia obejmują przyszłe przypisania zmiennych. Na przykład w problemie z 4 queens za każdym razem, gdy rozwiązanie rozwiązuje królową, inne królowe nie mogą umieścić w rzędzie żadnej innej królowej, jeśli bieżąca królowa jest na przekątnej. Propagacja może znacznie przyspieszyć wyszukiwanie, ograniczając zbiór wartości zmiennych, które musi badać rozwiązanie.
- Śledzenie wsteczne ma miejsce wtedy, gdy rozwiązanie nie może przypisać wartości do następnej zmiennej z powodu ograniczeń lub znajdzie rozwiązanie. W obu przypadkach solalizator przechodzi do poprzedniego etapu i zmienia wartość zmiennej na tym etapie na wartość, która nie została jeszcze wypróbowana. W przykładzie z 4 queens oznacza to przeniesienie królowej do nowego kwadratu w bieżącej kolumnie.
Następnie pokazaliśmy, w jaki sposób programowanie ograniczające wykorzystuje propagację i śledzenie wsteczne do rozwiązania problemu 4 queens.
Załóżmy, że rozwiązanie rozpoczyna się od dowolnego umieszczenia królowej w lewym górnym rogu. To swego rodzaju hipoteza; być może okaże się, że nie ma rozwiązania z królową w lewym górnym rogu.
Jakie ograniczenia możemy wprowadzić przy tej hipotezie? Jednym z ograniczeń jest to, że w kolumnie może być tylko jedna królowa (szare X poniżej), a drugi zakaz 2 królowych po tej samej przekątnej (czerwone znaki X poniżej).
Trzecie ograniczenie nie zezwala na królowe w tym samym rzędzie:
Nasze ograniczenia zostały rozpowszechnione, możemy przetestować kolejną hipotezę i umieścić drugą królową na jednym z pozostałych dostępnych kwadratów. Rozwiązanie może np. umieścić w nim pierwszy dostępny kwadrat w drugiej kolumnie:
Po propagowaniu ograniczenia po przekątnej widzimy, że w trzeciej lub ostatnim wierszu nie ma dostępnych kwadratów:
Na tym etapie nie możemy znaleźć żadnych rozwiązań, więc musimy się wycofać. Rozwiązanie może np. wybrać inny dostępny kwadrat w drugiej kolumnie. Jednak na skutek propagacji ograniczeń królowa umieszcza się w drugim wierszu trzeciej kolumny, nie pozostawiając przy tym żadnych miejsc dla czwartej królowej:
Rozwiązanie musi więc wrócić do początku, tym razem aż do miejsca, w którym znajdowała się pierwsza królowa. Pokazaliśmy, że żadne rozwiązanie problemu królowych nie zajmie narożnego placu.
W rogu nie ma królowej, więc rozwiązanie przesuwa pierwszą królową w dół o kolejną i rozpowszechnia się, pozostawiając tylko jedno miejsce dla drugiej królowej:
Z kolei powtórna propagacja ujawnia już tylko jedno miejsce dla trzeciej królowej:
O czwartą i ostatnią królową:
Mamy pierwsze rozwiązanie! Gdybyśmy poprosili nas, żeby przestał po znalezieniu pierwszego rozwiązania, działanie zakończyło się tutaj. W przeciwnym razie śledzenie zostałoby ponowione i w pierwszej kolejności umieszczane byłyby pierwszą królową w trzecim rzędzie pierwszej kolumny.
Rozwiązanie wykorzystujące CP-SAT
Zadanie N-queens idealnie nadaje się do ograniczania programowania. W tej sekcji omówimy krótki program w Pythonie, który korzysta z funkcji rozwiązania CP-SAT do znalezienia wszystkich rozwiązań tego problemu.
Zaimportuj biblioteki
Poniższy kod importuje wymaganą bibliotekę.
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;
Deklarowanie modelu
Poniższy kod deklaruje model CP-SAT.
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()}"); } }
Tworzenie zmiennych
Zmienne tworzy tablica o nazwie 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}"); }
Zakładamy, że queens[j]
to numer wiersza królowej w kolumnie j
.
Oznacza to, że queens[j] = i
oznacza, że w wierszu i
i w kolumnie j
jest królowa.
Tworzenie ograniczeń
Oto kod, który tworzy ograniczenia tego problemu.
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);
Kod używa metody AddAllDifferent
, która wymaga, aby wszystkie elementy tablicy zmiennej były różne.
Zobaczmy, w jaki sposób te ograniczenia spełniają 3 warunki problemu N-queens (queens w różnych rzędach, kolumnach i po przekątnych).
Każda królowa w jednym rzędzie
Zastosowanie do metody queens
metody AllDifferent
rozwiązania wymusza, aby wartości queens[j]
były różne w przypadku każdego elementu j
, co oznacza, że wszystkie królowe muszą znajdować się w różnych wierszach.
Żadne dwie królowe w tej samej kolumnie
To ograniczenie znajduje się w definicji elementu queens
.
Ponieważ 2 elementy właściwości queens
nie mogą mieć tego samego indeksu, dwie królowe nie mogą znajdować się w tej samej kolumnie.
Żadne dwie królowe po tej samej przekątnej
Ograniczenie po przekątnej jest nieco trudniejsze niż w przypadku ograniczeń dotyczących wierszy i kolumn. Po pierwsze, jeśli dwie królowe leżą po tej samej przekątnej, musi być spełniony jeden z tych warunków:
- Każda z dwóch królowej ma taki sam numer wiersza i numer kolumny.
Oznacza to, że
queens(j) + j
ma tę samą wartość dla 2 różnych indeksówj
. - Liczba wierszy pomniejszona o numer kolumny dla każdej z dwóch królowej jest taka sama.
W tym przypadku
queens(j) - j
ma tę samą wartość dla dwóch różnych indeksówj
.
Jeden z tych warunków oznacza, że królowe leżą na tej samej przekątnej w górę (od lewej do prawej), a drugi po tej samej przekątnej malejącej. To, który warunek odpowiada rosnącej, a która malejącej, zależy od kolejności wierszy i kolumn. Jak wspomnieliśmy w poprzedniej sekcji, kolejność nie ma wpływu na zestaw rozwiązań, a jedynie na sposób ich wizualizacji.
Ograniczenie po przekątnej oznacza, że wartości queens(j) + j
muszą być różne, a wartości queens(j) - j
muszą być różne w przypadku różnych elementów j
.
Aby zastosować metodę AddAllDifferent
do metody queens(j) + j
, umieszczamy N wystąpień zmiennej (j
, od 0
do N-1
) w tablicy diag1
w ten sposób:
q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i) diag1.append(q1) model.Add(q1 == queens[j] + j)
Następnie stosujemy AddAllDifferent
do diag1
.
model.AddAllDifferent(diag1)
Ograniczenie dla zasobu queens(j) - j
jest tworzone w podobny sposób.
Tworzenie drukarki rozwiązań
Aby wydrukować wszystkie rozwiązania problemu N-queens, musisz przekazać wywołanie zwrotne (tzw. drukarkę rozwiązań) do rozwiązania CP-SAT. Wywołanie zwrotne wydrukuje każde nowe rozwiązanie, gdy je znajdzie. Poniższy kod tworzy drukarkę rozwiązań.
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_; }
Pamiętaj, że drukarka rozwiązań musi być napisana jako klasa Pythona ze względu na interfejs w Pythonie w przypadku odpowiedniego rozwiązania C++.
Rozwiązania są wydrukowane w drukarce rozwiązań za pomocą poniższych wierszy.
for v in self.__variables: print('%s = %i' % (v, self.Value(v)), end = ' ')
W tym przykładzie self.__variables
to zmienna queens
, a każdy element v
odpowiada jednemu z 8 wpisów w tabeli queens
. Powoduje to wydrukowanie rozwiązania w takiej postaci: x0 = queens(0) x1 = queens(1) ... x7 = queens(7)
, gdzie xi
to numer kolumny królowej w wierszu i
.
Następna sekcja zawiera przykład rozwiązania.
Wywoływanie rozwiązania i wyświetlanie wyników
Poniższy kod uruchamia funkcję i wyświetla rozwiązania.
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);
Program znajduje 92 różne rozwiązania do planszy 8 x 8. Oto pierwszy.
Q _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ ...91 other solutions displayed... Solutions found: 92
Aby rozwiązać zadanie dotyczące tablicy o innym rozmiarze, wpisz N jako argument wiersza poleceń. Jeśli na przykład program nazywa się queens
, usługa python nqueens_sat.py 6
rozwiązuje problem z planszą 6 x 6.
Cały program
Oto cały program N-queens.
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()}"); } }
Rozwiązanie korzystające z pierwotnego rozwiązania CP
Poniższe sekcje przedstawiają program w Pythonie, który rozwiązuje n-queens przy użyciu oryginalnego rozwiązania CP. Zalecamy jednak korzystanie z nowszego narzędzia do rozwiązywania problemów z CP-SAT.
Zaimportuj biblioteki
Poniższy kod importuje wymaganą bibliotekę.
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;
Deklarowanie rozwiązania
Poniższy kod deklaruje oryginalne rozwiązanie CP.
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");
Tworzenie zmiennych
Metoda IntVar
rozwiązania tworzy zmienne zadania w postaci tablicy o nazwie 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}"); }
W każdym rozwiązaniu queens[j] = i
oznacza, że w kolumnie j
i w wierszu i
występuje królowa.
Tworzenie ograniczeń
Oto kod, który tworzy ograniczenia tego problemu.
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());
Te ograniczenia gwarantują 3 warunki zadania N-queens (Królowe w różnych wierszach, kolumnach i po przekątnych).
Każda królowa w jednym rzędzie
Zastosowanie do metody queens
metody AllDifferent
rozwiązania wymusza, aby wartości queens[j]
były różne w przypadku każdego elementu j
, co oznacza, że wszystkie królowe muszą znajdować się w różnych wierszach.
Żadne dwie królowe w tej samej kolumnie
To ograniczenie znajduje się w definicji elementu queens
.
Ponieważ 2 elementy właściwości queens
nie mogą mieć tego samego indeksu, dwie królowe nie mogą znajdować się w tej samej kolumnie.
Żadne dwie królowe po tej samej przekątnej
Ograniczenie po przekątnej jest nieco trudniejsze niż w przypadku ograniczeń dotyczących wierszy i kolumn. Po pierwsze, jeśli dwie królowe leżą po tej samej przekątnej, musi być spełniony jeden z tych warunków:
- Jeśli przekątna jest malejąco (od lewej do prawej), obie te 2 królowe mają równe numery wierszy i numerów kolumn. Zatem
queens(i) + i
ma tę samą wartość dla dwóch różnych indeksówi
. - Jeśli przekątna jest rosnąca, liczba wierszy pomniejszona o numer kolumny każdej z dwóch królowych jest taka sama. W tym przypadku
queens(i) - i
ma tę samą wartość dla dwóch różnych indeksówi
.
Zatem ograniczenie po przekątnej polega na tym, że wartości queens(i) + i
muszą być różne, podobnie jak wartości queens(i) - i
dla różnych elementów i
.
Powyższy kod dodaje to ograniczenie, stosując metodę AllDifferent
do queens[j] + j
i queens[j] - j
dla każdego elementu i
.
Dodawanie kreatora decyzji
Kolejnym krokiem jest utworzenie kreatora decyzji, który będzie określać strategię wyszukiwania dla danego problemu. Strategia wyszukiwania może mieć duży wpływ na czas wyszukiwania ze względu na propagację ograniczeń, co zmniejsza liczbę wartości zmiennych, które musi zbadać rozwiązanie. Wiedzieliśmy już o tym w przykładzie 4-queens.
Ten kod tworzy konstruktor decyzji za pomocą metody Phase
rozwiązania.
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);
Więcej informacji o argumentach wejściowych do metody Phase
znajdziesz w artykule Narzędzie do podejmowania decyzji.
Jak działa kreator decyzji w przykładzie z 4 queens
Przyjrzyjmy się, w jaki sposób kreator decyzji kieruje wyszukiwanie w przykładzie z 4 queens.
Rozwiązanie rozpoczyna się od queens[0]
, pierwszej zmiennej w tablicy, zgodnie z dyrektywą CHOOSE_FIRST_UNBOUND
. Rozwiązanie przypisuje do funkcji queens[0]
najmniejszą wartość, która nie została jeszcze wypróbowana, czyli 0 na tym etapie, zgodnie z instrukcjami ASSIGN_MIN_VALUE
. Pierwsza królowa umieszcza się w lewym górnym rogu planszy.
Następnie rozwiązanie wybiera zmienną queens[1]
, która jest teraz pierwszą niepowiązaną zmienną w tabeli queens
. Po rozpowszechnieniu ograniczeń w przypadku królowej w kolumnie 1 dostępne są 2 wiersze: wiersz 2 lub wiersz 3. Opcja ASSIGN_MIN_VALUE
instruuje osobę wykonującą rozwiązanie do przypisania queens[1] = 2
. Jeśli zamiast tego ustawisz IntValueStrategy
na ASSIGN_MAX_VALUE
, rozwiązanie do rozwiązywania problemów przypisze wartość queens[1] = 3
.
Możesz sprawdzić, czy pozostała część wyszukiwania działa zgodnie z tymi samymi regułami.
Wywoływanie rozwiązania i wyświetlanie wyników
Poniższy kod uruchamia funkcję, która ją wyświetla.
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();
Oto pierwsze znalezione przez program rozwiązanie dotyczące tablicy 8 x 8.
Q _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ ...91 other solutions displayed... Statistics failures: 304 branches: 790 wall time: 5 ms Solutions found: 92
Aby rozwiązać zadanie dotyczące tablicy o innym rozmiarze, wpisz N jako argument wiersza poleceń. Na przykład python nqueens_cp.py 6
rozwiązuje problem z płytką 6 x 6.
Cały program
Pełny program znajdziesz poniżej.
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}"); } }
Liczba rozwiązań
Liczba rozwiązań rośnie mniej więcej wykładniczo wraz z rozmiarem planszy:
Rozmiar planszy | Rozwiązania | Czas znalezienia wszystkich rozwiązań (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 |
Wiele rozwiązań to po prostu obrócenia innych, a technikę zwaną rozdrabnianiem symetrii można wykorzystać, aby zmniejszyć ilość niezbędnych obliczeń. Nie korzystamy z tego tutaj. Rozwiązanie powyżej nie jest tak szybkie, a jedynie proste. Oczywiście moglibyśmy zrobić to znacznie szybciej, gdybyśmy potrzebowali tylko jednego rozwiązania zamiast wszystkich: kilku milisekund w przypadku płyt o rozmiarach do 50.