首先，我要声明这是一项大学作业，所以我不是要求有人为我编写代码，我只需要指出正确的方向。:)
好的，所以我需要编写一个算法来解决任意大小的任何（可解决的）数独板。我编写了一个递归函数，可以快速解决任何 9x9 板（约 1 毫秒），但是当我做较大的板（16x16）时，很难解决它。我已经进行了 20 分钟的测试，它可以' t似乎解决它。它可以解决简单的 16x16 难题，甚至可以解决空白的 16x16 板，所以我认为问题不是尺寸问题。我认为问题更可能是算法。
无论如何，这是我程序的基本逻辑..
- 我有一个 3D 向量来存储我的每个正方形的可能值
- 当一个值放在一个正方形中时，它会从它所在的周围正方形、行和列的可能值中删除
那么我的求解功能基本上是：
bool solve() {
if (there are no unfilled squares)
return true
if (the board is unsolvable - there are empty squares that have no possible values)
return false
while (there are empty squares)
{
int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square
if (squaresFilled == 0)
break;
}
//exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess
while (there are empty squares that have choices left) {
find the square with the least number of choices
if (the square with the least number of choices has 0 choices)
return false; //not solvable.
remove that choice from the 3D vector (vector that has the choices for each square)
make a copy of the board and the 3D choices vector
fill the square with the choice
if (solve())
return true; //we're done
restore the board and choices vector
//the guess didn't work so keep looping and make a new guess with the restored board and choices -- the choice we just made has been removed though so it won't get made again.
}
return false; //can't go any further
}
这有什么低效的吗？有什么办法可以让它更好地工作吗？我猜一个 16x16 的板需要这么长时间是因为它的决策树对于一个没有太多填充的板来说太大了。不过这很奇怪，因为 9x9 板会很快解决。
任何想法或建议都会非常棒。如果有任何我错过的信息，也请告诉我！