algorithm - 使用 A*(A-Star) 搜索解决数独难题

Question

<分区>

Answer 1

A* 是一种图形搜索算法，可找到从源到目的地(或一组目的地)之间的最短路径。

要在您的问题上使用 A*，您需要将其减少到 shortest path problem .

在您的情况下，它可以通过定义一个状态图来实现 - 其中图中的每个节点都是一个部分完整的数独表，并且一条边表示您可以从一个状态移动到另一个状态。

正式地:

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 }

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