作者：winnie de pooh

關(guān)鍵詞：滑動拼圖，估價函數(shù)，A*算法，逆序數(shù)，動態(tài)交互

1、前言

滑動拼圖是非常經(jīng)典的游戲，網(wǎng)絡(luò)上有各種語言實現(xiàn)的滑動拼圖程序。本程序是在mathematica當(dāng)中實現(xiàn)的滑動拼圖，在Wolfram Demostrations Project上有一個差不多的CDF項目，覺得十分地有意思，所以模仿了一下，完全沒有使用Project的代碼。

圖1  Wolfram Demostrations Project滑動拼圖

相比網(wǎng)站上的例子，本程序采用逆序數(shù)定理保證每一個初始情況都能被還原，也增加了通常模式下支持自己圖片導(dǎo)入游戲的模式，更是增加了一個挑戰(zhàn)模式，增加了A*算法尋找最優(yōu)解的函數(shù)和功能，能夠得到目前初始條件下的達(dá)到最優(yōu)解的步數(shù)。

本程序使用的是Button作為按鍵，動態(tài)功能使用Annotation實現(xiàn)，而網(wǎng)站上Project使用的是Manipulate，本程序使用的是DynamicModule，具有更快且更好自定義的特點。

圖2  本程序的界面和A*算法預(yù)測的最佳步數(shù)

本程序的挑戰(zhàn)模式的每塊拼圖都是隱藏的，在點擊下才會顯示，每次只會同時顯示一張圖片，所以增加了相應(yīng)的還原難度。

圖3  挑戰(zhàn)模式

2、滑動拼圖中的A*算法

A*算法是一種啟發(fā)式的局部貪婪算法，通過將當(dāng)前狀態(tài)下的所有后續(xù)節(jié)點與最終目標(biāo)解進(jìn)行對比，對于某個格局，通過一次移動滑塊而得到的格局，稱為其后繼格局。我們需要找到某個中間格局的所有后繼格局，即每種可能的走法所能得到的格局，并計算得到這個格局的代價。同時，為了盡快到達(dá)目標(biāo)格局，我們需要對這些后繼格局進(jìn)行評價，找出一個可能最先到達(dá)目標(biāo)格局的。

圖4  初始狀態(tài)和后續(xù)可能狀態(tài)對比

通過比較初始狀態(tài)所對應(yīng)的所有可能狀態(tài)與目標(biāo)狀態(tài)的差值，將差值最小的后續(xù)節(jié)點作為下一步節(jié)點。

   差值為33  

圖5  后續(xù)狀態(tài)與目標(biāo)狀態(tài)的差值

按照最小差值的狀態(tài)移動之后，再次生成其所對應(yīng)的可能后續(xù)狀態(tài)（不包含前一步狀態(tài)），再次計算與目標(biāo)狀態(tài)的差值，執(zhí)行下一步移動，如此循環(huán)，直到達(dá)到目標(biāo)狀態(tài)，程序結(jié)束。

3、逆序數(shù)定理

在一個排列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序。一個排列中逆序的總數(shù)就稱為這個排列的逆序數(shù)。也就是說，對于n個不同的元素，先規(guī)定各元素之間有一個標(biāo)準(zhǔn)次序（例如n個不同的自然數(shù)，可規(guī)定從小到大為標(biāo)準(zhǔn)次序），于是在這n個元素的任一排列中，當(dāng)某兩個元素的實際先后次序與標(biāo)準(zhǔn)次序不同時，就說有1個逆序。一個排列中所有逆序總數(shù)叫做這個排列的逆序數(shù)。

初始狀態(tài)的逆序數(shù)可以判斷該初始狀態(tài)能否達(dá)到目標(biāo)狀態(tài)，只有逆序數(shù)為偶數(shù)的初始狀態(tài)才能還原為目標(biāo)狀態(tài)。

最后,歡迎通過公眾號"320科技工作室"聯(lián)系我們.