N-Kraliçe Sorunu

İlerleyen bölümlerde, satranç oyununa dayalı bir kombinasyon problemini kullanarak kısıtlama programlamasını (CP) göstereceğiz. Satrançta kraliçeler yatay, dikey veya çapraz olarak saldırabilir. N-queens problemi şu soruyu sorar:

N kraliçe, ikisinin birbirine saldırmaması için NxN satranç tahtasına nasıl yerleştirilebilir?

Aşağıda, N = 4 için N-queens problemine olası bir çözüm görebilirsiniz.

Aynı satır, sütun veya köşegende iki vezir yoktur.

Bunun bir optimizasyon sorunu olmadığını unutmayın. Tek bir optimum çözüm yerine, tüm olası çözümleri bulmak isteriz. Bu da söz konusu çözümleri kısıtlama programlaması için doğal bir aday haline getirir. Aşağıdaki bölümlerde N-queens problemine CP yaklaşımı anlatılmakta ve bu problemi hem CP-SAT çözücüyü hem de orijinal CP çözücüyü kullanarak çözen programlar sunulmaktadır.

N-queens problemine CP yaklaşımı

CP çözücü, uygun çözümleri bulmak için bir problemdeki değişkenlere olası tüm değer atamalarını sistematik bir şekilde deneyerek çalışır. 4'lü veli probleminde, çözücü en soldaki sütundan başlar ve her bir sütuna arka arkaya bir tane ve daha önce yerleştirilmiş vezirlerin saldırıya uğramadığı bir yere bir vezir yerleştirir.

Çoğaltma ve geri izleme

Kısıt programlama aramasının iki temel öğesi vardır:

• Çoğaltma: Çözme aracı bir değişkene her değer atadığında kısıtlamalar, atanmamış değişkenlerin olası değerleri üzerinde kısıtlamalar ekler. Bu kısıtlamalar gelecekteki değişken atamalarına yayılır. Örneğin, 4'lü vezir probleminde çözücü, bir vezir yerleştirdiğinde şu anki veziğin bulunduğu satıra ve köşegenlere başka bir vezir yerleştiremez. Yayılım, çözücünün keşfetmesi gereken değişken değer grubunu azaltarak aramayı önemli ölçüde hızlandırabilir.
• Geri izleme, çözücü kısıtlamalar nedeniyle bir sonraki değişkene değer atayamadığında veya bir çözüm bulduğunda gerçekleşir. Her iki durumda da çözücü, önceki aşamaya geri döner ve o aşamadaki değişkenin değerini daha önce denenmemiş bir değerle değiştirir. 4'lü veli örneğinde bu, mevcut sütundaki bir veliyi yeni bir kareye taşımak anlamına gelir.

Ardından, kısıt programlamasının 4-kraliçe problemini çözmek için yayılım ve geri izlemeyi nasıl kullandığını göreceksiniz.

Çözücünün sol üst köşeye rastgele bir şekilde bir veli yerleştirerek başladığını varsayalım. Bu bir çeşit varsayım. Belki de sol üst köşede bir kraliçe yoksa hiçbir çözümün olmadığı ortaya çıkar.

Bu hipoteze dayanarak hangi kısıtlamaların yayılmasını sağlayabiliriz? Bir kısıtlama, bir sütunda yalnızca bir vezir bulunabilmesidir (aşağıdaki gri X'ler), başka bir kısıtlama ise aynı köşegende iki vezir olmasını yasaklar (aşağıdaki kırmızı X'ler).

Üçüncü kısıtlamamız, aynı satırdaki kraliçeleri yasaklar:

Kısıtlamalarımız yayıldı. Başka bir hipotezi test edebilir ve kalan karelerden birine ikinci bir vezir yerleştirebiliriz. Çözme aracımız bunun içine ikinci sütundaki kullanılabilir ilk kareyi yerleştirmeye karar verebilir:

Çapraz kısıtlamayı uyguladıktan sonra, üçüncü sütunda veya son satırda kullanılabilir kare kalmadığını görebiliriz:

Bu aşamada mümkün olan bir çözüm olmadığı için geriye dönük bir yaklaşım izlememiz gerekir. Seçeneklerden biri, çözücünün ikinci sütunda bulunan diğer kareyi seçmesidir. Bununla birlikte, sınırlama yayılması, bir veliyi üçüncü sütunun ikinci satırına zorlayarak dördüncü vezir için geçerli noktalar bırakmaz:

Problem çözme aracı, bu sefer ilk kraliçenin yerleşimine geri dönmek zorunda. Köşedeki karede kraliçelerin sorunu için hiçbir çözüm olamayacağını göstermiş bulunuyoruz.

Köşede vezir olamayacağından, çözücü ilk vezni bir aşağı hareket ettirir ve yayılarak ikinci vezir için yalnızca bir nokta bırakır:

Tekrar çoğaltıldığında üçüncü vezir için yalnızca bir yer kalır:

Dördüncü ve son vezir için:

İlk çözümümüz var. Problem çözme aracımıza ilk çözümü bulduktan sonra durmasını söylesek her şey burada biter. Aksi takdirde, tekrar geri gider ve ilk vezi ilk sütunun üçüncü satırına yerleştirilir.

CP-SAT kullanan çözüm

N-queens problemi en çok kısıt programlamaya uygundur. Bu bölümde, sorunun tüm çözümlerini bulmak için CP-SAT çözücüyü kullanan kısa bir Python programına göz atacağız.

Kitaplıkları içe aktarın

Aşağıdaki kod gerekli kitaplığı içe aktarır.

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;

Modeli bildirin

Aşağıdaki kod CP-SAT modelini tanımlar.

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()}");
    }
}

Değişkenleri oluşturma

Problem çözme aracı, problem için değişkenleri queens adlı bir dizi olarak oluşturur.

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}");
}

Burada queens[j] değerinin, j sütunundaki velizin satır numarası olduğunu varsayıyoruz. Diğer bir deyişle, queens[j] = i, i. satır ve j sütununda bir vezir olduğu anlamına gelir.

Not: Bir çözüm diyagramı çizerken, satırların aşağıdan yukarıya mı yoksa yukarıdan aşağıya mı sıralandığına (ve sütunların soldan sağa veya tersinin mi sıralandığına) bağlı olarak farklı bir resim elde edersiniz. Ancak sıralama, tüm olası çözümleri değil, yalnızca bunların diyagramda temsil edilme şeklini değiştirir.

Kısıtlamaları oluşturma

Problemin kısıtlamalarını oluşturan kodu burada bulabilirsiniz.

Python

# All rows must be different.
model.add_all_different(queens)

# No two queens can be on the same diagonal.
model.add_all_different(queens[i] + i for i in range(board_size))
model.add_all_different(queens[i] - i for i in range(board_size))

C++

// The following sets the constraint that all queens are in different rows.
cp_model.AddAllDifferent(queens);

// No two queens can be on the same diagonal.
std::vector<LinearExpr> diag_1;
diag_1.reserve(board_size);
std::vector<LinearExpr> diag_2;
diag_2.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
  diag_1.push_back(queens[i] + i);
  diag_2.push_back(queens[i] - i);
}
cp_model.AddAllDifferent(diag_1);
cp_model.AddAllDifferent(diag_2);

Java

// All rows must be different.
model.addAllDifferent(queens);

// No two queens can be on the same diagonal.
LinearExpr[] diag1 = new LinearExpr[boardSize];
LinearExpr[] diag2 = new LinearExpr[boardSize];
for (int i = 0; i < boardSize; ++i) {
  diag1[i] = LinearExpr.newBuilder().add(queens[i]).add(i).build();
  diag2[i] = LinearExpr.newBuilder().add(queens[i]).add(-i).build();
}
model.addAllDifferent(diag1);
model.addAllDifferent(diag2);

C#

// All rows must be different.
model.AddAllDifferent(queens);

// No two queens can be on the same diagonal.
LinearExpr[] diag1 = new LinearExpr[BoardSize];
LinearExpr[] diag2 = new LinearExpr[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
    diag1[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/i);
    diag2[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/-i);
}

model.AddAllDifferent(diag1);
model.AddAllDifferent(diag2);

Kod, bir değişken dizisinin tüm öğelerinin farklı olmasını gerektiren AddAllDifferent yöntemini kullanır.

Bu kısıtlamaların, N-queens problemi için (farklı satır, sütun ve köşegenlere sahip kraliçeler) üç koşulu nasıl garanti ettiğini görelim.

Aynı satırda iki vezir yer almaz

Çözme aracının AllDifferent yöntemini queens için uygulamak, queens[j] değerlerini her bir j için farklı olmaya zorlar. Bu, tüm ana sayıların farklı satırlarda olması gerektiği anlamına gelir.

Aynı sütunda iki vezir bulunamaz

Bu kısıtlama, queens tanımında örtülüdür. Hiçbir queens öğesi aynı dizine sahip olamayacağından aynı sütunda iki vezir bulunamaz.

Aynı köşegende iki vezir olamaz

Çapraz sınırlama, satır ve sütun kısıtlamalarından biraz daha karmaşıktır. Öncelikle, iki vezir aynı köşegen üzerinde bulunuyorsa aşağıdaki koşullardan biri doğru olmalıdır:

• İki vezirden her birinin satır numarası ile sütun numarası eşittir. Diğer bir deyişle, queens(j) + j iki farklı dizin için aynı değere sahiptir j.
• İki vezirden her birinin satır numarası ile sütun numarası arasındaki fark eşittir. Bu durumda, queens(j) - j iki farklı dizin j için aynı değere sahiptir.

Bu koşullardan biri, kraliçelerin aynı artan köşegen üzerinde uzanmaları (soldan sağa), diğeri ise aynı azalan köşegen üzerinde uzanmaları anlamına gelir. Hangi koşul artan, hangilerinin azalan düzende karşılık geldiği, satır ve sütunları nasıl düzenlediğinize bağlıdır. Önceki bölümde belirtildiği gibi, sıralamanın çözüm grubu üzerinde herhangi bir etkisi yoktur, yalnızca bunları nasıl görselleştirdiğiniz üzerinde etkisi yoktur.

Dolayısıyla, çapraz sınırlama, farklı j için queens(j) + j değerlerinin tamamının farklı olması ve queens(j) - j değerlerinin tamamının farklı olması gerektiğidir.

AddAllDifferent yöntemini queens(j) + j alanına uygulamak amacıyla, j için 0 ile N-1 aralığındaki N örneğini aşağıdaki şekilde diag1 dizisine yerleştirdik:

q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i)
diag1.append(q1)
model.Add(q1 == queens[j] + j)

Ardından diag1 için AddAllDifferent uygularız.

model.AddAllDifferent(diag1)

queens(j) - j kısıtlaması benzer şekilde oluşturulur.

Bir çözüm yazıcısı oluşturun

N-queens probleminin tüm çözümlerini yazdırmak için CP-SAT çözücüye çözüm yazıcısı adı verilen bir geri arama iletmeniz gerekir. Geri çağırma, çözücü tarafından bulunan her bir yeni çözümü yazdırır. Aşağıdaki kod bir çözüm yazıcısı oluşturur.

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_;
}

Temel C++ çözücüdeki Python arayüzü nedeniyle çözüm yazıcısının Python sınıfı olarak yazılması gerektiğini unutmayın.

Çözümler, çözüm yazıcısında aşağıdaki satırlarla yazdırılır.

for v in self.__variables:
print('%s = %i' % (v, self.Value(v)), end = ' ')

Bu örnekte self.__variables, queens değişkenidir ve her v, queens öğesinin sekiz girişinden birine karşılık gelir. Aşağıdaki biçimde bir çözüm yazdırılır: x0 = queens(0) x1 = queens(1) ... x7 = queens(7) burada xi, i numaralı satırdaki veli sütun numarasıdır.

Sonraki bölümde bir çözüm örneği gösterilmektedir.

Çözücüyü çağırma ve sonuçları görüntüleme

Aşağıdaki kod çözücüyü çalıştırır ve çözümleri gösterir.

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);

Programda 8x8 boyutunda bir beyaz tahta için 92 farklı çözüm bulunur. İşte ilki.

        Q _ _ _ _ _ _ _
        _ _ _ _ _ _ Q _
        _ _ _ _ Q _ _ _
        _ _ _ _ _ _ _ Q
        _ Q _ _ _ _ _ _
        _ _ _ Q _ _ _ _
        _ _ _ _ _ Q _ _
        _ _ Q _ _ _ _ _
        ...91 other solutions displayed...
        Solutions found: 92

Farklı boyuttaki bir panoyla ilgili problemi, komut satırı bağımsız değişkeni olarak N değerini geçirerek çözebilirsiniz. Örneğin, programın adı queens ise python nqueens_sat.py 6, 6x6 tahtası için sorunu çözer.

Programın tamamı

N-queens programının tamamını burada bulabilirsiniz.

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()}");
    }
}

Orijinal CP çözücüyü kullanan çözüm

Aşağıdaki bölümlerde, orijinal CP çözücüyü kullanarak N-queen'leri çözen bir Python programı sunulmaktadır. (Bununla birlikte, yeni CP-SAT çözücüyü kullanmanızı öneririz)

Kitaplıkları içe aktarın

Aşağıdaki kod gerekli kitaplığı içe aktarır.

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;

Çözücüyü bildirme

Aşağıdaki kod orijinal CP çözücüyü tanımlar.

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");

Değişkenleri oluşturma

Çözücünün IntVar yöntemi, problem için değişkenleri queens adlı bir dizi olarak oluşturur.

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}");
}

Herhangi bir çözüm için queens[j] = i, j sütununda ve i satırında bir "üst düzey" olduğu anlamına gelir.

Kısıtlamaları oluşturma

Problemin kısıtlamalarını oluşturan kodu burada bulabilirsiniz.

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());

Bu kısıtlamalar, N-queens problemi için (farklı satır, sütun ve köşegenlerdeki kraliçeler) üç koşulu garanti eder.

Aynı satırda iki vezir yer almaz

Çözme aracının AllDifferent yöntemini queens için uygulamak, queens[j] değerlerini her bir j için farklı olmaya zorlar. Bu, tüm ana sayıların farklı satırlarda olması gerektiği anlamına gelir.

Aynı sütunda iki vezir bulunamaz

Bu kısıtlama, queens tanımında örtülüdür. Hiçbir queens öğesi aynı dizine sahip olamayacağından aynı sütunda iki vezir bulunamaz.

Aynı köşegende iki vezir olamaz

Çapraz sınırlama, satır ve sütun kısıtlamalarından biraz daha karmaşıktır. İlk olarak, iki vezir aynı köşegen üzerinde bulunuyorsa aşağıdakilerden biri doğru olmalıdır:

• Köşeden köşegen azalansa (soldan sağa gidiyorsa) iki vezirden her birinin satır numarası artı sütun numarası eşittir. Dolayısıyla queens(i) + i, iki farklı dizin i için aynı değere sahiptir.
• Köşeden köşegen artan düzendeyse iki vezirden her birinin satır numarası ile sütun numarası arasındaki fark eşittir. Bu durumda queens(i) - i, iki farklı dizin i için aynı değere sahiptir.

Dolayısıyla, çapraz sınırlama, queens(i) + i değerlerinin tamamının farklı olması ve aynı şekilde farklı i için queens(i) - i değerlerinin tamamının farklı olması gerektiğidir.

Yukarıdaki kod, her bir i için queens[j] + j ve queens[j] - j uygulamalarına AllDifferent yöntemini uygulayarak bu kısıtlamayı ekler.

Karar oluşturucuyu ekleme

Sonraki adım, sorun için arama stratejisini belirleyen bir karar oluşturucu oluşturmaktır. Arama stratejisi, kısıtlamaların yayılması nedeniyle arama süresi üzerinde büyük bir etkiye sahip olabilir. Bu da çözücünün keşfetmesi gereken değişken değerlerinin sayısını azaltır. 4-queens örneğinde bunun bir örneğini görebilirsiniz.

Aşağıdaki kod, çözücünün Phase yöntemini kullanarak bir karar oluşturucu oluşturur.

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 yönteminin giriş bağımsız değişkenleriyle ilgili ayrıntılar için Karar oluşturucu bölümüne bakın.

4-kraliçe örneğinde karar oluşturucunun işleyiş şekli

4-queens örneğinde karar oluşturucunun aramayı nasıl yönlendirdiğine göz atalım. Çözme aracı, CHOOSE_FIRST_UNBOUND tarafından belirtildiği gibi dizideki ilk değişken olan queens[0] ile başlar. Daha sonra çözücü, queens[0] değerine henüz denenmemiş en küçük değeri (ASSIGN_MIN_VALUE tarafından belirtildiği gibi bu aşamada 0) atar. Böylece ilk vezir, tahtanın sol üst köşesine yerleştirir.

Daha sonra çözücü, queens nesnesindeki ilk bağlantısı kaldırılan değişken olan queens[1]'yi seçer. Kısıtlamalar uygulandıktan sonra, 1. sütundaki bir vezir için iki olası satır bulunur: 2. satır veya 3. satır. ASSIGN_MIN_VALUE seçeneği, çözücüyü queens[1] = 2 atamasına yönlendirir. (Bunun yerine IntValueStrategy değerini ASSIGN_MAX_VALUE olarak ayarlarsanız çözücü queens[1] = 3 değerini atar.)

Aramanın geri kalanının aynı kuralları izleyip izlemediğini kontrol edebilirsiniz.

Çözücüyü çağırma ve sonuçları görüntüleme

Aşağıdaki kod çözücüyü çalıştırır ve çözümü gösterir.

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();

Programın 8x8'lik bir beyaz tahta için bulduğu ilk çözümü burada bulabilirsiniz.

        Q _ _ _ _ _ _ _
        _ _ _ _ _ _ Q _
        _ _ _ _ Q _ _ _
        _ _ _ _ _ _ _ Q
        _ Q _ _ _ _ _ _
        _ _ _ Q _ _ _ _
        _ _ _ _ _ Q _ _
        _ _ Q _ _ _ _ _
        ...91 other solutions displayed...
        Statistics
        failures: 304
        branches: 790
        wall time: 5 ms
        Solutions found: 92

Farklı boyuttaki bir panoyla ilgili problemi, komut satırı bağımsız değişkeni olarak N değerini geçirerek çözebilirsiniz. Örneğin, python nqueens_cp.py 6, 6x6 bir beyaz tahta için sorunu çözer.

Programın tamamı

Programın tamamı aşağıda gösterilmektedir.

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}");
    }
}

Çözüm sayısı

Çözümlerin sayısı, panonun boyutuna göre kabaca katlanarak artar:

Pano boyutu	Çözümler	Tüm çözümleri bulma süresi (ms)
1	1	0
2	0	0
3	0	0
4	2	0
5	10	0
6	4	0
7	40	3
8	92	9
9	352	35
10	724	95
11	2680	378
12	14200	2198
13	73712	11628
14	365596	62427
15	2279184	410701

Birçok çözüm yalnızca diğer çözümlerin döndürülmesinden ibarettir ve gereken hesaplama miktarını azaltmak için simetri kırma adı verilen bir teknik kullanılabilir. Burada bunu kullanmıyoruz; yukarıdaki çözümümüzün hızlı olması değil, basit olması amaçlanmıştır. Elbette, tümü yerine tek bir çözüm bulmak isteseydik çok daha hızlı yapabiliriz. Bu çözüm, 50'ye kadar olan kart boyutları için birkaç milisaniyeden fazla olmamalıdır.