數(shù)字華容道，是在4x4的格子中，依次從左到右，從上到下放置1-15這15個(gè)數(shù)字。經(jīng)過(guò)一定的隨機(jī)，必須將這15個(gè)數(shù)字復(fù)原。每個(gè)數(shù)字只能向相鄰的唯一空格移動(dòng)。難度更高的，格子和數(shù)字會(huì)更多，比如5x5。
我在開(kāi)發(fā)一個(gè)類(lèi)數(shù)字華容道游戲時(shí)，發(fā)現(xiàn)自己3x3的格子，居然怎么都解不出來(lái)。比如：一排1、2、3，二排4、5、6，三排8，7。經(jīng)過(guò)網(wǎng)上查詢(xún)，才知道完全隨機(jī)位置的數(shù)值華容道僅有50%的概率是有解的。而我就是用的完全隨機(jī)方式去打亂次序。
網(wǎng)上有兩篇文章說(shuō)的很好，以下是根據(jù)這兩篇文章的總結(jié)。
數(shù)字華容道必然有解的前提
首先，要弄清楚一個(gè)概念：逆序數(shù)。逆序數(shù)，即一個(gè)數(shù)字序列，將其中所有數(shù)字依次兩兩對(duì)比，若大數(shù)在前，小數(shù)在后，那么這就是一對(duì)逆序數(shù)。這里說(shuō)到的逆序數(shù)，指的是數(shù)字序列中逆序數(shù)的數(shù)量。比如：上文提到的1、2、3、4、5、6、8、7，逆序數(shù)只有1個(gè)，即8和7。
另外，還有一點(diǎn)要提出來(lái)。一般來(lái)講，復(fù)原狀態(tài)（初始狀態(tài)）的數(shù)字華容道，會(huì)有一個(gè)空格，一般會(huì)設(shè)置在最末行的右下角。但也可以根據(jù)實(shí)際的需求，設(shè)置在其他行。請(qǐng)留意，初始空格所在的行數(shù)，是決定是否有解的一個(gè)重要因素。
數(shù)字華容道，必然有解，只存在于如下3個(gè)細(xì)分情形：
- 若格子列數(shù)為奇數(shù)，則逆序數(shù)必須為偶數(shù)；
- 若格子列數(shù)為偶數(shù)，且逆序數(shù)為偶數(shù)，則當(dāng)前空格所在行數(shù)與初始空格所在行數(shù)的差為偶數(shù)；
- 若格子列數(shù)為偶數(shù)，且逆序數(shù)為奇數(shù)，則當(dāng)前空格所在行數(shù)與初始空格所在行數(shù)的差為奇數(shù)。
實(shí)際的推演涉及到我一時(shí)難以徹底理解的數(shù)學(xué)推算，我只能用淺顯的方式來(lái)理解這個(gè)問(wèn)題。
為什么？
首先，有解的前提在于：當(dāng)前空格回到初始空格所在行數(shù)時(shí)，逆序數(shù)一定得是偶數(shù)！為什么，我不清楚。
要想把空格移動(dòng)到初始空格所在行，必須進(jìn)行若干次上下移動(dòng)和若干次左右移動(dòng)。
左右移動(dòng)，不會(huì)改變逆序數(shù)；上下移動(dòng)，若格子列數(shù)為奇數(shù)，則每次增減偶數(shù)個(gè)逆序數(shù)，若格子列數(shù)為偶數(shù)，則每次增減奇數(shù)個(gè)逆序數(shù)。
也就是說(shuō)：
- 格子列數(shù)為奇數(shù)，怎么移動(dòng)，都不會(huì)改變?cè)嫉哪嫘驍?shù)。因?yàn)槠鏀?shù)加減偶數(shù)還是奇數(shù)，偶數(shù)加減偶數(shù)還是偶數(shù)。所以，只要保證逆序數(shù)是偶數(shù)即可，不必關(guān)心空格的位置。
- 格子列數(shù)為偶數(shù)，那么進(jìn)行奇數(shù)次上下移動(dòng)，會(huì)改變其逆序數(shù)的奇偶性。所以，如果當(dāng)前逆序數(shù)是偶數(shù)，要想有解，就要保證實(shí)際上下移動(dòng)會(huì)進(jìn)行偶數(shù)次，也就是說(shuō)空格所在行與初始空格所在行的差為偶數(shù)。
- 同理，若當(dāng)前逆序數(shù)是奇數(shù)，要想有解，要進(jìn)行奇數(shù)次的移動(dòng)，才能保證最終逆序數(shù)是偶數(shù)。
如何轉(zhuǎn)換逆序數(shù)奇偶性
具體實(shí)現(xiàn)應(yīng)該很簡(jiǎn)單，不多說(shuō)了，就說(shuō)一點(diǎn)。如果想更改一個(gè)數(shù)字序列的逆序數(shù)的奇偶性，只需要調(diào)換一對(duì)逆序數(shù)的位置即可。
最后
可能是CS106A課程上的一句話(huà)，并不是原文：
程序員要在不理解內(nèi)在實(shí)現(xiàn)邏輯的情況下，也能順暢地使用別人的成果。
不理解沒(méi)關(guān)系，會(huì)用就行。
參考文檔：
