摘要：寫在最前本次分享一下通過廣度優先搜索解決八數碼問題并展示其最短路徑的動畫效果。一個排列中逆序的總數就稱為這個排列的逆序數。如果起始狀態與結束狀態的逆序數的奇偶性相同，則說明狀態可達，反之亦然。

本次分享一下通過廣度優先搜索解決八數碼問題并展示其最短路徑的動畫效果。

歡迎關注我的博客，不定期更新中——

該效果為從[[2, 6, 3],[4, 8, 0],[7, 1, 5]] ==> [[[1, 2, 3],[4, 5, 6],[7, 8, 0]]]的效果展示

源碼地址

配置方式如下：

var option = {
    startNode: [
        [2, 6, 3],
        [4, 8, 0],
        [7, 1, 5]
    ],
    endNode: [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 0]
    ],
    animateTime: "300" //每次交換數字所需要的動畫時間
}
var eightPuzzles = new EightPuzzles(option)

百度一下可以百度出來很多介紹，在此簡單說明一下八數碼問題所要解決的東西是什么，即將一幅圖分成3*3的格子其中八個是圖一個空白，俗稱拼圖游戲=。=，我們需要求解的就是從一個散亂的狀態到恢復原狀最少需要多少步，以及每步怎么走。

我們可以抽象為現有數字0-8在九宮格中，0可以和其他數字交換。同時有一個開始狀態和結束狀態，現在需要求解出從初始到結束所需要的步數與過程。

網上有很多算法可以解決八數碼問題，本次我們采用最容易理解也是最簡單的廣度優先搜索（BFS），雖然是無序搜索并且浪費效率，不過我們還是先解決問題要緊，優化的方式大家可以接著百（谷）度（歌）一下。比如A*之類的，因為作者也不太會（逃。

現在我們已知廣搜的相關概念，那么如何結合到八數碼問題中呢？

首先我們需要將八數碼中即0-8這九個數的每一種組合當做一種狀態，那么按照排列組合定理我們可以求出八數碼可能存在的狀態數：9！即362880種排列組合。

對八數碼的每種狀態轉換為代碼中的表達方式，在此作者使用的是通過二維數組的形式，在文章的開頭的配置方式中就可以看到初始與最終狀態的二維數組表示。

為什么選擇二維數組？因為對于0的移動限定是有一定空間邊界的，比如0如果在第二行的最右邊，那么0只能進行左上下三種移動方式。通過二維數組的兩種下標可以很方便的來判斷下一個狀態的可選方向。

將每種狀態轉化為二維數組后，就可以配合廣搜來進行遍歷。初始狀態可以設定為廣搜中圖的第一層，由初始狀態通過判斷0的移動方向可以得到不大于4中狀態的子節點，同時需要維護一個對象來記錄每個子節點的父節點是誰以此來反推出動畫的運動軌跡及一個對象來負責判斷當前子節點先前是否已出現過，出現過則無需再壓入隊。至此反復求出節點的子節點并無重復的壓入隊。

在遍歷狀態的過程中，可以將二維數組轉化為數字或字符串，如123456780。在變為一維數組后便可以直接判斷該狀態是否等于最終狀態，因為從數組變為了字符串或數字的基本類型就可以直接比較是否相等。如果相等那么從該節點一步步反推父節點至起始節點，得到動畫路徑。

在頁面中通過動畫路徑生成動畫。

當你明白了思想之后，我們將其轉化為代碼思路既可以表示為如下步驟：

初始節點壓入隊。

初始節點狀態計入哈希表中。

出隊，訪問節點。

創建節點的子結點，檢查是否與結束狀態相同。若是，搜索結束，若否，檢查哈希表是否存在此狀態。若已有此狀態，跳過，若無，把此結點壓入隊。

重復3，4步驟，即可得解。

根據目標狀態結點回溯其父節點，可以得到完整的路徑。

通過路徑生成動畫

看起來一切都很美好是不是？但是我們仍然忽略了一個問題，很關鍵。

如果真的像拼圖一樣，從一個已知狀態打散到另一個狀態，那么肯定是可以復原的。但是我們現在的配置策略是任意的，從而我們需要判斷起始狀態是否可以達到結束狀態。判斷方式是通過起始狀態和結束狀態的逆序數是否同奇偶來判斷。

逆序數：在一個排列中，如果一對數的前后位置與大小順序相反，即前面的數大于后面的數，那么它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。一個排列中所有逆序總數叫做這個排列的逆序數。

如果起始狀態與結束狀態的逆序數的奇偶性相同，則說明狀態可達，反之亦然。至于為什么，作者嘗試通過簡單的例子來試圖說明并推廣到整個結論：

//起始狀態為[[1,2,3],[4,5,6],[7,8,0]]
//可以看做字符串123456780
//結束狀態為[[1,2,3],[4,5,6],[7,0,8]]
//可以看做字符串123456708

這個變換只需要一步，即0向左與8進行交換。那么對于逆序數而言，0所在的位置是無關緊要的，因為它比誰都小，不會導致位置變化逆序數改變。所以0的橫向移動不會改變逆序數的奇偶性。

//起始狀態為[[1,2,3],[4,5,6],[7,8,0]]
//可以看做字符串123456780
//結束狀態為[[1,2,3],[4,5,0],[7,8,6]]
//可以看做字符串123450786

這個變換同樣只需要一步，即0向上與6進行交換。我們已知0的位置不會影響逆序數的值。那么現在我們只需要關注6的變化。6從第6位置變為第9位置，導致7與8所在位置之前的逆序數量出現了變化。7、8都比6大，則整體逆序數量會減少2，但是逆序數-2仍然保持了奇偶性。與此同時我們可以知道，當0縱向移動的時候，中間的兩個數（當前例子7、8的位置）只會有三種情況。要不都比被交換數大（比如7、8比6大）要不一個大一個小，要不都小。如果一大一小，則逆序數仍會保持不變，因為總量上會是+1-1；都小的話則逆序數會+2，奇偶性同樣不受到影響。故我們可以認為，0的橫向與縱向移動并不會改變逆序數的奇偶性。從而我們可以在一開始通過兩個狀態的逆序數的奇偶性來判斷是否可達。

EightPuzzles.prototype.isCanMoveToEnd = function(startNode, endNode) {
    startNode = startNode.toString().split(",")
    endNode = endNode.toString().split(",")
    if(this.calParity(startNode) === this.calParity(endNode)) {
        return true 
    } else {
        return false
    }
}
EightPuzzles.prototype.calParity = function(node) {
    var num = 0
    console.log(node)
    node.forEach(function(item, index) {
        for(var i = 0; i < index; i++) {
            if(node[i] != 0) {
                if (node[i] < item) {
                    num++
                } 
            }
        }
    })
    if(num % 2) {
        return 1
    } else {
        return 0
    }
}

EightPuzzles.prototype.solveEightPuzzles = function() {
    if(this.isCanMoveToEnd(this.startNode, this.endNode)) {
        var _ = this
        this.queue.push(this.startNode)
        this.hash[this.startNodeStr] = this.startNode
        while(!this.isFind) { 
            var currentNode = this.queue.shift(),
                currentNodeStr = currentNode.toString().split(",").join("") //二維數組變為字符串
            if(_.endNodeStr === currentNodeStr) { //找到結束狀態
                var path = []; // 用于保存路徑
                var pathLength = 0
                var resultPath = []
                for (var v = _.endNodeStr; v != _.startNodeStr; v = _.prevVertx[v]) {
                    path.push(_.hash[v]) // 頂點添加進路徑
                }
                path.push(_.hash[_.startNodeStr])
                pathLength = path.length
                for(var i = 0; i < pathLength; i++) {
                    resultPath.push(path.pop())
                }
                setTimeout(function(){
                    _.showDomMove(resultPath)
                }, 500)
                _.isFind = true
                return
            }
            result = this.getChildNodes(currentNode) //獲得節點子節點
            result.forEach(function (item, i) {
                var itemStr = item.toString().split(",").join("")
                if (!_.hash[itemStr]) { //判斷是否已存在該節點
                    _.queue.push(item)
                    _.hash[itemStr] = item
                    _.prevVertx[itemStr] = currentNodeStr //記錄節點的父節點
                }
                
            })
        }
    } else {
        console.log("無法進行變換得到結果")
    }
    
}

EightPuzzles.prototype.calDom = function(node) { //根據當前狀態渲染各數字位置
    node.forEach(function(item, index) {
        item.forEach(function(obj, i) {
            $("#" + obj).css({left: i * (100+2), top: index* (100 + 2)})
        })
    })
}
EightPuzzles.prototype.showDomMove = function(path) {
    var _ = this
    path.forEach(function(item, index) { //每次狀態改變調用一次渲染函數
        setTimeout(function(node) {
            this.calDom(node)
        }.bind(_, item), index * _.timer)
    })
}

JS 中的廣度與深度優先遍歷

八數碼問題判定是否解的證明

慣例po作者的博客，不定時更新中——

有問題歡迎在issues下交流。