用A*(A-Star)搜索解决sudoku难题

Question

我想用A*搜索来解决数独难题。如何定义g(n)和h(n)？H和g应该是什么？？

我想在python中编写这些代码，但是如果有任何伪代码，我们将不胜感激。

Answer 1

A*是一种图搜索算法，它在源到目标(或一组目标)之间找到最短路径。

要在您的问题上使用A*，您需要将其简化为最短路径问题。

在您的例子中，可以通过定义一个状态图来实现--图中的每个节点都是一个部分完整的sudoku表，边表示可以从一种状态移动到另一种状态。

正式：

G = (V,E)
V = { s | for each valid state s of the sudoku board}
E = { (u,v) | can move from state u to state v by adding one number }

现在，您需要找到从起始状态(给定的板)到目标状态(完全有效的板)的最短路径。