एक पहेली खेल

Question

के लिए बोर्ड उत्पन्न करने के लिए एल्गोरिदम बनाने के लिए संघर्ष करना मैं एक पहेली पहेली खेल बनाना चाहता हूं। प्रश्न के लिए, मान लीजिए कि बोर्ड एक ग्रिड है जिसमें 4 x 4 वर्ग शामिल हैं। (वास्तविक पहेली खेल में, यह संख्या 1..15 होगी)

एक संख्या केवल प्रत्येक कॉलम में एक बार हो सकती है और एक बार प्रत्येक पंक्ति में, सुडोकू की तरह थोड़ा, लेकिन "वर्ग" के बिना।

मान्य:

[1, 2, 3, 4 
2, 3, 4, 1 
3, 4, 1, 2 
4, 1, 2, 3] 

मैं एक एल्गोरिथ्म है कि लगातार उत्पन्न होगा वैध, यादृच्छिक n x, n बोर्डों के साथ आ नहीं कर पा रहे।

मैं इसे सी # में लिख रहा हूं।

Answer 1

मैं सोच सकता हूं कि सबसे आसान तरीका आंशिक गेम बनाना और इसे हल करना होगा। यदि यह हल करने योग्य नहीं है, या यदि यह गलत है, तो दूसरा करें। ;-)

Answer 2

वर्गों के बिना सुडोकू सुडोकू की तरह थोड़ा सा लगता है। :)

http://www.codeproject.com/KB/game/sudoku.aspx

वे वहाँ का उपयोग बोर्ड जनरेटर कोड का एक विवरण नहीं है।

Answer 3

ऐसे कई संयोजन नहीं हैं जिन्हें आपको आजमाने की आवश्यकता है। आप हमेशा एक वैध बोर्ड को पुनर्व्यवस्थित कर सकते हैं ताकि शीर्ष पंक्ति 1,2,3,4 (प्रतीकों को रीमेप करके) हो, और बायां कॉलम 1,2,3,4 (4 से 4 पंक्तियों को पुन: व्यवस्थित करके) हो। प्रत्येक पंक्ति पर शेष 3 प्रतीकों के केवल 6 क्रमपरिवर्तन होते हैं, ताकि आप उन पर लूप कर सकें जो 216 संभावित बोर्ड मान्य हैं। आप मान्य लोगों को भी स्टोर कर सकते हैं।

फिर यादृच्छिक रूप से एक वैध बोर्ड चुनें, यादृच्छिक रूप से पंक्तियों को पुनर्व्यवस्थित करें, और यादृच्छिक रूप से प्रतीकों को पुन: असाइन करें।

Answer 4

ऐसा लगता है कि आप इस वैध उदाहरण को एल्गोरिदम में इनपुट के रूप में उपयोग कर सकते हैं जो यादृच्छिक रूप से दो पंक्तियों को एक यादृच्छिक संख्या में बदल देता है, फिर दो यादृच्छिक कॉलम को यादृच्छिक संख्या में बदल देता है।

Answer 5

http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ देखें - उसे कई पहेली मिल गई हैं जिनमें सटीक रूप से यह बाधा है (दूसरों के बीच)।

Answer 6

अपना पहला वैध उदाहरण का उपयोग करें:

1 2 3 4 
2 3 4 1 
3 4 1 2 
4 1 2 3 

फिर से बेतरतीब ढंग से 2 क्रमपरिवर्तन बनाने {1, 2, 3, 4}।

पंक्तियों की अनुमति देने के लिए पहले और कॉलम को अनुमति देने के लिए दूसरा उपयोग करें।

आप Knuth के The Art of Computer Programming (TAOCP), वॉल्यूम 4 फ़स्किकल 2, जेनरेटिंग ऑल टुपल्स एंड पर्म्यूटेशंस (2005), वी + 128 पीपी में क्रमपरिवर्तन बनाने के कई तरीके पा सकते हैं। आईएसबीएन 0-201-85393-0।

आप (बात यह है कि क्रमपरिवर्तन की चर्चा की) एक लाइब्रेरी में कोई प्रति, एक प्रीप्रिंट नहीं मिलती है तो उसकी साइट पर उपलब्ध है: fasc2b.ps.gz

---

संपादित करें - सुधार

उपर्युक्त समाधान 500-इन्टर्रल सर्वर त्रुटि के समान है। लेकिन मुझे लगता है कि दोनों को सभी वैध व्यवस्था नहीं मिलेंगी।

उदाहरण के लिए वे मिल जाएगा:

1 3 2 4 
3 1 4 2 
2 4 1 3 
4 2 3 1 

यह नहीं लेकिन एक:

1 2 3 4 
2 1 4 3 
3 4 1 2 
4 3 2 1 

एक और चरण की जरूरत है: पंक्तियों और स्तंभों उलटफेर (या तो मेरी या 500 के रास्ते का प्रयोग करके) के बाद, एक और क्रमपरिवर्तन बनाएं (इसे s3 पर कॉल करें) और सरणी में सभी संख्याओं को अनुमति देने के लिए इसका उपयोग करें।

s3 = randomPermutation(1 ... n) 
for i=1 to n 
    for j=1 to n 
    array[i,j] = s3(array[i,j]) 

Answer 7

मैं सी # नहीं बोलता, लेकिन निम्नलिखित एल्गोरिदम को आसानी से अनुवादित किया जाना चाहिए।

एसोसिएट प्रत्येक पंक्ति और स्तंभ के साथ संख्या 1..N से मिलकर एक सेट:,

for i = 1 to N 
    row_set[i] = column_set[i] = Set(1 .. N) 

फिर मैट्रिक्स के माध्यम से एक भी पास कर में मान्य सेट तत्वों से बेतरतीब ढंग से प्रत्येक स्थिति के लिए एक प्रवेश चुनने वह पंक्ति और स्तंभ। संबंधित पंक्ति और कॉलम सेट से चुने गए नंबर को हटाएं।

for r = 1 to N 
    for c = 1 to N 
    k = RandomChoice(Intersection(column_set[c], row_set[r])) 
    puzzle_board[r, c] = k 
    column_set[c] = column_set[c] - k 
    row_set[r] = row_set[r] - k 
    next c 
next r 

Answer 8

ग्राफ रंग एल्गोरिदम पर मेरी श्रृंखला पढ़कर प्रारंभ:

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

यह इससे आपकी समस्या से कोई लेना-देना नहीं है की तरह लग रहा है, लेकिन समय आपका काम हो गया द्वारा, आप देखेंगे कि इसमें आपकी समस्या के साथ सब कुछ है।

---

ठीक है, अब आप पढ़ा है कि, आप जानते हैं कि आप का वर्णन एक सुडोकू की तरह पहेली करने के लिए एक ग्राफ रंग एल्गोरिथ्म का उपयोग और फिर पहेली का एक विशिष्ट उदाहरण को हल कर सकते हैं। लेकिन स्पष्ट रूप से आप पर पहेली उत्पन्न करने के लिए उसी एल्गोरिदम का उपयोग कर सकते हैं।

अपने ग्राफ क्षेत्रों को परिभाषित करके प्रारंभ करें जो पूरी तरह से जुड़े हुए हैं।

फिर एल्गोरिदम को संशोधित करें ताकि यह दो समाधान ढूंढने का प्रयास कर सके।

अब एक खाली ग्राफ बनाएं और यादृच्छिक रंग में यादृच्छिक रंग में से एक क्षेत्र सेट करें। ग्राफ को हल करने का प्रयास करें। क्या दो समाधान थे? फिर एक और यादृच्छिक रंग जोड़ें। दुबारा कोशिश कीजिये। क्या कोई समाधान नहीं था? फिर एक कदम का बैक अप लें और एक अलग यादृच्छिक रंग जोड़ें।

ऐसा करना जारी रखें - यादृच्छिक रंग जोड़ना, जब आपको कोई समाधान नहीं मिलता है, तब तक बैकट्रैकिंग करना जारी रहता है, और तब तक जारी रहता है जब तक कि आपको कोई पहेली न मिल जाए जिसमें अद्वितीय समाधान हो। और आपने कल लिया; आपके पास एक यादृच्छिक पहेली जनरेटर है।

Answer 9

ऐसा लगता है कि आप समान रूप से वितरित Latin Squares उत्पन्न करना चाहते हैं।

यह pdf जैकबसन और मैथ्यू द्वारा एक विधि का एक विवरण नहीं है (जो कहीं और प्रकाशित किया गया था, जिनमें से एक संदर्भ यहां पाया जा सकता: http://designtheory.org/library/encyc/latinsq/z/)

या आप संभवतः उनमें से एक "बहुत" पूर्व उत्पन्न कर सकता है (जहाज भेजने से पहले :-)), एक फ़ाइल में स्टोर करें और यादृच्छिक रूप से एक चुनें।

आशा है कि मदद करता है।

Answer 10

एक और समाधान यह होगा। मान लीजिए कि आपके पास कई समाधान हैं। उनमें से प्रत्येक के लिए, आप पहचानकर्ताओं को अनुमति देकर एक नया समाधान उत्पन्न कर सकते हैं (1..15)। ये नए समाधान निश्चित रूप से वही हैं, लेकिन एक खिलाड़ी के लिए वे अलग दिखाई देंगे।

क्रमशः प्रत्येक पहचानकर्ता को प्रारंभिक समाधान में एक सरणी में एक इंडेक्स के रूप में इलाज करके और फिर उस सरणी को शफल करने के द्वारा क्रमबद्ध किया जा सकता है।