数独求解器BackTracking与模拟退火

Question

在进一步阅读之前，假设您知道什么sudoku游戏以及如何解决它。

因此，我创建了一个具有蛮力的sudoku求解器:算法如下

1. (通过简单的规则检查)计算每个空单元格的所有可能值。
2. 计数空细胞
3. 如果任何单元格只有一种可能性，则设置单元格值并重新计算所有可能性。
4. 再计数空细胞
5. 如果旧的空单元数<新的空单元数，重复
6. 否则使用暴力

蛮力算法

1. (嵌套)对每个单元适用第一种可能性

1. 检查isSolved是否正确？休息:否则，应用第二种可能性并重复。

虽然上面的B.F.算法适用于简单的和中等的问题，但是对于每个单元来说有很多可能的困难问题，但是由于嵌套的for循环，程序崩溃了。

我的回溯算法使用相同的第一个algo来缩小搜索范围，然后

1. 为第一个空单元设置第一个可能性
2. 检查网格isValid==true；(如果解决了，则中断)，否则设置下一个单元格的第一个可能性，重复
3. 如果网格isValid==false，返回到以前的单元格并设置下一个可能性并继续

我已经在6x6网格上应用了BackTracking算法，它可以工作，我还没有在9x9网格上应用它。

模拟退火算法：

1. 随机设置每个空单元格的值
2. 计算误差计数
3. 生成随机邻接解和重计数错误。
4. 如果新错误计数<旧错误计数:保持新网格，否则保持旧网格
5. 如果网格被解决，则中断；否则重复。

现在我的问题是：

1. 我的模拟退火算法正确吗？
2. 显然，BackTracking解决问题的速度比BruteForce快得多，模拟退火解决问题的速度有多快？由于它是随机移动的，它最终可能要花费比BackTracking更长的时间来解决。
3. 如何在步骤3中生成随机邻接解？

Answer 1

1. 我的模拟退火算法正确吗？

这不是模拟退火，您描述的是随机爬山。当新配置比旧配置糟糕时，SA也会接受具有一定概率的新配置(并随着时间的推移降低该概率)。您没有具体说明如何计算“错误计数”，以及您已经提到的生成“相邻解决方案”的方式。它将取决于这些细节，如果一个不确定的算法会陷入一个局部最小值(这意味着它不会产生一个错误计数为0的解决方案)。请注意，即使您实现了正确的SA算法，也不能保证它会找到全局最优，这可能就是您在这里所要寻找的。

1. 显然，BackTracking解决问题的速度比BruteForce快得多，模拟退火解决问题的速度有多快？

这取决于这两种实现的实际实现，以及您在每个实现中投入多少优化工作。然而，一个真正的SA算法需要你指定一个“初始温度”和一个“降温”速率，如果你把这些参数指定错了，你就会得到一个非常慢的算法，或者一个根本找不到解决方案的算法。简单的“爬山”很可能会给你提供后者。

1. 如何在步骤3中生成随机邻接解？

您可以尝试不同的东西，但是一种简单的方法可能是修改一个单元格，然后逐个交换一个数字。另一种简单的方法是将每个数字从1到9在网格上分配9次，然后随机交换单元格内容。

检查一下我在这么老的问题上的答案。