使用 A*(A-Star) 搜索解决数独难题
solve sudoku puzzle using A*(A-Star) search
我想使用 A* 搜索解决 sudoku 难题。
如何定义 g(n) 和 h(n)？ h 和 g 应该是多少？
我想在 python 中编写代码，但任何伪代码都将不胜感激
A* 是一种图形搜索算法，可找到从源到目的地（或一组目的地）之间的最短路径。
要在您的问题上使用 A*，您需要将其减少到 shortest path problem。
在你的情况下，它可以通过定义一个状态图来实现 - 其中图中的每个节点都是部分完整的数独 table，并且一条边表示你可以从一个状态移动到另一个状态。
正式：
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 }
现在，您需要找到从起始状态（给定的棋盘）到目标状态（完整有效的棋盘）的最短路径。
我想使用 A* 搜索解决 sudoku 难题。 如何定义 g(n) 和 h(n)？ h 和 g 应该是多少？
我想在 python 中编写代码，但任何伪代码都将不胜感激
A* 是一种图形搜索算法，可找到从源到目的地（或一组目的地）之间的最短路径。
要在您的问题上使用 A*，您需要将其减少到 shortest path problem。
在你的情况下，它可以通过定义一个状态图来实现 - 其中图中的每个节点都是部分完整的数独 table，并且一条边表示你可以从一个状态移动到另一个状态。
正式：
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 }
现在，您需要找到从起始状态（给定的棋盘）到目标状态（完整有效的棋盘）的最短路径。