एक प्रभावी सुडोकू सॉल्वर

Question

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

शायद किसी प्रोग्राम में ऐसा करने का सबसे आसान तरीका प्रत्येक कॉलम और पंक्ति के माध्यम से लूप पार्स का एक टन है, प्रत्येक सेल के संभावित मान एकत्रित करें, फिर केवल एक संभावना के साथ कोशिकाओं को बाहर निकालें (चाहे वे केवल हों 1 संख्या, या वे अपनी पंक्ति/कॉलम में एकमात्र सेल हैं जिसमें यह संख्या शामिल है) जब तक कि आपके पास हल की गई पहेली न हो। बेशक, कार्रवाई के एक बड़े विचार को हर प्रोग्रामर के दिमाग में लाल झंडा उठाना चाहिए।

जो मैं खोज रहा हूं वह इस चूसने वाले को सबसे कुशल तरीके से सुलझाने के तरीके के बारे में सोचने की पद्धति है (कृपया बहुत अधिक कोड शामिल न करने का प्रयास करें - मैं उस भाग को स्वयं समझना चाहता हूं)।

यदि संभव हो तो मैं गणितीय एल्गोरिदम से बचना चाहता हूं - यह बहुत आसान होगा और 100% मेरा काम नहीं होगा।

यदि कोई सुडोकू पहेली (चाहे मानव या कंप्यूटर द्वारा) को हल करने के लिए एक चरण-दर-चरण, कुशल विचार प्रक्रिया प्रदान कर सकता है, तो मैं सबसे ज्यादा खुश हूं :)। मैं कुछ ऐसी चीज की तलाश में हूं जो अस्पष्ट है (इसलिए यह एक चुनौती है), लेकिन मुझे शुरू करने के लिए पर्याप्त जानकारीपूर्ण (इसलिए मैं पूरी तरह से खो नहीं गया)।

बहुत धन्यवाद,

Justian मेयेर

संपादित करें:

मेरे कोड को देखते हुए, मैं सोच को मिला: क्या इन सुलझाने राज्यों के भंडारण के लिए संभावनाओं के कुछ होगा (यानी सुडोकू ग्रिड)। 2 डी Arrays और 3 डी Arrays दिमाग में आते हैं। कौन सा सबसे अच्छा हो सकता है? 2 डी सतह से प्रबंधन करना आसान हो सकता है, लेकिन 3 डी Arrays "बॉक्स"/"पिंजरे" संख्या भी प्रदान करेगा।

संपादित करें:

कोई बात नहीं। मैं एक 3 डी सरणी के साथ जा रहा हूँ।

Answer 1

यह इस बात पर निर्भर करता है कि आप कुशल कैसे परिभाषित करते हैं।

आप एक ब्रूट फोर्स विधि का उपयोग कर सकते हैं, जो प्रत्येक कॉलम और पंक्ति के माध्यम से खोजता है, प्रत्येक सेल के संभावित मान एकत्र करता है, फिर केवल एक संभावना के साथ कोशिकाओं को बाहर निकाल देता है।

यदि आपके पास एक से अधिक संभावनाओं के साथ शेष कोशिकाएं हैं, तो पहेली स्थिति को बचाएं, सेल को सबसे कम संभावनाओं के साथ चुनें, संभावनाओं में से एक चुनें, और पहेली को हल करने का प्रयास करें। यदि आपके द्वारा चुनी गई संभावना एक पहेली विरोधाभास की ओर ले जाती है, तो सहेजे गए पहेली स्थिति को पुनर्स्थापित करें, सेल पर वापस जाएं और एक अलग संभावना चुनें। यदि आपके द्वारा उठाए गए सेल में से कोई भी संभावना पहेली को हल नहीं करती है, तो अगले सेल को सबसे कम संभावनाओं के साथ चुनें। शेष संभावनाओं और कोशिकाओं के माध्यम से चक्र जब तक आप पहेली हल नहीं किया है।

पहेली को हल करने का प्रयास प्रत्येक कॉलम और पंक्ति के माध्यम से खोजना है, प्रत्येक सेल के संभावित मान एकत्रित करना, फिर केवल एक संभावना के साथ कोशिकाओं को बाहर निकालना। जब सभी कोशिकाओं को तनख्वाह कर दिया जाता है, तो आपने पहेली को हल कर लिया है।

आप एक तार्किक/गणितीय विधि का उपयोग कर सकते हैं, जहां आपका कोड पहेली हल होने तक विभिन्न रणनीतियों की कोशिश करता है। विभिन्न रणनीतियों को देखने के लिए Google को "सुडोकू रणनीतियों" के साथ खोजें। तार्किक/गणितीय तरीकों का उपयोग करके, आपका कोड "व्याख्या" कर सकता है कि पहेली को कैसे हल किया गया था।

Answer 2

जब मैंने मेरा बनाया, मैंने सोचा कि मैं बिना किसी बैकट्रैक किए नियमों के एक सेट का उपयोग करके हर बोर्ड को हल कर सकता हूं। यह असंभव साबित हुआ क्योंकि मानव खिलाड़ियों को लक्षित करने वाले पहेली को संभावित रूप से कुछ परिकल्पना करने की आवश्यकता होती है।

तो मैं एक पहेली को हल करने के लिए बुनियादी "नियम" को लागू करने के साथ शुरू करना चाहता हूं, जो अगले नियम को लागू करने का प्रयास कर रहा है, जो कि आखिरी बार कहां रुक गया था। अंत में, मुझे रिकर्सिव एल्गोरिदम को मजबूर करने के लिए एक ब्रूट जोड़ने के लिए मजबूर होना पड़ा, लेकिन अधिकांश पहेलियों को वास्तव में इसका उपयोग किए बिना हल किया जाता है।

मैंने अपने सुडोकू सॉल्वर के बारे में एक ब्लॉग पोस्ट लिखा था। बस "एल्गोरिदम" अनुभाग के माध्यम से पढ़ें और आपको एक अच्छा अच्छा विचार मिलेगा कि मैं इसके बारे में कैसे गया।

http://www.byteauthor.com/2010/08/sudoku-solver/

Answer 3

किसी को भी एक संदर्भ एंड्रॉयड कार्यान्वयन की ज़रूरत है तो मैं एक समाधान ऊपर पोस्ट से एल्गोरिथ्म का उपयोग करता है लिखा था।

पूर्ण खुला स्रोत यहाँ कोड: https://github.com/bizz84/SudokuSolver

साथ ही, इस समाधान एक वेब सर्वर से JSON प्रारूप में सुडोकू पहेलियां लोड करता है और पदों परिणामों पर वापस।

Answer 4

आपको सुडोकू समस्या को SATisfiability problem पर कम करने के बारे में सोचना चाहिए।

यह विधि आपको ऐ के बारे में भी mathematically लेकिन अधिक logically सोचने के लिए नहीं आने देगा।

कदम से लक्ष्य चरण मूल रूप से है:

* Find all the constraints that a Sudoku has. (line, column, box). 
* Write these constraints as boolean constraints. 
* Put all these constraints in a Boolean Satisfiability Problem. 
* Run a SAT solver (or write your own ;)) on this problem. 
* Transform the SAT solution into the solution of the initial Sudoku. 

यह SAT4J का उपयोग करने और आप अपने काम यहाँ की जावा एप्लेट पा सकते हैं द्वारा Ivor Spence द्वारा किया गया है: http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html।

आप एसएटी 4 जे वेबसाइट से सीधे जावा कोड भी डाउनलोड कर सकते हैं, यह देखने के लिए कि यह कैसा दिखता है: http://sat4j.org/products.php#sudoku।

और अंत में, इस विधि का बड़ा लाभ यह है: आप N*N Sudokus को हल कर सकते हैं, न कि केवल 9*9, जो मुझे लगता है, एआई के लिए और अधिक चुनौतीपूर्ण है।