以下各節將說明限製程式設計 (CP) 以西洋棋遊戲為主軸的組合問題。皇后在棋子中發動攻擊 水平、垂直和對角線符合 N 個女王的問題會問：
如何將 N 酷兒放在 NxN 西洋棋盤上，讓兩人一同攻擊 嗎？
以下是 N = 4 的 N 個求助問題解決方案。
同一列、欄或對角線皆沒有兩個天後。
請注意，這並不是最佳化問題：我們希望找出所有可能的 而不是單一最佳解決方案，因此自然是適合 限製程式設計。 以下各節說明解決 N queens 問題的 CP 方法。 提出能同時使用 CP-SAT 解析器和原始 CPP 解決的程式 解開謎題。
解決 N 王朝問題的 CP 方法
CP 解題工具的運作原理是系統嘗試所有 將值對應到問題中的變數，並找出 可行的解決方案在 4 個女王問題中，解題工具會從最左邊開始 然後依序在各欄中填入一位皇后， 並未受到任何先前施加的女王攻擊。
傳播及反向追蹤
限製程式設計搜尋有兩個關鍵元素：
- 傳播 - 每次解題工具將值指派給變數時， 對未指派的可能值設有限制 變數。這些限制會「傳播」至日後的變數指派。 舉例來說，在 4 個女王問題中，解題工具每次給出一人魔王時，就會是 就不能在資料列上放置任何其他皇后，且目前女皇就在對角線上 傳播有助於大幅加快搜尋速度， 可執行解題工具所必須探索的變數值。
- 「反向追蹤」是指解題工具無法為下一個符記指派值的情況 錯誤或尋找解題方式。無論是哪一種情況， 求解工具返回軌跡轉至前一個階段，並在 並將該階段的值改為從未嘗試過的值以 4 個女王為例 也就是將皇后移至目前欄上的新正方形。
接下來，你將看到限製程式設計如何使用傳播和回溯至 就能解決 4 個角的問題
假設解題工具一開始是任意將女王放在左上方 。這樣的假設是但若沒有解決 有皇后，
根據這個假設，我們能傳播哪些限制？其中一項限制是 一個欄中只能有一個皇后 (下面的灰色 X 號)，另一個 限制禁止在同一對角線使用兩段變角 (下圖的紅色 X)。
我們的第三個限制禁止在同一列中加油：
我們對限制條件大有套用， 我們可以測試另一個假設，並在 然後在其中一個可用方格中進行。我們的解題工具可能會 把它放在第二欄中第一個可用的正方形：
傳播對角限制後，我們可以看到 第三欄或最後一列的可用正方形：
在這個階段沒有可用的解決方案，因此我們必須反過來追溯。選項之一 ，讓解題工具在第二欄中選擇另一個可用的正方形。 然而，限制傳播會強制將佇列傳遞至第二列 第三欄，而第四個女王的位都無效：
因此解題工具必須再次向前推 第一女王的位置我們已經證明上述王者沒有解決方案 將出現圓角正方形
由於角落沒有女王，因此解題工具會將第一個女王向下移動 然後傳播給第二位皇后，
再次傳播，只會顯示第三位皇后的剩餘空位：
為第四次與最終女王：
我們有第一個解決方案！假如我們指示解題工具在發現後停止 第一種解決方案就在此結束否則的話 將第一排王后放在第一欄的第三列。
使用 CP-SAT 的解決方案
N 票問題最適合用來限製程式設計。在本 一節，我們會逐步解說一個簡短的 Python 程式，該程式使用 CP-SAT 解析工具 找出問題的所有解決方案。
匯入程式庫
下列程式碼會匯入所需的程式庫。
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;
宣告模型
下列程式碼宣告 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()}"); } }
建立變數
解題工具會建立問題的變數，做為名為 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}"); }
這裡我們假設 queens[j] 是第 j 欄中該女王的資料列編號。
換句話說，queens[j] = i 表示第 i 列和 j 欄都有皇后。
建立限制
以下程式碼會建立問題限制條件。
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);
程式碼使用 AddAllDifferent 方法，此方法需要
變數陣列
我們來看看這些限制條件如何保證 N 個滿足雙贏的三項條件 問題 (會填入不同的列、欄和對角線)。
同一排沒有兩名皇后
將解題工具的 AllDifferent 方法套用到 queens 即可強制
每個 j 的 queens[j] 都不同，這表示所有皇后都必須位於
不同的資料列
同一欄中沒有兩名皇后
這項限制在 queens 的定義中。
由於 queens 的兩個元素不能有相同的索引，因此不能有兩個皇后
。
同一對角線沒有兩名皇后
對角線限制比列和欄限制還小一些。 首先，如果兩名皇后在同一對角線上，請滿足以下其中一項條件 須為 true：
- 兩個天後的列數加上欄號均為相等。
換句話說，
queens(j) + j對兩個不同索引擁有相同的值j。 - 列號減去兩個女王的欄號是相等的。
在這個例子中，
queens(j) - j有兩個不同的索引j值相同。
其中一項條件是指天後在同一對角線 ( 另一個則是依遞減順序排列 例如對角線或斜體字哪個條件對應至遞增，而哪個符合遞減規則 取決於您選擇列與欄的順序。如 上一節，排序不會影響 並以視覺化方式呈現解決方案
因此對角線限制條件是 queens(j) + j 的值必須全部
且 queens(j) - j 的值必須不同，
不同的 j。
為了將 AddAllDifferent 方法套用至 queens(j) + j，我們放入 N 個例項
變數的 j (從 0 到 N-1) 轉換為陣列 diag1，如下所示：
q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i) diag1.append(q1) model.Add(q1 == queens[j] + j)
接著，將 AddAllDifferent 套用至 diag1。
model.AddAllDifferent(diag1)
以類似方式建立 queens(j) - j 的限制。
建立解決方案印表機
如要列印所有 N queens 問題的解決方案，您必須傳遞回呼、 名為「解決方案印表機」的 CP-SAT 解析器。回呼會輸出每個 很新的解決方式下列程式碼建立解決方案 和印表機。
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_; }
請注意，由於 給基礎 C++ 解題器的 Python 介面。
這些解決方案會在解決方案印表機的下列幾行顯示。
for v in self.__variables: print('%s = %i' % (v, self.Value(v)), end = ' ')
在此範例中，self.__variables 是變數 queens，而每個 v
對應了 queens 的 8 個項目之一。這樣會在
下列格式：x0 = queens(0) x1 = queens(1) ... x7 = queens(7)，其中
xi 是第 i 列的皇后欄編號。
下一節是解決方案範例。
呼叫解題工具並顯示結果
下列程式碼會執行解題工具並顯示解決方案。
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);
該計畫找到 92 種適用於 8x8 遊戲板的解題方法。這是第一項。
Q _ _ _ _ _ _ _
_ _ _ _ _ _ Q _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
...91 other solutions displayed...
Solutions found: 92您可以將 N 做為
指令列引數舉例來說，如果程式的名稱是 queens，
python nqueens_sat.py 6 解決了 6x6 遊戲板的問題。
整個計畫
以下是 N 個女王節目的完整節目。
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()}"); } }
使用原始 CP 解析器的解決方案
以下各節將說明使用 原始 CP 解析工具 (但我們建議您使用新版 CP-SAT 解析工具)。
匯入程式庫
下列程式碼會匯入所需的程式庫。
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;
宣告解題工具
下列程式碼會宣告原始 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");
建立變數
解題工具的 IntVar 方法會以陣列建立問題變數
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}"); }
針對任何解，queens[j] = i 表示 j 欄和資料列都有皇后
i。
建立限制
以下程式碼會建立問題限制條件。
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());
這些限制可保證 N 會問題必須符合三種條件 ( 。
同一排沒有兩名皇后
將解題工具的 AllDifferent 方法套用到 queens 即可強制
每個 j 的 queens[j] 都不同，這表示所有皇后都必須位於
不同的資料列
同一欄中沒有兩名皇后
這項限制在 queens 的定義中。
由於 queens 的兩個元素不能有相同的索引，因此不能有兩個皇后
。
同一對角線沒有兩名皇后
對角線限制比列和欄限制還小一些。 首先，如果兩名皇后在同一對角線上，必須符合下列其中一項條件：
- 如果對角線遞減 (從左到右)，列號加上
兩個女王的欄號都是相等的。因此
queens(i) + i具有 兩個不同索引i的值相同。 - 如果對角線遞增，列號減去各列的欄號
兩個皇后相等在本例中，
queens(i) - i的值相同 產生兩個不同的索引i
因此對角線限制條件是 queens(i) + i 的值必須全部
同理，queens(i) - i 的值也必須不同，
不同的 i。
上述程式碼會套用
AllDifferent敬上
為每個 i 編寫 queens[j] + j 和 queens[j] - j 方法。
新增決策者
接著請建立決策工具，設定搜尋廣告策略 以便解決問題這項搜尋策略對於搜尋時間、搜尋時間 都有重大影響 由於限制的傳播，因此可減少變數值的數量 必須探索解題工具您已經在 4 個請求範例。
下列程式碼使用解題工具的
Phase敬上
方法。
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);
詳情請參閱決策建立工具
Phase 方法的輸入引數
決策建立工具在 4 章範例中的運作方式
接著來看看決策者如何引導使用者進行搜尋
4 個請求範例。
解題工具開頭為 queens[0]，也就是陣列中的第一個變數，如方向所示
製作者：CHOOSE_FIRST_UNBOUND。解題工具接著會將最小的 queens[0] 指派給最低值
表示此階段尚未嘗試的值 (目前為 0)，如
ASSIGN_MIN_VALUE。這會導致
資訊。
接著，解題工具會選取 queens[1]，這是現在第一個未繫結變數。
queens。傳播限制條件後，
填入第 1 列：第 2 列或第 3 列。ASSIGN_MIN_VALUE 選項會將
來指派 queens[1] = 2 的解題工具。(如果您將 IntValueStrategy 設為
ASSIGN_MAX_VALUE，解題工具會指派 queens[1] = 3)。
您可以檢查其他搜尋作業是否遵循相同的規則。
呼叫解題工具並顯示結果
下列程式碼會執行解題工具並顯示解決方案。
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();
以下是本程式為 8x8 遊戲板找到的第一個解決方案。
Q _ _ _ _ _ _ _
_ _ _ _ _ _ Q _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
...91 other solutions displayed...
Statistics
failures: 304
branches: 790
wall time: 5 ms
Solutions found: 92您可以將 N 做為
指令列引數舉例來說，python nqueens_cp.py 6 可以解決問題
安裝在 6x6 主機板上
整個計畫
完整計畫如下所示。
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}"); } }
解決方案數量
溶液的數量大致上會大幅增長：
| 主面板大小 | 解決方案 | 尋找所有解決方案的時間 (毫秒) |
|---|---|---|
| 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 |
許多解法都只是轉動其他解決方法，並且稱為對稱技術 以減少所需的運算量不使用 在這裡上述解決方案的訴求不是快速簡單。當然 我們就能更快速地找到解決方案 全部數秒內，遊戲板大小最多 50 毫秒就不要超過數毫秒。