博客

数字华容道，是在4×4的格子中，依次从左到右，从上到下放置1-15这15个数字。经过一定的随机，必须将这15个数字复原。每个数字只能向相邻的唯一空格移动。难度更高的，格子和数字会更多，比如5×5。

我在开发一个类数字华容道游戏时，发现自己3×3的格子，居然怎么都解不出来。比如：一排1、2、3，二排4、5、6，三排8，7。经过网上查询，才知道完全随机位置的数值华容道仅有50%的概率是有解的。而我就是用的完全随机方式去打乱次序。

网上有两篇文章说的很好，以下是根据这两篇文章的总结。

数字华容道必然有解的前提

首先，要弄清楚一个概念：逆序数。逆序数，即一个数字序列，将其中所有数字依次两两对比，若大数在前，小数在后，那么这就是一对逆序数。这里说到的逆序数，指的是数字序列中逆序数的数量。比如：上文提到的1、2、3、4、5、6、8、7，逆序数只有1个，即8和7。

另外，还有一点要提出来。一般来讲，复原状态(初始状态)的数字华容道，会有一个空格，一般会设置在最末行的右下角。但也可以根据实际的需求，设置在其他行。请留意，初始空格所在的行数，是决定是否有解的一个重要因素。

数字华容道，必然有解，只存在于如下3个细分情形：

若格子列数为奇数，则逆序数必须为偶数；

若格子列数为偶数，且逆序数为偶数，则当前空格所在行数与初始空格所在行数的差为偶数；

若格子列数为偶数，且逆序数为奇数，则