"फ्लिप ऑल" (लाइट आउट) गेम के लिए कोई भी एल्गोरिदम? इस गेम में

Question

: http://www.mathsisfun.com/games/allout.html हल फ़ंक्शन किसी भी मामले को हल कर सकता है, भले ही आप मूल बोर्ड का "दुरुपयोग" कैसे करें। इस खेल को हल करने के लिए कृपया मुझे एल्गोरिदम बताएं। मैंने दिनों के लिए सोचने की कोशिश की है लेकिन अभी भी सभी मामलों को हल करने के लिए कोई सुराग नहीं मिला है।

ठीक है, के बाद कुछ उत्तर और टिप्पणियां पढ़ें (और कम से प्रकाश बाहर खेल का शीघ्रता से अवलोकन किया है), मैं अपने प्रश्न का विस्तार:

विल खेल अलग अगर मैं ग्रिड के आकार का विस्तार (करने के लिए की तरह 25x25)? किसी भी मामले को हल करने के लिए अभी भी कोई संभावित एल्गोरिदम स्वीकार्य समय (< 2s) में हल करने के लिए?

एक वृक्ष संरचना जहां प्रत्येक नोड खेल राज्य और राज्यों के बच्चों उन राज्यों के बीच संक्रमण का प्रतिनिधित्व करते है को लागू करें:

Answer 1

यह गेम अधिकतर लाइट्स आउट के रूप में जाना जाता है, और इसमें कई सुरुचिपूर्ण समाधान हैं, जो कुछ मानक लेकिन कुछ हद तक उन्नत गणित में आधारित हैं। मैं उन सभी का वर्णन यहां नहीं करूंगा लेकिन यदि आप Google को थोड़ा सा सरलता से प्रक्रियाओं से लेकर रैखिक बीजगणित या समूह सिद्धांत में परिवर्तित करने के सभी प्रकार के स्पष्टीकरण पा सकते हैं। कुछ लिंक:

http://www.hamusutaa.com/pilot/solution.html

http://www.ripon.edu/academics/macs/summation/2010/articles/M.%20Madsen%20-%20Lights%20Out.pdf

http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf

संपादित: पुन: अपने दूसरे प्रश्न। मेरे द्वारा पोस्ट किए गए दूसरे लिंक में प्रस्तुत एल्गोरिदम ओ (एन^6) समय में एक एन एक्स एन बोर्ड को हल कर सकता है, जिसका अर्थ है कि आप 25 x 25 बोर्ड को जल्दी से हल करने में सक्षम होना चाहिए।

Answer 2

सबसे ऐ "खेल" समस्याओं की तरह, वहाँ एक सामान्य तरीका है।

या तो इसे चौड़ाई-पहली खोज के रूप में करें (गहराई-ठीक ठीक है अगर आप पिछले राज्यों का लॉग रखते हैं जो आपने देखा है और उन्हें फिर से देखने से इंकार कर दिया है, और आपको इष्टतम समाधान खोजने की परवाह नहीं है) या आओ आशावादी हेरिस्टिक के साथ जो आपको ए * का उपयोग करने की अनुमति देता है। एक सुंदर भयानक ह्युरिस्टिक मैं सोच सकता हूं "पहेली को जीतने के लिए फ़्लॉल करने की आवश्यकता वाली मंडलियों की संख्या, 5 से विभाजित है।" मुझे यकीन नहीं है कि क्या कोई बेहतर है; मुझे इस पर लोगों के इनपुट को सुनने में दिलचस्पी होगी (ध्यान दें कि इसे आशावादी होना चाहिए, यानी, हेरिस्टिक कभी भी आवश्यक चालों की संख्या की गणना नहीं कर सकता है।)

अधिक जानकारी में जाना थोड़ा मूर्ख है यह इतना बड़ा विषय है, और इसके अलावा, यदि आप जानते हैं कि चौड़ाई-पहली खोज या ए * कैसे करना है, तो यह बहुत आसान है।

Answer 3

इस समस्या को हल करने के लिए एक प्रसिद्ध विधि है। X_1, ..., x_n को समाधान के भाग के रूप में n'th बटन दबाएं या नहीं, और a_1, ..., an_n प्रारंभिक स्थिति होने दें। आप नीचे कुछ लिख सकते हैं

a_1 a_2 a_3 
a_4 a_5 a_6 
a_7 a_8 a_9 

अब,:

मान लीजिए कि आप एक 3x3 समस्या को सुलझाने रहे हैं, और चर इस तरह स्थापित कर रहे हैं:

x_1 x_2 x_3 
x_4 x_5 x_6 
x_7 x_8 x_9 

और इस प्रारंभिक अवस्था है समीकरण (अंकगणित मॉड्यूलो 2 में) कि समाधान को संतुष्ट करना चाहिए।यह मूल रूप से नियम को एन्कोड कर रहा है कि किस स्विच से एक विशेष प्रकाश टॉगल हो जाता है।

a_1 = x_1 + x_2 + x_4 
a_2 = x_1 + x_2 + x_3 + x_5 
... 
a_5 = x_2 + x_4 + x_5 + x_6 + x_8 
... 
a_9 = x_6 + x_8 + x_9 

अब आप एक साथ समीकरणों के इस सेट को हल करने के लिए गाऊशियन उन्मूलन का उपयोग कर सकते हैं। चूंकि आप अंकगणित मॉड्यूलो 2 में काम कर रहे हैं, यह वास्तविक संख्याओं पर एक साथ समीकरणों की तुलना में वास्तव में थोड़ा आसान है। उदाहरण के लिए, दूसरे समीकरण में x_1 से छुटकारा पाने के लिए, बस इसे पहले समीकरण जोड़ें।

a_1 + a_2 = (x_1 + x_2 + x_4) + (x_1 + x_2 + x_3 + x_5) = x_3 + x_4 + x_5 

विशेष रूप से, गणित सापेक्ष 2 में गाऊसी उन्मूलन एल्गोरिथ्म है:

• उस में एक x_1 साथ एक समीकरण उठाओ। इसे नाम दें E_1।
• इसमें एक x_1 के साथ हर दूसरे अज्ञात समीकरण में E_1 जोड़ें।
• x_2, x_3, ...., x_n के लिए दोहराना।

अब, ई_एन एक समीकरण है जिसमें केवल x_n है। आप x_n के मान को प्रतिस्थापित कर सकते हैं जो आप इससे पहले के समीकरणों में प्राप्त करते हैं। E_ {n-1}, ..., E_1 के लिए दोहराएं।

कुल मिलाकर, यह ओ (एन^3) संचालन में समस्या हल करता है।

यहां कुछ कोड है।

class Unsolvable(Exception): 
    pass 

def switches(vs): 
    n, m = len(vs), len(vs[0]) 
    eqs = [] 
    for i in xrange(n): 
     for j in xrange(m): 
      eq = set() 
      for d in xrange(-1, 2): 
       if 0 <= i+d < n: eq.add((i+d)*m+j) 
       if d != 0 and 0 <= j+d < m: eq.add(i*m+j+d) 
      eqs.append([vs[i][j], eq]) 

    N = len(eqs) 
    for i in xrange(N): 
     for j in xrange(i, N): 
      if i in eqs[j][1]: 
       eqs[i], eqs[j] = eqs[j], eqs[i] 
       break 
     else: 
      raise Unsolvable() 
     for j in xrange(i+1, N): 
      if i in eqs[j][1]: 
       eqs[j][0] ^= eqs[i][0] 
       eqs[j][1] ^= eqs[i][1] 

    for i in xrange(N-1, -1, -1): 
     for j in xrange(i): 
      if i in eqs[j][1]: 
       eqs[j][0] ^= eqs[i][0] 
       eqs[j][1] ^= eqs[i][1] 
    return [(i//m,i%m) for i, eq in enumerate(eqs) if eq[0]] 

print switches(([1, 0, 0], [0, 1, 0], [0, 0, 1], [0, 0, 0])) 

आप इसे एक समय में प्रारंभिक स्थिति देते हैं। यह उन स्विचों को वापस करता है जिन्हें आपको सभी रोशनी बंद करने के लिए दबाए जाने की आवश्यकता होती है।

यह मेरे लैपटॉप पर आधे सेकेंड से भी कम समय में 50x50 समस्या हल करता है।