ランダムでは、例年5月にある友好祭で一人一作品を作り提出するという伝統があるらしいです。この記事では、友好祭に提出する作品として現在絶賛制作中の「8パズル」の進捗報告をかいていきます。

8パズルとは

記事の一番上の画像のように、ランダムに配置された状態から、1から8の数字が順に並べられた状態に出来るだけ少ない移動で目標状態を目指すやつです。

何を作りたいのか

Python/Unityで

最短手数とステップを求める
盤面を生成する
プレイヤーがマスを動かせるようにする
数字が揃ったら終了する
ヒントボタンが押されたら盤面を一つ、最短手数に基づいて変える（もしできたら）
文字だけじゃなくて、プレイヤーが好きな画像を設定できる（もしできたら）

ゲームを作りたい

できたこと1　最短手数とステップを求める

最短手数を求めるのに幅優先探索がいいということは聞いていたので、頑張って実装してみました。

（幅優先探索は、出発点に近い点から順に探索するアルゴリズムです。詳しいことは、Qiitaに載ってます）

実装する際に詰まったことは、実行時間の遅さです。８パズルは最長手が３１手なのですが、１５手ですら２秒位かかり、現実的なプログラムではありませんでした。これは、探したら双方向探索なる方法があるらしく、それで解決しました。

（双方向探索は、初期状態と目標状態の2つから同時に探索を始め、同じ状態になったら終了するアルゴリズムです。）参考ししたサイト

できたこと2　盤面を生成する

盤面を生成することは簡単だったのですが、それが解けるかどううかを判断するのが大変でした。Pythonだと配列の比較が簡単だったのですが、C#だと上手くいきませんでした。対応策として、SequenceEqual()を使い配列を比較しました。（Unityのコードは基本的にC#で書かないといけないのですが苦手なので、最初は好きな言語であるPythonで書きました）

できたこと3　マスを動かす

ここから、C#（Unity）で作ることに飽きてきたので、Pygameに方針転換しました。マスのリストを更新し忘れたり、画面外にマスが動いたり、想定している場所に動かなかったりと大変でした。最終的には、下のように書けました。

                if event.key == K_RIGHT:
                    dest = (x - 1) + y * 3
                    if not dest in adjacent[space]:
                        continue
                    num_rect[start_lst[space] - 1].move_ip(-100, 0)
                    num_rect[start_lst[dest] - 1].move_ip(100, 0)
                    start_lst[dest], start_lst[space] = start_lst[space], start_lst[dest]
                    space = dest

できたこと4　ヒントを表示する

最短経路は

class State:
    def __init__( self, board, space, prev, way, trial ):
        self.board = board
        self.space = space
        self.prev = prev
        self.way = way
        self.trial = trial