Решение Sudoku в java с использованием backtrack

Question

Я пытаюсь написать решение sudoku с помощью java. Я использовал для этого общий алгоритм возврата. Но программа не работает должным образом (возвращение нуля)

Вот код

public class Sudoku { 

    int[][] board;                //Sudoku board 


    public Sudoku() {               //constructor 
     this.board = new int[9][9];    
     for(int i=0;i<9;i++) 
      for(int j=0;j<9;j++) 
       board[i][j]=0; 
    } 

    public Sudoku(int[][] board){            //constructor 
     this.board=board; 
    } 


    public int[][] Solve(int[][] board){ 
     int i, j, k,l,val;              //iterators 
     int empty=1;               //empty flag 
     int[][] temp=new int[9][9];            //temporary array for backtracking 
     temp=board; 
     for(i=0;i<9;i++)              //check if any empty space available 
      for(j=0;j<9;j++){ 
       if(board[i][j]==0){ 
        empty=0; 
        break; 
       } 
      } 
     if(empty==1)return board; 
     for(i=0;i<9;i++) 
      outerLoop: 
      for(j=0;j<9;j++){ 
       if(board[i][j]>0)continue; 
       for(val=1;val<10;val++){          //try values 
        for(k=0;k<9;k++){ 
         if(board[i][k]==val)break;        //check row consistancy 
         if(board[k][j]==val)break;        //check column consistancy  
        } 
        for(k=(i/3)*3;k<(i/3+1)*3;k++)        //check latin square consistancy 
         for(l=(j/3)*3;l<((j/3+1)*3);l++) 
          if(board[k][l]==val)break;      
        temp[i][j]=val;            //put consistant value 
        Solve(temp);            //recursive call for backtrack 
       } 
     } 
     return null;                
    } 


    public static void main(String[] args) { 
     // TODO code application logic here 
     int[][] board={ {5,3,0,0,7,0,0,0,0}, 
         {6,0,0,1,9,5,0,0,0}, 
         {0,9,8,0,0,0,0,6,0}, 
         {8,0,0,0,6,0,0,0,3}, 
         {4,0,0,8,0,3,0,0,1}, 
         {7,0,0,0,2,0,0,0,6}, 
         {0,6,0,0,0,0,2,8,0}, 
         {0,0,0,4,1,9,0,0,5}, 
         {0,0,0,0,8,0,0,7,9}}; 
     Sudoku s=new Sudoku(board); 
     int[][] temp=new int[9][9]; 
     temp=s.Solve(board); 
     for(int i=0;i<9;i++){ 
      System.out.println(""); 
      for(int j=0;j<9;j++){ 
       System.out.print(temp[i][j]); 
       System.out.print(","); 
      } 
     } 
    }  
} 

Я поставил нулевое обратное заявление в связи с Netbeans предложений, но это должно никогда не возвращаться пустыми. Я не могу найти ошибку. Заранее спасибо за вашу помощь.

Answer 1

Я собираюсь сосредоточиться на Solve(int[][]) метода:

public int[][] Solve(int[][] board){ 

Под Java именования, методы должны быть верблюжьего: solve(int[][] board)

int i, j, k,l,val; 

Если необходимо, вы не должны определять итераторы в начале метода. Это дает им «ложное чувство цели», что делает код более сложным для интерпретации.

int empty=1; 

Это должно быть логическое значение, потому что это только когда-либо имеет значение 1 или 0. Логическое значение будет гораздо более удобным для чтения здесь: boolean empty = false;

int[][] temp=new int[9][9];            
    temp=board; 

Кроме того, я советую разбивая код в «параграфы» или связанные с ними операции. Это будет хорошим местом для нового абзаца, поскольку вы переходите от определений к некоторой исходной логике.

for(i=0;i<9;i++)               
     for(j=0;j<9;j++){ 
      if(board[i][j]==0){ 
       empty=true; 
       break; 
      } 
     } 
    if(!empty)return board; 

Это должен быть его собственный абзац, поскольку он обрабатывает одну задачу, проверяя, разрешена ли доска. Я также обновил его, чтобы показать, как boolean читает лучше.

for(i=0;i<9;i++) 
     outerLoop: 
     for(j=0;j<9;j++){ 
      if(board[i][j]>0)continue; 
      for(val=1;val<10;val++){           
       for(k=0;k<9;k++){ 
        if(board[i][k]==val)break;        
        if(board[k][j]==val)break;         
       } 
       for(k=(i/3)*3;k<(i/3+1)*3;k++)        
        for(l=(j/3)*3;l<((j/3+1)*3);l++) 
         if(board[k][l]==val)break;      
       temp[i][j]=val;            
       Solve(temp);             
      } 
    } 
    return null;                
} 

Ваш код имеет два оператора возврата, один для готовой доски и один, который ловит логические ошибки. Ошибка в вашем рекурсивном вызове. Просто вызов Solve(temp); не сохранит никаких изменений, внесенных вами в данные. Рекурсивная функция работает только в том случае, если вы используете новую информацию, генерируемую рекурсивным вызовом. Поэтому, чтобы исправить вашу ошибку, верните свой рекурсивный вызов:

return Solve(temp);