مشكلة كوينز-ن

في الأقسام التالية، سنوضح البرمجة المقيدة (CP) من خلال مشكلة اتحادية تستند إلى لعبة الشطرنج. في لعبة الشطرنج، يمكن للملكة الهجوم أفقيًا وعموديًا وقطريًا. تسأل مشكلة N-queens:

كيف يمكن وضع N Queens على لوح شطرنج NxN بحيث لا يهاجم اثنان منهم بعضهما البعض؟

أدناه، يمكنك رؤية حل واحد ممكن لمشكلة N-queens لـ N = 4.

لا توجد ملكتان في نفس الصف أو العمود أو القطر.

لاحظ أن هذه ليست مشكلة متعلقة بالتحسين: نريد العثور على جميع الحلول الممكنة، بدلاً من حل واحد مثالي، مما يجعله مرشحًا طبيعيًا للبرمجة المقيدة. تصف الأقسام التالية نهج CP لمشكلة N-queens، وتقدّم البرامج التي تحلها باستخدام كل من أداة حل CP-SAT والأداة الأصلية لحلول CP-SAT.

نهج CP لمشكلة N-queens

تعمل أداة حلّ CP من خلال إجراء محاولة منهجية لجميع عمليات تحديد القيم الممكنة للمتغيّرات ضمن مسألة، وذلك للعثور على الحلول الممكنة. في مشكلة 4 كوينات، تبدأ أداة الحلّ من العمود الموجود في أقصى اليسار وتضع ملكة واحدة بشكل متتالٍ في كل عمود، في موقع لا تهاجمه أي ملكات تم وضعها سابقًا في السابق.

الانتشار والتتبع

هناك عنصران رئيسيان لبحث برمجة القيد:

• النشر - في كل مرة تعيّن فيها أداة الحلّ قيمة لمتغيّر، تضيف القيود قيودًا على القيم المحتملة للمتغيرات غير المعيّنة. يتم نشر هذه القيود في تعيينات المتغيّرات المستقبلية. على سبيل المثال، في مشكلة 4 كوينات، في كل مرة تضع فيها أداة الحل ملكة، لا يمكن وضع أي ملكات أخرى في الصف والأقطار التي تكون فيها الملكة الحالية عليها. يمكن أن يؤدي الانتشار إلى تسريع عملية البحث بشكل كبير عن طريق تقليل مجموعة القيم المتغيّرة التي يجب على أداة الحلّ استكشافها.
• تحدث عملية تتبُّع التغييرات عندما لا تتمكّن أداة الحلّ من تخصيص قيمة للمتغيّر التالي بسبب القيود أو عندما تعثر على حل. في كلتا الحالتين، يتراجع الخبير عن مرحلة سابقة ويغير قيمة المتغير في تلك المرحلة إلى قيمة لم تجربها بالفعل. في مثال الملكات الأربع، هذا يعني نقل ملكة إلى مربع جديد في العمود الحالي.

بعد ذلك، سترى كيف تستخدم البرمجة المقيدة الانتشار والتتبع العكسي لحل مشكلة 4 كوينات.

لنفترض أنّ أداة الحلّ تبدأ بوضع ملكة بشكل عشوائي في أعلى يسار الشاشة. هذه فرضية من أنواع الفرضيات، وربما يتضح لنا أنه لا يوجد حل مع وجود ملكة في أعلى الجانب الأيسر.

في ضوء هذه الفرضية، ما القيود التي يمكننا تطبيقها؟ أحد القيد هو أنه لا يمكن أن يكون هناك سوى ملكة واحدة في العمود (الأحرف X الرمادية أدناه)، وهناك قيد آخر يمنع ملكتين بنفس القطر (Xs الحمراء أدناه).

القيد الثالث يمنع السيدات من صف واحد:

تم نشر القيود لدينا، ويمكننا اختبار فرضية أخرى، ووضع ملكة ثانية على أحد المربعات المتبقية المتاحة. قد تقرر أداة الحلّ لدينا وضع أول مربع متاح فيه في العمود الثاني:

بعد نشر القيد القطري، يمكننا ملاحظة أنه لا يترك أي مربعات متوفرة في العمود الثالث أو الصف الأخير:

في ظل عدم إيجاد حلول ممكنة في هذه المرحلة، علينا التراجع عن قرارنا. أحد الخيارات هو أن تختار أداة الحلّ المربّع الآخر المتاح في العمود الثاني. ومع ذلك، يفرض انتشار القيد بعد ذلك الملكة في الصف الثاني من العمود الثالث، بدون ترك نقاط صالحة للملكة الرابعة:

وبالتالي، يجب على أداة الحلّ أن تتراجع مرة أخرى، هذه المرة وصولاً إلى موضع الملكة الأولى. لقد أظهرنا الآن أنه لا يوجد حل لمشكلة الملكات يشغل مربعًا عند زاوية.

ونظرًا لعدم إمكانية وجود ملكة في الزاوية، فإن أداة الحلّ تحرك الملكة الأولى لأسفل بمقدار واحد، وينشر، مع ترك مكان واحد فقط للملكة الثانية:

يؤدي التكاثر مرة أخرى إلى ظهور مكان واحد فقط للملكة الثالثة:

وبالنسبة للملكة الرابعة والأخيرة:

لدينا الحل الأول لدينا. إذا وجّهنا أداة الحلّ لدينا إلى التوقف بعد إيجاد الحل الأول، سينتهي الأمر هنا. وإلا، فسيتم التراجع مرة أخرى ووضع الملكة الأولى في الصف الثالث من العمود الأول.

الحلّ باستخدام CP-SAT

تُعد مشكلة N-queens مناسبة بشكل مثالي لقيود البرمجة. سنتناول في هذا القسم برنامجًا قصيرًا في لغة بايثون يستخدم أداة حل CP-SAT للعثور على جميع الحلول للمشكلة.

استيراد المكتبات

يستورد الرمز التالي المكتبة المطلوبة.

Python

import sys
import time
from ortools.sat.python import cp_model

C++

#include <stdlib.h>

#include <sstream>
#include <string>
#include <vector>

#include "absl/strings/numbers.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/sorted_interval_list.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverSolutionCallback;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;

C#

using System;
using Google.OrTools.Sat;

تعريف النموذج

يوضح الرمز التالي نموذج CP-SAT.

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

Java

CpModel model = new CpModel();

C#

        CpModel model = new CpModel();

        int BoardSize = 8;
        // There are `BoardSize` number of variables, one for a queen in each
        // column of the board. The value of each variable is the row that the
        // queen is in.
        IntVar[] queens = new IntVar[BoardSize];
        for (int i = 0; i < BoardSize; ++i)
        {
            queens[i] = model.NewIntVar(0, BoardSize - 1, $"x{i}");
        }

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

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

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

        // Creates a solver and solves the model.
        CpSolver solver = new CpSolver();
        SolutionPrinter cb = new SolutionPrinter(queens);
        // Search for all solutions.
        solver.StringParameters = "enumerate_all_solutions:true";
        // And solve.
        solver.Solve(model, cb);

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts : {solver.NumConflicts()}");
        Console.WriteLine($"  branches  : {solver.NumBranches()}");
        Console.WriteLine($"  wall time : {solver.WallTime()} s");
        Console.WriteLine($"  number of solutions found: {cb.SolutionCount()}");
    }
}

إنشاء المتغيّرات

تنشئ أداة الحلّ متغيّرات المسألة كصفيف باسم queens.

Python

# There are `board_size` number of variables, one for a queen in each column
# of the board. The value of each variable is the row that the queen is in.
queens = [model.new_int_var(0, board_size - 1, f"x_{i}") for i in range(board_size)]

C++

// There are `board_size` number of variables, one for a queen in each column
// of the board. The value of each variable is the row that the queen is in.
std::vector<IntVar> queens;
queens.reserve(board_size);
Domain range(0, board_size - 1);
for (int i = 0; i < board_size; ++i) {
  queens.push_back(
      cp_model.NewIntVar(range).WithName("x" + std::to_string(i)));
}

Java

int boardSize = 8;
// There are `BoardSize` number of variables, one for a queen in each column of the board. The
// value of each variable is the row that the queen is in.
IntVar[] queens = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
  queens[i] = model.newIntVar(0, boardSize - 1, "x" + i);
}

C#

int BoardSize = 8;
// There are `BoardSize` number of variables, one for a queen in each
// column of the board. The value of each variable is the row that the
// queen is in.
IntVar[] queens = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
    queens[i] = model.NewIntVar(0, BoardSize - 1, $"x{i}");
}

نفترض هنا أن queens[j] هو رقم صف الملكة في العمود j. بمعنى آخر، تعني queens[j] = i أن هناك ملكة في الصف i والعمود j.

ملاحظة: عند رسم رسم بياني لأحد الحلول، ستحصل على صورة مختلفة اعتمادًا على ما إذا كان يتم ترتيب الصفوف من أسفل إلى أعلى أو من أعلى إلى أسفل (وما إذا كانت الأعمدة يتم ترتيبها من اليسار إلى اليمين أو العكس). ومع ذلك، لا يغير الترتيب مجموعة جميع الحلول الممكنة، فقط طريقة تمثيلها في الرسم التخطيطي.

وضع القيود

إليك التعليمة البرمجية التي تنشئ قيودًا للمشكلة.

Python

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

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

C++

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

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

Java

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

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

C#

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

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

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

تستخدم التعليمة البرمجية الطريقة AddAllDifferent، والتي تتطلب أن تكون جميع عناصر الصفيف المتغير مختلفة.

لنرى كيف تضمن هذه القيود الشروط الثلاثة لمشكلة N-queens (الملكات في صفوف وأعمدة وأقطار مختلفة).

لا توجد ملكتان في الصف نفسه

في حال تطبيق طريقة AllDifferent الخاصة بأداة الحلّ على queens، يجب أن تكون قيم queens[j] مختلفة لكل j، ما يعني أنّ جميع الملكة يجب أن تكون في صفوف مختلفة.

لا توجد ملكتان في نفس العمود

وهذا القيد ضمني في تعريف queens. بما أنّه لا يمكن أن يكون لعنصران من queens الفهرس نفسه، لا يمكن أن تظهر ملكتان في العمود نفسه.

ما مِن ملكات على القطر نفسه

القيد القطري أصعب قليلاً من قيود الصفوف والعمود. أولاً، إذا وضعت سيدتان على نفس القطر، يجب أن يكون أحد الشروط التالية صحيحًا:

• رقم الصف بالإضافة إلى رقم العمود لكل من الملكتين متساويتان. بمعنى آخر، يحتوي الحقل queens(j) + j على القيمة نفسها لفهرسَين مختلفَين j.
• رقم الصف مطروحًا منه رقم العمود لكل من الملكتين متساوين. في هذه الحالة، تكون القيمة نفسها للدالة queens(j) - j لفهرسين مختلفين j.

أحد هذه الشروط يعني أن الملكات تكمن على نفس القطر التصاعدي ( من اليسار إلى اليمين)، بينما تعني الأخرى أنهما تكمن على نفس القطر التنازلي. أي شرط يتجاوب مع التصاعدي وأي شرط تنازلي يعتمد على كيفية ترتيب الصفوف والأعمدة. كما هو مذكور في القسم السابق، ليس لترتيب الحلول تأثير في طريقة عرضها فقط.

إذًا، يكون القيد القطري هو أن قيم queens(j) + j يجب أن تكون مختلفة، وأن قيم queens(j) - j يجب أن تكون مختلفة لمختلف j.

لتطبيق طريقة AddAllDifferent على queens(j) + j، نضع N مثيلات للمتغير، لـ j من 0 إلى N-1، في صفيف، diag1، على النحو التالي:

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

ثم نطبق AddAllDifferent على diag1.

model.AddAllDifferent(diag1)

يتم إنشاء القيد لـ queens(j) - j بشكل مشابه.

إنشاء طابعة حل

لطباعة جميع الحلول لمشكلة N-queens، عليك تمرير استدعاء، يُسمى طابعة الحلول، إلى أداة حل CP-SAT. تطبع معاودة الاتصال كل حل جديد كما تعثر عليه أداة الحلّ. تنشئ التعليمة البرمجية التالية طابعة حلول.

Python

class NQueenSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, queens: list[cp_model.IntVar]):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__queens = queens
        self.__solution_count = 0
        self.__start_time = time.time()

    @property
    def solution_count(self) -> int:
        return self.__solution_count

    def on_solution_callback(self):
        current_time = time.time()
        print(
            f"Solution {self.__solution_count}, "
            f"time = {current_time - self.__start_time} s"
        )
        self.__solution_count += 1

        all_queens = range(len(self.__queens))
        for i in all_queens:
            for j in all_queens:
                if self.value(self.__queens[j]) == i:
                    # There is a queen in column j, row i.
                    print("Q", end=" ")
                else:
                    print("_", end=" ")
            print()
        print()

C++

int num_solutions = 0;
Model model;
model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) {
  LOG(INFO) << "Solution " << num_solutions;
  for (int i = 0; i < board_size; ++i) {
    std::stringstream ss;
    for (int j = 0; j < board_size; ++j) {
      if (SolutionIntegerValue(response, queens[j]) == i) {
        // There is a queen in column j, row i.
        ss << "Q";
      } else {
        ss << "_";
      }
      if (j != board_size - 1) ss << " ";
    }
    LOG(INFO) << ss.str();
  }
  num_solutions++;
}));

Java

static class SolutionPrinter extends CpSolverSolutionCallback {
  public SolutionPrinter(IntVar[] queensIn) {
    solutionCount = 0;
    queens = queensIn;
  }

  @Override
  public void onSolutionCallback() {
    System.out.println("Solution " + solutionCount);
    for (int i = 0; i < queens.length; ++i) {
      for (int j = 0; j < queens.length; ++j) {
        if (value(queens[j]) == i) {
          System.out.print("Q");
        } else {
          System.out.print("_");
        }
        if (j != queens.length - 1) {
          System.out.print(" ");
        }
      }
      System.out.println();
    }
    solutionCount++;
  }

  public int getSolutionCount() {
    return solutionCount;
  }

  private int solutionCount;
  private final IntVar[] queens;
}

C#

public class SolutionPrinter : CpSolverSolutionCallback
{
    public SolutionPrinter(IntVar[] queens)
    {
        queens_ = queens;
    }

    public override void OnSolutionCallback()
    {
        Console.WriteLine($"Solution {SolutionCount_}");
        for (int i = 0; i < queens_.Length; ++i)
        {
            for (int j = 0; j < queens_.Length; ++j)
            {
                if (Value(queens_[j]) == i)
                {
                    Console.Write("Q");
                }
                else
                {
                    Console.Write("_");
                }
                if (j != queens_.Length - 1)
                    Console.Write(" ");
            }
            Console.WriteLine("");
        }
        SolutionCount_++;
    }

    public int SolutionCount()
    {
        return SolutionCount_;
    }

    private int SolutionCount_;
    private IntVar[] queens_;
}

تجدر الإشارة إلى أنّه يجب كتابة طابعة الحل كفئة Python، وذلك بسبب واجهة Python للحلّ الأساسي C++.

تتم طباعة الحلول بواسطة الأسطر التالية في طابعة الحل.

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

في هذا المثال، self.__variables هو المتغير queens، ويتجاوب كل v مع أحد إدخالات queens الثمانية. يؤدي هذا إلى طباعة حل بالصيغة التالية: x0 = queens(0) x1 = queens(1) ... x7 = queens(7) حيث xi هو رقم عمود الملكة في الصف i.

يعرض القسم التالي مثالاً للحلّ.

الاتصال بأداة الحلّ وعرض النتائج

يُشغِّل الرمز التالي أداة الحلّ ويعرض الحلول.

Python

solver = cp_model.CpSolver()
solution_printer = NQueenSolutionPrinter(queens)
solver.parameters.enumerate_all_solutions = True
solver.solve(model, solution_printer)

C++

// Tell the solver to enumerate all solutions.
SatParameters parameters;
parameters.set_enumerate_all_solutions(true);
model.Add(NewSatParameters(parameters));

const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
LOG(INFO) << "Number of solutions found: " << num_solutions;

Java

CpSolver solver = new CpSolver();
SolutionPrinter cb = new SolutionPrinter(queens);
// Tell the solver to enumerate all solutions.
solver.getParameters().setEnumerateAllSolutions(true);
// And solve.
solver.solve(model, cb);

C#

// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
SolutionPrinter cb = new SolutionPrinter(queens);
// Search for all solutions.
solver.StringParameters = "enumerate_all_solutions:true";
// And solve.
solver.Solve(model, cb);

يعثر البرنامج على 92 حلاً مختلفًا للوحة 8×8. آدِي أَوِّلْ إِدْخَالْ.

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

يمكنك حل مشكلة لوحة ذات حجم مختلف عن طريق تمرير N كوسيطة سطر أوامر. على سبيل المثال، إذا كان اسم البرنامج queens، يحلّ python nqueens_sat.py 6 مشكلة لوح 6×6.

البرنامج بأكمله

في ما يلي البرنامج الكامل لبرنامج N-queens.

Python

"""OR-Tools solution to the N-queens problem."""
import sys
import time
from ortools.sat.python import cp_model


class NQueenSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, queens: list[cp_model.IntVar]):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__queens = queens
        self.__solution_count = 0
        self.__start_time = time.time()

    @property
    def solution_count(self) -> int:
        return self.__solution_count

    def on_solution_callback(self):
        current_time = time.time()
        print(
            f"Solution {self.__solution_count}, "
            f"time = {current_time - self.__start_time} s"
        )
        self.__solution_count += 1

        all_queens = range(len(self.__queens))
        for i in all_queens:
            for j in all_queens:
                if self.value(self.__queens[j]) == i:
                    # There is a queen in column j, row i.
                    print("Q", end=" ")
                else:
                    print("_", end=" ")
            print()
        print()



def main(board_size: int) -> None:
    # Creates the solver.
    model = cp_model.CpModel()

    # Creates the variables.
    # There are `board_size` number of variables, one for a queen in each column
    # of the board. The value of each variable is the row that the queen is in.
    queens = [model.new_int_var(0, board_size - 1, f"x_{i}") for i in range(board_size)]

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

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

    # Solve the model.
    solver = cp_model.CpSolver()
    solution_printer = NQueenSolutionPrinter(queens)
    solver.parameters.enumerate_all_solutions = True
    solver.solve(model, solution_printer)

    # Statistics.
    print("\nStatistics")
    print(f"  conflicts      : {solver.num_conflicts}")
    print(f"  branches       : {solver.num_branches}")
    print(f"  wall time      : {solver.wall_time} s")
    print(f"  solutions found: {solution_printer.solution_count}")


if __name__ == "__main__":
    # By default, solve the 8x8 problem.
    size = 8
    if len(sys.argv) > 1:
        size = int(sys.argv[1])
    main(size)

C++

// OR-Tools solution to the N-queens problem.
#include <stdlib.h>

#include <sstream>
#include <string>
#include <vector>

#include "absl/strings/numbers.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/sorted_interval_list.h"

namespace operations_research {
namespace sat {

void NQueensSat(const int board_size) {
  // Instantiate the solver.
  CpModelBuilder cp_model;

  // There are `board_size` number of variables, one for a queen in each column
  // of the board. The value of each variable is the row that the queen is in.
  std::vector<IntVar> queens;
  queens.reserve(board_size);
  Domain range(0, board_size - 1);
  for (int i = 0; i < board_size; ++i) {
    queens.push_back(
        cp_model.NewIntVar(range).WithName("x" + std::to_string(i)));
  }

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

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

  int num_solutions = 0;
  Model model;
  model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) {
    LOG(INFO) << "Solution " << num_solutions;
    for (int i = 0; i < board_size; ++i) {
      std::stringstream ss;
      for (int j = 0; j < board_size; ++j) {
        if (SolutionIntegerValue(response, queens[j]) == i) {
          // There is a queen in column j, row i.
          ss << "Q";
        } else {
          ss << "_";
        }
        if (j != board_size - 1) ss << " ";
      }
      LOG(INFO) << ss.str();
    }
    num_solutions++;
  }));

  // Tell the solver to enumerate all solutions.
  SatParameters parameters;
  parameters.set_enumerate_all_solutions(true);
  model.Add(NewSatParameters(parameters));

  const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
  LOG(INFO) << "Number of solutions found: " << num_solutions;

  // Statistics.
  LOG(INFO) << "Statistics";
  LOG(INFO) << CpSolverResponseStats(response);
}

}  // namespace sat
}  // namespace operations_research

int main(int argc, char** argv) {
  int board_size = 8;
  if (argc > 1) {
    if (!absl::SimpleAtoi(argv[1], &board_size)) {
      LOG(INFO) << "Cannot parse '" << argv[1]
                << "', using the default value of 8.";
      board_size = 8;
    }
  }
  operations_research::sat::NQueensSat(board_size);
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverSolutionCallback;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;

/** OR-Tools solution to the N-queens problem. */
public final class NQueensSat {
  static class SolutionPrinter extends CpSolverSolutionCallback {
    public SolutionPrinter(IntVar[] queensIn) {
      solutionCount = 0;
      queens = queensIn;
    }

    @Override
    public void onSolutionCallback() {
      System.out.println("Solution " + solutionCount);
      for (int i = 0; i < queens.length; ++i) {
        for (int j = 0; j < queens.length; ++j) {
          if (value(queens[j]) == i) {
            System.out.print("Q");
          } else {
            System.out.print("_");
          }
          if (j != queens.length - 1) {
            System.out.print(" ");
          }
        }
        System.out.println();
      }
      solutionCount++;
    }

    public int getSolutionCount() {
      return solutionCount;
    }

    private int solutionCount;
    private final IntVar[] queens;
  }

  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the model.
    CpModel model = new CpModel();

    int boardSize = 8;
    // There are `BoardSize` number of variables, one for a queen in each column of the board. The
    // value of each variable is the row that the queen is in.
    IntVar[] queens = new IntVar[boardSize];
    for (int i = 0; i < boardSize; ++i) {
      queens[i] = model.newIntVar(0, boardSize - 1, "x" + i);
    }

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

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

    // Create a solver and solve the model.
    CpSolver solver = new CpSolver();
    SolutionPrinter cb = new SolutionPrinter(queens);
    // Tell the solver to enumerate all solutions.
    solver.getParameters().setEnumerateAllSolutions(true);
    // And solve.
    solver.solve(model, cb);

    // Statistics.
    System.out.println("Statistics");
    System.out.println("  conflicts : " + solver.numConflicts());
    System.out.println("  branches  : " + solver.numBranches());
    System.out.println("  wall time : " + solver.wallTime() + " s");
    System.out.println("  solutions : " + cb.getSolutionCount());
  }

  private NQueensSat() {}
}

C#

// OR-Tools solution to the N-queens problem.
using System;
using Google.OrTools.Sat;

public class NQueensSat
{
    public class SolutionPrinter : CpSolverSolutionCallback
    {
        public SolutionPrinter(IntVar[] queens)
        {
            queens_ = queens;
        }

        public override void OnSolutionCallback()
        {
            Console.WriteLine($"Solution {SolutionCount_}");
            for (int i = 0; i < queens_.Length; ++i)
            {
                for (int j = 0; j < queens_.Length; ++j)
                {
                    if (Value(queens_[j]) == i)
                    {
                        Console.Write("Q");
                    }
                    else
                    {
                        Console.Write("_");
                    }
                    if (j != queens_.Length - 1)
                        Console.Write(" ");
                }
                Console.WriteLine("");
            }
            SolutionCount_++;
        }

        public int SolutionCount()
        {
            return SolutionCount_;
        }

        private int SolutionCount_;
        private IntVar[] queens_;
    }

    static void Main()
    {
        // Constraint programming engine
        CpModel model = new CpModel();

        int BoardSize = 8;
        // There are `BoardSize` number of variables, one for a queen in each
        // column of the board. The value of each variable is the row that the
        // queen is in.
        IntVar[] queens = new IntVar[BoardSize];
        for (int i = 0; i < BoardSize; ++i)
        {
            queens[i] = model.NewIntVar(0, BoardSize - 1, $"x{i}");
        }

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

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

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

        // Creates a solver and solves the model.
        CpSolver solver = new CpSolver();
        SolutionPrinter cb = new SolutionPrinter(queens);
        // Search for all solutions.
        solver.StringParameters = "enumerate_all_solutions:true";
        // And solve.
        solver.Solve(model, cb);

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts : {solver.NumConflicts()}");
        Console.WriteLine($"  branches  : {solver.NumBranches()}");
        Console.WriteLine($"  wall time : {solver.WallTime()} s");
        Console.WriteLine($"  number of solutions found: {cb.SolutionCount()}");
    }
}

الحلّ باستخدام أداة حلّ CP الأصلية

تقدم الأقسام التالية برنامجًا بلغة Python يحل ملكات N-queens باستخدام أداة حل CP الأصلية. (ومع ذلك، ننصح باستخدام أداة حلّ CP-SAT الأحدث).

استيراد المكتبات

يستورد الرمز التالي المكتبة المطلوبة.

Python

import sys
from ortools.constraint_solver import pywrapcp

C++

#include <cstdint>
#include <cstdlib>
#include <sstream>
#include <vector>

#include "ortools/base/logging.h"
#include "ortools/constraint_solver/constraint_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;

C#

using System;
using Google.OrTools.ConstraintSolver;

تعريف أداة الحلّ

يوضّح الرمز التالي أداة حلّ CP الأصلية.

Python

solver = pywrapcp.Solver("n-queens")

C++

Solver solver("N-Queens");

Java

Solver solver = new Solver("N-Queens");

C#

Solver solver = new Solver("N-Queens");

إنشاء المتغيّرات

تنشئ الطريقة IntVar في أداة الحلّ متغيرات المسألة على أنّها مصفوفة باسم queens.

Python

# The array index is the column, and the value is the row.
queens = [solver.IntVar(0, board_size - 1, f"x{i}") for i in range(board_size)]

C++

std::vector<IntVar*> queens;
queens.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
  queens.push_back(
      solver.MakeIntVar(0, board_size - 1, absl::StrCat("x", i)));
}

Java

int boardSize = 8;
IntVar[] queens = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
  queens[i] = solver.makeIntVar(0, boardSize - 1, "x" + i);
}

C#

const int BoardSize = 8;
IntVar[] queens = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
    queens[i] = solver.MakeIntVar(0, BoardSize - 1, $"x{i}");
}

بالنسبة إلى أي حلّ، تعني queens[j] = i أنّ هناك رتبة كوين في العمود j والصف i.

وضع القيود

إليك التعليمة البرمجية التي تنشئ قيودًا للمشكلة.

Python

# All rows must be different.
solver.Add(solver.AllDifferent(queens))

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

C++

// The following sets the constraint that all queens are in different rows.
solver.AddConstraint(solver.MakeAllDifferent(queens));

// All columns must be different because the indices of queens are all
// different. No two queens can be on the same diagonal.
std::vector<IntVar*> diag_1;
diag_1.reserve(board_size);
std::vector<IntVar*> diag_2;
diag_2.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
  diag_1.push_back(solver.MakeSum(queens[i], i)->Var());
  diag_2.push_back(solver.MakeSum(queens[i], -i)->Var());
}
solver.AddConstraint(solver.MakeAllDifferent(diag_1));
solver.AddConstraint(solver.MakeAllDifferent(diag_2));

Java

// All rows must be different.
solver.addConstraint(solver.makeAllDifferent(queens));

// All columns must be different because the indices of queens are all different.
// No two queens can be on the same diagonal.
IntVar[] diag1 = new IntVar[boardSize];
IntVar[] diag2 = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
  diag1[i] = solver.makeSum(queens[i], i).var();
  diag2[i] = solver.makeSum(queens[i], -i).var();
}
solver.addConstraint(solver.makeAllDifferent(diag1));
solver.addConstraint(solver.makeAllDifferent(diag2));

C#

// All rows must be different.
solver.Add(queens.AllDifferent());

// All columns must be different because the indices of queens are all different.
// No two queens can be on the same diagonal.
IntVar[] diag1 = new IntVar[BoardSize];
IntVar[] diag2 = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
    diag1[i] = solver.MakeSum(queens[i], i).Var();
    diag2[i] = solver.MakeSum(queens[i], -i).Var();
}

solver.Add(diag1.AllDifferent());
solver.Add(diag2.AllDifferent());

تضمن هذه القيود الشروط الثلاثة لمشكلة N-queens (الملكات في صفوف وأعمدة وأقطار مختلفة).

لا توجد ملكتان في الصف نفسه

في حال تطبيق طريقة AllDifferent الخاصة بأداة الحلّ على queens، يجب أن تكون قيم queens[j] مختلفة لكل j، ما يعني أنّ جميع الملكات يجب أن تكون في صفوف مختلفة.

لا توجد ملكتان في نفس العمود

وهذا القيد ضمني في تعريف queens. بما أنّه لا يمكن أن يكون لعنصران من queens الفهرس نفسه، لا يمكن أن تظهر ملكتان في العمود نفسه.

ما مِن ملكات على القطر نفسه

القيد القطري أصعب قليلاً من قيود الصفوف والعمود. أولًا، إذا كانت هناك ملكتان توضع على نفس القطر، فينبغي أن يكون ما يلي صحيحًا:

• إذا كان القطر تنازليًا (يتحرك من اليسار إلى اليمين)، فإن رقم الصف ورقم العمود لكل من الملكتين متساويان. لذلك فإن queens(i) + i لها نفس القيمة لفهرسين مختلفين i.
• إذا كان القطر تصاعديًا، فإن رقم الصف مطروحًا منه رقم العمود لكل من الملكتين يساوي. في هذه الحالة، يحتوي queens(i) - i على القيمة نفسها لفهرسين مختلفين i.

إذًا، يكون القيد القطري هو أن قيم queens(i) + i يجب أن تكون مختلفة، وبالمثل، يجب أن تكون قيم queens(i) - i مختلفة لمختلف i.

يضيف الرمز البرمجي أعلاه هذا القيد من خلال تطبيق الطريقة AllDifferent على queens[j] + j وqueens[j] - j لكل i.

إضافة أداة إنشاء القرار

الخطوة التالية هي إنشاء إحدى منصات إنشاء القرار، التي تحدد استراتيجية البحث للمشكلة. يمكن أن يكون لاستراتيجية البحث تأثير كبير في وقت البحث، بسبب انتشار القيود، ما يقلّل من عدد القيم المتغيّرة التي يجب على أداة الحلّ استكشافها. لقد رأيت مثالاً على ذلك من قبل في مثال أربع ملكات.

يُنشئ الرمز البرمجي التالي أداة إنشاء قرارات باستخدام طريقة 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- Queens. تبدأ أداة الحلّ بـ queens[0]، وهو المتغيّر الأول في الصفيف، حسب إرشادات CHOOSE_FIRST_UNBOUND. بعد ذلك، تُخصِّص أداة الحلّ لـ queens[0] أصغر قيمة لم يسبق أن جرَّبتها، وهي 0 في هذه المرحلة، وفقًا لتعليمات ASSIGN_MIN_VALUE. يضع هذا الملكة الأولى في الزاوية اليسرى العلوية من اللوحة.

بعد ذلك، تختار أداة الحلّ queens[1]، الذي أصبح الآن أول متغيّر غير مرتبط في queens. بعد نشر القيود، هناك صفان محتملان للملكة في العمود 1: الصف 2 أو الصف 3. يوجّه الخيار ASSIGN_MIN_VALUE الحلّ لتعيين queens[1] = 2. (إذا تم بدلاً من ذلك ضبط السمة IntValueStrategy على ASSIGN_MAX_VALUE، ستحدّد أداة الحلّ القيمة queens[1] = 3).

ويمكنك التأكد من أن بقية عمليات البحث تتبع القواعد نفسها.

الاتصال بأداة الحلّ وعرض النتائج

يُشغِّل الرمز التالي أداة الحلّ ويعرض الحلّ.

Python

# Iterates through the solutions, displaying each.
num_solutions = 0
solver.NewSearch(db)
while solver.NextSolution():
    # Displays the solution just computed.
    for i in range(board_size):
        for j in range(board_size):
            if queens[j].Value() == i:
                # There is a queen in column j, row i.
                print("Q", end=" ")
            else:
                print("_", end=" ")
        print()
    print()
    num_solutions += 1
solver.EndSearch()

C++

// Iterates through the solutions, displaying each.
int num_solutions = 0;

solver.NewSearch(db);
while (solver.NextSolution()) {
  // Displays the solution just computed.
  LOG(INFO) << "Solution " << num_solutions;
  for (int i = 0; i < board_size; ++i) {
    std::stringstream ss;
    for (int j = 0; j < board_size; ++j) {
      if (queens[j]->Value() == i) {
        // There is a queen in column j, row i.
        ss << "Q";
      } else {
        ss << "_";
      }
      if (j != board_size - 1) ss << " ";
    }
    LOG(INFO) << ss.str();
  }
  num_solutions++;
}
solver.EndSearch();

Java

int solutionCount = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
  System.out.println("Solution " + solutionCount);
  for (int i = 0; i < boardSize; ++i) {
    for (int j = 0; j < boardSize; ++j) {
      if (queens[j].value() == i) {
        System.out.print("Q");
      } else {
        System.out.print("_");
      }
      if (j != boardSize - 1) {
        System.out.print(" ");
      }
    }
    System.out.println();
  }
  solutionCount++;
}
solver.endSearch();

C#

// Iterates through the solutions, displaying each.
int SolutionCount = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
    Console.WriteLine("Solution " + SolutionCount);
    for (int i = 0; i < BoardSize; ++i)
    {
        for (int j = 0; j < BoardSize; ++j)
        {
            if (queens[j].Value() == i)
            {
                Console.Write("Q");
            }
            else
            {
                Console.Write("_");
            }
            if (j != BoardSize - 1)
                Console.Write(" ");
        }
        Console.WriteLine("");
    }
    SolutionCount++;
}
solver.EndSearch();

إليك الحل الأول الذي وجده البرنامج للوحة 8×8.

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

يمكنك حل مشكلة لوحة ذات حجم مختلف عن طريق تمرير N كوسيطة سطر أوامر. على سبيل المثال، يحل python nqueens_cp.py 6 مشكلة لوح 6×6.

البرنامج بأكمله

يظهر البرنامج الكامل أدناه.

Python

"""OR-Tools solution to the N-queens problem."""
import sys
from ortools.constraint_solver import pywrapcp


def main(board_size):
    # Creates the solver.
    solver = pywrapcp.Solver("n-queens")

    # Creates the variables.
    # The array index is the column, and the value is the row.
    queens = [solver.IntVar(0, board_size - 1, f"x{i}") for i in range(board_size)]

    # Creates the constraints.
    # All rows must be different.
    solver.Add(solver.AllDifferent(queens))

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

    db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)

    # Iterates through the solutions, displaying each.
    num_solutions = 0
    solver.NewSearch(db)
    while solver.NextSolution():
        # Displays the solution just computed.
        for i in range(board_size):
            for j in range(board_size):
                if queens[j].Value() == i:
                    # There is a queen in column j, row i.
                    print("Q", end=" ")
                else:
                    print("_", end=" ")
            print()
        print()
        num_solutions += 1
    solver.EndSearch()

    # Statistics.
    print("\nStatistics")
    print(f"  failures: {solver.Failures()}")
    print(f"  branches: {solver.Branches()}")
    print(f"  wall time: {solver.WallTime()} ms")
    print(f"  Solutions found: {num_solutions}")


if __name__ == "__main__":
    # By default, solve the 8x8 problem.
    size = 8
    if len(sys.argv) > 1:
        size = int(sys.argv[1])
    main(size)

C++

// OR-Tools solution to the N-queens problem.
#include <cstdint>
#include <cstdlib>
#include <sstream>
#include <vector>

#include "ortools/base/logging.h"
#include "ortools/constraint_solver/constraint_solver.h"

namespace operations_research {

void NQueensCp(const int board_size) {
  // Instantiate the solver.
  Solver solver("N-Queens");

  std::vector<IntVar*> queens;
  queens.reserve(board_size);
  for (int i = 0; i < board_size; ++i) {
    queens.push_back(
        solver.MakeIntVar(0, board_size - 1, absl::StrCat("x", i)));
  }

  // Define constraints.
  // The following sets the constraint that all queens are in different rows.
  solver.AddConstraint(solver.MakeAllDifferent(queens));

  // All columns must be different because the indices of queens are all
  // different. No two queens can be on the same diagonal.
  std::vector<IntVar*> diag_1;
  diag_1.reserve(board_size);
  std::vector<IntVar*> diag_2;
  diag_2.reserve(board_size);
  for (int i = 0; i < board_size; ++i) {
    diag_1.push_back(solver.MakeSum(queens[i], i)->Var());
    diag_2.push_back(solver.MakeSum(queens[i], -i)->Var());
  }
  solver.AddConstraint(solver.MakeAllDifferent(diag_1));
  solver.AddConstraint(solver.MakeAllDifferent(diag_2));

  DecisionBuilder* const db = solver.MakePhase(
      queens, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);

  // Iterates through the solutions, displaying each.
  int num_solutions = 0;

  solver.NewSearch(db);
  while (solver.NextSolution()) {
    // Displays the solution just computed.
    LOG(INFO) << "Solution " << num_solutions;
    for (int i = 0; i < board_size; ++i) {
      std::stringstream ss;
      for (int j = 0; j < board_size; ++j) {
        if (queens[j]->Value() == i) {
          // There is a queen in column j, row i.
          ss << "Q";
        } else {
          ss << "_";
        }
        if (j != board_size - 1) ss << " ";
      }
      LOG(INFO) << ss.str();
    }
    num_solutions++;
  }
  solver.EndSearch();

  // Statistics.
  LOG(INFO) << "Statistics";
  LOG(INFO) << "  failures: " << solver.failures();
  LOG(INFO) << "  branches: " << solver.branches();
  LOG(INFO) << "  wall time: " << solver.wall_time() << " ms";
  LOG(INFO) << "  Solutions found: " << num_solutions;
}

}  // namespace operations_research

int main(int argc, char** argv) {
  int board_size = 8;
  if (argc > 1) {
    board_size = std::atoi(argv[1]);
  }
  operations_research::NQueensCp(board_size);
  return EXIT_SUCCESS;
}

Java

// OR-Tools solution to the N-queens problem.
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;

/** N-Queens Problem. */
public final class NQueensCp {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Instantiate the solver.
    Solver solver = new Solver("N-Queens");

    int boardSize = 8;
    IntVar[] queens = new IntVar[boardSize];
    for (int i = 0; i < boardSize; ++i) {
      queens[i] = solver.makeIntVar(0, boardSize - 1, "x" + i);
    }

    // Define constraints.
    // All rows must be different.
    solver.addConstraint(solver.makeAllDifferent(queens));

    // All columns must be different because the indices of queens are all different.
    // No two queens can be on the same diagonal.
    IntVar[] diag1 = new IntVar[boardSize];
    IntVar[] diag2 = new IntVar[boardSize];
    for (int i = 0; i < boardSize; ++i) {
      diag1[i] = solver.makeSum(queens[i], i).var();
      diag2[i] = solver.makeSum(queens[i], -i).var();
    }
    solver.addConstraint(solver.makeAllDifferent(diag1));
    solver.addConstraint(solver.makeAllDifferent(diag2));

    // Create the decision builder to search for solutions.
    final DecisionBuilder db =
        solver.makePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

    int solutionCount = 0;
    solver.newSearch(db);
    while (solver.nextSolution()) {
      System.out.println("Solution " + solutionCount);
      for (int i = 0; i < boardSize; ++i) {
        for (int j = 0; j < boardSize; ++j) {
          if (queens[j].value() == i) {
            System.out.print("Q");
          } else {
            System.out.print("_");
          }
          if (j != boardSize - 1) {
            System.out.print(" ");
          }
        }
        System.out.println();
      }
      solutionCount++;
    }
    solver.endSearch();

    // Statistics.
    System.out.println("Statistics");
    System.out.println("  failures: " + solver.failures());
    System.out.println("  branches: " + solver.branches());
    System.out.println("  wall time: " + solver.wallTime() + "ms");
    System.out.println("  Solutions found: " + solutionCount);
  }

  private NQueensCp() {}
}

C#

// OR-Tools solution to the N-queens problem.
using System;
using Google.OrTools.ConstraintSolver;

public class NQueensCp
{
    public static void Main(String[] args)
    {
        // Instantiate the solver.
        Solver solver = new Solver("N-Queens");

        const int BoardSize = 8;
        IntVar[] queens = new IntVar[BoardSize];
        for (int i = 0; i < BoardSize; ++i)
        {
            queens[i] = solver.MakeIntVar(0, BoardSize - 1, $"x{i}");
        }

        // Define constraints.
        // All rows must be different.
        solver.Add(queens.AllDifferent());

        // All columns must be different because the indices of queens are all different.
        // No two queens can be on the same diagonal.
        IntVar[] diag1 = new IntVar[BoardSize];
        IntVar[] diag2 = new IntVar[BoardSize];
        for (int i = 0; i < BoardSize; ++i)
        {
            diag1[i] = solver.MakeSum(queens[i], i).Var();
            diag2[i] = solver.MakeSum(queens[i], -i).Var();
        }

        solver.Add(diag1.AllDifferent());
        solver.Add(diag2.AllDifferent());

        // Create the decision builder to search for solutions.
        DecisionBuilder db = solver.MakePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        // Iterates through the solutions, displaying each.
        int SolutionCount = 0;
        solver.NewSearch(db);
        while (solver.NextSolution())
        {
            Console.WriteLine("Solution " + SolutionCount);
            for (int i = 0; i < BoardSize; ++i)
            {
                for (int j = 0; j < BoardSize; ++j)
                {
                    if (queens[j].Value() == i)
                    {
                        Console.Write("Q");
                    }
                    else
                    {
                        Console.Write("_");
                    }
                    if (j != BoardSize - 1)
                        Console.Write(" ");
                }
                Console.WriteLine("");
            }
            SolutionCount++;
        }
        solver.EndSearch();

        // Statistics.
        Console.WriteLine("Statistics");
        Console.WriteLine($"  failures: {solver.Failures()}");
        Console.WriteLine($"  branches: {solver.Branches()}");
        Console.WriteLine($"  wall time: {solver.WallTime()} ms");
        Console.WriteLine($"  Solutions found: {SolutionCount}");
    }
}

عدد الحلول

يرتفع عدد الحلول بشكل كبير تقريبًا مع حجم اللوحة:

حجم اللوحة	الحلول	الوقت المستغرق للعثور على جميع الحلول (بالمللي ثانية)
1	1	0
2	0	0
3	0	0
4	2	0
5	10	0
6	4	0
7	40	3
8	92	9
9	352	35
10	724	95
11	2680	378
12	14200	2198
13	73712	11628
14	365596	62427
15	2279184	410701

العديد من الحلول هي مجرد دورات لأخرى، ويمكن استخدام تقنية تسمى كسر التماثل لتقليل كمية العمليات الحسابية المطلوبة. نحن لا نستخدم ذلك هنا؛ فالحل الذي نقدمه أعلاه ليس الغرض منه أن يكون سريعًا، بل بسيطًا فقط. بالطبع، يمكننا أن نجعل الأمر أسرع بكثير إذا أردنا العثور على حل واحد فقط بدلاً من جميعهم: ليس أكثر من بضع ميلي ثانية لأحجام الألواح حتى 50.