java - बैकट्रैकिंग और रिकर्सन का उपयोग करते हुए जावा में सुडोकू सॉल्वर




recursion backtracking sudoku (5)

मैं 9x 9 ग्रिड के लिए जावा में सुडोकू सॉल्वर प्रोग्रामिंग कर रहा हूं।

मेरे पास विधियां हैं:

  • ग्रिड मुद्रण

  • दिए गए मूल्यों के साथ बोर्ड शुरू करना

  • संघर्ष के लिए परीक्षण (यदि एक ही संख्या एक ही पंक्ति या 3x3 उप-ग्रिड में है)

  • अंक रखने के लिए एक विधि, एक-एक करके, जिसके लिए सबसे अधिक काम की आवश्यकता होती है।

इससे पहले कि मैं उस विधि के साथ विस्तार से आगे बढ़ूं, ध्यान रखें कि मुझे इसे हल करने के लिए रिकर्सन का उपयोग करना होगा, साथ ही साथ बैकट्रैकिंग (यहां एप्लेट को उदाहरण के रूप में देखें http://www.heimetli.ch/ffh/simplifiedsudoku.html )

इसके अलावा, मैं ऊपरी बाईं ओर से, पहले कॉलम के माध्यम से, और फिर दूसरे कॉलम इत्यादि के माध्यम से लंबवत नीचे चलकर इस सुडोकू को हल कर रहा हूं।

अब तक, मेरे पास निम्नलिखित है:

public boolean placeNumber(int column){

    if (column == SUDOKU_SIZE){  // we have went through all the columns, game is over

        return true;

    }

    else
    {
        int row=0;  //takes you to the top of the row each time

        while (row < SUDOKU_SIZE)    loops through the column downwards, one by one
        {

            if (puzzle[row][column]==0){  //skips any entries already in there (the given values)

                puzzle[row][column]=1;   //starts with one

                while(conflictsTest(row,column)){   //conflictsTest is the method I wrote, which checks if the given parameters are in conflict with another number

                    puzzle[row][column] += 1;  

                }


           //BACK TRACKING 

                placeNumber(column);      //recursive call

            }
            else{
              row++;                  // row already has a number given, so skip it
            }
        }

        column++;              // move on to second column
        placeNumber(column);

    }
    return false; // no solutions to this puzzle
}

जहां मैंने बैकट्रैकिंग लेबल किया है, जहां मेरा मानना ​​है कि मेरे शेष कोड को जाने की जरूरत है।

मैंने कुछ के साथ कुछ सोचा:

  • यदि मान 10 है, तो उस मान को शून्य पर वापस सेट करें, एक पंक्ति वापस जाएं, और उस मान को 1 से बढ़ाएं

वह बैकट्रैकिंग 'रणनीति' बिल्कुल कई कारणों से काम नहीं करती है:

  1. क्या होगा अगर पिछली पंक्ति, एक दिया गया मान था (उर्फ मुझे इसे बढ़ाने या इसे छूने वाला नहीं है, बल्कि इसके बजाय, मैंने जो अंतिम मूल्य रखा है, उस पर वापस जाएं)

  2. क्या होगा यदि पिछला मान 9 था। और यदि मैंने 1 से बढ़ाया, तो अब हम 10 पर हैं, जो काम नहीं करेगा।

क्या कोई व्यक्ति कृपा करके मेरी सहायता करेगा?


Answers

सबसे पहले , अनुकूलन के लिए एक सुझाव: यह जांचते समय कि आप जिस सेल को सेल में डाल रहे हैं, वह पहले से ही उसी पंक्ति, कॉलम या मिनीग्रिड में मौजूद है, आपको लूप या ऐसा कुछ चलाने की ज़रूरत नहीं है। आप सरणी अनुक्रमण द्वारा त्वरित जांच कर सकते हैं।

3 9 x 9 बूलियन डबल आयामी सरणी पर विचार करें:

boolean row[9][9], col[9][9], minigrid[9][9]

हम यह जांचने के लिए पहली सरणी का उपयोग करेंगे कि एक ही पंक्ति में कोई संख्या मौजूद है या नहीं, यह जांचने के लिए दूसरी सरणी है कि एक ही कॉलम में कोई संख्या मौजूद है, और मिनी ग्रिड के लिए तीसरा है।

मान लीजिए कि आप अपने सेल में नंबर एन डालना चाहते हैं, जे । आप जांच लेंगे कि पंक्ति [i] [n-1] सत्य है या नहीं। यदि हां, तो मैं पंक्ति में पहले से ही एन शामिल है। इसी तरह, आप जांच लेंगे कि क्या कोल [जे] [एन -1] और मिनीग्रिड [ग्रिड्नम] [एन -1] सच है।

यहां ग्रिड्नम मिनी ग्रिड का सूचकांक है, जहां आप जिस सेल को एक नंबर डालना चाहते हैं, वह है। सेल i, j के लिए मिनी ग्रिड नंबर की गणना करने के लिए, i और j को 3 से विभाजित करें, पूर्व के अभिन्न अंग को 3 से गुणा करें, और इसे बाद के अभिन्न अंग में जोड़ें।

यह कैसा दिखता है:

gridnum = (i/3)*3 + j/3

मैं और जे के लिए i / 3 और j / 3 के मूल्यों को देखकर, आपको यह पता चल जाएगा कि यह कैसे काम करता है। साथ ही, यदि आप किसी सेल में कोई संख्या डालते हैं, तो सरणी को भी अपडेट करें। जैसे पंक्ति [i] [n-1] = true

यदि कोई ऐसा हिस्सा है जिसे आप समझ नहीं पाते हैं, तो एक टिप्पणी पोस्ट करें और मैं इसे समझाने के लिए अपना उत्तर संपादित करूंगा।

दूसरा , इसे हल करने के लिए रिकर्सन और बैकट्रैकिंग का उपयोग करना बहुत आसान है।

boolean F( i, j) // invoke this function with i = j = 0
{
If i > 8: return true // solved

for n in 1..9
 {
 check if n exists in row, column, or mini grid by the method I described

 if it does: pass ( skip this iteration )

 if it doesn't
  {
   grid[i][j] = n
   update row[][], col[][], minigrid[][]

   if F( if j is 8 then i+1 else i, if j is 8 then 0 else j+1 ) return true // solved
  }
 }
 return false // no number could be entered in cell i,j
}

कुछ विचार जो सहायक हो सकते हैं (रिकर्सन और बैकट्रैकिंग के संबंध में)

//some attributes you might need for storing e.g. the configuration to track back to.

boolean legal(Configuration configuration) {

}

int partSolution(Configuration configuration) {
  if (legal(configuration))
    return partSolution(nextConfiguration())
  else
    return partSolution(previousConfiguration())    
}

Configuration nextConfiguration() {
 //based on the current configuration and the previous tried ones,
 //return the next possible configuration:
 //next number to enter, next cell to visit
}

Configuration previousConfiguration() {
 //backtrack
}

solve () {
  call partSolution with start configuration while partSolution < 9x9
}

कॉन्फ़िगरेशन क्लास लिखें जो ग्रिड को दर्ज संख्याओं के साथ रखता है और कुछ अन्य विशेषताओं जैसे कि आकार और # नब्स दर्ज किए गए हैं और इस बारे में सोचें कि और क्या चाहिए


यदि कोई समाधान नहीं मिल पाता है तो मैं प्रत्येक सेल की जांच करता हूं और एक रिकर्सन चरण वापस जाता हूं।

अधिक जानकारी में: अगले सेल पर जाएं, यदि मान x == 0 है, तो जांचें कि x + 1 मान्य होगा, यदि सही है, तो अगले संभावित सेल के साथ विधि को कॉल करके अगले सेल पर जाएं। यदि संख्या मान्य नहीं है तो x + 2 इत्यादि चेक करें यदि कोई संख्या वैध वापसी झूठी नहीं है और पिछले कॉल में x + 1 चरण दोहराएं। यदि आप किसी संख्या के अंदर एक सेल को हिट करते हैं, तो रिकर्सन को कॉल न करें लेकिन सीधे अगली पर जाएं, इस प्रकार आपको किसी भी पूर्व दर्ज सेल को ध्वजांकित करने की आवश्यकता नहीं है।

छद्म कोड:

fillcell cell
 while cell is not 0
  cell = next cell
 while cell value < 10
  increase cell value by one
  if cell is valid 
    if fillcell next cell is true
      return true
return false

यह सुनिश्चित नहीं है कि यह सही है लेकिन इसे विचार दिखाना चाहिए।


मुझे नहीं पता कि आप सुडोकू को हल करने के लिए कैसे जा रहे हैं, लेकिन यदि आप ब्रूट फोर्स विधि का उपयोग करते हैं (और इसलिए यह मुझे लगता है कि आप जो वर्णन करते हैं) आपको यह समझना चाहिए कि आपकी डेटा संरचना उचित नहीं है।

इसके साथ मेरा मतलब है कि प्रत्येक सेल केवल एक संख्या नहीं होना चाहिए, बल्कि संख्याओं का एक सेट होना चाहिए (जिसे संभवतः वहां रखा जा सकता है)।

इसलिए, दिए गए नंबरों को सिंगलटन सेट के रूप में दर्शाया जाएगा, जबकि रिक्त स्थान जिन्हें आप {1,2,3,4,5,6,7,8,9} के साथ प्रारंभ कर सकते हैं। और फिर लक्ष्य गैर-सिंगलटन कोशिकाओं को कम करना है जब तक कि सभी कोशिकाएं सिंगलेट न हों।

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

और फिर, जब "अगली संख्या की कोशिश कर रहा है" तो आप सेट से अगला नंबर लेते हैं। दिए गए कोशिकाओं का कोई अगला नंबर नहीं है, इसलिए आप उन्हें बदल नहीं सकते हैं। इस तरह, आपके द्वारा वर्णित कठिनाइयों को गायब कर दिया जाता है (थोड़ा सा, कम से कम)।

------ संपादित करें, सीखने के बाद कि ब्रूट फोर्स की आवश्यकता है।

आपका शिक्षक स्पष्ट रूप से आपको रिकर्सन के चमत्कार सिखाना चाहता है। बहुत अच्छा!

उस स्थिति में, हमें केवल यह जानने की जरूरत है कि कौन से कक्ष दिए गए हैं, और जो नहीं हैं।

यहां इस्तेमाल किया जा सकता है कि एक विशेष आसान तरीका किसी भी गैर-दिए गए सेल में 0 रखना है, क्योंकि दिए गए कोशिकाएं परिभाषा के अनुसार 1,2,3,4,5,6,7,8,9 है।

अब रिकर्सिव ब्रूट फोर्स को काम करने के तरीके के बारे में सोचें।

हमारे पास एन खाली कोशिकाओं के साथ सुडोकू को हल करने का लक्ष्य है। अगर हमारे पास ऐसा फ़ंक्शन था जो एन -1 रिक्त कक्षों (या सिग्नल कि यह हल करने योग्य नहीं है) के साथ सुडोकू को हल करेगा, तो यह कार्य आसान होगा:

let c be some empty cell.
let f be the function that solves a sudoku with one empty cell less.
for i in 1..9
   check if i can be placed in c without conflict
   if not continue with next i
   place i in c
   if f() == SOLVED then return SOLVED
return NOTSOLVABLE

यह छद्म कोड कुछ खाली सेल चुनता है, और उसके बाद वहां मौजूद सभी संख्याओं की कोशिश करता है। चूंकि एक सुडोकू है - परिभाषा के अनुसार - केवल एक ही समाधान, केवल निम्नलिखित मामले हैं:

  • हमने सही संख्या चुना है। फिर एफ () शेष समाधान मिलेगा और वापस लौटाएगा।
  • हमने गलत नंबर चुना है: f () संकेत देगा कि सुडोकू हमारे सेल में उस गलत संख्या के साथ हल करने योग्य नहीं है।
  • हमने सभी नंबरों की जांच की, लेकिन कोई भी सही नहीं था: फिर हमारे पास एक असफल सुडोकू है और हम इसे हमारे कॉलर को संकेत देते हैं।

कहने की जरूरत नहीं है, एल्गोरिदम इस धारणा पर निर्भर करता है कि हम केवल उन संख्याओं को रखते हैं जो वर्तमान स्थिति से विवादित नहीं हैं। उदाहरण के लिए, हम वहां 9 स्थान नहीं डालते हैं, उसी पंक्ति में, कॉलम या बॉक्स में पहले से ही 9

अगर अब हम सोचते हैं कि हमारे रहस्यमय, अभी तक अज्ञात फ़ंक्शन f() कैसा दिखता है, तो यह पता चला है कि यह लगभग उतना ही होगा जितना हमारे पास पहले से ही है!
एकमात्र मामला जिसे हमने अभी तक नहीं माना है, 0 खाली कोशिकाओं के साथ एक सुडोकू है। इसका मतलब है, अगर हमें लगता है कि कोई और खाली कोशिकाएं नहीं हैं, तो हम जानते हैं कि हमने सुडोकू को हल किया है और केवल हल किया है।

किसी समस्या को हल करने के लिए एक रिकर्सिव फ़ंक्शन लिखते समय यह सामान्य चाल है। हम हल कर रहे हैं (), और हम जानते हैं, कि समस्या बिल्कुल हल करने योग्य है। इसलिए, हम पहले से ही उस फ़ंक्शन का उपयोग कर सकते हैं जिसे हम केवल तब तक लिख रहे हैं जब तक हम सुनिश्चित करते हैं कि प्रत्येक रिकर्सन के साथ, समस्या किसी भी तरह समाधान के करीब हो जाती है। अंत में, हम तथाकथित बेस केस तक पहुंचते हैं, जहां हम बिना किसी रिकर्सन के समाधान दे सकते हैं।

हमारे मामले में हम जानते हैं कि सुडोकू सुलभ है, इसके अलावा, हम जानते हैं कि इसमें बिल्कुल एक समाधान है। एक खाली सेल में एक टुकड़ा रखकर, हम समाधान के करीब आते हैं (या निदान के लिए कि कोई नहीं है) और उस कार्य को नई, छोटी समस्या को दोबारा दें जो हम सिर्फ लिख रहे हैं। मूल मामला "0 खाली कोशिकाओं के साथ सुडोकू" है जो वास्तव में समाधान है

(यदि कई संभावित समाधान हैं तो चीजें थोड़ा अधिक जटिल हो जाती हैं, लेकिन हम इसे अगले पाठ के लिए छोड़ देते हैं।)


असल में, ऑब्जेक्ट पैरामीटर को पुन: असाइन करना तर्क को प्रभावित नहीं करता है, उदाहरण के लिए,

private void foo(Object bar) {
    bar = null;
}

public static void main(String[] args) {
    String baz = "Hah!";
    foo(baz);
    System.out.println(baz);
}

"Hah!"इसके बजाय प्रिंट करेंगे null। इसका कारण यह है कि barयह मान की एक प्रति है baz, जो कि सिर्फ एक संदर्भ है"Hah!" ।यदि यह वास्तविक संदर्भ स्वयं था, तो fooफिर bazसे परिभाषित किया होगा null





java recursion backtracking sudoku