sudoku solver using backtracking

Question

Я недавно работал над алгоритмом решения sudoku для обратного отслеживания, и в настоящее время я хотел бы спросить, как мне следует изменить метод solve() от void до логического.

Я использую очень простой алгоритм с возвратами, и это в настоящее время работает нормально, но я предпочел бы иметь логическое значение вместо пустоты, потому что имея printstack не очень приятно ...

Спасибо !

public class Backtracking{ 


static int backtrack = 0; 


//check if valid in row 
protected static boolean validInRow(int row, int value) 
{ 
    for(int col = 0; col < 9; col++) 
    if(board[row][col] == value) 
     return false ; 

    return true ; 
} 

    //check if valid in column 
protected static boolean validInCol(int col, int value) 
{ 
    for(int row = 0; row < 9; row++) 
    if(board[row][col] == value) 
     return false ; 

    return true ; 
} 

//check if valid in 3*3 
protected static boolean validInBlock(int row, int col, int value) 
{ 
    row = (row/3) * 3 ; 
    col = (col/3) * 3 ; 

    for(int r = 0; r < 3; r++) 
     for(int c = 0; c < 3; c++) 
     if(board[row+r][col+c] == value) 
     return false ; 

    return true ; 
} 




     //call other methods 
public void solve(int row, int col) throws Exception 
{ 

    if(row > 8) 
    throw new Exception("Solution found") ; 
    else 
    { 

    while(board[row][col] != 0) 
    { 
     if(++col > 8) 
     { 
      col = 0 ; 
      row++ ; 


      if(row > 8) 
       throw new Exception("Solution found") ; 
     } 
    } 


    for(int value = 1; value < 10; value++) 
    { 
     if(validInRow(row,value) && validInCol(col,value) && validInBlock(row,col,value)) 
     { 
      board[row][col] = value; 
      new PrintEvent(board); 



      if(col < 8) 
       solve(row, col + 1); 
      else 
       solve(row + 1, 0); 

      backtrack++; 
     } 
     } 


     board[row][col] = 0; 

     } 
    } 
} 

Answer 1

Ну, вы могли бы catch исключение, чтобы избежать трассировки стека, но это еще не очень красиво. Что вы можете сделать после того, как изменить тип возвращаемого значения boolean является:

 if(col < 8) { 
      if (solve(row, col + 1)) { 
       return true; 
      } 
     } else { 
      if (solve(row + 1, 0)) { 
       return true; 
      } 
     } 

, а затем, конечно, изменить throw заявления return true;.

Answer 2

public boolean solve(int row, int col) throws Exception 
{ 
    { 

    while(board[row][col] != 0) 
    { 
     if(++col > 8) 
     { 
      col = 0 ; 
      row++ ; 


      if(row > 8) 
      return true 
     } 
    } 


    for(int value = 1; value < 10; value++) 
    { 
     if(validInRow(row,value) && validInCol(col,value) && validInBlock(row,col,value)) 
     { 
      board[row][col] = value; 
      new PrintEvent(board); 



      if(col < 8) 
       solve(row, col + 1); 
      else 
       solve(row + 1, 0); 

      backtrack++; 
     } 
     } 


     board[row][col] = 0; 

     } 
    } 
return false; 
}