रिकर्सन: त्रुटि के मामले में पूर्ण करने के लिए पूर्णांक 1 से 9, और (आंशिक रूप से) रिवर्स अनुक्रम के विभिन्न संयोजनों को कैसे आज़माएं?

Question

भाषा: जावा

उद्देश्य: सामान्य:

• जांच करें कि क्या:) है कि एक पुनरावर्ती विधि का समाधान करें (: एक सुडोकू खेल

  विशिष्ट समाधान पंक्ति, कॉलम या बॉक्स में अन्य संख्याओं के साथ संख्या विवाद

• खाली खाली स्थान में [1-9] के बीच पूर्णांक में भरता है यदि यह मामला नहीं है और अगले खाली स्थान पर जाएं
• (आंशिक रूप से या पूरी तरह से) प्रगति को उलट देता है यदि रिक्त स्थान को पूर्णांक द्वारा पूर्ण नहीं किया जा सकता है [1] -9] संघर्ष के बिना। फिर फिर भी कोशिश करें जब तक कि सभी खाली रिक्त स्थान भरे न हों (और सुडोकू हल हो जाता है)।

समस्या: छोरों n पूर्णांक में भरने की कोशिश, लेकिन हमेशा पहले सबसे कम संख्या की कोशिश करेंगे। यदि मैं रिकर्सन का उपयोग करना चाहता था तो पूर्णांक हमेशा एक जैसा होगा।

प्रश्न: 1. आप के बीच के अंक में कोड भरने बनाने के लिए और सहित है 1 9 को

1. कैसे आप प्रत्यावर्तन का उपयोग करते हैं आंशिक या पूर्ण मिटाने के लिए प्रगति और विभिन्न संख्याओं का प्रयास करें।

2. (अतिरिक्त) मैंने अब तक सुडोकू को आंशिक रूप से हल करने के लिए कोड बनाया है (जब तक खाली वर्ग नहीं भरा जा सकता) लेकिन अब यह पहले वर्ग में भी भर नहीं जाता है, भले ही पहले किया गया हो। यह मेरा मुख्य प्रश्न नहीं है, लेकिन यदि कोई व्यक्ति किसी मुद्दे को नोटिस करता है, तो अगर मुझे बताया गया तो मैं बहुत आभारी रहूंगा।

की समीक्षा: मैं प्रत्यावर्तन पर पाठ्यक्रम सामग्री पढ़ रहा हूँ, लेकिन सही जानकारी नहीं मिल रहा।

अस्वीकरण:

// finds the next empty square (in "reading order") 
// returns array of first row then column coordinate 
// if there is no empty square, returns .... (FILL IN!) 
int[] findEmptySquare() { 
int[] rowcol; 
int[] noMoreCells; 
rowcol = new int[2]; 
noMoreCells = new int[2]; 
noMoreCells[0] = -1; 
noMoreCells[1] = -1; 

for(int r = 0; r < ms; r++){ 
    for(int c = 0; c < ms; c++){ 
    if(grid[r][c] == 0){ 
     if(r != rempty || c != cempty){ //check that the location of empty cell is not the same as last one 
     rempty = r; 
     cempty = c; 
     rowcol[0] = r; // 0 for row 
     rowcol[1] = c; // 1 for column 
     //System.out.println(" column c:"+rowcol[1]+" row r:"+rowcol[0]); //column c5 r 3 
     return rowcol; 
     }//end if 
     else{ 
     System.out.println("findEmptySquare: found same empty square twice"); 
     return noMoreCells; 
     }//end else 
    }//end if 
    }//end for 
}//end for 

System.out.println("findEmptySquare: no more empty cells"); 
return null; //no more empty cells 
} 

:

 // prints all solutions that are extensions of current grid 
     // leaves grid in original state 
void solve() { 
//local variables 
int[] currentSquare; 
int currentRow; 
int currentColumn; 
boolean checkConflict; 
currentSquare = new int[2]; 

//saftey limit for testing 
int limit; 
limit = 0; 

while(findEmptySquare() != null){ 

    currentSquare = findEmptySquare().clone(); 
    currentRow = currentSquare[0]; 
    currentColumn = currentSquare[1]; 
    //System.out.println(" column c:"+currentColumn+" row r:"+currentRow); //column c5 r 3 

    if(currentSquare[0] != -1){ 

    for(int n = 1; n <= ms; n++){ 
     checkConflict = givesConflict(currentRow, currentColumn, n); 
     if(checkConflict == false){ 
     grid[currentRow][currentColumn] = n; 
     }//end if 
    }//end for 
    }//end if 
    else{ 
    System.out.println("solve: findEmptySquare was -1"); 
    break; 
    } 

    //Safety limit 
    limit++; 
    if (limit > 20){ 
    System.out.println("break"); 
    break; 
    }//end if 

}//end while 
} 

यहाँ विधि है कि खाली वर्गों पाता है: विधि printMatrix के बाहर सभी println आदेशों परीक्षण

यहाँ के लिए कर रहे हैं सवाल में विधि है

यदि आवश्यक हो, तो संपूर्ण कोड (इंडेंटेशन गन्दा है क्योंकि मुझे मैन्युअल रूप से स्पाक जोड़ना पड़ा एस स्टैक ओवरफ्लो पर):

// Alain Lifmann. Date: 26/9/2015 
// Description of program: runs sudoku game 
import java.util.*; 

class Sudoku { 
    int ms = 9; //maze Size 
    int rempty; //keeping track of empty squares, row nr. (array) 
    int cempty; //keeping track of empty squares, column nr. (array) 
    int SIZE = 9;  // size of the grid 
    int DMAX = 9;  // maximal digit to be filled in 
    int BOXSIZE = 3; // size of the boxes 
    int[][] grid;  // the puzzle grid; 0 represents empty 

     // a challenge-sudoku from the web 
    int[][] somesudoku = new int[][] {   
{ 0, 6, 0, 0, 0, 1, 0, 9, 4 }, //original  
    // { 0, 0, 0, 0, 0, 1, 0, 9, 4 }, //to get more solutions 
{ 3, 0, 0, 0, 0, 7, 1, 0, 0 }, 
{ 0, 0, 0, 0, 9, 0, 0, 0, 0 }, 

{ 7, 0, 6, 5, 0, 0, 2, 0, 9 }, 
{ 0, 3, 0, 0, 2, 0, 0, 6, 0 }, 
{ 9, 0, 2, 0, 0, 6, 3, 0, 1 }, 

{ 0, 0, 0, 0, 5, 0, 0, 0, 0 }, 
{ 0, 0, 7, 3, 0, 0, 0, 0, 2 }, 
{ 4, 1, 0, 7, 0, 0, 0, 8, 0 }, 
    }; 

    // a test-sudoku from oncourse 
    int[][] testsudoku = new int[][] {   
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },  
{ 4, 5, 6, 7, 8, 9, 1, 2, 3 }, 
{ 7, 8, 9, 1, 2, 3, 4, 5, 6 }, 

{ 2, 1, 4, 3, 6, 5, 8, 9, 7 }, 
{ 3, 6, 5, 8, 9, 7, 2, 1, 4 }, 
{ 8, 9, 7, 2, 1, 4, 3, 6, 5 }, 

{ 5, 3, 1, 6, 4, 2, 9, 7, 8 }, 
{ 6, 4, 2, 9, 7, 8, 5, 3, 1 }, 
{ 9, 7, 8, 5, 3, 1, 6, 4, 2 }, 
    }; 

    // a test-sudoku modified to be incomplete 
    int[][] testsudoku2 = new int[][] {   
{ 0, 0, 3, 0, 5, 6, 7, 8, 0 },  
{ 0, 5, 0, 7, 0, 0, 1, 0, 3 }, 
{ 7, 0, 0, 1, 0, 3, 4, 5, 6 }, 

{ 2, 1, 4, 3, 6, 5, 8, 0, 7 }, 
{ 3, 0, 5, 8, 0, 7, 0, 1, 0 }, 
{ 0, 9, 7, 0, 1, 4, 3, 0, 5 }, 

{ 0, 0, 0, 6, 4, 2, 9, 7, 8 }, 
{ 0, 4, 2, 9, 7, 8, 0, 0, 1 }, 
{ 0, 0, 0, 5, 3, 1, 0, 4, 0 }, 
    }; 

    int solutionnr = 0; //solution counter 

    // ----------------- conflict calculation -------------------- 

    // is there a conflict when we fill in d at position r,c? 
    boolean givesConflict(int r, int c, int d) { 
if(rowConflict(r, d) == true){ 
    return true; 
}//end if 
if(colConflict(c, d) == true){ 
    return true; 
}//end if 
if(boxConflict(r, c, d) == true){ 
    return true; 
}//end if  
return false; 
    }//end givesConflict 


    boolean rowConflict(int r, int d) { 
    for(int i = 0; i < ms; i++){ 
    if(d == grid[r][i]){ 
    //System.out.println("rowconflict r:"+r+" d:"+d); 
    return true; 
    }//end if 
    }//end for 

    return false; //no conflict 
    } 

    boolean colConflict(int c, int d) { 
    for(int i = 0; i < ms; i++){ 
    if(d == grid[i][c]){ 
    //System.out.println("column conflict c:"+c+" d:"+d); 
    return true; 
    }//end if 
    }//end for 

    return false; //no conflict 
    } 

    boolean boxConflict(int rr, int cc, int d) { //test 5,3,1 
int rs; // Box-row start point 
int cs; // Box-column start point 
rs = rr - rr%3; 
cs = cc - cc%3; 
//System.out.println("box start is row "+rs+" , column "+cs); 

for(int r = rs; r < rs + 3; r++){ 
    for(int c = cs; c < cs + 3; c++){ 

    if(d == grid[r][c]){ 
     //System.out.println("r:"+r+" c:"+c); 
     return true; 
    }//end if 

    }//end for 
}//end for 

    return false; //no conflict 
    } 

    // --------- solving ---------- 

    // finds the next empty square (in "reading order") 
    // returns array of first row then column coordinate 
    // if there is no empty square, returns .... (FILL IN!) 
    int[] findEmptySquare() { 
int[] rowcol; 
int[] noMoreCells; 
rowcol = new int[2]; 
noMoreCells = new int[2]; 
noMoreCells[0] = -1; 
noMoreCells[1] = -1; 

    for(int r = 0; r < ms; r++){ 
     for(int c = 0; c < ms; c++){ 
    if(grid[r][c] == 0){ 
     if(r != rempty || c != cempty){ //check that the location of empty cell is not the same as last one 
     rempty = r; 
     cempty = c; 
     rowcol[0] = r; // 0 for row 
     rowcol[1] = c; // 1 for column 
     //System.out.println(" column c:"+rowcol[1]+" row r:"+rowcol[0]); //column c5 r 3 
     return rowcol; 
     }//end if 
     else{ 
     System.out.println("findEmptySquare: found same empty square twice"); 
     return noMoreCells; 
     }//end else 
    }//end if 
    }//end for 
    }//end for 

    System.out.println("findEmptySquare: no more empty cells"); 
    return null; //no more empty cells 
     } 

    // prints all solutions that are extensions of current 
    // leaves grid in original state 
    void solve() { 
//local variables 
int[] currentSquare; 
int currentRow; 
int currentColumn; 
boolean checkConflict; 
currentSquare = new int[2]; 

//saftey limit for testing 
int limit; 
limit = 0; 

while(findEmptySquare() != null){ 

    currentSquare = findEmptySquare().clone(); 
    currentRow = currentSquare[0]; 
    currentColumn = currentSquare[1]; 
    //System.out.println(" column c:"+currentColumn+" row r:"+currentRow); //column c5 r 3 

    if(currentSquare[0] != -1){ 

    for(int n = 1; n <= ms; n++){ 
     checkConflict = givesConflict(currentRow, currentColumn, n); 
     if(checkConflict == false){ 
     grid[currentRow][currentColumn] = n; 
     }//end if 
    }//end for 
    }//end if 
    else{ 
    System.out.println("solve: findEmptySquare was -1"); 
    break; 
    } 

    //Safety limit 
    limit++; 
    if (limit > 20){ 
    System.out.println("break"); 
    break; 
    }//end if 

}//end while 
    } 

    // ------------------------- misc ------------------------- 

    // print the grid, 0s are printed as spaces 
    void printMatrix(){ 
int ms; //matrix Size 
ms = 9; 
//layer indication symbols 
String end; 
String mid; 
String cut; 
end = "+"; 
mid = "-"; 
cut = ""; 
for(int i = 0; i < 2*ms-1; i++){ 
    cut = cut + mid; 
}//end for 

    System.out.println(end+cut+end); 
for(int i = 0; i < ms; i++){ 
    if(i % 3 == 0 && i != 0){ 
    System.out.println(mid+cut+mid); 
    }//end if 
    for(int j = 0; j < ms; j++){ 
    if(j % 3 == 0){ 
     System.out.print("|"); 
    }//end if 
    else{ 
     System.out.print(" "); 
    }//end else 
    if(grid[i][j] != 0){ 
     System.out.print(grid[i][j]); 
    }//end if 
    else{ 
     System.out.print(" "); 
    }//end else 
    }//end for j 
    System.out.print("|"); 
    System.out.println(); 
}//end for i 
System.out.println(end+cut+end); 
    }//end method 

    // reads the initial grid from stdin 
    void read() { 
Scanner sc = new Scanner(System.in); 

for (int r=0; r<SIZE; r++) { 
    if (r % BOXSIZE == 0) { 
    sc.nextLine(); // read away top border of box 
    } 
    for (int c=0; c < SIZE; c++) { 
    if (c % BOXSIZE == 0) { 
     sc.next(); // read away left border of box 
    } 
    String square = sc.next(); 
    if (".".equals(square)) { 
     grid[r][c] = 0; // empty sqaure 
    } else { 
     grid[r][c] = Integer.parseInt(square); 
    } 
    //System.out.print(grid[r][c]); 
    } 
    sc.nextLine(); // read away right border 

} 
sc.nextLine(); // read away bottom border 
    } 

    // --------------- where it all starts -------------------- 




    void solveIt() { 
grid = somesudoku.clone();  // set used grid (before doing anything else) 
printMatrix(); 
solve(); 
printMatrix(); 


/* test material 
printMatrix(); 
//System.out.println(givesconflict(1,1,3)); 
System.out.println(rowConflict(0,1)); 
System.out.println(colConflict(0,1)); 
System.out.println(boxConflict(0,0,1)); 
findEmptySquare(); 
*/ 
    }// end solveIt 

    public static void main(String[] args) { 
new Sudoku().solveIt(); 
    } 
    } 

Answer 1

इस समस्या को बैकट्रैकिंग द्वारा हल किया जा सकता है। आपको सभी संभावित विकल्पों के माध्यम से पुन: साझा करना होगा, लेकिन जब आपको कोई गलत समस्या आती है, तो उस पथ से वापस आएं। आप इस लिंक http://learnfreecodes.blogspot.in/2015/11/sudoku-solver-using-backtracking-in-java.html