जावास्क्रिप्ट में सुडोकू हल करना

सुडोकू एक लोकप्रिय पहेली खेल है जिसका मुख्य कार्य संख्याओं को सही क्रम में रखना है।

खेल का मैदान 9x9 कोशिकाओं का एक वर्ग है। कोशिकाओं को नौ 3x3 खंडों में बांटा गया है। प्रत्येक सेल में, एक से नौ तक की संख्या दर्ज की जा सकती है। सुडोकू का मूल नियम यह है कि किसी संख्या को पंक्ति, स्तंभ और खंड में दोहराया नहीं जा सकता है।

कैट के तहत जावास्क्रिप्ट में कार्यान्वित एक सुडोकू समाधान एल्गोरिदम है। पहेली को हल करने के लिए केवल बुनियादी रणनीति पर विचार किया जाता है, लेकिन यह बड़ी संख्या में प्रकाश और मध्यम स्तर के सुडोकू के लिए पर्याप्त है।

मुख्य विचार

एक क्षेत्र में एक कोशिका में तीन अवस्थाएँ हो सकती हैं:

• शुरू में मूल्य निर्धारित किया जाता है
• अज्ञात - मान परिभाषित नहीं है
• हल - मूल्य मिला

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

एक समाधान की तलाश समाप्त हो जाती है, यदि सभी अनसुलझे कोशिकाओं की गणना करने के बाद, उनमें से कोई भी समाधान नहीं खोज सका या उम्मीदवारों की संख्या नहीं बदली गई:

/** *   * *      ,       *   ,   . */ function solve() { var changed = 0; do { //        changed = updateSuggests(); steps++; if ( 81 < steps ) { //    break; } } while (changed); }; // end of method solve() /** *    * *    --   ,   . */ function updateSuggests() { var changed = 0; var buf = arrayDiff(solved[1][3][2], rowContent(1)); buf = arrayDiff(buf, colContent(3)); buf = arrayDiff(buf, sectContent(1, 3)); for ( var i=0; i<9; i++) { for ( var j=0; j<9; j++) { if ( 'unknown' != solved[i][j][1] ) { //    ,   continue; } // "" changed += solveSingle(i, j); // " " changed += solveHiddenSingle(i, j); } } return changed; }; // end of method updateSuggests() 

एल्गोरिदम कार्यान्वयन

सुडोकू को हल करने के कई तरीके हैं, लेकिन प्रदर्शन उद्देश्यों के लिए, दो सरल तरीकों पर विचार करें: लोनेर और हिडन लोनेर । सुडोकू को हल करने के लिए ये मूल तरीके हैं और बुनियादी सिद्धांतों को सीखने के लिए महान हैं।

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

 /** *  "" */ function solveSingle(i, j) { solved[i][j][2] = arrayDiff(solved[i][j][2], rowContent(i)); solved[i][j][2] = arrayDiff(solved[i][j][2], colContent(j)); solved[i][j][2] = arrayDiff(solved[i][j][2], sectContent(i, j)); if ( 1 == solved[i][j][2].length ) { //      markSolved(i, j, solved[i][j][2][0]); return 1; } return 0; }; // end of method solveSingle() 

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

 /** *  " " */ function solveHiddenSingle(i, j) { var less_suggest = lessRowSuggest(i, j); var changed = 0; if ( 1 == less_suggest.length ) { markSolved(i, j, less_suggest[0]); changed++; } var less_suggest = lessColSuggest(i, j); if ( 1 == less_suggest.length ) { markSolved(i, j, less_suggest[0]); changed++; } var less_suggest = lessSectSuggest(i, j); if ( 1 == less_suggest.length ) { markSolved(i, j, less_suggest[0]); changed++; } return changed; }; // end of method solveHiddenSingle() /** *      */ function lessRowSuggest(i, j) { var less_suggest = solved[i][j][2]; for ( var k=0; k<9; k++ ) { if ( k == j || 'unknown' != solved[i][k][1] ) { continue; } less_suggest = arrayDiff(less_suggest, solved[i][k][2]); } return less_suggest; }; // end of method lessRowSuggest() /** *      */ function lessColSuggest(i, j) { var less_suggest = solved[i][j][2]; for ( var k=0; k<9; k++ ) { if ( k == i || 'unknown' != solved[k][j][1] ) { continue; } less_suggest = arrayDiff(less_suggest, solved[k][j][2]); } return less_suggest; }; // end of method lessColSuggest() /** *      */ function lessSectSuggest(i, j) { var less_suggest = solved[i][j][2]; var offset = sectOffset(i, j); for ( var k=0; k<3; k++ ) { for ( var l=0; l<3; l++ ) { if ( ((offset.i+k) == i && (offset.j+l) == j)|| 'unknown' != solved[offset.i+k][offset.j+l][1] ) { continue; } less_suggest = arrayDiff(less_suggest, solved[offset.i+k][offset.j+l][2]); } } return less_suggest; }; // end of method lessSectSuggest() 

के उपयोग

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

प्रारंभिक मान 9x9 पूर्णांक मैट्रिक्स द्वारा दिए गए हैं। यदि मूल्य निर्धारित नहीं है और संख्या अलग है, तो कोशिकाओं में "0" लिखा जाता है।

 var in_val = [ [0, 0, 3, 0, 0, 8, 2, 0, 4], [0, 2, 0, 0, 6, 4, 0, 1, 0], [9, 0, 0, 0, 0, 0, 0, 0, 8], [0, 8, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 6, 9, 8, 0], [0, 0, 0, 0, 0, 0, 5, 0, 0], [0, 0, 4, 9, 0, 7, 0, 3, 0], [8, 0, 0, 0, 0, 1, 0, 0, 0], [0, 7, 0, 0, 5, 0, 4, 0, 0] ]; var sudoku = new Sudoku(in_val); document.write(sudoku.html()); 

एल्गोरिथ्म का परिणाम इस तरह दिखता है:



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

संदर्भ

सुडोकू [विकिपीडिया]
सुडोकू को कैसे हल करें: तरीके, तरीके और रणनीति

UPD उपयोगकर्ता rozboris कृपया एक डेमो बनाया

यूपीडी 2 रिवर्स खोज लागू । अब सभी सुडोकू हल। और रोजबोरिस से एक नया डेमो ।

UPD3 चूंकि लेख के लिंक मर गए हैं, मैंने Google कोड पर स्रोत कोड पोस्ट किया है।