用状态空间法求解9-宫图问题的理论研究

对用状态空间法求解 9 宫图问题时的状态变化规律进行研究 .通过研究发现 ,对于 9 宫图问题的任意实例 ,当其逆序数为偶数时 ,状态总是由逆序数为偶数的一个状态到达逆序数为偶数的另一个状态 ,并且总能在有限步内把棋子按次序排列好 ;当其逆序数为奇数时 ,状态总是由逆序数为奇数的一个状态到达逆序数为奇数的另一个状态 ,并且总是不能把棋子按次序排列好 ,但总能到达状态 12 345 6 87.通过理论证明 ,指出 9 宫图问题的状态空间由两个连通分支组成 :逆序数为偶数的连通分支E和逆序数为奇数的连通分支O .若 9 宫图实例的初始状态和目标状态位于不同的连通分支 ,则实例无解 ;若 9 宫图实例的初始状态和目标状态位于同一连通分支 ,则必可在有限步内求得实例的解 .

A study on the solution of 9-room diagram by state space method

The state-change law of solving 9-room diagram by state space method is researched in this paper. It is discovered that,for any instance of the 9-room diagram,if the contra-order number is even,the state is always from one state with even contra-order number to another state with even contra-order number,and the chessman can surely be arranged in order in the limited steps. If the contra-order number is odd,the state is always from one state with odd contra-order number to another state with odd contra-order number,and the chessman can not be arranged in order but can arrive at the state 12345687 in the limited steps. By giving the proof in theory,it is pointed out that the state space of 9-room problem is composed of two connected branches-the branch E,in which the contra-order number is even,and the branch O,in which the cowtra-prder nwmber is odd. If the original state and the object state of any 9-room instance are located in different connected branches,the instance has no solution;and if both the original state and the object state are located in the same connected branch,the solution of the instance can be obtained in the limited steps.