解迷宮的一個數學方法

這篇文章翻譯自這裏，原作者是我，想可能早有數學家提出，只不過是了一了自己的心願而已。
要解迷宮就必須借助矩陣，而且一定是具備可解的條件，就是迷宮可清清楚楚地拆開成由外而內的一層層，每一層之間是獨立(換句話說，如何改動這一層也影響不了另一層的空間分佈)，而用可通達性矩陣(accessibility matrix)就可以完整地描述這一層的空間分佈，而每一層的空間分佈指的是它到底被牆璧分成了幾多個不可以不經另一層才抵達的區間，簡單點說，如果第一層被分成了三區間，玩家處身於其中一個區間中是不可能在同一層穿牆而到另一個區間，其他遊戲的物件也需循守同樣的規則，這些區間亦是獨立的，發生在一區間的事不可以影響的另一區間。另外，我們亦假設玩家必須由一層進入最近的一層，不可以有隊道由第一層跳到第三層。
可通達性矩陣(accessibility matrix)就是整個解迷宮方式的靈魂，它借用了圖論的慨念，把一層中各區間能否去到另一層的各區間用1和0去表達，例如第一層有3個區間而第二層有5個區間，則我們可以用一3*5的可通達性矩陣來表達雙方的互通程度;又或者用一幅三點到五點的可通達性圖來表達。我們可以如是者把由第一層到第二層，第二層到第三層....如此類推的可通達性圖或n幅可通達性矩陣來表達。如此我們便完整地述描整個迷宮的可通達性，要解迷﹐即利用可通達性圖找出一條在入口所在的層及區間到出口所在的層及區間的路徑，而通常迷宮都是把入口定在最外層的一個區間而出口定在最外層的另一個區間，另外亦可利用n幅可通達性矩陣作運算而求指定的解，用人算來可能會很麻煩，但用電腦去解則一點難度也沒有。

Method to solve a maze

Is there a sure-fire way to solve a maze? Is it really just luck but no skills and intelligences involved?

I approach this question when I was in sixth year of my Highschool. What give me a hint is the Map theory. In map theory you can always represent the points and edges by accessibility matrix, then by analyzing those matrix, you can deduce the various properties of the map. If two maps has identical accessibility matrix, then they are equivalents.

So I analyze the maze problem from this standpoint. I notice that any maze could be partitioned as layers stacked together from inner to outer, which outermost has the biggest length and the innermost has shortest length. Then in each layer, we see there are walls further partition each layers as independent areas. The goal of solving a mazing could reformulate as how to get from a partition within a layer to another partition in another layer. Then it begin to look like a problem within the domain of knowledge of map theory, since it is again about accessibility from one area to another area. How do we know about accessibility in a maze?

Simple, after we partition the layers of the maze, we can represent each area in each layer as a point in the map. So all the points in the same layer share the same level in the map. What make a maze a maze is the differential accessibility of each partitions to the partitions in the next layer. Thus we can again represent the one step inner layer of maze as another set of points in a map. If a partition A in outer layer could access the partition B in the inner layer, then we draw a line connecting them two. Repeat the process and we will have a map that represent the partitions of layers as point, and the path connecting them as lines. Continue the process until we have all partitions and pathways between them represented.

Now we have a map. Then we can write out the Accessibility matrix just like in Map Theory. Now we can apply the knowledge of the map theory to solve a maze. Usually, the objective of solving a maze is started at one partition in the outermost layer to another partition on the other side of the map in the outermost layer through various pathways. We remember from the map theory that the n-th power of the Accessibility martix denote how many ways we could arrive from a point to another point in n-step without turning back. If there exists a pathway from starting point to exit within n-th step, the value of the entry in column and row of respective partitions would be greater than 1. So what did is just to repeat the multiplication of the Accessibility matrix until we see the value of entry in the desired partitions of layers is greater than zero.
We could reconstruct other mazes from the original by switching the orders of layers without changing the pathways if it is possible(i.e. The relationship between the partitions remain the same), since the innermost layer has smallest number of partitions. However we alter the maze, we just need to alter the columns and rows of the changed layer in the Accessibility matrix. If we have done the multiplication, we only need to alter the columns and rows of the changed layer in the Accessibility matrix.(In other form, to do a linear transformation of the matrix.)
A boarder set of Maze questions is not just about whether there exists a pathway from one particular partition in one layer to another particular partition in another layer. It is given a random partition in a random layer in the maze, can we get to another random partition in another random layer within n-th step?
By using this tool, we can generate maze and test the various parameters of its accessibility, and we can also evolve new maze with the parameter we demanded using evolutionary computing(without the necessity of designing the maze ourselves.) Thus we can play a Pac-Man Game without any repetition of the maze. How boring it is to play with the same maze for over 300 rounds as in old days of Apple?