マインスイーパーでの再帰処理の理解のために

１．概要

このページは、「マインスイーパー（再帰処理）」のプログラムを理解するために、簡素化した例での再帰処理を説明しています。

参考

ある定義の中で自分自身を呼び出す（使用する）ことを再帰的定義と呼びます。そのように定義された関数などでの処理を再帰処理と言います。

再帰処理はいろいろなパターンがあります。このマインスイーパーのような連鎖的な「探索」だけではなく、「階乗」や「数列の和」を求めたり、「フラクタル図形」を描いたりすることにも使われます。再帰処理についてもっと広く学びたい場合は、ネットでこれらのキーワードで検索してみてください。

２．再帰処理の基本：1次元配列での例

実際のマインスイーパーのゲームの盤面は２次元配列になりますが、最初は１次元配列で再帰処理を考えてみるとよいでしょう。

下記のプログラムは、一次元配列a内の指定した位置から右方向へ、０ではないところまで表示するプログラムです。ここでは、関数check()が再帰処理をしています。つまり、check()の関数定義文の中でcheck()を呼んでいます。

プログラム

int[] a = {0, 1, 0, 3, 0, 0, 0, 7, 8, 0};
int rc = 0;  //デバッグ＆学習用。再帰呼び出しのカウンタ。広域変数。

void setup() {
  check(4);  //引数の値を0,1,2,5,9などに変更して実行してみると良いでしょう。
}

void check(int x) {
  rc++;  //　デバッグ＆学習用
  String local_rc = str(rc);  //　デバッグ＆学習用。再帰呼び出しのカウンタ。ローカル変数。
  println("  ->Enter check(", x, ")    <"+local_rc+">");  //　デバッグ＆学習用
  if (x < 10) {
    println(a[x]);
    if (a[x] == 0) {
      check(x+1);
    }
  }
  println("  --- return  <"+local_rc+"> ---");  //デバッグ＆学習用
  return;
}

実行結果

  ->Enter check( 4 )    <1>
0
  ->Enter check( 5 )    <2>
0
  ->Enter check( 6 )    <3>
0
  ->Enter check( 7 )    <4>
7
  --- return  <4> ---
  --- return  <3> ---
  --- return  <2> ---
  --- return  <1> ---

配列aの4番目の位置から開始して右方向に0→0→0→7とチェックをしながら表示をしていき、7番目の位置で初めて0ではない値になったので、表示を終了しています。

check(x)は、一次元配列aのx番目の位置から右方向に次々と値をチェックしていきます。もしa[x]の値が0の場合、xに1を加えたx+1を引数にしてcheck()を再帰的に呼び出しています。もしa[x]の値が0以外の場合は、それ以上の再帰呼び出しはせずに、returnします。

実行結果に示すように、再帰のレベルは<1>→<2>→<3>→…とどんどん深くなって、returnによって<4>→<3>→<2>→…と戻ってきます。

再帰処理を書く時は、最後にreturnを入れるのを忘れないでください。再帰処理の場合、returnがないとしばしばスタックオーバーフロー（エラーメッセージはMaximum call stack size exceeded.など）になります。

やってみよう

setup() の中にある check(4) の引数を、4以外のいろいろな値に変えて動作を追跡してみると良いでしょう。

３．再帰処理の応用：2次元配列

（１）周囲８方向のセルのチェック

実際のマインスイーパーゲームでは、上記のような１次元配列ではなく２次元配列になります。このため、再帰でチェックしていく方向も、右方向だけではなく周囲８方向になります。

ちなみに、周囲８方向のセルをチェックするには、中心のセルを i行 j列とすると、二重のfor文（diのループ、djのループ）を用いて

for (int di = -1; di < 2; di++) {
    for (int dj = -1; dj < 2; dj++) {
      ...
        *//ここで2次元配列の[i+di]行[j+dj]列の中身をチェック*
    }
}

とすると簡潔にまとまります。具体例として、1行1列（[1][1]、i=1、j=1）をクリックして開いた場合、チェックする周辺の隣接セルは下記のようになります。（①～⑨はチェックする順番です）

di	dj	チェックするセル [ i+di ][ j+dj ]	方向	具体例
-1	-1	[ 1+(-1) ] [ 1+(-1) ]	①左上	[ 0 ] [ 0 ]
-1	0	[ 1+(-1) ] [ 1+0 ]	② 上	[ 0 ] [ 1 ]
-1	1	[ 1+(-1)1 ] [ 1+1 ]	③右上	[ 0 ] [ 2 ]
0	-1	[ 1+0 ] [ 1+(-1) ]	④ 左	[ 1 ] [ 0 ]
0	0	[ 1+0 ] [ 1+0 ]	⑤中央	[ 1] [ 1 ]
0	1	[ 1+0 ] [ 1+1 ]	⑥ 右	[ 1] [ 2 ]
1	-1	[ 1+1 ] [ 1+(-1) ]	⑦左下	[ 2] [ 0 ]
1	0	[ 1+1 ] [ 1+0 ]	⑧ 下	[ 2] [ 1 ]
1	1	[ 1+1 ] [ 1+1 ]	⑨右下	[ 2] [ 2 ]

[ i+di ] [ j+dj ]

（２）すでにチェックしたセルはチェックしない

８方向を再帰的にチェックしていくと、周囲のセルで重複するものが出てくるので、すでにチェックしたセルを何度もチェックして堂々巡りしてしまう場合があります。この場合、スタックオーバーフローエラーになったりします。これを防ぐために、セルの状態（既にチェックしたかどうか）を表す配列（下記プログラムではcellState[][]）を用意して、チェック済みのところを記録し、そこはもうチェックしないようにします。

（３）応用版のプログラム

これらを考慮したプログラムは、以下のようになります。

プログラム

int[][] cellValue = {  //セルの中身。-1：爆弾  0：空  その他：隣接する爆弾数
  {-1, 1, 0, 1, 1},
  {1, 1, 0, 1, -1},
  {1, 1, 0, 1, 1},
  {-1, 2, 1, 0, 0},
  {2, -1, 1, 0, 0}
};
int[][] cellState;  //　セルの状態。0:未オープン   1:オープン
int rc=0;  //　デバッグ＆学習用

void setup() {
  size(500, 500);
  cellState = new int[5][5];
  for (int i = 0; i<5; i++) {
    for (int j = 0; j<5; j++) {
      cellState[i][j]=0;  //　最初は、全て未オープン
    }
  }
}

void draw() {
  background(255);
  drawCell();    //　盤面の描画
}

// 盤面の描画
void drawCell() {
  fill(200);
  for (int i = 0; i<5; i++) {
    for (int j = 0; j<5; j++) {
      if (cellState[i][j]==0) {  //オープンされていないセル
        fill(200);
        rect(j*100, i*100, 100, 100);
      } else if (cellState[i][j]==1) {    //オープンされたセル
        fill(255);
        rect(j*100, i*100, 100, 100);
        if (cellValue[i][j] != 0) {  //中身が0の場合は、数字を表示しない
          textSize(50);
          fill(0);
          text(cellValue[i][j], j*100+35, i*100+70);
        }
      }
    }
  }
}

//マウスクリック処理
void mousePressed() {
  int mj;
  int mi;
  mj = int(mouseX/100);  //x座標から列番号を算出する
  mi = int(mouseY/100);  //y座標から行番号を算出する
  println("★clicked[", mi, "][", mj, "]");  //　デバッグ＆学習用
  if ((mi >= 0) && (mi < 5) && (mj >= 0) && (mj < 5)) {   //盤面内であり、
    if (cellState[mi][mj] == 0) {  //そのセルがオープンされていない状態（==0）の場合のみ、以下を行う
      cellState[mi][mj] = 1;
      //もし中身が0（空）だったら、その周辺セルも開ける必要があるので、checkAroundを実行する
      if (cellValue[mi][mj]==0) {
        checkAround(mi, mj);
      }
    }
  }
}

//周囲チェック処理（再帰処理）
void checkAround(int pi, int pj) {
  rc++;  //　デバッグ＆学習用
  String local_rc = str(rc);  //　デバッグ＆学習用
  println("->Enter checkAround(", pi, ",", pj, ")    <"+local_rc+">");  //　デバッグ＆学習用
  for (int di = -1; di < 2; di++) {
    for (int dj = -1; dj < 2; dj++) {
      println(" check [", pi+di, "][", pj+dj, "]    <"+local_rc+">");  //　デバッグ＆学習用
      // 盤面外はチェックできないので次の方向の確認に移る。
      if ((pi + di < 0) || (pi + di >= 5) || (pj + dj < 0) || (pj + dj >= 5)) {
        continue;
      }
      // オープンされていないセル(==0)の場合のみ、以下の処理をする
      if (cellState[pi+di][pj+dj] == 0) {
        cellState[pi+di][pj+dj] = 1;
        //もし中身が0（空）だったら、その隣接セルも開ける必要があるので、checkAroundを実行する
        if (cellValue[pi+di][pj+dj]==0) {
          println("   == Opened & 0     <"+local_rc+">");  //　デバッグ＆学習用
          checkAround(pi+di, pj+dj);
        }
      }
    }
  }
  println("------ return  <"+local_rc+"> ------");  //　デバッグ＆学習用
  return;  //再帰の終了条件は、周辺セル全てのチェックの完了（di,djループ完了）
}

（４）再帰関数checkAround()の解説

checkAround()は周囲セルの値をチェックする関数で、再帰呼び出しをしています。ここで、二重のfor文で周囲のセルをチェックしていきますが、各セルのチェックにおいて、以下のようにしています。

そのセルが盤面外であったらチェックはせず、次の周囲セルのチェックに移ります。
そのセルがまだオープンされていなければ（cellState[…][…]==0）、オープンしてから（cellState[…][…]=1）、そのセルの中身をチェックします。（すでにオープンしているセルならばこれらの処理はしません。すぐに次の周囲セルのチェックに移ります。）
もしそのセルの中身が0であったら、今度はそのセルを中心とした周囲セルをチェックするために、そのセルを引数として再帰呼び出しをします。

そして、二重のfor文で9セル（周囲８方向の隣接セルと中央の自分自身）をチェックし終えたらreturnします。

やってみよう

配列cellValueの中身をいろいろと変えてみて、動作を確かめてみてください。