第3章图搜索与问题求解 例3.2在一个3×3的方格棋盘上放置着1,2,3,4,5,6， 7,8八个数码，每个数码占一格，且有一个空格。这些数码可 在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空 格。现在的问题是：对于指定的初始棋局和目标棋局（如图3-3 所示)，给出数码的移动序列。该问题称为八数码难题或重排九 宫问题 。 可以看出，图中的一条边（即相邻两个节点的连线）就对应 次数码移动，反之，一次数码移动也就对应着图中的一条边。而 数码移动是按数码的移动规则进行的。所以，图中的一条边也 就代表一个移动规则或者移动规则的一次执行。于是，这个八数 码问题也就是要在该有向图中寻找目标节点，或找一条从初始节 点到目标节点的路径问题。第 3 章 图搜索与问题求解 例 3.2 在一个3×3的方格棋盘上放置着1, 2, 3, 4, 5, 6, 7, 8八个数码, 每个数码占一格, 且有一个空格。 这些数码可 在棋盘上移动, 其移动规则是：与空格相邻的数码方可移入空 格。现在的问题是：对于指定的初始棋局和目标棋局(如图3-3 所示), 给出数码的移动序列。该问题称为八数码难题或重排九 宫问题。 可以看出,图中的一条边(即相邻两个节点的连线)就对应一 次数码移动,反之, 一次数码移动也就对应着图中的一条边。而 数码移动是按数码的移动规则进行的。所以, 图中的一条边也 就代表一个移动规则或者移动规则的一次执行。于是,这个八数 码问题也就是要在该有向图中寻找目标节点, 或找一条从初始节 点到目标节点的路径问题