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

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

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

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

الحل

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

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

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

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

الانتشار والتتبع العكسي

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

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

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

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

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

الخطوة الأولى في عملية الانتشار

القيد الثالث يحظر ظهور الأميرات في الصف نفسه:

الخطوة الثانية في عملية الانتشار

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

الخطوة الثالثة لعملية الانتشار

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

الخطوة الرابعة للانتشار

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

الخطوة السادسة لعملية الانتشار

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

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

الخطوة التاسعة في الانتشار

يكشف النشر مرة أخرى عن بقعة واحدة فقط للملكة الثالثة:

الخطوة العاشرة لعملية الانتشار

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

الخطوة الثانية عشرة حول الانتشار

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

حلّ باستخدام 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 الفهرس ذاته، فلا يمكن استخدام حقلين في نفس العمود.

لا توجد ملكتان على نفس القطر

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

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

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

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

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

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

بعد ذلك، نطبِّق AddAllDifferent على diag1.

model.AddAllDifferent(diag1)

يتم إنشاء القيد لـ queens(j) - j بالطريقة نفسها.

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

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

Python

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

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

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

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

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

C++‎

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

Java

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

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

  public int getSolutionCount() {
    return solutionCount;
  }

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

#C

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

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

    public int SolutionCount()
    {
        return SolutionCount_;
    }

    private int SolutionCount_;
    private IntVar[] queens_;
}

لاحظ أنه يجب كتابة طابعة الحل باعتبارها فئة بايثون، بسبب 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 الأصلية

تقدم الأقسام التالية برنامج بايثون يحل لغة 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]&nbsp;+&nbsp;j وqueens[j]&nbsp;-&nbsp;j لكل i.

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

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

تُنشئ التعليمة البرمجية التالية أداة إنشاء قرارات باستخدام Phase .

Python

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

C++‎

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

Java

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

#C

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

راجع أداة إنشاء القرارات للحصول على تفاصيل حول إدخال وسيطات إلى الطريقة Phase.

كيف تعمل أداة إنشاء القرار في مثال 4 ملكات

لنلقِ نظرة على الطريقة التي توجه بها أداة إنشاء القرارات البحث في مثال لـ 4 ملكات: تبدأ أداة الحلّ بـ queens[0]، وهو المتغيّر الأول في الصفيف حسب التوجيهات بواسطة CHOOSE_FIRST_UNBOUND تضع أداة الحلّ بعد ذلك queens[0] أصغر قيمة لم تتم تجربتها من قبل، وهي 0 في هذه المرحلة، حسب توجيهات ASSIGN_MIN_VALUE هذا يضع الملكة الأولى في الزاوية اليسرى العليا من لوح.

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

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

عليك استدعاء أداة الحلّ وعرض النتائج.

يقوم التعليمة البرمجية التالية بتشغيل أداة الحل وعرض الحل.

Python

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

C++‎

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

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

Java

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

#C

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

إليك الحل الأول الذي توصل إليه البرنامج للوحة مقاس 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}");
    }
}

عدد الحلول

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

حجم اللوحةالحلولوقت العثور على كل الحلول (بالملّي ثانية)
110
200
300
420
5100
640
7403
8929
935235
1072495
112680378
12142002198
137371211628
1436559662427
152279184410701

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