在接下來的各節中，我們將根據西洋棋遊戲，說明組合性問題的限制 (CP)。象棋中可以水平、垂直和對角線進行攻擊。N 女王問題詢問：
如何將 NxN 皇后放在 NxN 棋盤上，讓對方不會互相攻擊？
下方則是「N = 4」的 N Quens 問題其中一種可能的解決方案。
同一列、欄或對角線沒有任何雙皇。
請注意，這並非最佳化問題：我們是想找出所有可能的解決方案，而不是一個最佳解決方案，那麼這正是限製程式設計的自然做法。以下各節說明使用 CP-SAT 解析器和原始 CP-SAT 解題工具解決 CP-SAT 問題的程式。
民生消費用品業的前瞻性問題
CP 解題工具的運作方式是，嘗試嘗試為問題中的變數指派所有可能的值，找出可行的解決方案。在 4 大問題中，解題器會從最左邊的欄開始，並在各欄中連續將一個女王放在原本不會被任何之前加持的那一隻皇后。
傳播與反向追蹤
限製程式設計搜尋包含兩個關鍵元素：
- 傳播 — 每次解題工具指派一個值給變數時，限制會為未指派的變數加入限制。這些限制會傳播到日後的變數指派作業。舉例來說，在問題中，每題有 4 隻皇后，每得一個皇后，都會不能在資料列上放置任何其他雙人，目前該女王所在的對角線也都無效。傳播工具可以減少解題工具必須探索的變數值組合，進而大幅加快搜尋速度。
- 當解題工具因限製而無法將值指派給下一個變數或找到解決方案時，即會發生「反向追蹤」。無論是哪一種情況，解方倒數都會回到前一個階段，並將該階段的變數值變更為尚未嘗試的值。在 4 吋的範例中，這表示將皇后移到目前資料欄的新正方形。
接下來，您會看到限製程式設計如何使用傳播和回溯追蹤功能，來解決 4 大問題。
假設解題工具從左上方角落放置一隻皇后，這是有點假設：若左上角有天王，或許就會發現沒有任何解決方案。
基於上述假設，我們可以套用哪些限制？其中一個限制是欄中只能有一個皇后 (下方灰色 X)，而另一個限制會禁止同一對角上的兩隻皇后 (下方紅色 X)。
我們的第三個限制禁止同一列的女王：
套用的限制後，我們可進行另一項假設，並在剩餘的其中一個可用正方形上放置第二個加讓使用者。我們的解題工具可能會決定將其放在第二欄的第一個可用的正方形中：
傳播對角線限制條件後，可以看到第三欄或最後一列沒有任何可用的正方形：
如果目前無法提供解決方案，我們就必須反向追蹤。其中一個選項是解題工具在第二欄中選擇其他可用的正方形。但是，限制條件傳播後，會強制將雙人加入第三欄的第二列，使第四位皇后沒有有效的位置：
因此，解題工具必須再次軌道，這次會回到第一個皇后的位子。我們目前發現，女王問題無法佔據圓角正方形。
由於在角落裡沒有任何女王，因此解題工具會把第一個女王拿下 1，然後傳播，只留下一個位置給第二個女王：
再次傳播後，只會出現剩下的第三個領袖上點：
然後是第四隻以及最後一個女王：
我們為您提供了第一個解決方案！如果我們在找到第一個解決方案後指示解題工具 就會從這裡結束否則，系統會再次反向軌跡，並將第一個女王放在第一欄的第三列。
使用 CP-SAT 的解決方案
N-queens 問題最適合用於限製程式設計。在本節中，我們會逐步介紹使用 CP-SAT 解題工具的簡易 Python 程式，找出問題的所有解決方案。
匯入程式庫
下列程式碼會匯入必要的程式庫。
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-queens 問題能滿足三個條件 (亦即代表不同資料列、資料欄和對角線)。
同一排沒有兩隻皇后
將解題工具的 AllDifferent 方法套用至 queens 會強制每個 j 的 queens[j] 值都不同，也就是說所有鏡頭都必須位於不同資料列。
同一欄中沒有兩隻皇后
這項限制在 queens 的定義中隱含。由於沒有兩個 queens 元素可有相同的索引，因此同一欄中不能出現兩個加大雙引號。
同一對角線沒有兩隻皇后
對角線限制條件有一點比列和欄限制還得簡單。首先，如果兩隻皇后落在同一對角線上，就必須滿足下列其中一項條件：
- 兩者的列號加上前兩個查詢的欄號相等。
換句話說，
queens(j) + j有兩個不同索引j的值相同。 - 資料列編號減去兩個加數的欄數，均相等。
在此範例中，兩個不同索引
j的queens(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 雙王問題的所有解決方案，您需要將名為「解決方案印表機」的回呼傳送至 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 介面，因此解決方案印表機必須編寫為 Python 類別。
解決方案印表機會依下列幾行列出解決方案。
for v in self.__variables:
print('%s = %i' % (v, self.Value(v)), end = ' ')
在這個範例中，self.__variables 是變數 queens，每個 v 都對應於 queens 的八個項目之一。這會以下列格式列印解決方案：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);
這個程式會為一個 8x8 板找到 92 個不同的解決方案。以下是第一項。
Q _ _ _ _ _ _ _
_ _ _ _ _ _ Q _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
...91 other solutions displayed...
Solutions found: 92
您可以用指令列引數的形式傳入 N，藉此解決不同大小的主面板的問題。舉例來說，如果程式的名稱是 queens，python nqueens_sat.py 6 就會解決 6x6 主機板的問題。
整個計畫
這裡提供 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()}");
}
}
使用原始 CP 解析器的解決方案
以下各節說明 Python 程式，使用原始 CP 解析器解決 N-queens。(不過，建議您使用較新的 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的值都相同。 - 如果對角線遞增，則列數減去兩個加數的欄數會相等。在本例中，兩個不同索引
i的queens(i) - i具有相同的值。
因此，對角線的限制是，queens(i) + i 的值必須全部不同，同樣地，不同 i 的 queens(i) - i 值必須全部不同。
上述程式碼會為每個 i 將 AllDifferent 方法套用至 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 個。