risolutore di sudoku che utilizza il backtracking

Question

Ho recentemente lavorato a un algoritmo di risoluzione del sudoku di backtracking e attualmente vorrei chiedere come dovrei passare a cambiare il mio metodo solve() da vuoto a booleano.

sto usando un algoritmo di backtracking molto semplice, e sta attualmente lavorando bene, ma preferirei avere un valore booleano invece di un vuoto, perché avere un printstack non è molto bello ...

Grazie !

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

Beh, si potrebbe catch l'eccezione di evitare la traccia dello stack, ma che non è ancora molto bella. Cosa si può fare dopo aver cambiato il tipo di ritorno a boolean è:

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

e poi, naturalmente, modificare le throw dichiarazioni 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; 
}