使用回溯的数独求解器

Question

我最近一直在研究回溯数独求解算法，现在我想问一下我应该如何将我的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; 
}