我最近一直在研究回溯数独求解算法,目前我想问一下我应该如何将我的solve()方法从void更改为boolean。
我正在使用一个非常简单的回溯算法,它目前工作正常,但我宁愿有一个布尔值而不是一个空值,因为有一个打印堆栈不是很好......
Thanks!
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;
}
}
}
嗯,你可以catch
避免堆栈跟踪的异常,但这仍然不是很漂亮。将返回类型更改为后可以做什么boolean
is:
if( col < 8 ) {
if (solve(row, col + 1)) {
return true;
}
} else {
if (solve(row + 1, 0)) {
return true;
}
}
然后当然,改变throw
声明给return true;
.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)