सुडोकू solver, बैक ट्रैकिंग और प्रत्यावर्तन

Question

मैं एक 9x9 ग्रिड के लिए जावा में एक सुडोकू solver प्रोग्रामिंग कर रहा हूँ का उपयोग कर।

मैं करने के लिए तरीके हैं:

• ग्रिड

• मुद्रण संघर्ष के लिए

• परीक्षण दिया मूल्यों के साथ बोर्ड को प्रारंभ (यदि एक ही नंबर एक ही पंक्ति या 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 पर हैं, जो काम नहीं करेगा।

किसी ने मुझे बाहर करने में मदद सकते हैं?

Answer 1

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

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

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

(कि नोट, जबकि पेंसिल और कागज के साथ एक सुडोकू को सुलझाने, एक अक्सर खाली कोशिकाओं में कम संख्या लिखते हैं क्या संख्या वहाँ संभव हो रहे हैं, जहाँ तक भी इसे हल किया है का ट्रैक रखने के।)

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

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

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

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

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

अब कैसे पुनरावर्ती जानवर बल काम कर बनाने के लिए के बारे में सोचने की सुविधा देता है।

हम n रिक्त कक्षों के साथ एक सुडोकू हल करने के लिए लक्ष्य है। हैं हम एक समारोह है कि n-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 

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

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

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

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

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

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

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

Answer 2

मैं पुनरावर्ती विधि करने के लिए दोनों मौजूदा पंक्ति और स्तंभ गुजर सुझाव देते हैं तो सभी की अनुमति मिल जाए उस कक्ष के लिए संख्या, प्रत्येक की अनुमति दी संख्या recursivly अगले स्तंभ के लिए विधि (या अगली पंक्ति अंतिम स्तंभ पर हैं) कहते हैं और इस कदम पूर्ववत के लिए यह एक मरे हुए ट्रैक की ओर जाता है, तो

public boolean fillCell(int r, int c) { 
    if last row and last cell { 
     //report success 
     return true 
    } 
    for i 1 to 9 { 
     if can place i on r, c { 
      board[r][c] = i 
      if !fillCell(next empty row, next empty column) { //DONT change r or c here or you will not be able to undo the move 
       board[r][c] = 0 
      } 
      /* 
      else { 
       return true; //returning true here will make it stop after 1 solution is found, doing nothing will keep looking for other solutions also 
      } 
      */ 

     } 
    } 
    return false   
} 

Answer 3

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

अधिक जानकारी में: मान 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 

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

Answer 4

कुछ विचार है कि उपयोगी हो सकता है

//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 
} 

एक विन्यास वर्ग में प्रवेश किया और के बारे में सोचने में प्रवेश किया संख्या और आकार और #numbers जैसे कुछ अन्य विशेषताओं के साथ ग्रिड रखती लिखने (प्रत्यावर्तन और बैक ट्रैकिंग के विषय में) क्या अन्य की आवश्यकता है

Answer 5

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

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

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

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

जाना चाहिए तुम्हें अपने सेल मैं, जे में एक नंबर n रखना चाहते हैं। आप जांचेंगे कि पंक्ति [i] [n-1] सत्य है या नहीं। यदि हां, तो i^वें पंक्ति में पहले से ही एन है। इसी प्रकार, आप जांच करेंगे कि col [j] [n-1] और minigrid [gridnum] [n-1] सत्य है।

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

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

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

की मैं/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 
}