A study on the solution of 9-room diagram by state space method
Han Ai-li · Journal of Shandong University · 2004
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.