इस खंड में, हम सुडोकू नामक प्रसिद्ध संख्या भूलभुलैया समस्या को हल करने का प्रयास करेंगे। सुडोकू एक 9 x 9 नंबर का ग्रिड है, और पूरे ग्रिड को भी 3 x 3 बॉक्स में विभाजित किया गया है सुडोकू को हल करने के लिए कुछ नियम हैं।
इस समस्या को हल करने के लिए हमें अंक 1 से 9 तक का उपयोग करना होगा।
एक अंक को एक पंक्ति, एक कॉलम या एक 3 x 3 बॉक्स में दोहराया नहीं जा सकता।
बैकट्रैकिंग एल्गोरिदम का उपयोग करके, हम सुडोकू समस्या को हल करने का प्रयास करेंगे। जब कोई सेल एक अंक से भर जाता है, तो यह जांचता है कि यह वैध है या नहीं। जब यह मान्य नहीं होता है, तो यह अन्य नंबरों की जांच करता है। यदि सभी नंबरों को 1-9 से चेक किया जाता है, और कोई मान्य अंक नहीं पाया जाता है, तो यह पिछले विकल्प पर वापस आ जाता है।
इनपुट और आउटपुट
इनपुट:यह सुडोकू ग्रिड के रूप में 9 x 9 मैट्रिक्स लेगा। कुछ मान ग्रिड में रखे जाते हैं। रिक्त स्थान को 0 से निरूपित किया जाता है।आउटपुट:संख्याओं से भरा अंतिम मैट्रिक्स (सुडोकू ग्रिड)। यदि समाधान मौजूद नहीं है, तो यह झूठी वापसी करेगा। 3 1 6 | 5 7 8 | 4 9 25 2 9 | 1 3 4 | 7 6 84 8 7 | 6 2 9 | 5 3 1------------------------2 6 3 | 4 1 5 | 9 8 79 7 4 | 8 6 3 | 1 2 58 5 1 | 7 9 2 | 6 4 3------------------------1 3 8 | 9 4 7 | 2 5 66 9 2 | 3 5 1 | 8 7 47 4 5 | 2 8 6 | 3 1 9
एल्गोरिदम
isPresentInCol(col, num)
इनपुट: कॉलम, और लक्षित संख्या।
आउटपुट - सही है जब संख्या दिए गए कॉलम में मौजूद है।
ग्रिड में प्रत्येक पंक्ति r के लिए प्रारंभ करें, यदि grid[r, col] =num करें, तो करें true किया हुआ वापस false अन्यथा समाप्त करें
isPresentInRow(पंक्ति, संख्या)
इनपुट - पंक्ति, और लक्षित संख्या।
आउटपुट - सही है जब संख्या दिए गए कॉलम में मौजूद है।
ग्रिड में प्रत्येक कॉलम सी के लिए शुरू करें, अगर ग्रिड [पंक्ति, सी] =संख्या करें, तो सही हो गया वापस लौटें अन्यथा झूठी वापसी करें अंत
isPresentInBox(boxStartRow, boxStartCol, num)
इनपुट - 3 x 3 बॉक्स की आरंभिक पंक्ति और स्तंभ, और लक्षित संख्या।
आउटपुट - सही है जब संख्या बॉक्स में मौजूद है।
बॉक्स में प्रत्येक पंक्ति r के लिए प्रारंभ करें, अगली 3 पंक्तियों के लिए प्रारंभ करें, बॉक्स में प्रत्येक कॉलम r के लिए अगले 3 कॉलम में करें, यदि ग्रिड [r, c] =num करें, तो सही किया हुआ वापस लौटें अन्यथा झूठी वापसी करेंअंत
findEmptyPlace(row, col)
इनपुट: ग्रिड में पंक्ति और स्तंभ।
आउटपुट - यदि ग्रिड [पंक्ति, कॉल] खाली है, तो सही लौटें, अन्यथा गलत।
ग्रिड में प्रत्येक पंक्ति r के लिए प्रारंभ करें, ग्रिड में प्रत्येक कॉलम c के लिए करें, यदि grid[r, c] =0 करें, तो true किया हुआ वापस करें falseEnd करें
isValidPlace(row, col, num)
इनपुट: पंक्ति, ग्रिड का एक स्तंभ, और जाँच करने के लिए संख्या।
आउटपुट: सच है, नंबर को स्थिति ग्रिड [पंक्ति, कॉल] पर रखने पर मान्य है।
शुरू करें यदि isPresentInRow(row, num) और isPresentInCol(col, num) और isPresntInBox(row - row mod 3, col - col mod 3, num) सभी गलत हैं, तो trueEnd लौटाएं
सॉल्व सुडोकू (सुडोकू ग्रिड)
इनपुट: सुडोकू का अनसुलझा ग्रिड।
आउटपुट: समाधान के बाद ग्रिड।
शुरू करें अगर ग्रिड में कोई जगह खाली नहीं है, तो नंबर 1 से 9 के लिए सही लौटें, यदि isValidPlace(row, col, number) करें, तो grid[row, col] :=number यदि हल करें सुडोकू =सत्य, तो वापस लौटें ट्रू ग्रिड [पंक्ति, कॉल]:=0 किया गया रिटर्न फॉल्सएंड
उदाहरण
#शामिल करें 0, 0, 0, 0, 0, 0, 0}, {0, 8, 7, 0, 0, 0, 0, 3, 1}, {0, 0, 3, 0, 1, 0, 0, 8, 0}, {9, 0, 0, 8, 6, 3, 0, 0, 5}, {0, 5, 0, 0, 9, 0, 6, 0, 0}, {1, 3, 0, 0, 0, 0, 2, 5, 0}, {0, 0, 0, 0, 0, 0, 0, 7, 4}, {0, 0, 5, 2, 0, 6, 3, 0, 0}};बूल isPresentInCol(int col, int num) {// चेक करें कि num col में मौजूद है या नहीं (int row =0; row आउटपुट
<पूर्व>3 1 6 | 5 7 8 | 4 9 25 2 9 | 1 3 4 | 7 6 84 8 7 | 6 2 9 | 5 3 1------------------------2 6 3 | 4 1 5 | 9 8 79 7 4 | 8 6 3 | 1 2 58 5 1 | 7 9 2 | 6 4 3------------------------1 3 8 | 9 4 7 | 2 5 66 9 2 | 3 5 1 | 8 7 47 4 5 | 2 8 6 | 3 1 9