用回溯算法求解数独问题

前几天我们在《浅析常见的算法范式》中讨论了一些常见的算法范式，但是还留下了回溯算法没有解决。本文来研究回溯算法。

回溯是通过逐步构建解决方案来解决递归问题的算法。通常回溯从可能的解决方案开始，如果它不起作用，则需要回溯并尝试另一种解决方案，直到找到可行的解决方案为止。回溯在解决 CSP（约束满足问题）时特别有用，例如填字游戏、口算题和数独等。

通常回溯算法可用于以下三种类型的问题：

需要找到可行解决方案的决策问题

需要找到最佳解决方案的优化问题

需要找到一组可行解决方案的列举问题

在本文中，我将通过解决数独问题来演示回溯策略。

解决数独问题

针对此类问题的回溯算法会尝试在每个空格中列举所有的数字，直到问题被解决为止。先从 main 方法开始：

接下来是算法的主要逻辑：

接下来看辅助函数的实现：

最后对算法进行测试：

以下是通过回溯法求解数独问题的模拟动画：

通过回溯法解决数独问题

希望本文能帮你理解回溯算法，以后我门还会再讨论更多有趣的算法。