計算機程序設(shè)計實現(xiàn)重排九宮格問題

【摘 要】本文通過解決計算機程序設(shè)計，從而實現(xiàn)重排九宮格問題，使我們青少年達到掌握更多的計算機知識，鍛煉編程能力。

【關(guān)鍵詞】計算機；九宮格；程序

重排九宮格顧名思義就是重新排列九宮圖的意思，其玩法是在3×3方格盤上，放有1-8八個數(shù)，剩下一格為空，每一空格其周圍的數(shù)字可移至空格。先設(shè)定初始排列數(shù)字，然后開始思考如何以最少的移動次數(shù)來達到目的。這類小游戲可以鍛煉人的逆向思維能力，是青少年非常喜愛的課余活動。

目前，人們已經(jīng)邁入了網(wǎng)絡時代，計算機和互聯(lián)網(wǎng)已經(jīng)與我們的日常工作、學習和生活息息相關(guān)，我們青少年更加應該掌握更多的計算機知識，尤其學習程序設(shè)計語言可以培養(yǎng)我們運用算法來解決實際問題的能力，這種解決問題的方式是計算機所獨有的，也只有通過對計算機程序設(shè)計語言和程序設(shè)計方法的學習才有可能獲得這種解決問題的能力。使用計算機程序設(shè)計的方式解決實際問題有諸多的好處主要表現(xiàn)在：

（1）程序設(shè)計的目標是用某種計算機高級算法語言編寫程序?qū)崿F(xiàn)特定的算法的功能。程序設(shè)計要具有強烈的創(chuàng)造意識，為實現(xiàn)預想的功能要不斷地設(shè)想多種方案，同時又需要具有十分嚴謹?shù)倪壿嬐评怼Ｒ虼顺绦蛟O(shè)計是獲得創(chuàng)造性修養(yǎng)與獲得正確思維方法的極好的科目；

（2）計算機程序設(shè)計與數(shù)學是緊密相互聯(lián)系而相輔相成的，它對數(shù)學的學習有著極大的促進作用。許多數(shù)學問題必須要用計算機才能最終解決問題，反之計算機的編程常常要借助數(shù)學的思想與方法才能出色完成任務；

（3）程序設(shè)計是學習其他學科的基礎(chǔ)，不論是文科還是理科，特別是學習理科學科，計算機是一種必不可少的工具。由于在計算機方面的興趣，新泰一中的高三學生霍達通過計算機程序設(shè)計了一個有效的算法，實現(xiàn)關(guān)于九宮格的重排問題。

為了實現(xiàn)重排九宮格的問題，系統(tǒng)在算法設(shè)計上使用廣度優(yōu)先搜索算法。廣度優(yōu)先搜索算法是一種圖形搜索算法。簡單的說，廣度優(yōu)先搜索算法從根節(jié)點開始，廣度優(yōu)先搜索算法沿著樹的寬度遍歷樹的節(jié)點。

如果所有節(jié)點均被訪問，則算法中止。廣度優(yōu)先搜索的實現(xiàn)一般采用open-closed表（在搜索算法過程中其鄰居節(jié)點尚未被檢驗過的節(jié)點會被放置在一個被稱為open的容器中，而被檢驗過的節(jié)點則被放置在被稱為closed的容器中，簡稱open-closed表）。

對于九宮格重排的問題，系統(tǒng)使用廣度優(yōu)先搜索算法隊列的形式來實現(xiàn)，具體實現(xiàn)的算法步驟如下：

步驟1：把初始的狀態(tài)節(jié)點放入一個隊列；

步驟2：如果隊列為空，則問題無解，退出。否則，檢查隊尾的狀態(tài)是否是目標狀態(tài)，如果是目標狀態(tài)，轉(zhuǎn)至步驟5；

步驟3：如果不是目標狀態(tài)，擴展當前節(jié)點，并為每個子節(jié)點配置指向父節(jié)點的指針，把不是當前節(jié)點的先輩的子節(jié)點加入到隊頭；

步驟4：隊尾指針指向下一個節(jié)點，轉(zhuǎn)至步驟2；

步驟5：當前節(jié)點通過其父指針回溯到初始狀態(tài)，并為每個節(jié)點設(shè)置其移動的方向，以記錄找到的這條路徑；

步驟6：根據(jù)找到的路徑移動九宮格到達目標狀態(tài)；

系統(tǒng)使用目前最流行的Windows平臺應用程序開發(fā)環(huán)境Visual Studio實現(xiàn)，程序在找到有效路徑后，一步一步地移動到目標狀態(tài)過程中，其中最難處理的部分是如何展示移動的過程。系統(tǒng)使用了一個巧妙的方法，系統(tǒng)在運行過程中記錄下每次移動的狀態(tài)矩陣，這樣就不必移動格子，只要修改格子里的數(shù)字就可以了。

程序的初始界面如下圖1所示，程序分為開始狀態(tài)和目標狀態(tài)，開始狀態(tài)顯示的是九宮格初始狀態(tài)，目標狀態(tài)顯示的是九宮格從開始狀態(tài)最終要移動到的狀態(tài)。程序開始運行前，先調(diào)整開始狀態(tài)和目標狀態(tài)到任意位置，如圖2所示。然后點擊開始，系統(tǒng)自動從設(shè)定的開始狀態(tài)一步一步移動的設(shè)定的目標狀態(tài)，如圖3所示。

在計算機程序?qū)崿F(xiàn)九宮格重排的過程中，不難發(fā)現(xiàn)利用巧妙的算法，計算機能方便快捷得解決人腦看來復雜或耗時的問題。而設(shè)計程序的過程不僅充滿趣味與挑戰(zhàn)，更能一勞永逸得解決一些需要不斷重復思考的問題。因此，處于人生充電期的青少年，應該勇敢進入計算機的廣闊世界，鍛煉編程能力，讓計算機成為自己未來求學和工作道路上的良師益友。