【VBA】迷路を解く

VBA

VBAで迷路を解いてみよう!

今回はPythonで習ったアルゴリズムをVBAに使用して迷路を解いてみたいと思います。

迷路ってどうやって解くの?

数年前の話ですが、転職するときにプログラミングの試験がありました。
そのときに出題された問題の中で「平面上の迷路のスタートからゴールまでの経路を
表示してください」という問題がありました。

アルゴリズムを使用すれば解ける問題だったのですが
当時のわたしはアルゴリズムについて知らなかったので
問題に全く歯が立ちませんでした。

ここ1~2年でPythonでアルゴリズムを勉強する機会に恵まれ
とあるアルゴリズムを使用すると簡単に迷路を解けることが分かりました。

幅優先探索を使うと迷路を解ける

アルゴリズムの中で幅優先探索というものがあります。

幅優先探索(はばゆうせんたんさく、英: breadth first search)はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。
出典:Wikipedia 幅優先探索

スタート地点から、隣り合う地点をどんどん検索していき
最終的にゴールを見つけるようなイメージです。

幅優先探索を迷路問題に適用すると、簡単に迷路を解くことができたので
そのスゴさにびっくりしました。

キュー(Queue)がない・・・

幅優先探索ではキュー(Queue)というデータ構造を使用します。
Pythonだとdequeがあるのですが、VBAにはキューがありません。

VBAのクラスモジュールの練習のため、以前キューをクラスとして実装しました。
こちらのキュークラスを使用して、迷路を解いてみます。

【VBA】キューを実装する
VBAにデータ構造のキューがないので クラスモジュールを使用してキューを実装してみます。

 

迷路をVBAで解いてみる

Mazeという名前のシートを作成し
セルに文字入力したものを迷路とみなします。

 

シート上の各文字の意味は以下になります。

S スタート位置です
G ゴール位置です
空白 通ることができます
# 壁なので通ることができません

 

幅優先探索で迷路を解くコードは以下になります。

 

キュークラスをクラスモジュールに貼り付けます。

【VBA】キューを実装する
VBAにデータ構造のキューがないので クラスモジュールを使用してキューを実装してみます。

 

最終行と最終列を取得するために
getMaxRowとgetMaxColを使用してます。

【VBA】最終行・最終列を取得する
for文などで1行目から最終行、または1列目から最終列まで 連続して処理を行いたいときがあります。 この記事では最終行と最終列を取得するVBAのサンプルコードをご紹介します。

 

現在できること

  • 長方形、正方形の迷路を解くことができる
  • スタートからゴールまでの正解の経路を算出する
  • ゴールできない場合は「ゴールできません」と表示する

 

コードを動かしてみる

下記のような9×9の迷路をシートに入力してみます。
「迷路を解く」ボタンを押すとsolveMazeサブプロシージャを実行します。

 

ボタンを押して迷路を解いてみます。
ゴールできる場合は、「ゴールできます」とメッセージボックスが表示されます。

 

そして、スタートからゴールまでの経路を緑色で表示します。

 

ゴールに到達できない迷路を用意します。

 

ボタンを押してプログラムを動かすとゴールに到達できないので
「ゴールできません」とメッセージボックスに表示されます。

迷路の自動生成

2018/8/9追記

迷路を自動で生成する記事を書きました。

【VBA】穴掘り法で迷路を自動生成
迷路を自動で生成してみる 以前、Excelのシートに入力した文字を迷路に見立てて 幅優先探索で迷路を解くプログラムをVBAで作成しました。

コメント