使用回溯的數獨求解器

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