带有回溯的数独算法- java
带有回溯的数独算法- java
提问于 2012-11-14 18:52:03
所以我有个大学作业要解决数独问题。我读到过算法X和舞蹈算法，但它们对我没有帮助。
我需要通过回溯来实现它。我用维基百科给出的位置上的数字硬编码了二维数组中的一些索引(所以我确信它是可解的)。
我得到的代码如下：
public void solveSudoku(int row, int col)
{
// clears the temporary storage array that is use to check if there are
// dublicates on the row/col
for (int k = 0; k < 9; k++)
{
dublicates[k] = 0;
}
// checks if the index is free and changes the input number by looping
// until suitable
if (available(row, col))
{
for (int i = 1; i < 10; i++)
{
if (checkIfDublicates(i) == true)
{
board[row][col] = i;
if (row == 8)
solveSudoku(0, col + 1);
else if (col == 8)
solveSudoku(row + 1, 0);
else
solveSudoku(row, col + 1);
board[row][col] = 0;
}
}
}
// goes to the next row/col
else
{
if (row == 8)
solveSudoku(0, col + 1);
else if (col == 8)
solveSudoku(row + 1, 0);
else
solveSudoku(row, col + 1);
}
}
/**
* Checks if the spot on the certain row-col index is free of element
*
* @param row
* @param col
* @return
*/
private boolean available(int row, int col)
{
if (board[row][col] != 0)
return false;
else
return true;
}
/**
* Checks if the number given is not already used in this row/col
*
* @param numberToCheck
* @return
*/
private boolean checkIfDublicates(int numberToCheck)
{
boolean temp = true;
for (int i = 0; i < dublicates.length; i++)
{
if (numberToCheck == dublicates[i])
{
temp = false;
return false;
}
else if (dublicates[i] == 0)
{
dublicates[i] = numberToCheck;
temp = true;
return true;
}
}
return temp;
}我让StackOverflow开机了
// goes to the next row/col
else
{
if (row == 8)
solveSudoku(0, col + 1);
else if (col == 8)
solveSudoku(row + 1, 0);
else
solveSudoku(row, col + 1);
}这意味着我必须在某个时刻停止递归，但我不知道如何停止递归！如果您在solve()函数中发现任何其他错误，请让我知道。因为我不确定我完全理解“回溯”这件事...
回答 4
Stack Overflow用户
发布于 2012-11-14 19:01:45
例如，如果跟踪当前的递归深度，则可以停止递归
public void solveSudoku(int row, int col, int recursionDepth) {
// get out of here if too much
if (recursionDepth > 15) return;
// regular code...
// at some point call self with increased depth
solveSudoku(0, col + 1, recursionDepth + 1);
}如果您在
()函数中发现任何其他错误，请让我知道。
代码太多:)
Stack Overflow用户
发布于 2012-11-14 19:03:07
这大致就是我过去做这件事的方式。
Whenever all the definite moves have been taken and there is a choice of equally good next moves:
copy your grid data structure and push it onto a stack.
take the first candidate move and continue solving recursively
Whereever you get stuck:
pop the saved grid off the stack
take the next candidate move.Stack Overflow用户
发布于 2012-11-15 20:26:51
我用一种更简单的方式实现了它：
public void solve(int row, int col)
{
if (row > 8)
{
printBoard();
System.out.println();
return;
}
if (board[row][col] != 0)
{
if (col < 8)
solve(row, col + 1);
else
solve(row + 1, 0);
}
else
{
for (int i = 0; i < 10; i++)
if (checkRow(row, i) && checkCol(col, i))
//&& checkSquare(row, col, i))
{
board[row][col] = i;
if (col < 8)
solve(row, col + 1);
else
solve(row + 1, 0);
}
board[row][col] = 0;
}
}
private boolean checkRow(int row, int numberToCheck)
{
for (int i = 0; i < 9; i++)
if (board[row][i] == numberToCheck)
return false;
return true;
}
private boolean checkCol(int col, int numberToCheck)
{
for (int i = 0; i < 9; i++)
if (board[i][col] == numberToCheck)
return false;
return true;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13377407
复制相关文章
相似问题
腾讯云开发者
