Java遞推數獨求解器，遞歸函數不返回正確的值

Question

我正在使用一個數獨解算器，並且無法正確返回/終止解算器功能。 moveOn()函數中的show()被調用，它顯示完成的數獨罰款，但解決返回false。我試圖解決問題解決時返回true，解決問題時爲null，但不知道如何完成此操作。

L是板的長度（一個9×9的數獨將具有L = 9）

getSquare(r,c)返回一個2維陣列代表獨板

不同校驗功能檢查的值看看一個值是否可以放在特定的位置。他們不是問題。

show()函數在控制檯打印數組，使其看起來像一個合適的數獨板。

我也有一個isSolved()功能，檢查2D數組，如果它是一個有效的解決sudoku返回true，otherweise返回false。我試圖實現這個以及進入solve()方法，希望用它來返回true，但沒有成功

//This method's only purpose it to call the findNum function on the next location in the sudoku 
public void moveOn(int row, int column) { 
    //if the previous location was not the last in the row move to ne next cell in said row. 
    //if it was the last location in the row, move to the first column of the next row 
    if (column + 1 != L) {solve(row, column + 1);} 
    else if (row + 1 != L) {solve(row + 1, 0);} 
    else {show();} 
} 

//This method finds a valid number for a specific location on the sudoku grid\ 
public boolean solve(int row, int column) { 
    if (row >= L) {return true;} 
    //pass over any numbers that are not empty 
    if (getSquare(row, column) != 0) {moveOn(row, column);} 
    else { 
     //attempt to find a valid number for the location 
     for (int n = 1; n <= L; n++) { 
      if (checkRow(row, n) && checkCol(column, n) && checkSquare(row, column, n)) { 
       // If a number is allowed at a specific location set that location to the number 
       setSquare(row, column, n); 
       //Begin checking for a solution based on previous numbers changed   
       moveOn(row, column); 
      }    
     } 
     //If no number is allowed in this space backtrack to the last successful number 
     //changed and reset all locations that have been changed recursively 
     setSquare(row, column, 0);   
    } 
    //If the puzzle is unsolveable 
    return false; 
} 

非常感謝任何人，可以幫助闡明這種情況的一些情況。 如果需要更多的我的代碼/信息，我會很樂意提供

樣品輸入文件：http://pastebin.com/6mSKT3ES

編輯：完整的代碼去除

Answer 1

你必須在solve功能只有一個return說法，那就是

return false; 

而且因爲這是在函數的最後一條語句，並無條件地執行，solve意志，除非EXCE ption被拋出，總是返回false。

要得到一個實際告訴您是否找到解決方案的返回值，您需要使返回值取決於一個條件。此外，一旦你找到了一個解決方案，對於合適的謎題，繼續搜索沒有意義。

所以你應該在搜索循環中添加一個條件return true;。爲此，您需要知道您何時找到解決方案。您纏繞遞歸中moveOn中間調用，因此最簡單的變化將是一個返回值添加到moveOn：

public boolean moveOn(int row, int column) { 
    //if the previous location was not the last in the row move to ne next cell in said row. 
    //if it was the last location in the row, move to the first column of the next row 
    if (column + 1 != L) {return solve(row, column + 1);} 
    else if (row + 1 != L) {return solve(row + 1, 0);} 
    else {show(); return true;} // reached end of grid, solved 
} 

和使用，在'解決'：

public boolean solve(int row, int column) { 
    //pass over any numbers that are not empty 
    if (getSquare(row, column) != 0) {return moveOn(row, column);} 
    else { 
     //attempt to find a valid number for the location 
     for (int n = 1; n <= L; n++) { 
      if (checkRow(row, n) && checkCol(column, n) && checkSquare(row, column, n)) { 
       // If a number is allowed at a specific location set that location to the number 
       setSquare(row, column, n); 
       //Begin checking for a solution based on previous numbers changed   
       if (moveOn(row, column)) { 
        return true;  // solved, yay! 
       } 
      }    
     } 
     //If no number is allowed in this space backtrack to the last successful number 
     //changed and reset all locations that have been changed recursively 
     setSquare(row, column, 0);   
    } 
    //If the puzzle is unsolveable 
    return false; 
} 

Answer 2

This code works... 

import java.io.*; 
import java.util.Arrays; 
import java.util.Scanner; 


public class Sudoku { 

    public static int suRows=9; 
    public static int suColumns=9; 
    public static int [][] suArray = new int[suRows][suColumns]; 
    public static int [] dummyRowArray = new int[suRows]; 
    public static int [] dummyColArray = new int[suColumns]; 
    public static int [][] dummy3x3Array = new int[3][3]; 
    public static int [] dummyArray = new int[9]; 

    //read the contents of the file into a 2 dimensional array 
    public static void readSudoku() throws FileNotFoundException, IOException 
    { 
     System.out.print("Please enter the full file name containing the Sudoku Puzzle (e.g:X:/sudoku_case1.txt):"); 
     Scanner scan = new Scanner (System.in); 
     String filename = scan.nextLine(); 
     File file = new File(filename); 

     if (file.exists()) 
     { 
      Scanner inFile = new Scanner(file); 
      for(int i=0; i<suRows; i++) 
      { 
       for(int j=0; j<suColumns; j++) 
       { 
        if(inFile.hasNextInt()) suArray[i][j] = inFile.nextInt(); 
       } 
      } 
     inFile.close(); 
     }  
    } 

    public static boolean inOrder(int [] a, int i, int j) 
    { 
     return a[i]<=a[j]; 
    } 

    public static void swap(int [] a, int i, int j) 
    { 
     int tmp = a[i]; 
     a[i] = a[j]; 
     a[j] = tmp; 
    } 


    public static void exchangeSort(int [] a) 
    { 
     for(int i=0;i<a.length;i++) 
     { 
      for(int j=1;j<a.length-i;j++) 
      { 
       if(!inOrder(a,j-1,j)) swap(a,j-1,j); 
      } 
     } 
    } 

    public static void displaySudoku(int [][] suArray) 
    { 
     for(int i=0; i<suArray.length;i++) 
     { 
      for(int j=0; j<suArray[i].length;j++) 
      { 
       System.out.print(suArray[i][j]); 
       System.out.print(" "); 
      } 
      System.out.println(); 
     }  
    }  

    //Check if there are any more zeros 
    public static boolean isComplete(int [][]suArray) 
    { 
     boolean result=true; 

     //Check every element for 0 
     for(int i=0; i<suArray[0].length; i++) 
     { 
      for(int j=0 ; j<suRows ; j++) 
      { 
       if(suArray[i][j]==0) return false; 
      } 
     } 
     System.out.println("There are no zeros in this Sudoku"); 
     return result; 
    }  


    //Check for adjacent duplicates 
    public static boolean isAdjacentDup(int [] a) 
    { 
     for(int i=1; i<a.length; i++) 
     { 
      if((a[i-1]!=0 || a[i]!=0)) 
      { 
        if(a[i-1]==a[i]) return true; 
      } 
     } 
     return false;  
    } 

    //Check for 1 through 9 
    public static boolean is1to9(int [] a) 
    { 
     int j=1; 
     for(int i=0; i<a.length; i++) 
     { 
      if(a[i]==j) j++; 
      else return false; 
     } 
     return true;  
    } 

    public static boolean isDuplicate(int [][]suArray) 
    { 
     boolean result=false; 

     //Check every row for duplicates 
     for(int i=0; i<suArray[0].length; i++) 
     { 
      for(int j=0 ; j<suRows ; j++) 
      { 
       dummyRowArray[j]=suArray[i][j]; 
      } 

      //Sort dummyArray so that duplicates can be checked 
      exchangeSort(dummyRowArray); 


      //Now check Adjacent elements for duplicates 
      if(isAdjacentDup(dummyRowArray)==true) 
      { 
       System.out.println("Duplicates are found in row"); 
       return true; 
      } 

     } 

     displaySudoku(suArray); 

     //Check every column for duplicates 
     for(int j=0; j<suArray[0].length; j++) 
     { 
      for(int i=0 ; i<suColumns ; i++) 
      { 
       dummyColArray[i]=suArray[i][j]; 
      } 

      //Sort dummyArray so that duplicates can be checked 
      exchangeSort(dummyColArray); 


      //Now check Adjacent elements for duplicates 
      if(isAdjacentDup(dummyColArray)==true) 
      { 
       System.out.println("Duplicates are found in columns"); 
       return true; 
      } 

     } 

     displaySudoku(suArray); 

     System.out.println("3X3:"); 

     //Check every 3X3 matrix for duplicates 
     // 1st block 
     if(is3x3Duplicate(suArray,0,3,0,3)==true) 
     { 
      System.out.println("1st Block has a duplicate"); 
      return true; 
     } 
     else System.out.println("1st Block has no duplicate"); 
     // 2nd block 
     if(is3x3Duplicate(suArray,0,3,3,6)==true) 
     { 
      System.out.println("2nd Block has a duplicate"); 
      return true; 
     } 
     // 3rd block 
     if(is3x3Duplicate(suArray,0,3,6,9)==true) 
     { 
      System.out.println("3rd Block has a duplicate"); 
      return true; 
     } 
     // 4th block 
     if(is3x3Duplicate(suArray,3,6,0,3)==true) 
     { 
      System.out.println("4th Block has a duplicate"); 
      return true; 
     } 
     // 5th block 
     if(is3x3Duplicate(suArray,3,6,3,6)==true) 
     { 
      System.out.println("5th Block has a duplicate"); 
      return true; 
     } 
     // 6th block 
     if(is3x3Duplicate(suArray,3,6,6,9)==true) 
     { 
      System.out.println("6th Block has a duplicate"); 
      return true; 
     } 
     // 7th block 
     if(is3x3Duplicate(suArray,6,9,0,3)==true) 
     { 
      System.out.println("7th Block has a duplicate"); 
      return true; 
     } 
     // 8th block 
     if(is3x3Duplicate(suArray,6,9,3,6)==true) 
     { 
      System.out.println("8th Block has a duplicate"); 
      return true; 
     } 
     // 9th block 
     if(is3x3Duplicate(suArray,6,9,6,9)==true) 
     { 
      System.out.println("9th Block has a duplicate"); 
      return true; 
     } 

     return result; 
    } 

    //Check every3X3 grid for duplicates 
    public static boolean is3x3Duplicate(int [][]suArray, int x1, int x2, int y1, int y2) 
    { 
     boolean result=false; 
     int k=0, l=0; 

     for(int i=x1; i<x2;i++) 
     { 
      for(int j=y1;j<y2;j++) 
      { 

       dummy3x3Array[k][l]=suArray[i][j]; 
       l++; 
      } 
      l=0; 
      k++; 
     } 
     displaySudoku(dummy3x3Array); 

     for(int i=0; i<dummy3x3Array.length; i++) 
     { 
      for(int j=0; j<dummy3x3Array.length; j++) 
      { 
       dummyArray[(i*dummy3x3Array.length) + j] = dummy3x3Array[i][j]; 
      } 
     } 

     System.out.println(Arrays.toString(dummyArray)); 

     //Sort dummyArray so that duplicates can be checked 
     exchangeSort(dummyArray); 



     //Now check Adjacent elements for duplicates 
     if(isAdjacentDup(dummyArray)==true) 
     { 
      System.out.println("Duplicates are found in blocks"); 
      return true; 
     } 

     return result; 
    } 

    //Check every3X3 grid for 1 trough 9 
    public static boolean is3x3have1to9(int [][]suArray, int x1, int x2, int y1, int y2) 
    { 
     boolean result=false; 
     int k=0, l=0; 

     for(int i=x1; i<x2;i++) 
     { 

      for(int j=y1;j<y2;j++) 
      { 

       dummy3x3Array[k][l]=suArray[i][j]; 
       l++; 
      } 
      l=0; 
      k++; 
     } 


     for(int i=0; i<dummy3x3Array.length; i++) 
     { 
      for(int j=0; j<dummy3x3Array.length; j++) 
      { 
       dummyArray[(i*dummy3x3Array.length) + j] = dummy3x3Array[i][j]; 
      } 
     } 



     //Sort dummyArray so that duplicates can be checked 
     exchangeSort(dummyArray); 



     //Now check Adjacent elements for duplicates 
     if(is1to9(dummyArray)==false) 
     { 
      System.out.println("Block doe snot have 1 through 9"); 
      return false; 
     } 

     return result; 
    } 



    public static boolean isValidSudoku(int [][] suArray) 
    { 
     // boolean result=true; 

     //All nos should be between 0 and 9 
     for(int i=0; i<suArray.length; i++) 
     { 
      for(int j=0; j<suArray[i].length; j++) 
      { 
        if(suArray[i][j]<0 || suArray[i][j]>9){ 
         System.out.println("Nos in the puzzle are out of range"); 
         return false; 
        } 
      } 
     } 

     //Call teh isDuplicate function to check for duplicates in the rows 
     if(isDuplicate(suArray)==true) return false; 

     return true; 

    } 

    public static boolean isSolvedSudoku(int [][] suArray) 
    { 
     //Check every row for 1 to 9 
     for(int i=0; i<suArray[0].length; i++) 
     { 

      for(int j=0 ; j<suRows ; j++) 
      { 
       dummyRowArray[j]=suArray[i][j]; 
      } 


      //Sort dummyArray so that duplicates can be checked 
      exchangeSort(dummyRowArray); 



      if(is1to9(dummyRowArray)==false) 
      { 
       System.out.println("1 through 9 not present in rows"); 
       return false; 
      } 


     } 
     //Check every column for 1 to 9 
     for(int j=0; j<suArray[0].length; j++) 
     { 

      for(int i=0 ; i<suColumns ; i++) 
      { 
       dummyColArray[i]=suArray[i][j]; 
      } 


      //Sort dummyArray so that duplicates can be checked 
      exchangeSort(dummyColArray); 



      //Now check Adjacent elements for duplicates 
      if(is1to9(dummyColArray)==false) 
      { 
       System.out.println("1 through 9 not present in columns"); 
       return false; 
      } 

     } 

     //Check every 3X3 matrix for 1 through 9 
     // 1st block 
     if(is3x3have1to9(suArray,0,3,0,3)==true) 
     { 
      System.out.println("1st Block does not contain 1 through 9"); 
      return false; 
     } 
     // 2nd block 
     if(is3x3have1to9(suArray,0,3,3,6)==true) 
     { 
      System.out.println("2nd Block does not contain 1 through 9"); 
      return false; 
     } 
     // 3rd block 
     if(is3x3have1to9(suArray,0,3,6,9)==true) 
     { 
      System.out.println("3rd Block does not contain 1 through 9"); 
      return false; 
     } 
     // 4th block 
     if(is3x3have1to9(suArray,3,6,0,3)==true) 
     { 
      System.out.println("4th Block does not contain 1 through 9"); 
      return false; 
     } 
     // 5th block 
     if(is3x3have1to9(suArray,3,6,3,6)==true) 
     { 
      System.out.println("5th Block does not contain 1 through 9"); 
      return false; 
     } 
     // 6th block 
     if(is3x3have1to9(suArray,3,6,6,9)==true) 
     { 
      System.out.println("6th Block does not contain 1 through 9"); 
      return false; 
     } 
     // 7th block 
     if(is3x3have1to9(suArray,6,9,0,3)==true) 
     { 
      System.out.println("7th Block does not contain 1 through 9"); 
      return false; 
     } 
     // 8th block 
     if(is3x3have1to9(suArray,6,9,3,6)==true) 
     { 
      System.out.println("8th Block does not contain 1 through 9"); 
      return false; 
     } 
     // 9th block 
     if(is3x3have1to9(suArray,6,9,6,9)==true) 
     { 
      System.out.println("9th Block does not contain 1 through 9"); 
      return false; 
     } 

     return true; 
    } 


    public static boolean solveSudoku(int [][] s) 
    { 
     //Check if Valid 
     if(isValidSudoku(suArray)==true) System.out.println("Sudoku is valid"); 
     else 
     { 
      System.out.println("Not valid!"); 
      return false; 
     } 
     //Check if Complete - No 0's in any place 
     if(isComplete(suArray)==true) 
     { 
      System.out.println("Sudoku is Complete"); 
      return true; 
     } 
     else System.out.println("Sudoku is not Complete"); 

     //Check if solved - 1-9 present in every row, column and 3x3 
     if(isSolvedSudoku(suArray)==true) System.out.println("Sudoku is Solved!"); 
     else System.out.println("Not Solved"); 

     //Locate the first 0 in the Sudoko puzzle 
     for(int i=0; i<suArray.length; i++) 
     { 
      for(int j=0 ; j<suArray[i].length ; j++) 
      { 
       if(suArray[i][j]==0) 
       { 
        System.out.println("0 found in location: " + i +" " + j); 
        for(int k=1;k<10;k++) 
        { 
         suArray[i][j]=k; 
         System.out.println("New value assigned to Sudoku: " + k); 
         displaySudoku(suArray); 
         if(solveSudoku(suArray))// isValidSudoku(suArray)) 
         { 
          displaySudoku(suArray); 
          System.out.println("New value assigned to Sudoku"); 
          return true; 
         } 
        }  

        suArray[i][j]=0; 
        return false; // remove this 
       } 
      } 
     } 

     return true; 
    } 



    public static void main(String[] args) throws FileNotFoundException, IOException { 


     readSudoku(); 
     displaySudoku(suArray); 

     if((isValidSudoku(suArray)!=true)) 
     { 
      System.out.println("The given Sudoku Puzzle is not Valid!. Exiting...."); 
      System.exit(0); 
     } 

     do 
     { 
      if(isSolvedSudoku(suArray)==true) 
      { 
       System.out.println("Sudoku is Completely Solved!"); 

      } 

      if(solveSudoku(suArray)==true) 
      { 
       System.out.println("Sudoku is now solved"); 

      } 
      else System.out.println("Not Complete"); 


     }while(isSolvedSudoku(suArray)!=true); 

     System.out.println("Sudoku is now completely solved:"); 
     displaySudoku(suArray); 


    } 
}