だんご屋のひまつぶしというパズルがあるそうです。
三本の串に刺さった、ある状態の赤、白、緑の団子を別の状態に移します。
このパズルを完全に解析したという記事がありました。
難しくて理解できなかったので、自分でも考えてみることにしました。
Pythonで与えられた状態から状態への最短手順を返します。
考え方
はじめは、最初の状態から最後の状態になるまで、ひたすらランダムに団子を動かすということをやっていました。一応、答えは出ますが、時間がかかりますし、最短ではありません。
この手の問題はダイクストラ法というのを使うらしいのですが、全く理解できなかったので自分で考えました。
最初の状態から動かすのは6パターンあります。団子は一本に三個までなので動かせない場合があり、そのパターンは無視します。動かした後の状態を全て保存します。
次の状態から動かすのは6通りあります。同様に動かせないパターンを無視し、また過去にあった状態も無視します。動かした後の状態を全て保存します。
これを最後の状態になるまで繰り返します。
コード
上の記事で最短手順が長いと紹介されていた問題を解いてみました。
赤白緑 緑白赤 なし → なし 赤緑緑 白赤白
def main():
state_from = [[1, 2, 3], [3, 2, 1], []]
state_to = [[], [1, 3, 3], [2, 1, 2]]
print("問題", state_from, ">>>", state_to)
result = solve_dango(state_from, state_to)
print("正解", result)
print("️手順再現")
print(state_from, ">>>", state_to)
show_steps(state_from, result)
def solve_dango(state_from, state_to):
moves = [[0, 1], [0, 2], [1, 2], [1, 0], [2, 0], [2, 1]]
steps = {}
state_list_done = []
state = state_from
state_list_done.append(state)
state_list = [state]
steps[str(state)] = []
for i in range(100):
state_list_new = []
for state in state_list:
if len(steps[str(state)]) < i:
continue
for step in moves:
state_next = move_dango(state, step)
if state_next == []:
continue
if not state_next in state_list_done:
steps[str(state_next)] = steps[str(state)][:]
steps[str(state_next)].append(step)
state_list_new.append(state_next)
else:
pass
if state_next == state_to:
return steps[str(state_next)]
state_list_done += state_list_new
state_list = state_list_new
def move_dango(state_moto, step):
state = copy.deepcopy(state_moto)
if len(state[step[0]]) == 0 or len(state[step[1]]) == 3:
return []
ball = state[step[0]].pop(0)
state[step[1]].insert(0, ball)
return state
def show_steps(state_from, steps):
state = copy.deepcopy(state_from)
print("初期状態", state)
for step in steps:
print("移動", step)
state = move_dango(state, step)
print("状態", state)
print("回数", len(steps))
if __name__ == "__main__":
main()
実行結果
問題 [[1, 2, 3], [3, 2, 1], []] >>> [[], [1, 3, 3], [2, 1, 2]]
正解 [[1, 2], [1, 2], [0, 1], [2, 1], [2, 0], [1, 2], [1, 2], [1, 2], [0, 1], [0, 1], [0, 1], [2, 0], [1, 0], [1, 2], [0, 1], [0, 1]]
️手順再現
[[1, 2, 3], [3, 2, 1], []] >>> [[], [1, 3, 3], [2, 1, 2]]
初期状態 [[1, 2, 3], [3, 2, 1], []]
移動 [1, 2]
状態 [[1, 2, 3], [2, 1], [3]]
移動 [1, 2]
状態 [[1, 2, 3], [1], [2, 3]]
移動 [0, 1]
状態 [[2, 3], [1, 1], [2, 3]]
移動 [2, 1]
状態 [[2, 3], [2, 1, 1], [3]]
移動 [2, 0]
状態 [[3, 2, 3], [2, 1, 1], []]
移動 [1, 2]
状態 [[3, 2, 3], [1, 1], [2]]
移動 [1, 2]
状態 [[3, 2, 3], [1], [1, 2]]
移動 [1, 2]
状態 [[3, 2, 3], [], [1, 1, 2]]
移動 [0, 1]
状態 [[2, 3], [3], [1, 1, 2]]
移動 [0, 1]
状態 [[3], [2, 3], [1, 1, 2]]
移動 [0, 1]
状態 [[], [3, 2, 3], [1, 1, 2]]
移動 [2, 0]
状態 [[1], [3, 2, 3], [1, 2]]
移動 [1, 0]
状態 [[3, 1], [2, 3], [1, 2]]
移動 [1, 2]
状態 [[3, 1], [3], [2, 1, 2]]
移動 [0, 1]
状態 [[1], [3, 3], [2, 1, 2]]
移動 [0, 1]
状態 [[], [1, 3, 3], [2, 1, 2]]
回数 16
答え合わせ
上の記事では16手とあったので正解が出せました。
コメント