9-宫图问题的求解算法研究

摘要

通过理论证明指出了9-宫图问题的状态空间由两个连通分支组成：逆序数为偶数的连通分支E和逆序数为奇数的连通分支O。对于9-宫图问题的任意实例I，，若初始状态和目标状态位于不同的连通分支，则实例I无解；若初始状态和目标状态位于同一连通分支，则必可在有限步内求得实例I的解。在此基础上给出了9-宫图问题的满足可判定性要求的求解算法，并给出了其正确性证明。