python 画面 マインスイーパ構成で動作するようにプログラムを構成する方法



マインスイーパー 作る (1)

ブルートフォースをかけたくない場合は、プロセスを決定木としてモデル化することができます。 あなたの例から始めましょう:

####
#21#
####

地雷の有効な配置を開始したい場合、この時点で基本的に8つの選択肢があります。 等価グループ内でどの正方形を選択するかはそれほど重要ではないので、それを3つの選択肢に絞り込むことができます。 木の枝 一つの枝を下っていきましょう。

*###
#11#
####

私はG1に鉱山を置いた、星印で示した。 また、この等価グループに関連付けられている数字(この場合は1つだけの数字)を更新しました。これにより、これらの番号付き正方形が1つ少ない地雷に接することができるようになりました。

これは次のステップへの私達の選択の自由を減らしていません、私達はまだ同等のグループのどれかに鉱山を置くことができます。 G1に別のものを配置しましょう。

*XX#
*01#
XXX#

別のアスタリスクは新しい鉱山を示し、番号付きの広場は再び1つ下げられています。 それは現在ゼロに達しています。つまり、これ以上炭鉱と国境を接することはできません。 それは私たちの次の鉱山配置の選択のために、 この番号のついた正方形に依存するすべての同値グループが除外されることを意味します。 X 、私たちが鉱山を置くことができない場所に正方形をマークします。 私たちは今1つだけ選択をすることができます:

*XX*
*00X
XXXX

これでブランチは終了し、有効な設定が見つかりました。 このようにしてこの木のすべての枝に沿って走ることによって、あなたはそれらすべてを見つけるはずです。 ここで私たちはあなたの最初の設定を見つけました。 もちろん、そこにたどり着く方法は複数あります。 もし私たちがG3に鉱山を置くことから始めていたら、他の2つをG1に置くことを余儀なくされたでしょう。 そのブランチは同じ設定になりますので、重複がないか確認してください。 私は今この冗長性を避ける方法を見ません。

2番目の構成は、G2から開始するか、G1に1つの鉱山を配置してからG2に2番目の鉱山を配置することによって見つかります。 どちらの場合でも、あなたは再びブランチの終わりに行きます:

**XX
X00X
XXXX

あなたの例のようにG1で地雷がゼロの無効な設定はポップアップしません。 あなたをそこに導く木に沿って有効な選択肢はありません。 これが有効な選択肢のツリー全体です。

Choice 1:        1     |     2     |     3
Choice 2:    1   2   3 | 1         | 1   
Choice 3:     3     1  |           |1

有効な構成は、それ以上の選択が不可能な分岐端です。

113
12
131
21
311

数の順序を無視すると、これは明らかに2つの等価なクラスに分類されます。

編集:これは少し前のことで、 github.com/LewisGaul/minegaulerQt含まれているコードを見たいのであれば、動作させています。

私は、掃海艇の確率を計算するプログラムを作成しようとしていますが、それを構築するための最良の方法を見つけるのに苦労しました。 以下の例では最初は非常に単純に見えるかもしれませんが、もっと複雑な設定を可能にするための最良の方法を知りたいと思います。 注意私は確率を計算する方法についての助けを探していません - 私は方法を知っています、私はちょうどそれを実行する必要があります!

私が計算しようとしていることを明確にするために、私は手作業でできる簡単な例を通して働きます。 マインスイーパ構成を検討する
# # # #
# 1 2 #
# # # #
ここで、 #はクリックされていないセルを表します。 1は、一番左の7個のクリックされていないセルにちょうど1個の地雷があることを示し、2は、一番右側の7個のセルに正確に2個の鉱山があることを示しています。この単純なケースでは2つだけ):

  1. 左端の3つのセルに1つの鉱山、右の3つのセルに2つの鉱山(合計3つの鉱山、3×3 = 9の組み合わせ)。

  2. 中央の4つのセルに1つの鉱山、右端の3つのセルに1つの鉱山(合計2つの鉱山、4×3 = 12の組み合わせ)。

鉱山がランダムセル内に存在する確率が約0.2であると仮定すると、(セルのランダム選択では)合計3つの鉱山よりも合計2つの鉱山が存在する可能性が高いため、鉱山の総数は構成においては、各構成の組み合わせの数と同様に重要です。 したがって、この場合、ケース1の確率は9 /(9 + 4×12)= 0.158で、左端の特定のセルに地雷がある確率は約0.158 / 3 = 0.05です。まったく同じ明らかにされた隣人を共有する)。

私はTkinterを使ってGUIを作成しました。これを使うと、例のような設定を簡単に入力することができます。この設定では、グリッドを派手な配列として格納します。 それから、クリックされた/番号が付けられたセルのそれぞれを分離するNumberGroupクラスを作成し、その番号とクリックされていない隣人の座標のセットを格納します。 等価グループを得るためにこれらを引くことができます...ただ2つではなく3つ以上の数があったなら、これはそれほど簡単ではないでしょうが。 しかし、ここからどのようにして異なる構成を取得するのかわからない 。 私はConfigurationクラスを作ることに興味を持っていましたが、異なるクラスがどのように一緒に機能するべきかについてあまり慣れていません。 下記の実用的なコードを参照してください。

注意:私はブルートフォースアプローチを試みることができたかもしれないことを承知していますが、可能であれば、等価グループを別々にしておくことを避けたいと思います(上記の例では3一番右の3) これについてのあなたの考えを聞きたいです。

import numpy as np

grid = np.array(
    [[0, 0, 0, 0],
     [0, 2, 1, 0],
     [0, 0, 0, 0]]
    )
dims = (3, 4) #Dimensions of the grid

class NumberGroup(object):
    def __init__(self, mines, coords, dims=None):
        """Takes a number of mines, and a set of coordinates."""
        if dims:
            self.dims = dims
        self.mines = mines
        self.coords = coords

    def __repr__(self):
        return "<Group of {} cells with {} mines>".format(
            len(self.coords), self.mines)

    def __str__(self):
        if hasattr(self, 'dims'):
            dims = self.dims
        else:
            dims = (max([c[0] for c in self.coords]) + 1,
                    max([c[1] for c in self.coords]) + 1)
        grid = np.zeros(dims, int)
        for coord in self.coords:
            grid[coord] = 1
        return str(grid).replace('0', '.').replace('1', '#')

    def __sub__(self, other):
        if type(other) is NumberGroup:
            return self.coords - other.coords
        elif type(other) is set:
            return self.coords - other.coords
        else:
            raise TypeError("Can only subtract a group or a set from another.")


def get_neighbours(coord, dims):
    x, y = coord
    row = [u for u in range(x-1, x+2) if u in range(dims[0])]
    col = [v for v in range(y-1, y+2) if v in range(dims[1])]
    return {(u, v) for u in row for v in col}

groups = []
all_coords = [(i, j) for i in range(dims[0])
    for j in range(dims[1])]
for coord, nr in [(c, grid[c]) for c in all_coords if grid[c] > 0]:
    empty_neighbours = {c for c in get_neighbours(coord, dims)
        if grid[c] == 0}
    if nr > len(empty_neighbours):
        print "Error: number {} in cell {} is too high.".format(nr, coord)
        break
    groups.append(NumberGroup(nr, empty_neighbours, dims))
print groups
for g in groups:
    print g
print groups[0] - groups[1]

更新:
他のクラスをいくつか追加して少し再構成しました(作業コードについては以下を参照)。これで等価グループを作成および表示できるようになりました。これは正しい方向へのステップです。 ただし、有効な構成を作成する方法で各グループに多数の地雷を割り当てることによって、可能なすべての地雷構成を反復する方法をさらに検討する必要があります。 任意の助けは大歓迎です。

例えば、
# # # #
# 2 1 #
# # # #
等価グループG1:左3、G2:中央4、G3:右3. 3つの等価グループがあります。次のようにグループに鉱山を割り当てます。

  • G1 = 2(最大の最初のグループ)=> G2 = 0 => G3 = 1(これはG1 = 2のすべての設定です)
  • G1 = 1(1ずつ減少)=> G2 = 1 => G3 = 0(これはすべてG1 = 1の場合です)
  • G1 = 0 => G2 = 2無効

それで我々は両方の設定にたどり着きます。 これはもっと複雑な設定のために働く必要があります!

import numpy as np

def get_neighbours(coord, dims):
    x, y = coord
    row = [u for u in range(x-1, x+2) if u in range(dims[0])]
    col = [v for v in range(y-1, y+2) if v in range(dims[1])]
    return {(u, v) for u in row for v in col}

class NrConfig(object):
    def __init__(self, grid):
        self.grid = grid
        self.dims = grid.shape # Dimensions of grid
        self.all_coords = [(i, j) for i in range(self.dims[0])
            for j in range(self.dims[1])]
        self.numbers = dict()
        self.groups = []
        self.configs = []
        self.get_numbers()
        self.get_groups()
        self.get_configs()

    def __str__(self):
        return str(self.grid).replace('0', '.')

    def get_numbers(self):
        for coord, nr in [(c, self.grid[c]) for c in self.all_coords
            if self.grid[c] > 0]:
            empty_neighbours = {c for c in get_neighbours(
                coord, self.dims) if self.grid[c] == 0}
            if nr > len(empty_neighbours):
                print "Error: number {} in cell {} is too high.".format(
                    nr, coord)
                return
            self.numbers[coord] = Number(nr, coord, empty_neighbours,
                self.dims)

    def get_groups(self):
        coord_neighbours = dict()
        for coord in [c for c in self.all_coords if self.grid[c] == 0]:
            # Must be a set so that order doesn't matter!
            coord_neighbours[coord] = {self.numbers[c] for c in
                get_neighbours(coord, self.dims) if c in self.numbers}
        while coord_neighbours:
            coord, neighbours = coord_neighbours.popitem()
            equiv_coords = [coord] + [c for c, ns in coord_neighbours.items()
                if ns == neighbours]
            for c in equiv_coords:
                if c in coord_neighbours:
                    del(coord_neighbours[c])
            self.groups.append(EquivGroup(equiv_coords, neighbours, self.dims))

    def get_configs(self):
        pass # WHAT GOES HERE?!


class Number(object):
    """Contains information about the group of cells around a number."""
    def __init__(self, nr, coord, neighbours, dims):
        """Takes a number of mines, and a set of coordinates."""
        self.nr = nr
        self.coord = coord
        # A list of the available neighbouring cells' coords.
        self.neighbours = neighbours
        self.dims = dims

    def __repr__(self):
        return "<Number {} with {} empty neighbours>".format(
            int(self), len(self.neighbours))

    def __str__(self):
        grid = np.zeros(self.dims, int)
        grid[self.coord] = int(self)
        for coord in self.neighbours:
            grid[coord] = 9
        return str(grid).replace('0', '.').replace('9', '#')

    def __int__(self):
        return self.nr


class EquivGroup(object):
    """A group of cells which are effectively equivalent."""
    def __init__(self, coords, nrs, dims):
        self.coords = coords
        # A list of the neighbouring Number objects.
        self.nr_neighbours = nrs
        self.dims = dims
        if self.nr_neighbours:
            self.max_mines = min(len(self.coords),
                max(map(int, self.nr_neighbours)))
        else:
            self.max_mines = len(coords)

    def __repr__(self):
        return "<Equivalence group containing {} cells>".format(
            len(self.coords))

    def __str__(self):
        grid = np.zeros(self.dims, int)
        for coord in self.coords:
            grid[coord] = 9
        for number in self.nr_neighbours:
            grid[number.coord] = int(number)
        return str(grid).replace('0', '.').replace('9', '#')


grid = np.array(
    [[0, 0, 0, 0],
     [0, 2, 1, 0],
     [0, 0, 0, 0]]
    )
config = NrConfig(grid)
print config
print "Number groups:"
for n in config.numbers.values():
    print n
print "Equivalence groups:"
for g in config.groups:
    print g




minesweeper