華容道\\開窗等經(jīng)典智力問題的求解算法研究

摘 要:本文在前人對華容道、孔明棋、九宮拼圖問題求解算法研究的基礎(chǔ)上，針對這些經(jīng)典智力問題的特點(diǎn)，利用廣度優(yōu)先和深度優(yōu)先搜索思路設(shè)計(jì)算法，并對算法進(jìn)行搜索減枝優(yōu)化，設(shè)計(jì)出了一個相對優(yōu)化的算法。對于開窗問題，本文通過對該問題規(guī)則的分析，設(shè)計(jì)出了一種效率較高的求解算法。通過使用C#語言編寫程序?qū)崿F(xiàn)算法以及軟件的求解功能，經(jīng)測試與運(yùn)行證實(shí)了本文求解算法的正確性和有效性，并給出了算法的核心C#代碼。

關(guān)鍵詞:搜索算法華容道孔明棋開窗游戲九宮圖程序設(shè)計(jì)

中圖分類號:TP312文獻(xiàn)標(biāo)識碼:A文章編號:1674-098X(2011)09(b)-0002-05

Researching the algorithm of solving classic mental problems of RoomEscape，fenestration and so on

Cui Yong-xiong1，Zhang Cong2，Pang Xu3

(University of Science and Technology Beijing，mathematical and physical college，

Dept of math，Xueyuan Road No.30 Haidian District Beijing 100083)

Abstract:Based on the predecessors' researches of solving algorithm to games，such as RoomEscape，Peg solitaire and Jiugong puzzles，according to the characteristics of the classic intelligence issues，this article，using the ideas of breadth first algorithm and depth first algorithm to design an algorithm，optimizing the algorithm by search pruning，designed a more optimizied algorithm.For fenestration problem，based on the analysis of this problem rules，this article designed a kind of high efficiency solving algorithm.By programming with c # language to realize this algorithm and the functions of this software，after testing and operating，the correctness and effectiveness of the solving algorithm in this paper are confirmed，and the core c # codes of the algorithm are given.

Key words:search algorithm;RoomEscape;Peg solitaire;fenestration game;Jiugong puzzles;program design

1 引言

隨著電子計(jì)算機(jī)的應(yīng)用逐漸普及，程序設(shè)計(jì)以及算法設(shè)計(jì)的相關(guān)技術(shù)飛速發(fā)展，大量優(yōu)秀的算法不斷涌現(xiàn)，例如:蟻群算法，遺傳算法，禁忌搜索算法等。但是大部分的算法主要用于科研及工程計(jì)算，而不被大眾所了解。為了將優(yōu)秀的算法應(yīng)用到實(shí)際當(dāng)中，展現(xiàn)算法的獨(dú)特魅力，普及算法相關(guān)知識。本文嘗試用計(jì)算機(jī)通過簡單易懂的算法和程序設(shè)計(jì)解決華容道、孔明棋、九宮圖、開窗經(jīng)典智力問題，并研究在這些經(jīng)典智力問題背后所蘊(yùn)含的數(shù)學(xué)原理。

2 經(jīng)典問題背景及概述

2.1 華容道問題背景及概述

華容道，古老的中國游戲，以其變化多端、百玩不厭的特點(diǎn)與魔方、獨(dú)立鉆石棋一起被國外智力專家并稱為“智力游戲界的三個不可思議”。它與七巧板、九連環(huán)等中國傳統(tǒng)益智玩具還有個代名詞叫作“中國的難題”。……