एन-क्वींस समरूपता ब्रेकिंग Google या टूल्स

Question

One of the samples for the Google or-tools is a solver for the n-queens problem. नीचे यह कहता है कि कार्यान्वयन को बाधा सॉल्वर को समरूपता को तोड़ने की बाधाओं को जोड़कर सुधार किया जा सकता है।

इंटरनेट के आसपास देख रहे हैं, I found the symmetry breaking constraints for the n-queens problem, लेकिन मैं अपने जीवन के लिए यह नहीं समझ सकता कि उनको बाधाओं में पाइथन कोड में कैसे परिवर्तित किया जाए जो उन्हें लागू करते हैं।

---

संपादित करें: यह एक बुरा सवाल, चलो अद्यतन था ...

क्या मैं कोशिश की है?

from ortools.constraint_solver import pywrapcp 

N = 8 
solver = pywrapcp.Solver("n-queens") 
# Creates the variables. 
# The array index is the column, and the value is the row. 
queens = [solver.IntVar(0, N - 1, "x%i" % i) for i in range(N)] 
# Creates the constraints. 
# All rows must be different. 
solver.Add(solver.AllDifferent(queens)) 
# All columns must be different because the indices of queens are all different. 
# No two queens can be on the same diagonal. 
solver.Add(solver.AllDifferent([queens[i] + i for i in range(N)])) 
solver.Add(solver.AllDifferent([queens[i] - i for i in range(N)])) 

# TODO: add symmetry breaking constraints 

db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) 
solver.NewSearch(db) 
num_solutions = 0 
while solver.NextSolution(): 
    num_solutions += 1 
solver.EndSearch() 
print() 
print("Solutions found:", num_solutions) 
print("Time:", solver.WallTime(), "ms") 

मैं जानता हूँ कि मैं सरल बाधाओं को सफलतापूर्वक लागू कर सकते हैं:

यहाँ ऊपर पहले लिंक से सेटअप है। अगर मैं सुनिश्चित करने के लिए समाधान हमेशा पहली पंक्ति पर पहले कॉलम में एक रानी है चाहता था, मुझे लगता है कि इस तरह से लागू कर सकते हैं:

solver.Add(queens[0] == 0) 

queens[0] चर पहले कॉलम में क्वीन्स स्थान का प्रतिनिधित्व करता है और इस बाधा ही है संतुष्ट जब पहली कॉलम में पहली पंक्ति में रानी है। यह निश्चित रूप से ऐसा नहीं है जो मैं करना चाहता हूं क्योंकि यह संभव है कि समाधान में किसी भी कोने कोशिकाएं शामिल न हों।

एन-क्वींस समस्या के लिए समरूपता तोड़ने की बाधाएं नीचे पाई गई हैं। वे सीधे दूसरे पैराग्राफ में लिंक से खींचे जाते हैं।

मैं समझता हूँ कि कैसे इन बाधाओं काम करते हैं। विचार यह है कि आप राज्य को समकक्ष राज्य में बदलने के लिए एन-क्वींस बोर्ड पर प्रत्येक सेल को इस फ़ंक्शन को लागू कर सकते हैं। इनमें से एक राज्य उस राज्य का वैधानिक प्रतिनिधित्व होगा। इसका उपयोग डुप्लिकेट मूल्यांकन को समाप्त करके भविष्य की प्रसंस्करण को पूर्ववत करने के लिए एक विधि के रूप में किया जाता है।

अगर मैं वास्तव में इस तथ्य के बाद इसे कार्यान्वित कर रहा था, तो मैं वही करूँगा जो मैंने ऊपर वर्णित किया है, प्रत्येक संभावित समरूपता ब्रेकिंग फ़ंक्शन का उपयोग करके राज्य को रूपांतरित करें, किसी प्रकार के राज्य हैश की गणना करें (उदाहरण के लिए चयनित पंक्ति की एक स्ट्रिंग प्रत्येक कॉलम में) और प्रत्येक प्रस्तावित समाधान के लिए सबसे कम है कि चुनें। उन लोगों पर भावी प्रसंस्करण छोड़ें जिन्हें हमने पहले देखा है।

मेरी समस्या यह है कि मुझे नहीं पता कि इन परिवर्तनों को Google या टूल्स बाधा प्रोग्रामिंग सॉल्वर के लिए बाधाओं में कैसे परिवर्तित किया जाए।

चलिए सबसे सरल, d1(r[i] = j) => r[j] = i, मुख्य विकर्ण के बारे में प्रतिबिंब को देखें। मुझे क्या पता है कि परिवर्तन को सभी कोशिकाओं पर लागू करने की आवश्यकता है, फिर मौजूदा स्थिति के मुकाबले एक को विस्तारित होने से रोकने के लिए। मुझे समझने के लिए पाइथन के बारे में पर्याप्त समझ में नहीं आता है कि परिवर्तन के लिए किस तरह की अभिव्यक्ति यहां काम करती है, और मैं यह समझ नहीं सकता कि इस विशेष सॉल्वर के लिए वर्तमान स्थिति में परिवर्तन की तुलना करने वाली बाधा कैसे बनाई जाए।

state = [queens[i].Value() for i in range(N)] 
symX = [state[N - (i + 1)] for i in range(N)] 
symY = [N - (state[i] + 1) for i in range(N)] 
symD1 = [state.index(i) for i in range(N)] 
symD2 = [N - (state.index(N-(i+1)) + 1) for i in range(N)] 
symR90 = [N - (state.index(i) + 1) for i in range(N)] 
symR180 = [N - (state[N-(i+1)] + 1) for i in range(N)] 
symR270 = [state.index(N-(i+1)) for i in range(N)] 

Answer 1

आपको समेकित समाधानों को खत्म करने वाली बाधाओं की पहचान करने के लिए मांग किए गए समाधानों के बीच ज्ञात समरूपता संबंधों का उपयोग करना होगा।

1. queens[0] >= N/2 के साथ हर समाधान के लिए, तो कोई और, खड़ी नजर आता, queens[0] <= N/2 साथ समाधान है। इसलिए, हम queens[0] के छोटे मूल्य के साथ समाधान के लिए की तलाश और निम्नलिखित बाधा जोड़ सकते हैं:

   solver.Add(queens[0] < (N+1)//2) # Handle both even and odd values of N 
   

2. फिर, एक समाधान हालत queens[0] < queens[N-1] संतोषजनक एक बराबर, क्षैतिज नजर आता, समाधान queens[0] > queens[N-1] संतोषजनक है।

   solver.Add(queens[0] < queens[N-1]) 
   

मैं आसानी से घूर्णी समरूपता को दर्शाती है की कोई समस्या तैयार नहीं कर सका: आप केवल उन समाधानों, जहां वाम-पंथी कॉलम में रानी सबसे दायीं ओर स्तंभ में रानी नीचे है देखने के लिए solver बता सकते हैं , लेकिन मुझे विश्वास है कि यह संभव है।

Answer 2

मैंने समेकन का उपयोग करके नई पेड़ के रूप में खोज पेड़ को छीनने के लिए एक कस्टम निर्णय बिल्डर का उपयोग करने की कोशिश की, लेकिन मैं इसे काम नहीं कर सका।

इसके बजाय मुझे एक खोज मॉनिटर का उपयोग करना पड़ा जो प्रत्येक समाधान की घटना को कैप्चर करता है और जांचता है कि वह समाधान पिछले एक की समरूपता है या नहीं।

यहां मैं खोज मॉनिटर का कोड जोड़ता हूं, "स्वीकार्यता" फ़ंक्शन को ओवरराइड करने वाले समाधान का कब्जा, और gen_symetries सभी संभावित समरूपता की गणना और जांच करने के लिए कार्य करता है।

class SearchMonitor(pywrapcp.SearchMonitor): 
    def __init__(self, solver, q): 
     pywrapcp.SearchMonitor.__init__(self, solver) 
     self.q = q 
     self.all_solutions = [] 
     self.unique_solutions = [] 
     self.n = len(self.q) 

    def AcceptSolution(self): 
     qval = [self.q[i].Value() for i in range(self.n)] 
     self.all_solutions.append(qval) 

     symmetries = [vv in self.unique_solutions for vv in gen_symmetries(self.n, qval)] 

     if sum(symmetries) == 0: 
      self.unique_solutions.append(qval) 

     return False 

def gen_symmetries(n, solution): 
    symmetries = [] 

    #x(r[i]=j) → r[n−i+1]=j 
    x = list(range(n)) 
    for index in range(n): 
     x[n - 1 - index] = solution[index] 

    symmetries.append(x) 

    #y(r[i]=j) → r[i]=n−j+1 
    y = list(range(n)) 
    for index in range(n): 
     y[index] = (n - 1 - solution[index]) 

    symmetries.append(y) 

    #d1(r[i]=j) → r[j]=i 
    d1 = list(range(n)) 
    for index in range(n): 
     d1[solution[index]] = index 

    symmetries.append(d1) 

    # d2(r[i]=j) → r[n−j+1]=n−i+1 
    d2 = list(range(n)) 
    for index in range(n): 
     d2[n - 1 - solution[index]] = (n - 1 - index) 

    symmetries.append(d2) 

    # r90(r[i]=j) → r[j] = n−i+1 
    r90 = list(range(n)) 
    for index in range(n): 
     r90[solution[index]] = (n - 1 - index) 

    symmetries.append(r90) 

    # r180(r[i]=j) → r[n−i+1]=n−j+1 
    r180 = list(range(n)) 
    for index in range(n): 
     r180[n - 1 - index] = (n - 1 - solution[index]) 

    symmetries.append(r180) 

    # r270(r[i]=j) → r[n−j+1]=i 
    r270 = list(range(n)) 
    for index in range(n): 
     r270[n - 1 - solution[index]] = index 

    symmetries.append(r270) 

    return symmetries 

बाद में आपको मॉनिटर को इस तरह अपने सॉल्वर में जोड़ना होगा।

monitor = SearchMonitor(solver, queens) 
solver.Solve(db, monitor) 
solver.NewSearch(db) 

और अंत में बस मुद्रण सभी अद्वितीय समाधान

print("Unique Solutions:", len(monitor.unique_solutions), monitor.unique_solutions) 

आप सार में पूर्ण काम कर उदाहरण देख सकते हैं।

https://gist.github.com/carlgira/7a4e6cf0f7b7412762171015917bccb4