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

我想用Python编写代码，但任何伪代码也将受到欢迎

回答：

A*是一种图搜索算法，它寻找从源到目的地（或一组目的地）的最短路径。

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

在你的情况下，可以通过定义一个状态图来实现——图中的每个节点都是一个部分填充的数独表格，边表示可以从一个状态移动到另一个状态。

正式地：

G = (V,E)V = { s | 对于数独棋盘的每个有效状态 s}E = { (u,v) | 可以通过添加一个数字从状态 u 移动到状态 v }

现在，你需要找到从起始状态（你给定的棋盘）到目标状态（一个完整有效的棋盘）的最短路径。