我有一个大学作业要解决数独……我读了一些有关算法X和Dancing算法的资料,但它们对我没有帮助。
我需要使用回溯法来解决问题。我已经在二维数组中硬编码了一些索引,这些索引来自维基百科上给出的数字位置(因此我确定这是可解的)。
我得到的代码如下:
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()
函数中的任何其他错误,请让我知道。因为我不确定我完全理解“回溯”...