記事一覧

一筆書きパズルの探索アルゴリズムの解説

 

  
目次     



  

一筆書きパズル Fill について

ハロー、みなさん。エジソンです。

最近、一筆書きパズル Fill というゲームで遊んでいます。

前回、以下のような記事を書きました。

今回はアルゴリズムの解説編です。

解説範囲

一筆書きパズルの解答アプリは、大きく分けると二つのプログラムで構成されています。

一つ目は、一筆書きパズルの解答を導くための核となるアルゴリズムを表現したプログラム。
二つ目は、一つ目のアルゴリズムの、ステップごとの動きを投影したアニメーションプログラム。

本記事では、この一つ目のアルゴリズムについて説明していきます。



パズルの探索アルゴリズム

まず、最初に一筆書きパズルのルールについて、整理します。
端的に言うと、一筆書きで全ての地面を通過すれば、クリアなゲームです。

これでは、大雑把すぎるので、もう少し細かくルールを定義していきます。

  • パズルのフィールドは、2×2のマス目で構成
  • マス目には壁と地面の二種類あり
  • 隣接されている地面と地面の間は自由に移動可能
  • 移動は上下左右の4方向で斜め移動は不可
  • ゲーム開始時のマス目の位置が予め決まっている(これを初期位置とする)
  • 初期位置は必ず地面となる
  • 一度移動した場所は通れない
  • 全ての地面を通過したらゲームクリア

ルールから、下図のようなアルゴリズムを考えてみました。

fill-answer_algo1.pngfill-answer_algo2.png

fill-answer_algo3.png 

fill-answer_algo4.png 

fill-answer_algo5.png 

上図で書いたアルゴリズムをプログラムにすると、2×2のマス目はMapクラス、一マスの移動はMoveクラスと言った具合に名付けました。

プログラムの細部に関しては、特に説明はしません。クラスの名前やメソッドの名前から何をしているかは分かる程度には汚くないはずですので、興味のある方はご覧ください。

ソース

関連記事

このエントリーをはてなブックマークに追加

コメント

コメントの投稿

非公開コメント

プロフィール

EZOLABブログへようこそ。
EZOLABは、札幌のソフトウェア会社です。

http://ezolab.co.jp

ezolab