नीचे दिए गए सेक्शन में, हम शतरंज के खेल पर आधारित कंबाइनेटर सवाल के आधार पर कंस्ट्रेंट प्रोग्रामिंग (सीपी) के बारे में बताएंगे. शतरंज में रानी हॉरिज़ॉन्टल, वर्टिकल, और तिरछे तरीके से हमला कर सकती है. N-क्वीन्स की समस्या के बारे में यह पूछा जाता है:
N क्वींस को NxN के शतरंज की बोर्ड पर कैसे रखा जा सकता है, ताकि दोनों एक-दूसरे पर हमला न कर सकें?
नीचे, N = 4 के लिए N-क्वींस से जुड़ी समस्या का संभावित समाधान दिया गया है.
कोई भी दो रानी एक ही पंक्ति, कॉलम या डायगनल पर नहीं हैं.
ध्यान रखें कि यह ऑप्टिमाइज़ेशन की समस्या नहीं है: हम एक सबसे बेहतर समाधान के बजाय, सभी संभावित समाधान ढूंढना चाहते हैं, जो इसे कंस्ट्रेंट प्रोग्रामिंग के लिए एक स्वाभाविक विकल्प बनाते हैं. नीचे दिए गए सेक्शन में, एन-क्वीन की समस्या को हल करने के लिए सीपी (CP) अप्रोच के बारे में बताया गया है. साथ ही, उन प्रोग्राम के बारे में भी बताया गया है जो CP-SAT सॉल्वर और ओरिजनल सीपी सॉल्वर, दोनों का इस्तेमाल करके इस समस्या को हल करते हैं.
एन-क्वींस समस्या को हल करने के लिए सीपी (सीपी) का तरीका
सीपी सॉल्वर, किसी सवाल में मौजूद वैरिएबल की वैल्यू के सभी संभावित असाइनमेंट को ध्यान में रखकर काम करता है, ताकि सही तरीकों का पता लगाया जा सके. चार-क्वींस वाले सवाल में, सॉल्वर सबसे बाईं ओर से शुरू होता है और हर कॉलम में क्रमिक तौर पर एक क्वीन रखता है. इस कॉलम में, ऐसी जगह मौजूद होती है जहां पहले रखी गई किसी क्वीन का हमला नहीं होता है.
प्रसार और बैकट्रैकिंग
कंस्ट्रेंट प्रोग्रामिंग खोज के दो मुख्य एलिमेंट हैं:
- प्रोपेगेशन — जब भी सॉल्वर किसी वैरिएबल को कोई वैल्यू असाइन करता है, तब सीमाएं असाइन नहीं किए गए वैरिएबल की संभावित वैल्यू पर पाबंदियां जोड़ देती हैं. ये पाबंदियां, आगे के वैरिएबल असाइनमेंट में लागू होती हैं. उदाहरण के लिए, 4-क्वींस के सवाल में, हर बार जब सॉल्वर किसी रानी को चुनता है, तो ऐसी और लाइन पर दूसरी क्वींस नहीं रखी जा सकतीं. प्रॉपेगेशन की मदद से, खोज की रफ़्तार बढ़ सकती है. ऐसा करने से, सॉल्वर में अलग-अलग वैरिएबल वैल्यू के सेट कम हो जाते हैं.
- बैकट्रैकिंग तब होती है, जब शर्तों की वजह से या तो सॉल्वर अगले वैरिएबल के लिए कोई वैल्यू असाइन नहीं कर सकता या फिर उसे कोई हल मिल जाता है. दोनों ही मामलों में, सॉल्वर पिछले चरण पर वापस लौट जाता है और उस चरण में वैरिएबल की वैल्यू को ऐसी वैल्यू में बदल देता है जिसे पहले कभी आज़माया न गया हो. 4-क्वीन्स के उदाहरण में, इसका मतलब है कि क्वीन को मौजूदा कॉलम में, नए स्क्वेयर में ले जाना है.
इसके बाद, आपको दिखेगा कि कंस्ट्रेंट प्रोग्रामिंग, 4-क्वींस की समस्या को हल करने के लिए प्रोपेगेशन और बैकट्रैकिंग का इस्तेमाल कैसे करती है.
मान लें कि सॉल्वर ऊपर बाएं कोने में एक रानी को स्वेच्छा से रखकर शुरुआत करता है. यह एक अनुमान है. ऐसा हो सकता है कि ऊपर बाएं कोने में रानी के साथ कोई हल मौजूद न हो.
इस परिकल्पना को देखते हुए, हम किन सीमाओं को लागू कर सकते हैं? इसमें एक सीमा यह है कि एक कॉलम में सिर्फ़ एक रानी हो सकती है (नीचे दिए गए स्लेटी रंग के X) और दूसरी पाबंदी, एक ही विकर्ण (नीचे मौजूद लाल X) पर दो क्वीन इस्तेमाल करने की अनुमति नहीं देती.
हमारे तीसरे कंस्ट्रेंट में, एक ही पंक्ति में मौजूद क्वींस इस्तेमाल करने की अनुमति नहीं है:
हमारी सीमाओं को आगे बढ़ाया गया. हम दूसरे अनुमान की जांच कर सकते हैं और बचे हुए स्क्वेयर में से एक पर दूसरी रानी को डाल सकते हैं. हमारा सॉल्वर दूसरे कॉलम में, पहले उपलब्ध स्क्वेयर को इसमें शामिल करने का फ़ैसला ले सकता है:
डायगनल कंस्ट्रेंट को लागू करने के बाद, हम देख सकते हैं कि इसके तीसरे कॉलम या आखिरी लाइन में कोई स्क्वेयर नहीं है:
इस समय कोई समाधान संभव नहीं है, तो हमें पीछे जाकर काम करना होगा. एक विकल्प, सॉल्वर के पास दूसरे कॉलम में मौजूद दूसरे स्क्वेयर को चुनने का विकल्प होता है. हालांकि, कंस्ट्रेंट प्रोपेगेशन की वजह से, रानी को तीसरे कॉलम की दूसरी लाइन में ले जाया जाता है. इससे चौथी रानी के लिए कोई मान्य स्पॉट नहीं बचता है:
इसलिए, सॉल्वर को फिर से पहली रानी के प्लेसमेंट पर वापस लौटना होगा. हमने दिखाया है कि क्वींस की समस्या का कोई भी हल, कोने के स्क्वेयर पर नहीं दिखेगा.
कोई रानी नहीं है, इसलिए सॉल्वर पहली रानी को एक-एक करके नीचे ले जाता है. इसके बाद, दूसरी रानी के लिए सिर्फ़ एक जगह छूट जाती है.
दोबारा से दिखाई देने से पता चलता है कि तीसरी महारानी के लिए सिर्फ़ एक जगह बची है:
चौथी और आखिरी रानी के लिए:
हमारे पास अपना पहला समाधान है! अगर हम पहला समाधान ढूंढने के बाद अपने सॉल्वर को रोकने के लिए कहते हैं, तो वह यहीं पर खत्म हो जाएगा. ऐसा न करने पर वह फिर से पीछे हो जाएगा और पहली रानी को पहले कॉलम की तीसरी पंक्ति में रख देगा.
CP-SAT के इस्तेमाल से जुड़ी समस्या का हल
N-क्वीन से जुड़ी समस्या, कंस्ट्रेंट प्रोग्रामिंग के लिए सबसे सही तरीका है. इस सेक्शन में, हम एक छोटे 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}"); }
यहां हम मान लेते हैं कि j
कॉलम में, रानी की पंक्ति का नंबर queens[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-क्वींस के सवाल (अलग-अलग लाइन, कॉलम, और डायगनल वाली क्वींस) के लिए, तीन स्थितियों की गारंटी कैसे मिलती है.
एक ही पंक्ति में कोई दो रानियां नहीं हैं
सॉल्वर के AllDifferent
तरीके को queens
पर लागू करने से, हर j
के लिए queens[j]
की वैल्यू अलग-अलग हो जाती है. इसका मतलब है कि सभी क्वीन अलग-अलग लाइन में होनी चाहिए.
एक ही कॉलम पर कोई दो क्वीन नहीं
यह कंस्ट्रेंट, queens
की परिभाषा में साफ़ तौर पर बताया गया है.
queens
के किसी भी दो एलिमेंट का इंडेक्स एक ही नहीं हो सकता, इसलिए एक ही कॉलम में दो रानियों को नहीं रखा जा सकता.
एक ही तिरछी दिशा में कोई दो रानियां नहीं
डाइगनल कंस्ट्रेंट, लाइन और कॉलम के कंस्ट्रेंट की तुलना में थोड़ा मुश्किल है. पहली, अगर दो रानी एक ही तिरछी दिशा में रखी हुई हैं, तो इनमें से कोई एक स्थिति सही होनी चाहिए:
- दोनों रानियों के लिए पंक्ति का नंबर और कॉलम का नंबर बराबर होता है.
दूसरे शब्दों में,
queens(j) + j
की दो अलग-अलग इंडेक्सj
के लिए एक ही वैल्यू है. - दोनों रानियों में से हर एक के लिए पंक्ति की संख्या घटाकर, कॉलम की संख्या बराबर होती है.
इस मामले में,
queens(j) - j
की दो अलग-अलग इंडेक्सj
के लिए एक ही वैल्यू है.
इनमें से एक स्थिति का मतलब है कि रानियां एक ही आरोही विकर्ण पर लेट रही हैं ( बाएं से दाएं जा रही हैं), जबकि दूसरे का मतलब है कि वे एक ही घटते हुए विकर्ण पर लेट हैं. कौनसी शर्त आरोही और किस अवरोही से संबंधित है यह इस बात पर निर्भर करता है कि आपने पंक्तियों और कॉलम को कैसे क्रम से लगाया है. जैसा कि पिछले सेक्शन में बताया गया था, समस्याओं को हल करने के क्रम का कोई असर सिर्फ़ इस बात पर नहीं पड़ता कि उन्हें किस तरह विज़ुअलाइज़ किया जाता है.
इसलिए, डायगनल कंस्ट्रेंट का मतलब है कि queens(j) + j
की वैल्यू अलग-अलग होनी चाहिए. साथ ही, अलग-अलग j
के लिए, queens(j) - j
की वैल्यू भी अलग-अलग होनी चाहिए.
AddAllDifferent
तरीके को queens(j) + j
पर लागू करने के लिए, हम j
के लिए 0
से N-1
तक, वैरिएबल के N इंस्टेंस को diag1
कैटगरी में इस तरह डालते हैं:
q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i) diag1.append(q1) model.Add(q1 == queens[j] + j)
इसके बाद, हम diag1
पर AddAllDifferent
लागू करते हैं.
model.AddAllDifferent(diag1)
queens(j) - j
के लिए कंस्ट्रेंट को इसी तरह बनाया गया है.
सलूशन प्रिंटर बनाएं
एन-क्वींस की समस्या के सभी समाधान प्रिंट करने के लिए, आपको सीपी-एसएटी सॉल्वर को एक कॉलबैक भेजना होगा. इस कॉलबैक को सॉल्यूशन प्रिंटर कहा जाता है. जैसे ही सॉल्वर को मिलता है वैसे ही कॉलबैक हर नए सलूशन को प्रिंट करता है. यह कोड एक सॉल्यूशन प्रिंटर बनाता है.
Python
class NQueenSolutionPrinter(cp_model.CpSolverSolutionCallback): """Print intermediate solutions.""" def __init__(self, queens: list[cp_model.IntVar]): cp_model.CpSolverSolutionCallback.__init__(self) self.__queens = queens self.__solution_count = 0 self.__start_time = time.time() @property def solution_count(self) -> int: return self.__solution_count def on_solution_callback(self): current_time = time.time() print( f"Solution {self.__solution_count}, " f"time = {current_time - self.__start_time} s" ) self.__solution_count += 1 all_queens = range(len(self.__queens)) for i in all_queens: for j in all_queens: if self.value(self.__queens[j]) == i: # There is a queen in column j, row i. print("Q", end=" ") else: print("_", end=" ") print() print()
C++
int num_solutions = 0; Model model; model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) { LOG(INFO) << "Solution " << num_solutions; for (int i = 0; i < board_size; ++i) { std::stringstream ss; for (int j = 0; j < board_size; ++j) { if (SolutionIntegerValue(response, queens[j]) == i) { // There is a queen in column j, row i. ss << "Q"; } else { ss << "_"; } if (j != board_size - 1) ss << " "; } LOG(INFO) << ss.str(); } num_solutions++; }));
Java
static class SolutionPrinter extends CpSolverSolutionCallback { public SolutionPrinter(IntVar[] queensIn) { solutionCount = 0; queens = queensIn; } @Override public void onSolutionCallback() { System.out.println("Solution " + solutionCount); for (int i = 0; i < queens.length; ++i) { for (int j = 0; j < queens.length; ++j) { if (value(queens[j]) == i) { System.out.print("Q"); } else { System.out.print("_"); } if (j != queens.length - 1) { System.out.print(" "); } } System.out.println(); } solutionCount++; } public int getSolutionCount() { return solutionCount; } private int solutionCount; private final IntVar[] queens; }
C#
public class SolutionPrinter : CpSolverSolutionCallback { public SolutionPrinter(IntVar[] queens) { queens_ = queens; } public override void OnSolutionCallback() { Console.WriteLine($"Solution {SolutionCount_}"); for (int i = 0; i < queens_.Length; ++i) { for (int j = 0; j < queens_.Length; ++j) { if (Value(queens_[j]) == i) { Console.Write("Q"); } else { Console.Write("_"); } if (j != queens_.Length - 1) Console.Write(" "); } Console.WriteLine(""); } SolutionCount_++; } public int SolutionCount() { return SolutionCount_; } private int SolutionCount_; private IntVar[] queens_; }
ध्यान दें कि सॉल्यूशन प्रिंटर को Python क्लास के तौर पर लिखा जाना चाहिए. ऐसा Python इंटरफ़ेस में दिए गए C++ सॉल्वर की वजह से होता है.
सलूशन प्रिंटर में, नीचे दी गई लाइनों के ज़रिए सलूशन प्रिंट किए जाते हैं.
for v in self.__variables: print('%s = %i' % (v, self.Value(v)), end = ' ')
इस उदाहरण में, self.__variables
वैरिएबल queens
है और हर v
, queens
की आठ एंट्री में से एक से मेल खाता है. यह समाधान को
इस रूप में प्रिंट करता है: x0 = queens(0) x1 = queens(1) ... x7 = queens(7)
, जहां
xi
, i
पंक्ति में रानी का कॉलम नंबर है.
अगले सेक्शन में, एक समाधान का उदाहरण दिया गया है.
सॉल्वर को कॉल करें और नतीजे दिखाएं
यह कोड, सॉल्वर चलाता है और सलूशन दिखाता है.
Python
solver = cp_model.CpSolver() solution_printer = NQueenSolutionPrinter(queens) solver.parameters.enumerate_all_solutions = True solver.solve(model, solution_printer)
C++
// Tell the solver to enumerate all solutions. SatParameters parameters; parameters.set_enumerate_all_solutions(true); model.Add(NewSatParameters(parameters)); const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model); LOG(INFO) << "Number of solutions found: " << num_solutions;
Java
CpSolver solver = new CpSolver(); SolutionPrinter cb = new SolutionPrinter(queens); // Tell the solver to enumerate all solutions. solver.getParameters().setEnumerateAllSolutions(true); // And solve. solver.solve(model, cb);
C#
// Creates a solver and solves the model. CpSolver solver = new CpSolver(); SolutionPrinter cb = new SolutionPrinter(queens); // Search for all solutions. solver.StringParameters = "enumerate_all_solutions:true"; // And solve. solver.Solve(model, cb);
कार्यक्रम में 8x8 बोर्ड के लिए 92 अलग-अलग समाधान मिलते हैं. यह रहा पहला सवाल।
Q _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ ...91 other solutions displayed... Solutions found: 92
N में को कमांड-लाइन आर्ग्युमेंट के तौर पर पास करके, किसी दूसरे साइज़ के बोर्ड की समस्या को हल किया जा सकता है. उदाहरण के लिए, अगर प्रोग्राम का नाम queens
है, तो
python nqueens_sat.py 6
6x6 बोर्ड की समस्या को हल करता है.
पूरा कार्यक्रम
N-क्वीन्स प्रोग्राम का पूरा प्रोग्राम यहां दिया गया है.
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()}"); } }
ओरिजनल सीपी सॉल्वर का इस्तेमाल करने वाला समाधान
यहां दिए गए सेक्शन में एक Python प्रोग्राम दिया गया है. इसमें ओरिजनल सीपी सॉल्वर का इस्तेमाल करके, एन-क्वीन की समस्याओं को हल किया जाता है. हालांकि, हम नया सीपी-एसएटी सॉल्वर इस्तेमाल करने का सुझाव देते हैं
लाइब्रेरी इंपोर्ट करना
नीचे दिया गया कोड, ज़रूरी लाइब्रेरी को इंपोर्ट करता है.
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;
सॉल्वर का एलान करें
इस कोड में मूल सीपी सॉल्वर का एलान किया गया है.
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-क्वीन के सवाल के साथ (अलग-अलग लाइन, कॉलम, और डायगनल वाली क्वीन) के लिए तीन शर्तें तय करने की गारंटी देती हैं.
एक ही पंक्ति में कोई दो रानियां नहीं हैं
सॉल्वर के AllDifferent
तरीके को queens
पर लागू करने से, हर j
के लिए queens[j]
की वैल्यू अलग-अलग हो जाती है. इसका मतलब है कि सभी क्वीन अलग-अलग लाइन में होनी चाहिए.
एक ही कॉलम पर कोई दो क्वीन नहीं
यह कंस्ट्रेंट, queens
की परिभाषा में साफ़ तौर पर बताया गया है.
queens
के किसी भी दो एलिमेंट का इंडेक्स एक ही नहीं हो सकता, इसलिए एक ही कॉलम में दो रानियों को नहीं रखा जा सकता.
एक ही तिरछी दिशा में कोई दो रानियां नहीं
डाइगनल कंस्ट्रेंट, लाइन और कॉलम के कंस्ट्रेंट की तुलना में थोड़ा मुश्किल है. पहली, अगर दो रानियां एक ही तिरछी होती हैं, तो इनमें से कोई एक बात सही होनी चाहिए:
- अगर विकर्ण बाएं से दाएं जा रहा है, तो दोनों रानियों के लिए पंक्ति की संख्या और कॉलम की संख्या बराबर है. इसलिए,
queens(i) + i
की दो अलग-अलग इंडेक्सi
के लिए एक ही वैल्यू है. - अगर विकर्ण बढ़ते हुए क्रम में है, तो दोनों रानियों की हर पंक्ति की संख्या में से हर कॉलम की संख्या घटाकर मिलने वाली संख्या बराबर होती है. इस मामले में,
queens(i) - i
की दो अलग-अलग इंडेक्सi
के लिए एक ही वैल्यू है.
इसलिए, डायगनल कंस्ट्रेंट का मतलब है कि queens(i) + i
की वैल्यू अलग-अलग होनी चाहिए. साथ ही, अलग-अलग i
के लिए, queens(i) - i
की वैल्यू भी अलग-अलग होनी चाहिए.
ऊपर दिया गया कोड, हर i
के लिए
AllDifferent
तरीके को queens[j] + j
और queens[j] - j
पर लागू करके, इस कंस्ट्रेंट को जोड़ता है.
डिसिज़न बिल्डर जोड़ें
अगला कदम है डिसिज़न बिल्डर बनाना. यह समस्या के लिए खोज की रणनीति सेट करता है. खोज की रणनीति, खोज करने के समय पर गहरा असर डाल सकती है. ऐसा पाबंदियों की वजह से होता है. इससे सॉल्वर को एक्सप्लोर करने वाली वैरिएबल वैल्यू की संख्या कम हो जाती है. आपने इसका एक उदाहरण पहले ही 4-क्वीन्स के उदाहरण में देखा है.
यहां दिया गया कोड, सॉल्वर के Phase
तरीके का इस्तेमाल करके डिसिज़न बिल्डर बनाता है.
Python
db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
C++
DecisionBuilder* const db = solver.MakePhase( queens, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);
Java
// Create the decision builder to search for solutions. final DecisionBuilder db = solver.makePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
C#
// Create the decision builder to search for solutions. DecisionBuilder db = solver.MakePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
Phase
तरीके से जुड़े इनपुट तर्कों की ज़्यादा जानकारी के लिए, डिसिज़न बिल्डर देखें.
चार-क्वीन वाले उदाहरण में डिसिज़न बिल्डर कैसे काम करता है
आइए, चार-क्वीन के उदाहरण में देखते हैं कि डिसिज़न बिल्डर, खोज को कैसे भेजता है.
सॉल्वर, queens[0]
से शुरू होता है. यह कलेक्शन का पहला वैरिएबल होता है. इसे CHOOSE_FIRST_UNBOUND
ने भेजा है. इसके बाद, सॉल्वर queens[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();
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}"); } }
हल की संख्या
बोर्ड के आकार के साथ विलयनों की संख्या करीब-करीब बढ़ जाती है:
बोर्ड का साइज़ | समाधान | सभी समाधान ढूंढने में लगने वाला समय (मि॰से॰) |
---|---|---|
1 | 1 | 0 |
2 | 0 | 0 |
3 | 0 | 0 |
4 | 2 | 0 |
5 | 10 | 0 |
6 | 4 | 0 |
7 | 40 | 3 |
8 | 92 | 9 |
9 | 352 | 35 |
10 | 724 | 95 |
11 | 2680 | 378 |
12 | 14200 | 2198 |
13 | 73712 | 11628 |
14 | 365596 | 62427 |
15 | 2279184 | 410701 |
कई समाधान सिर्फ़ दूसरे लोगों का रोटेशन होते हैं. साथ ही, सिमेट्री ब्रेकिंग नाम की तकनीक का इस्तेमाल करके, कंप्यूटेशन की ज़रूरत को कम किया जा सकता है. हम यहां इसका इस्तेमाल नहीं करते; ऊपर बताए गए समाधान को तेज़ नहीं, बल्कि सामान्य तरीके से पेश किया गया है. ज़ाहिर है कि हम इसे ज़्यादा तेज़ बना सकते हैं, अगर हमें इन सभी के बजाय सिर्फ़ एक समाधान खोजना हो: 50 तक के बोर्ड साइज़ के लिए कुछ मिलीसेकंड से ज़्यादा नहीं.