자바 재귀 스도쿠 솔버, 재귀 함수가 올바른 값을 반환하지 않습니다.

Question

스도쿠 솔버를 작업하고 있고 솔버 함수를 올바르게 반환하거나 종료하는 데 문제가 있습니다. moveOn() 함수에있는 show() 함수가 호출되면 완료된 스도쿠 벌금이 표시되지만 solve는 false를 반환합니다. 문제를 해결할 때 진정한 답을 풀려고 노력하고 있지만 해결할 수없는 경우에는이를 수행하는 방법을 모릅니다.

L

보드의 길이

getSquare(r,c)가

다른 체크 기능 확인 스도쿠 보드를 나타내는 2 차원 배열의 값을 리턴 (9 X 9 스도쿠 9 = L을 가질 것이다) 값이 특정 위치에 맞는지 확인하십시오. 그들은 문제가되지 않습니다.

show() 함수는 콘솔에서 배열을 인쇄하므로 적절한 스도쿠 보드처럼 보입니다.

또한 2D 배열을 검사하는 isSolved() 함수가 있으며 유효한 해결 스도쿠가 true를 반환하면 otherweise가 false를 반환합니다. 나는이뿐만 아니라에 사실이 반환하는 데 사용할 바라고 solve() 메소드를 구현하려고했습니다,하지만 어떤 성공을 상황에 도움이 되거 도움이 될 수 있습니다 사람에

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

및

그 함수의 마지막 문장, 그리고 무조건적 exce하지 않는 한, solve 의지, 실행 이후 ption이 throw됩니다. 항상 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); 


    } 
}