ปัญหาของราชินี N

ในส่วนต่อไปนี้ เราจะอธิบายการเขียนโปรแกรมจุดจำกัด (CP) ตามโจทย์แบบผสมที่อิงตามเกมหมากรุก ในการเล่นหมากรุก ราชินีสามารถโจมตี ในแนวนอน แนวตั้ง และแนวทแยงได้ โจทย์ N-queens ถามว่า

จะวาง N ควีนบนกระดานหมากรุก NxN ได้อย่างไร เพื่อไม่ให้พวกมันสองคนมาโจมตีกัน

ด้านล่าง คุณสามารถดูวิธีแก้ไขที่เป็นไปได้สำหรับโจทย์ N-queens สำหรับ N = 4

โซลูชัน

ไม่มีควีน 2 ตัวอยู่ในแถว คอลัมน์ หรือแนวทแยงมุมเดียวกัน

โปรดทราบว่านี่ไม่ใช่ปัญหาด้านการเพิ่มประสิทธิภาพ เราอยากค้นหาโซลูชันที่เป็นไปได้ทั้งหมด แทนที่จะเป็นโซลูชันที่ดีที่สุดเพียงโซลูชันเดียว ซึ่งทำให้โซลูชันนั้นเป็นตัวเลือกทั่วไปสำหรับเขียนโปรแกรมแบบมีข้อจำกัด ส่วนต่อไปนี้อธิบายวิธี CP ของโจทย์ N-queens และนำเสนอโปรแกรมที่แก้โจทย์โดยใช้ทั้งตัวแก้โจทย์ CP-SAT และตัวแก้โจทย์ CP ดั้งเดิม

แนวทาง CP ในโจทย์ N-queens

เครื่องมือแก้โจทย์ CP ทำงานโดยพยายามระบุค่าที่เป็นไปได้ทั้งหมดให้กับตัวแปรในโจทย์อย่างเป็นระบบเพื่อค้นหาวิธีแก้ปัญหาที่ทำได้ ในโจทย์ปัญหา 4 ควีน เครื่องมือแก้โจทย์จะเริ่มที่คอลัมน์ซ้ายสุดและวางควีน 1 ตัวต่อ 1 คอลัมน์ ณ ตำแหน่งที่ไม่ถูกโจมตีโดยราชินีที่วางไว้ก่อนหน้านี้

การเผยแพร่และการย้อนกลับ

การค้นหาด้วยการเขียนโปรแกรมแบบจํากัดมีองค์ประกอบหลัก 2 อย่าง ได้แก่

  • การเผยแพร่ — ทุกครั้งที่เครื่องมือแก้โจทย์กำหนดค่าให้กับตัวแปร ข้อจำกัดจะเพิ่มข้อจำกัดเกี่ยวกับค่าที่เป็นไปได้ของตัวแปรที่ไม่ได้กำหนด ข้อจำกัดเหล่านี้นำไปใช้ในการมอบหมายตัวแปรในอนาคต เช่น ในโจทย์ปัญหา 4 ควีน ทุกครั้งที่เครื่องมือแก้โจทย์วางควีน จะวางควีนตัวอื่นๆ บนแถวไม่ได้และในแนวทแยงที่ควีนปัจจุบันเปิดอยู่ การแพร่พันธุ์จะช่วยประหยัดเวลาในการค้นหาได้อย่างมากโดยการลดชุดค่าตัวแปรที่เครื่องมือแก้โจทย์จะต้องสำรวจ
  • การย้อนกลับจะเกิดขึ้นเมื่อเครื่องมือแก้โจทย์กำหนดค่าให้กับตัวแปรถัดไปไม่ได้เนื่องจากข้อจำกัด หรือพบคำตอบไม่ได้ ในทั้งสองกรณี ตัวแก้ปัญหาจะย้อนกลับไปยังขั้นตอนก่อนหน้า และเปลี่ยนค่าของตัวแปรในขั้นตอนนั้นเป็นค่าที่ยังไม่ได้ลองใช้ ในตัวอย่าง 4-Queen นั่นหมายถึงการย้ายราชินีไปยังสี่เหลี่ยมจัตุรัสใหม่ในคอลัมน์ปัจจุบัน

ถัดไป คุณจะเห็นว่าการเขียนโปรแกรมข้อจำกัดใช้การขยายและการย้อนกลับในการแก้ปัญหา 4-queens อย่างไร

สมมติว่าการแก้โจทย์ปัญหาเริ่มต้นด้วยการวางตำแหน่งราชินีไว้มุมซ้ายบนโดยพลการ นี่เป็นสมมติฐานบางอย่าง บางทีอาจกลับว่าไม่มีโซลูชันใด ที่มีรูปควีนอยู่ที่มุมซ้ายบน

จากสมมติฐานนี้ เราเผยแพร่ข้อจำกัดใดได้บ้าง ข้อจำกัดหนึ่งคือสามารถมีควีนได้เพียง 1 ตัวในคอลัมน์ (เครื่องหมาย X สีเทาด้านล่าง) และอีกหนึ่งข้อจำกัดห้ามไม่ให้มีควีน 2 ตัวในเส้นทแยงมุมเดียวกัน (กากบาทสีแดงด้านล่าง)

ขั้นตอนแรกการนำไปใช้งาน

ข้อจำกัดข้อที่ 3 ไม่อนุญาตให้ใช้ Queen บนแถวเดียวกัน

ขั้นตอนที่ 2 ของการนำไปใช้

ข้อจำกัดของเราเผยแพร่ออกไป เราสามารถทดสอบสมมติฐานอื่น และวางราชินีที่ 2 บนสี่เหลี่ยมจัตุรัสที่เหลือได้ เครื่องมือแก้โจทย์ของเราอาจตัดสินใจ ที่จะวางไว้ในสี่เหลี่ยมจัตุรัสแรกที่มีอยู่ในคอลัมน์ที่ 2 ดังนี้

ขั้นตอนที่ 3 ในการเผยแพร่

หลังจากการเผยแพร่ข้อจำกัดในแนวทแยง เราจะเห็นว่าจุดยึดไม่มีสี่เหลี่ยมจัตุรัสที่ใช้ได้ในคอลัมน์ที่ 3 หรือแถวสุดท้าย ดังนี้

ขั้นตอนที่ 4 การนำไปใช้งาน

แต่ในขั้นนี้ยังไม่มีวิธีแก้ปัญหาใดๆ เราจึงต้องย้อนกลับ ตัวเลือกหนึ่งมีไว้เพื่อให้เครื่องมือแก้โจทย์เลือกสี่เหลี่ยมจัตุรัสอื่นๆ ที่ใช้ได้ในคอลัมน์ที่ 2 อย่างไรก็ตาม การแพร่ข้อจำกัดจะบังคับให้ควีนอยู่ในแถวที่ 2 ของคอลัมน์ที่ 3 โดยไม่ทิ้งจุดที่ถูกต้องสำหรับควีนที่ 4 ดังนี้

ขั้นตอนที่ 6 ของการนำไปใช้

การแก้โจทย์จะต้องย้อนกลับไปยังตำแหน่งเดิมของราชินีองค์แรกจนสุด เราได้แสดงให้เห็นแล้วว่าไม่มีวิธีแก้ปัญหา สำหรับราชินีที่กินพื้นที่สี่เหลี่ยมมุมฉาก

เนื่องจากจะไม่มีควีนอยู่ที่มุม เครื่องมือแก้โจทย์จึงจะย้ายราชินีองค์แรกลงทีละ 1 ตัว แล้วกระจายเหลือเพียงจุดเดียวสำหรับราชินีองค์ที่ 2

ขั้นตอนที่ 9 ในการเผยแพร่

การเผยแพร่อีกครั้งจะแสดงจุดที่เหลืออยู่เพียงจุดเดียวสำหรับราชินีองค์ที่ 3

ขั้นตอนที่ 10 ในการนำไปใช้

และสำหรับราชินีองค์ที่ 4 ซึ่งเป็นพระราชินีองค์สุดท้าย

ขั้นตอนที่ 12 ของการแพร่พันธุ์

เรามีโซลูชันแรกแล้ว หากเราสั่งให้เครื่องมือแก้โจทย์หยุดหลังจากพบวิธีแก้ปัญหาแรกแล้ว ปัญหาก็จะสิ้นสุดที่นี่ มิเช่นนั้น จะย้อนกลับอีกครั้ง และวางควีนแรกไว้ในแถวที่ 3 ของคอลัมน์แรก

โซลูชันที่ใช้ CP-SAT

โจทย์ N-queens เหมาะกับการเขียนโปรแกรมจำกัด ในส่วนนี้ เราจะแนะนำโปรแกรม Python สั้นๆ ที่ใช้โปรแกรมแก้โจทย์ 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 ซึ่งกำหนดให้องค์ประกอบทั้งหมดของอาร์เรย์ตัวแปรจะแตกต่างกัน

มาดูกันว่าข้อจำกัดเหล่านี้รับประกันเงื่อนไข 3 ข้อของโจทย์ N-queens อย่างไร (ควีนอยู่ในแถว คอลัมน์ และแนวทแยงต่างๆ)

ไม่มีควีนสองตัวในแถวเดียวกัน

การใช้เมธอด AllDifferent ของโปรแกรมแก้โจทย์กับ queens จะบังคับให้ค่าของ queens[j] แตกต่างกันสำหรับ j แต่ละรายการ ซึ่งหมายความว่าควีนทั้งหมดต้องอยู่ในแถวที่ต่างกัน

ไม่มีควีนสองตัวในคอลัมน์เดียวกัน

ข้อจำกัดนี้ไม่เจาะจงในนิยามของ queens เนื่องจากองค์ประกอบ 2 รายการของ queens ที่มีดัชนีเหมือนกันไม่ได้ มีควีน 2 รายการอยู่ในคอลัมน์เดียวกันไม่ได้

ไม่มีควีนสองตัวในแนวทแยงมุมเดียวกัน

จุดยึดในแนวทแยงจะซับซ้อนกว่าข้อจำกัดแถวและคอลัมน์เล็กน้อย ประการแรก ถ้าควีนสองตัวอยู่บนเส้นทแยงมุมเดียวกัน เงื่อนไขข้อใดข้อหนึ่งต่อไปนี้ต้องเป็นจริง

  • หมายเลขแถวบวกกับหมายเลขคอลัมน์สำหรับราชินีทั้ง 2 ตัวเท่ากัน กล่าวคือ queens(j) + j มีค่าเหมือนกันสำหรับดัชนี 2 ดัชนีที่แตกต่างกัน j
  • หมายเลขแถวลบด้วยหมายเลขคอลัมน์ของควีน 2 ตัวเท่ากัน ในกรณีนี้ queens(j) - j มีค่าเดียวกันสำหรับดัชนี 2 ดัชนีที่แตกต่างกัน 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 แต่ละรายการตรงกับ 1 ใน 8 รายการของ 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 วิธีสำหรับกระดานขนาด 8x8 นี่คือคำถามข้อแรก

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

คุณจะแก้โจทย์ของกระดานขนาดอื่นได้โดยส่งผ่าน N เป็นอาร์กิวเมนต์บรรทัดคำสั่ง ตัวอย่างเช่น ถ้าโปรแกรมชื่อ queens python nqueens_sat.py 6 จะแก้ปัญหาสำหรับกระดานขนาด 6x6

ทั้งโปรแกรม

ข้อมูลโปรแกรม N-queens มีดังนี้

Python

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


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

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

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

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

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



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

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

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

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

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

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


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

C++

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

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

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

namespace operations_research {
namespace sat {

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

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

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

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

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

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

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

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

}  // namespace sat
}  // namespace operations_research

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

Java

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

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

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

    public int getSolutionCount() {
      return solutionCount;
    }

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

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

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

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

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

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

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

  private NQueensSat() {}
}

C#

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

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

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

        public int SolutionCount()
        {
            return SolutionCount_;
        }

        private int SolutionCount_;
        private IntVar[] queens_;
    }

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

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

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

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

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

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

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

โซลูชันที่ใช้ตัวแก้โจทย์ CP เดิม

ส่วนต่อไปนี้จะแสดงโปรแกรม Python ที่แก้โจทย์ N-queen โดยใช้โปรแกรมแก้ 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());

ข้อจำกัดเหล่านี้รับประกัน 3 เงื่อนไขของโจทย์ N-queen (ควีนคือมีแถว คอลัมน์ และแนวทแยงที่ไม่เหมือนกัน)

ไม่มีควีนสองตัวในแถวเดียวกัน

การใช้เมธอด AllDifferent ของเครื่องมือแก้โจทย์กับ queens จะบังคับให้ค่าของ queens[j] แตกต่างกันสำหรับ j แต่ละรายการ ซึ่งหมายความว่าควีนทั้งหมดต้องอยู่ในแถวที่ต่างกัน

ไม่มีควีนสองตัวในคอลัมน์เดียวกัน

ข้อจำกัดนี้ไม่เจาะจงในนิยามของ queens เนื่องจากองค์ประกอบ 2 รายการของ queens ที่มีดัชนีเหมือนกันไม่ได้ มีควีน 2 รายการอยู่ในคอลัมน์เดียวกันไม่ได้

ไม่มีควีนสองตัวในแนวทแยงมุมเดียวกัน

จุดยึดในแนวทแยงจะซับซ้อนกว่าข้อจำกัดแถวและคอลัมน์เล็กน้อย ลำดับแรก ถ้าควีนสองตัวอยู่บนเส้นทแยงมุมเดียวกัน ข้อใดข้อหนึ่งต่อไปนี้ต้องเป็นจริง

  • หากเส้นทแยงมุมจากมากไปน้อย (จากซ้ายไปขวา) หมายเลขแถวบวกหมายเลขคอลัมน์สำหรับควีนทั้ง 2 ตัวจะเท่ากัน ดังนั้น queens(i) + i จึงมีค่าเดียวกันสำหรับดัชนี 2 ดัชนีที่ต่างกัน i
  • หากเส้นทแยงมุมจากน้อยไปมาก หมายเลขแถวลบด้วยหมายเลขคอลัมน์ของควีนทั้ง 2 ตัวจะเท่ากัน ในกรณีนี้ queens(i) - i มีค่าเดียวกันสำหรับดัชนี 2 ดัชนีที่แตกต่างกัน i

ดังนั้นค่าจำกัดแนวทแยงมุมคือค่าของ queens(i) + i ทั้งหมดต้องแตกต่างกัน และในทำนองเดียวกัน ค่าของ queens(i) - i ก็ต้องต่างกันสำหรับ i ที่ต่างกัน

โค้ดด้านบนได้เพิ่มข้อจำกัดนี้โดยใช้เมธอด AllDifferent กับ queens[j]&nbsp;+&nbsp;j และ queens[j]&nbsp;-&nbsp;j สําหรับ i แต่ละรายการ

เพิ่มเครื่องมือสร้างการตัดสินใจ

ขั้นตอนต่อไปคือการสร้างเครื่องมือตัดสินใจ ซึ่งจะกำหนดกลยุทธ์การค้นหาสำหรับปัญหา กลยุทธ์การค้นหาอาจส่งผลอย่างมากต่อเวลาในการค้นหา เนื่องจากมีการเพิ่มข้อจำกัด ซึ่งช่วยลดจำนวนค่าตัวแปรที่เครื่องมือแก้โจทย์จะต้องสำรวจ คุณได้ดูตัวอย่างเรื่องนี้ไปแล้วในตัวอย่าง 4-queens

โค้ดต่อไปนี้จะสร้างตัวสร้างการตัดสินใจโดยใช้เมธอด 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 กัน เครื่องมือแก้โจทย์คณิตเริ่มต้นด้วย queens[0] ซึ่งเป็นตัวแปรแรกในอาร์เรย์ ตามที่กำหนดโดย CHOOSE_FIRST_UNBOUND จากนั้นเครื่องมือแก้โจทย์จะกำหนด queens[0] เป็นค่าที่น้อยที่สุดที่ระบบยังไม่ได้ลองใช้ ซึ่งเป็น 0 ในขั้นตอนนี้ ตามคำสั่งของ ASSIGN_MIN_VALUE ซึ่งจะวางพระราชินีองค์แรกไว้ที่มุมซ้ายบนของกระดาน

จากนั้น เครื่องมือแก้โจทย์จะเลือก queens[1] ซึ่งตอนนี้เป็นตัวแปรแรกที่ไม่มีการเชื่อมโยงใน queens หลังจากเผยแพร่ข้อจำกัดแล้ว จะมีแถวที่เป็นไปได้ 2 แถวสำหรับราชินีในคอลัมน์ 1 ได้แก่ แถว 2 หรือแถว 3 ตัวเลือก ASSIGN_MIN_VALUE จะสั่งให้ตัวแก้ปัญหากำหนด queens[1] = 2 (แต่หากตั้งค่า IntValueStrategy เป็น ASSIGN_MAX_VALUE เครื่องมือแก้โจทย์จะกำหนด queens[1] = 3)

คุณตรวจสอบได้ว่าการค้นหาที่เหลือเป็นไปตามกฎเดียวกันหรือไม่

เรียกใช้เครื่องมือแก้โจทย์และแสดงผลลัพธ์

โค้ดต่อไปนี้จะเรียกใช้ตัวแก้โจทย์และแสดงโซลูชัน

Python

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

C++

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

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

Java

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

C#

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

นี่คือโซลูชันแรกที่โปรแกรมพบสำหรับกระดานขนาด 8x8

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

คุณจะแก้โจทย์ของกระดานขนาดอื่นได้โดยส่งผ่าน N เป็นอาร์กิวเมนต์บรรทัดคำสั่ง ตัวอย่างเช่น python nqueens_cp.py 6 จะแก้โจทย์ สำหรับกระดานขนาด 6x6

ทั้งโปรแกรม

โปรดดูรายการโปรแกรมที่สมบูรณ์ด้านล่าง

Python

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


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

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

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

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

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

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

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


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

C++

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

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

namespace operations_research {

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

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

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

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

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

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

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

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

}  // namespace operations_research

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

Java

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

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

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

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

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

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

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

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

  private NQueensCp() {}
}

C#

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

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

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

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

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

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

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

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

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

จำนวนคำตอบ

จำนวนคำตอบจะเพิ่มขึ้นประมาณเท่าๆ กันกับขนาดของกระดาน:

ขนาดกระดานโซลูชันเวลาในการค้นหาโซลูชันทั้งหมด (มิลลิวินาที)
110
200
300
420
5100
640
7403
8929
935235
1072495
112680378
12142002198
137371211628
1436559662427
152279184410701

คำตอบหลายๆ อย่างเป็นเพียงการหมุนเวียนของโฆษณาแบบอื่นเท่านั้น และระบบนำเทคนิคที่เรียกว่าการแยกสมมาตรไปใช้เพื่อลดจำนวนการคำนวณที่ต้องใช้ได้ เราไม่ใช้คำว่านั้นที่นี่ โซลูชันของเราด้านบน ไม่ได้มุ่งหวังให้รวดเร็ว เพียงใช้ง่าย แน่นอนว่าเราจะทำให้ได้เร็วขึ้นมากหากเราต้องการค้นหาโซลูชันเพียงโซลูชันเดียว แทนที่จะเป็นทั้งหมด โดยใช้เวลาไม่เกิน 2-3 มิลลิวินาทีสำหรับขนาดกระดานสูงสุด 50 เครื่อง