見出し画像

マインスイーパーを作って腕試し

jig.jp engineers

はじめに

こんにちは、アプリ開発を担当しているHです。社内の雑談でふと、マインスイーパーを何分で作れるかでプログラミング力がわかるらしいという話題になりました。社員の何人かが、それぞれ得意な言語で実装に挑戦してみたのでその紹介です。

マインスイーパーの要件

マインスイーパーはGoogle検索からプレイしてみることができます。ルールについてはご存じの方が多いと思いますので説明を省略させていただきます。実装を簡単にするため、GUI/CUIを問わない・目印として設置できる旗は実装しなくても良いとして簡略化しています。実装が必要な要件を列挙すると以下のようになります。

  • マスを選択するたびに、更新されたマス目が表示される

  • はじめに選択したマスは地雷にならない

  • 開いたマスには8近傍の地雷の個数が表示される

  • 選択したマスの8近傍に地雷が0個であれば、1個以上のマスまで自動で開く

  • 地雷があるマスを選択したら、ゲームオーバーとしてゲームが終了する

  • 地雷があるマス以外を全て開けたら、ゲームクリアとしてゲームが終了する

以上のように、入力があるたびにフィールド更新していく必要があります。そのため、フィールドをどのようなデータ構造で持っておくかによって実装方法が変わってきます。

実装の紹介

私含め3名の実装を抜粋して紹介します。使用言語はPython, C, Flutter/Dartになります。開発速度重視で実装したコードなので読みにくい部分があると思いますがご了承ください。

デモ

コードを実行するとそれぞれ次のように表示されます。

Python実装

開けるマスの座標を入力して選択するCUIになっています。

Python実装

C実装

こちらも開けるマスの座標を入力して選択するCUIになっています。
フラグを立てる機能も実装されています。

C実装

Flutter実装

開けるマスをクリックして選択するGUIになっています。ヘッダに地雷の数と空いていないマスの残り個数が表示されています。DartPadにあるので動かしてみてください。

Flutter実装

フィールド情報の持ち方

各マスについて地雷があるかどうか、8近傍の地雷の個数、空いているかどうかが分かる必要があります。全員がフィールドとして二次元配列を持つ実装にしましたがマスの情報の持ち方はそれぞれ違いました。

Python実装では各セルをCellTypeとして、地雷があるかどうか・空いているかどうかのフラグと8近傍の地雷の個数を数字として持っています。そのセル情報を二次元配列1つで持っています。

# Python
CellType = TypedDict("CellType", {
    "is_open": bool,
    "is_mine": bool,
    "quantity": Optional[int]
})

BoardType = List[List[CellType]]

C実装では二次元配列2つに分けています。boardに8近傍の地雷の個数・空いているかどうかを持ち、maskで地雷があるかどうかが分かるようになっています。

/* C */
int board[size][size];
int bombs[size * size - 1];
int mask[size][size];

Dart実装では各マスに数字と座標を持っています。数字は-1と0を空いているかどうか、0から8を8近傍の地雷の個数、10を地雷かどうかとしています。そのセル情報をPython実装と同様に二次元配列に持っています。

// Dart
const _bomb = 10;
const _init = -1;

final field = useState(List.generate(
  height,
  (y) => List.generate(width, (x) => Mine(_init, x, y)),
));

空いているマスの探索

Python, C, Dartの順に探索の実装を抜粋したものになります。フィールドのデータ構造がそれぞれ異なるため差異がありますが、全員が再帰的に探索する手法で実装しています。

# Python
def open(x: int, y: int, board: BoardType, is_click: bool) -> BoardType:
    
    if board[y][x]["is_open"]:
        return board
    
    if board[y][x]["is_mine"]:
        return None
    
    cnt = count(x, y, board)
    
    board[y][x]["is_open"] = True
    board[y][x]["quantity"] = cnt

    if cnt == 0:
        for i in range(-1, 2):
            for j in range(-1, 2):
                if i == 0 and j == 0:
                    continue
                if y + i < 0 or y + i == len(board[0]):
                    continue
                if x + j < 0 or x + j == len(board[0]):
                    continue
                board = open(x + j, y + i, board, False)
    
    if is_click:
        display(board)
        
    return board

/* C */
void chainOpen(int startFrom[2]) {
    printf("(%d,%d):%d\n", startFrom[0], startFrom[1], board[startFrom[0]][startFrom[1]]);
    if(board[startFrom[0]][startFrom[1]] != 0) return;
    int i, j, dest[2];
    for(i = -1; i <= 1; i++) {
        for(j = -1; j <= 1; j++) {
            dest[0] = startFrom[0] + i;
            dest[1] = startFrom[1] + j;
            if(i == 0 && j == 0) continue;
            if((dest[0] < 0 || dest[0] >= size) || (dest[1] < 0 || dest[1] >= size)) continue;
            if(board[dest[0]][dest[1]] != -1 && mask[dest[0]][dest[1]] == 1) {
                mask[dest[0]][dest[1]] = 0;
                chainOpen(dest);
            }
        }
    }
}

// Dart
void dfs(int x, int y) {
      if (x < 0 || y < 0) return;
      if (x >= width || y >= height) return;

      final p = field.value[y][x];
      if (p.state >= 0) return;

      final c = counter(x, y);
      field.value[y][x] = Mine(c, x, y);

      if (c > 0) return;

      for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
          final px = i - 1 + x;
          final py = j - 1 + y;

          dfs(px, py);
        }
      }
    }

処理内容としては、

  • 地雷やフィールド外であれば処理しない

  • 現在のマスを空いている状態に更新

  • 8近傍の個数を格納

  • 8近傍の個数が0なら現在のマス以外の8近傍に対して再帰的に処理

をしています。

おわりに

マインスイーパーを何分で実装できるかということで実装の紹介でした。振り返って見るとデータ構造の持ち方に個性が出ていたり、探索は同じような処理を実装していたりしていて面白かったです！私のFlutterでの実装は90分ほどかかりました。ぜひ何分でマインスイーパーを実装できるか挑戦してみてください！


この記事が気に入ったらサポートをしてみませんか？