數(shù)字華容道凰慈，是在4x4的格子中汞幢，依次從左到右，從上到下放置1-15這15個數(shù)字微谓。經(jīng)過一定的隨機森篷，必須將這15個數(shù)字復(fù)原。每個數(shù)字只能向相鄰的唯一空格移動豺型。難度更高的，格子和數(shù)字會更多姻氨，比如5x5。
我在開發(fā)一個類數(shù)字華容道游戲時前联，發(fā)現(xiàn)自己3x3的格子似嗤，居然怎么都解不出來届宠。比如：一排1、2顽馋、3幌羞，二排4属桦、5他爸、6，三排8系谐，7。經(jīng)過網(wǎng)上查詢鄙煤，才知道完全隨機位置的數(shù)值華容道僅有50%的概率是有解的梯刚。而我就是用的完全隨機方式去打亂次序薪寓。
網(wǎng)上有兩篇文章說的很好，以下是根據(jù)這兩篇文章的總結(jié)锥腻。
數(shù)字華容道必然有解的前提
首先母谎，要弄清楚一個概念：逆序數(shù)。逆序數(shù)供璧，即一個數(shù)字序列冻记，將其中所有數(shù)字依次兩兩對比，若大數(shù)在前演顾，小數(shù)在后钠至，那么這就是一對逆序數(shù)胎源。這里說到的逆序數(shù)，指的是數(shù)字序列中逆序數(shù)的數(shù)量宪卿。比如：上文提到的1万栅、2、3休溶、4、5芭碍、6禾进、8、7艇拍，逆序數(shù)只有1個卸夕，即8和7婆瓜。
另外，還有一點要提出來个初。一般來講猴蹂，復(fù)原狀態(tài)（初始狀態(tài)）的數(shù)字華容道，會有一個空格珍逸，一般會設(shè)置在最末行的右下角聋溜。但也可以根據(jù)實際的需求，設(shè)置在其他行漱病。請留意把曼，初始空格所在的行數(shù)，是決定是否有解的一個重要因素。
數(shù)字華容道型雳，必然有解，只存在于如下3個細分情形：
- 若格子列數(shù)為奇數(shù)沿量，則逆序數(shù)必須為偶數(shù)冤荆；
- 若格子列數(shù)為偶數(shù)，且逆序數(shù)為偶數(shù)乌妒，則當前空格所在行數(shù)與初始空格所在行數(shù)的差為偶數(shù)撤蚊；
- 若格子列數(shù)為偶數(shù)损话，且逆序數(shù)為奇數(shù)，則當前空格所在行數(shù)與初始空格所在行數(shù)的差為奇數(shù)光涂。
實際的推演涉及到我一時難以徹底理解的數(shù)學推算，我只能用淺顯的方式來理解這個問題忘闻。
為什么屎篱？
首先，有解的前提在于：當前空格回到初始空格所在行數(shù)時重虑，逆序數(shù)一定得是偶數(shù)秦士！為什么，我不清楚提针。
要想把空格移動到初始空格所在行曹傀，必須進行若干次上下移動和若干次左右移動。
左右移動皆愉，不會改變逆序數(shù)；上下移動久锥，若格子列數(shù)為奇數(shù)，則每次增減偶數(shù)個逆序數(shù)絮重，若格子列數(shù)為偶數(shù)青伤，則每次增減奇數(shù)個逆序數(shù)。
也就是說：
- 格子列數(shù)為奇數(shù)潮模，怎么移動痴施，都不會改變原始的逆序數(shù)。因為奇數(shù)加減偶數(shù)還是奇數(shù)动遭，偶數(shù)加減偶數(shù)還是偶數(shù)神得。所以，只要保證逆序數(shù)是偶數(shù)即可宵蕉，不必關(guān)心空格的位置羡玛。
- 格子列數(shù)為偶數(shù)宗苍，那么進行奇數(shù)次上下移動，會改變其逆序數(shù)的奇偶性讳窟。所以，如果當前逆序數(shù)是偶數(shù)谋右，要想有解倚评，就要保證實際上下移動會進行偶數(shù)次，也就是說空格所在行與初始空格所在行的差為偶數(shù)天梧。
- 同理霞丧，若當前逆序數(shù)是奇數(shù)蛹尝，要想有解，要進行奇數(shù)次的移動挫酿，才能保證最終逆序數(shù)是偶數(shù)早龟。
如何轉(zhuǎn)換逆序數(shù)奇偶性
具體實現(xiàn)應(yīng)該很簡單，不多說了葱弟，就說一點猜丹。如果想更改一個數(shù)字序列的逆序數(shù)的奇偶性射窒，只需要調(diào)換一對逆序數(shù)的位置即可。
最后
可能是CS106A課程上的一句話脉顿，并不是原文：
程序員要在不理解內(nèi)在實現(xiàn)邏輯的情況下，也能順暢地使用別人的成果祥楣。
不理解沒關(guān)系汉柒，會用就行。
參考文檔：
