ヘビとはしご、最後の四角に着陸するかどうか確認してください

Question

私はリンクリストを使って、蛇とはしごのゲームをPythonで実装しています。ノードは次の四角にリンクし、最後の四角は最初の四角にリンクします。 （円形）。私もヘビとはしごを持っているので、各ノードにはdestinationというパラメータがあります。どこにもリンクされていなければNone、それ以外の場合はaddress of the other nodeが含まれています。

私のゲームに関して特別なことは、私にfixed rollがあるということです。私の固定ロールが4なら、私はalways move 4 nodesになります。私が着陸しているノードがヘビやラダーに接続されているなら、そこに行くでしょう。

私は4番目の正方形、または私のロールがある正方形で始まります。

最後の広場に着陸するかどうかを確認する方法が必要です。

は16個の正方形、と私は第二広場で始まり2のロールを考えてみましょう。しかし、はしごがあるので、私は第11四角に移動します。今は2つのノードを移動するたびに。 2ターン後、私は黄色の広場に移動します。それから私が再び動くとき、私は最終的な正方形に移動し、正方形1に戻ってきます（勝つために最終的な正方形に上陸しなければなりません）。しかし、私は2つを回転させ続けると、決して最後の正方形に着くことはないことに気づき、これを検出する方法が必要です。

私はコードは必要ありませんが、最終的な正方形に着陸しないかどうかをどのように検出することができるかを示唆しています。ありがとうございます

Answer 1

あなたの問題は、四角いトラバーサルでサイクルを見つけるという問題になります。 全体的な考え方は次のようになります。「最終的な広場に達することなく同じノードを2回以上訪問した場合、私は決して到達しません。

これは、訪問したメンバーを正方形のクラスに含めて、前に訪問した正方形に到着したかどうかを確認するなどして実装できます。その場合、トラバーサルを止めることができます。

Answer 2

移動を表すグラフで到達可能性分析を行うことができます。ここでは、位置から複数の可能な動きを持っている場合は、変更の検出はもう少し複雑になり

nodes = list(range(16)) 
roll = list(range(1,4)) 
A = list(range(16)) 
A[1] = 10 
A[9] = 6 
A[5] = 13 
edges = {(i,j): A[(i+j)%16] for i in nodes for j in roll} 

change = True 
start = current = 0 
states = set([start]) 
oldlen = len(states) 
while change: 
    current = edges[(current, 2)] 
    states.add(current) 
    change = (oldlen != len(states)) 
    oldlen = len(states) 

print(states) 

ことを行うコード です。