बैकट्रैकिंग के साथ सुडोकू एल्गोरिदम - जावा

Question

तो मेरे पास सुडोकू को हल करने के लिए यह विश्वविद्यालय असाइनमेंट है ... मैंने एल्गोरिदम एक्स और नृत्य एल्गोरिदम के बारे में पढ़ा है, लेकिन उन्होंने मेरी मदद नहीं की।

मुझे इसे बैकट्रैकिंग के साथ बनाना होगा। मैंने विकिपीडिया से दिए गए स्थानों पर संख्याओं के साथ दो आयामी सरणी में कुछ इंडेक्स को हार्ड-कोड किया (इसलिए मुझे यकीन है कि यह हल करने योग्य है)।

कोड मुझे मिल गया है निम्नलिखित:

public void solveSudoku(int row, int col) 
    { 
     // clears the temporary storage array that is use to check if there are 
     // dublicates on the row/col 
     for (int k = 0; k < 9; k++) 
     { 
     dublicates[k] = 0; 
     } 
     // checks if the index is free and changes the input number by looping 
     // until suitable 
     if (available(row, col)) 
     { 
     for (int i = 1; i < 10; i++) 
     { 
      if (checkIfDublicates(i) == true) 
      { 
       board[row][col] = i; 
       if (row == 8) 
        solveSudoku(0, col + 1); 
       else if (col == 8) 
        solveSudoku(row + 1, 0); 
       else 
        solveSudoku(row, col + 1); 

       board[row][col] = 0; 
      } 
     } 
     } 
     // goes to the next row/col 
     else 
     { 
     if (row == 8) 
      solveSudoku(0, col + 1); 
     else if (col == 8) 
      solveSudoku(row + 1, 0); 
     else 
      solveSudoku(row, col + 1); 
     } 
    } 

    /** 
    * Checks if the spot on the certain row-col index is free of element 
    * 
    * @param row 
    * @param col 
    * @return 
    */ 
    private boolean available(int row, int col) 
    { 
     if (board[row][col] != 0) 
     return false; 
     else 
     return true; 
    } 

    /** 
    * Checks if the number given is not already used in this row/col 
    * 
    * @param numberToCheck 
    * @return 
    */ 
    private boolean checkIfDublicates(int numberToCheck) 
    { 
     boolean temp = true; 
     for (int i = 0; i < dublicates.length; i++) 
     { 
     if (numberToCheck == dublicates[i]) 
     { 
      temp = false; 
      return false; 
     } 
     else if (dublicates[i] == 0) 
     { 
      dublicates[i] = numberToCheck; 
      temp = true; 
      return true; 
     } 
     } 
     return temp; 
    } 

मैं

// goes to the next row/col 
      else 
      { 
      if (row == 8) 
       solveSudoku(0, col + 1); 
      else if (col == 8) 
       solveSudoku(row + 1, 0); 
      else 
       solveSudoku(row, col + 1); 
      } 

जिसका मतलब है कि मैं कुछ बिंदु पर प्रत्यावर्तन रोकने के लिए उस पर StackOverflow हो रही है, लेकिन मैं समझ नहीं सकता यह कैसे बाहर! यदि आपको solve() फ़ंक्शन में कोई अन्य गलती मिलती है - तो मुझे बताएं। क्योंकि मुझे यकीन है कि मैं "बैक ट्रैकिंग" बात पूरी तरह से समझते हैं ...

Answer 1

उदाहरण के लिए आप प्रत्यावर्तन बंद कर सकते हैं यदि आप वर्तमान प्रत्यावर्तन गहराई

public void solveSudoku(int row, int col, int recursionDepth) { 
    // get out of here if too much 
    if (recursionDepth > 15) return; 

    // regular code... 
    // at some point call self with increased depth 
    solveSudoku(0, col + 1, recursionDepth + 1); 
} 

---

और अगर आप का ट्रैक रखने नहीं कर रहा हूँ हल() फ़ंक्शन में कोई अन्य गलतियों को ढूंढें - मुझे बताएं।

बहुत ज्यादा कोड :)

Answer 2

यह मोटे तौर पर जिस तरह से मैं यह पूर्व में की गई है।

Whenever all the definite moves have been taken and there is a choice of equally good next moves: 
    copy your grid data structure and push it onto a stack. 
    take the first candidate move and continue solving recursively 
    Whereever you get stuck: 
     pop the saved grid off the stack 
     take the next candidate move. 

Answer 3

मैं एक और अधिक सरल तरीके से इसे बनाया:

public void solve(int row, int col) 
    { 
     if (row > 8) 
     { 
     printBoard(); 
     System.out.println(); 
     return; 
     } 
     if (board[row][col] != 0) 
     { 
     if (col < 8) 
      solve(row, col + 1); 
     else 
      solve(row + 1, 0); 
     } 
     else 
     { 
     for (int i = 0; i < 10; i++) 
      if (checkRow(row, i) && checkCol(col, i)) 
        //&& checkSquare(row, col, i)) 
      { 
       board[row][col] = i; 
       if (col < 8) 
        solve(row, col + 1); 
       else 
        solve(row + 1, 0); 
      } 
     board[row][col] = 0; 
     } 
    } 

    private boolean checkRow(int row, int numberToCheck) 
    { 
     for (int i = 0; i < 9; i++) 
     if (board[row][i] == numberToCheck) 
      return false; 

     return true; 
    } 

    private boolean checkCol(int col, int numberToCheck) 
    { 
     for (int i = 0; i < 9; i++) 
     if (board[i][col] == numberToCheck) 
      return false; 

     return true; 
    } 

Answer 4

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

यदि पूर्व मामला है, तो आप इसे देख सकते हैं: A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm। यह काफी स्पष्ट है और पीछे तर्क भी बताता है।

एनबी। एल्गोरिदम एक्स एक बैकट्रैकिंग एल्गोरिदम है, इसलिए यदि यह आपकी एकमात्र आवश्यकता है, तो आप निश्चित रूप से इस दृष्टिकोण का उपयोग कर सकते हैं।

उम्मीद है कि इससे मदद मिल सकती है।