N クイーン問題

以下のセクションでは、チェスゲームに基づく組み合わせ問題による制約プログラミング（CP）について説明します。チェスではクイーンが横方向、縦方向、 対角方向に攻撃できますN クイーンズ問題は問いかけます。

NxN のチェス盤に N 匹のクイーンを置いて、2 匹が互いに攻撃しないようにするにはどうすればよいでしょうか。

下の図は、N = 4 の場合の N クイーンズ問題の解法の一例です。

解決策

同じ行、列、対角線上にクイーンが 2 人ずついない。

これは最適化の問題ではありません。最適な解を 1 つではなく、考えられるすべての解決策を見つけることが制約プログラミングの当然の候補となります。以下のセクションでは、N クイーン問題に対する CP のアプローチについて説明し、CP-SAT ソルバーと元の CP ソルバーの両方を使用して CP を解くプログラムを紹介します。

N クイーン問題への CP アプローチ

CP ソルバーは、問題内の変数に対するすべての値を代入しようと体系的に試み、実行可能な解を見つけます。4 クイーン問題では、解法は左端の列から開始し、それまでに配置されたクイーンによって攻撃されていない位置で、各列にクイーン 1 人を連続して配置します。

伝播とバックトラッキング

制約プログラミング検索には、次の 2 つの重要な要素があります。

  • 伝播 - ソルバーが変数に値を代入するたびに、制約によって、割り当てられていない変数の有効な値に対する制限が追加されます。こうした制限は、将来の変数割り当てにも反映されます。たとえば、4 クイーン問題では、解法がクイーンを配置するたびに、現在のクイーンと対角線上に他のクイーンを配置できません。伝播により、ソルバーが探索する必要がある変数値のセットが減るため、検索を大幅に高速化できます。
  • バックトラッキングは、制約のために解法が次の変数に値を割り当てられない場合、または解を見つけた場合に発生します。いずれの場合も、ソルバーは前のステージにバックトラックを行い、そのステージの変数の値をまだ試行されていない値に変更します。4-クイーンサイズの例では、現在の列の新しい正方形にクイーンを移動します。

次に、制約プログラミングで伝播とバックトラックを使用して 4 クイーンの問題を解決する方法を見ていきます。

解法では、左上隅にクイーンを任意に配置するとします。これは一種の仮説であり、左上隅の女王がいるだけでは解法が存在できないということになるかもしれません。

この仮説の場合、どのような制約を伝播できるでしょうか。1 つの制約として、1 列に 1 つのクイーンのみ（下のグレーの X）と、2 つのクイーンが同じ対角線上に配置することを禁止しています（下の赤い X）。

伝播の最初のステップ

3 つ目の制約では、同じ行でクイーンを獲得することを禁止しています。

プロセスの 2 番目のステップ

制約が伝播したら、別の仮説を検証し、使用可能な残りの正方形のいずれかに 2 番目のクイーンを配置できます。その場合、解法により、2 列目の使用可能な最初の正方形に配置するようにします。

プロパゲーションの第 3 ステップ

対角線制約を伝播すると、3 列目または最後の行のどちらにも使用可能な正方形が残っていないことがわかります。

伝播の 4 つ目のステップ

現段階では解決策を見出せないため、後戻りする必要があります。選択肢の 1 つとして、解法は 2 番目の列で使用可能な他の正方形を選択します。ただし、制約の伝播により、クイーンは 3 列目の 2 行目に強制され、4 番目のクイーンには有効なスポットが残りません。

結果の 6 番目のステップ

したがって、解法は再び逆戻りしなければならず、今度は最初の女王の場所まで遡ります。私たちは今、クイーンズの問題の解法が角の四角に占めることはないということが明らかになりました。

隅にはクイーンがいないため、ソルバーは最初のクイーンを 1 つ下げて伝播し、2 番目のクイーンには 1 つのスポットだけを残します。

伝播の 9 番目のステップ

再び伝播すると、3 番目のクイーンたちについて残るところが 1 つあることが明らかになります。

伝播の 10 番目のステップ

最後の 4 番目のクイーン:

伝播の 12 ステップ

最初の解決策があります。最初の解を見つけた後に止めるように解法を指示すると、ここで終了します。それ以外の場合は、再びバックトラックを行い、最初のクイーンが最初の列の 3 行目に配置されます。

CP-SAT を使用したソリューション

N クイーン問題は、理想的には制約プログラミングに適しているこのセクションでは、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 クイーン問題（異なる行、列、対角線でのクイーン）の 3 つの条件を保証する様子を見てみましょう。

同じ列に並ぶクイーンは 2 人いない

ソルバーの AllDifferent メソッドを queens に適用すると、queens[j] の値が j ごとに異なるようになります。つまり、すべてのクイーンが異なる行に存在する必要があります。

同じ列にクイーン以外の人物が 2 人もいない

この制約は、queens の定義で暗黙的に指定されます。 queens の 2 つの要素が同じインデックスを持つことはできないため、同じ列に 2 つのクイーンを含めることはできません。

同じ対角線上にクイーンが 2 人いない

対角線の制約は、行や列の制約よりもやや複雑です。まず、2 人のクイーンが同じ対角線上に横たわっている場合は、次のいずれかの条件を満たす必要があります。

  • 2 つのクイーンのそれぞれの行番号と列番号は同じです。 つまり、queens(j) + j は 2 つの異なるインデックス j に対して同じ値を持ちます。
  • 2 つのクイーンそれぞれの行番号から列番号を引いた値は同じです。 この場合、queens(j) - j は 2 つの異なるインデックス j に対して同じ値を持ちます。

一方は、クイーンたちが同じ斜め上向き（左から右へ向かって）にあり、もう一方は同じ斜め下向きにあることを意味します。どちらの条件が昇順に対応し、どの条件が降順に対応するかは、行と列の順番によって異なります。前のセクションで説明したように、順序はソリューションのセットには影響せず、可視化方法にのみ影響します。

したがって、対角線上の制約では、j が異なると、queens(j) + j の値はすべて異なっている必要があり、queens(j) - j の値はすべて異なっている必要があります。

AddAllDifferent メソッドを queens(j) + j に適用するには、次のように、変数の N 個のインスタンス（0 から N-1 までの j）を配列 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 の 8 つのエントリの 1 つに対応しています。これにより、解答が 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 ソルバーを使用する解答

以下のセクションでは、元の CP ソルバーを使用して N クイーンズを解決する Python プログラムを示します。（ただし、新しい 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 クイーン問題に対する 3 つの条件（異なる行、列、対角線でのクイーンなど）が保証されます。

同じ列に並ぶクイーンは 2 人いない

ソルバーの AllDifferent メソッドを queens に適用すると、queens[j] の値が j ごとに異なるようになります。つまり、すべてのクイーンが異なる行に存在する必要があります。

同じ列にクイーン以外の人物が 2 人もいない

この制約は、queens の定義で暗黙的に指定されます。 queens の 2 つの要素が同じインデックスを持つことはできないため、同じ列に 2 つのクイーンを含めることはできません。

同じ対角線上にクイーンが 2 人いない

対角線の制約は、行や列の制約よりもやや複雑です。まず、2 人の女王が同じ対角線上に横たわっている場合は、次のいずれかに該当する必要があります。

  • 対角線が降順（左から右に行く）の場合、2 つのクイーンズのそれぞれの行番号と列番号が同じになります。したがって、queens(i) + i は 2 つの異なるインデックス i に対して同じ値を持ちます。
  • 対角線が昇順の場合、2 つのクイーンズのそれぞれの行番号から列番号を引いた値は同じになります。この場合、queens(i) - i は 2 つの異なるインデックス i に対して同じ値を持ちます。

したがって、対角線上の制約では、i が異なると、queens(i) + i の値はすべて異なっている必要があり、同様に queens(i) - i の値もすべて異なっていなければなりません。

上記のコードでは、i ごとに AllDifferent メソッドを queens[j]&nbsp;+&nbsp;j と queens[j]&nbsp;-&nbsp;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-Quens サンプルで、意思決定ビルダーがどのように検索を指示するかを見てみましょう。ソルバーは、CHOOSE_FIRST_UNBOUND によって指示されるように、配列の最初の変数である queens[0] で始まります。次に、ソルバーは queens[0] に、まだ試行されていない最小値（ASSIGN_MIN_VALUE で指定されているとおり、この段階では 0）を割り当てます。これにより、最初のクイーンがボードの左上に配置されます。

次に、ソルバーは queens[1] を選択します。これは、queens の最初のバインドされていない変数です。制約を伝播すると、列 1 のクイーンに対して行 2 と行 3 の 2 つの行が存在することになります。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}");
    }
}

ソリューションの数

ソリューションの数は、ボードの規模に応じてほぼ指数関数的に増加します。

ボードサイズソリューションすべての解を見つけるまでの時間（ミリ秒）
110
200
300
420
5100
640
7403
8929
935235
1072495
112680378
12142002198
137371211628
1436559662427
152279184410701

多くの解決策は単なる回転であり、対称性の解除と呼ばれる手法を使用すると、必要な計算量を削減できます。ここでは使用しません。上記のソリューションは高速にするためのものではありません。もちろん、ボードサイズ 50 までのボードサイズを数ミリ秒以内に抑えて、すべてのソリューションではなく 1 つのソリューションのみを見つけたい場合、はるかに高速になります。