マインスイーパーの地雷を配置するアルゴリズム

概要

今回は、マインスイーパーでの地雷を配置するアルゴリズムについて、急遽作成してみたくなったので、Python作っていきます。

プログラム

ゲームボードの作成

下記コードがゲームボードを作成するプログラムです。
TODOの箇所のコードを有効化し、地雷を配置する処理を書いていきます。

import tkinter as tk
from tkinter import messagebox
import random

class Minesweeper:
    """
    マインスイーパークラス
    """
    def __init__(self, master, rows=10, cols=10, mines=10):
        self.master = master
        self.rows = rows # 列数
        self.cols = cols # 行数
        self.mines = mines # 地雷の数
        self.buttons = [] # セルの配列

        # ゲームボードの作成
        for row in range(self.rows):
            button_row = []
            for col in range(self.cols):
                button = tk.Button(master, width=2, command=lambda r=row, c=col: self.click(r, c))
                button.grid(row=row, column=col)
                button_row.append(button)
            self.buttons.append(button_row)

        # TODO:地雷の配置
        # self.place_mines()

def main():
    root = tk.Tk()
    root.title("Minesweeper")
    _ = Minesweeper(root)
    root.mainloop()

if __name__ == "__main__":
    main()

実行してみると、ゲームボードが表示されました（当然動きません）

地雷の配置（chatGPT版）

まずは、チャットGPTにコードを書いてもらいました。
内容としては、mine_coordsにset()を定義しデータが重複しないようにしています。

あとは、ランダムに横と縦の配列番号を選び地雷を配置していき、whileで指定した地雷の数に到達したら処理を終了という流れです。

def place_mines(self):
   self.mine_coords = set()
   while len(self.mine_coords) < self.mines:
       row = random.randint(0, self.rows - 1)
       col = random.randint(0, self.cols - 1)
       self.mine_coords.add((row, col))

問題点

実はこのコード問題があります。
地雷の数が多くなると、ループ回数が増えてしまいます。
完全にランダムなため同じ配列番号が何回も登場してしまうため、
10 × 10のゲームボードで地雷100個を指定すると、大体520回くらいの処理回数になります。

アルゴリズム修正版

以下のコードが改良したプログラムとなります。
mine_indicesには、被りの無いランダムな数列が格納されます。

for文の中で、mine_indicesから取り出した値から配列にセットします。

39 の場合は、
row は 39 から 10(行数)を割ったときの、商の整数 3
col は 39 から 10(行数)を割ったときの、あまり 9
の配列にセットされます。

これで、10 × 10のゲームボードで地雷100個を指定すると、100回のループ処理になり、最適化できました。

def place_mines(self):
    self.mine_coords = set()
    total_cells = self.rows * self.cols
    mine_indices = random.sample(range(total_cells), self.mines)

    for index in mine_indices:
        row = index // self.cols
        col = index % self.cols
        self.mine_coords.add((row, col))

おわりに

今回は、マインスイーパーでの地雷を配置するアルゴリズムを作成しました。もっといいアルゴリズムがあれば教えてください。

地雷を配置するだけでは、ゲームにならないのでその他の機能も作らなければなりません。

下記のリポジトリで、一応ゲームが動くところまでできたので、興味のある方はぜひ見てみてください。

ここまで読んでいただきありがとうございました。

開発中の画面です↓