540377D 石川貴大 Mimesチーム
- 初級: 76~79%
- 中級: 54~57%
- 上級: 12~14%
メインクラス.
MimesAvatarクラスとMimesPlayerクラスの共通メソッドを実装した抽象クラス.
| プロパティ | 説明 |
|---|---|
| protected boolean[][] flags | 旗の座標を表すプロパティ. |
| メソッド | 説明 |
|---|---|
| abstract protected int wrappedGetWidth() | 盤の横幅のゲッター. |
| abstract protected int wrappedGetHeight() | 盤の縦幅のゲッター. |
| abstract protected int wrappedGetCell(int x, int y) | 指定した座標の状態のゲッター. |
| abstract protected void wrappedOpen(int x, int y) | 指定した座標を開く. |
| protected boolean openAround(int x, int y) | 指定した座標の周りを全て開く. 旗が立っている場合は開かない. |
| protected boolean openAllSecureSquares() | 全てのマスをスキャンして、確実に爆弾のないマスを開く. |
| protected int countFlagsAround(int x, int y) | 指定した座標の周りの旗の数を取得する. |
| protected void scanAndFlag() | 全てのマスをスキャンして、確実に爆弾のあるマスに旗を立てる. |
| protected void putFlagsAround(int x, int y) | 指定した座標の周りの未開封マスに旗を立てる. |
| protected int countUnopenedSquaresAround(int x, int y) | 指定した座標の周りのまだ開封していないマスの数を取得する. |
ある時点の盤の状態から、とあるマスに爆弾があると仮定した先を解かせる、メインのプレイ ヤーの分身. 本ゲームの盤には一切影響を与えずに、マインスイーパーのゲームをシミュレー ションすることができる. 盤の状態を分岐させて、安全なマスの共通部分を考えるのに使うこと ができる.
| プロパティ | 説明 |
|---|---|
| private int[][] cells | 盤の各座標の状態を格納するプロパティ. 配列の要素が表す意味は以下. |
| private boolean[][] newlyOpenedSquarePositions | -2が入っている座標を格納するプロパティ. |
| private int width | 盤の横幅を表すプロパティ. |
| private int height | 盤の縦幅を表すプロパティ. |
| 数値 | 意味 |
|---|---|
| -2 | マスは未開封だが、確実に爆弾が入っていない. |
| -1 | マスは未開封. |
| 0 | 開封済みで周りに爆弾はない. |
| 1~ | 開封済みで周りには数字の数だけ爆弾がある. |
| メソッド | 説明 |
|---|---|
| public void execute() | Avatarにマインスイーパーの続きを解かせる. |
| public boolean[][] getNewlyOpenedSquarePositions() | -2が入っている座標を返すゲッター. Avatarが作られたのちに、確実に爆弾が入っていないと明らかになったマスの座標を表す. |
| protected int wrappedGetWidth() | 盤の横幅を返すゲッター. |
| protected int wrappedGetHeight() | 盤の縦幅を返すゲッター. |
| protected int wrappedGetCell(int x, int y) | Avatarが解いている仮想的なゲームにおいて、指定した座標の数値を返すゲッター. |
| protected void wrappedOpen(int x, int y) | Avatarが解いている仮想的なゲームにおいて、指定した座標のマスを開封する. |
マインスイーパーを解く主体.
| メソッド | 説明 |
|---|---|
| protected void start() | マインスイーパーを解き始める. 具体的なアルゴリズムは以下. |
| private boolean openByTwoWorldsDeduction() | startメソッドの中での解法のアルゴリズム3つ目を行うメソッド. |
| private boolean openByThreeWorldsDeduction() | startメソッドの中での解法のアルゴリズム4つ目を行うメソッド. |
| private void copyFlagsArray(boolean[][] flags, boolean[][] fakeFlags) | flagsの中身をfakeFlagsにコピーする. |
| private int openedCellsCount() | いくつのマスを開封したか取得する. |
| protected int wrappedGetWidth() | 盤の横幅のゲッター. |
| protected int wrappedGetHeight() | 盤の縦幅のゲッター. |
| protected int wrappedGetCell(int x, int y) | 指定したマスの状態を取得する. |
| protected void wrappedOpen(int x, int y) | 指定したマスを開封する. |
- 盤の真ん中を開封. そこが1だったらその隣も開く.
- 盤の全体を読み込んで、確実に旗を立てられるところに立てる.
- 盤の全体を読み込んで、2通りに旗を立てるパターンが分岐する箇所を探す(例えば、1を表すマスの周りに未開封のマスが2つあり、どちらかに爆弾がある場合). 場合ごとに仮に旗を立ててみてその先を仮想プレイヤーAvatarに解かせる. 2つのAvatarが確実に解けるところまで解いたら、2つのAvatarが共通して確実に爆弾が存在しないとしたマスを特定する. このマスにはメインのゲームにおいても確実に爆弾が入ってないので、開封しても安全である.
- さっきのアルゴリズムの3通りに分岐するバージョンを実施する.
- 左上から読みこんで、最初の旗の立ってない未開封マスを開く(運任せ). ゲーム序盤は少し小細工する.
- 設計について openByXWorldsDeductionというメソッド群は共通メソッドを持っているのでもう少しDRYにできたかもしれないが、本番にDeployするソフトウェアでもないし深くは考えなかった.
- 正解率について 提出したプログラムでは、確実に開けるマスを開き尽くしたら、あとは運任せに開封するだけなのが伸び代. マスに爆弾がある確率を計算するなどの工夫ができそうだが、確実に開ける場所を開くだけのアルゴリズムで目標勝率を十分に達成できたので、これ以上は突き詰めないことにした. 確実に開けるマスを探すアルゴリズムにしても、openByXWorldsDeduction (X > 2)を実装すればもう少し勝率が上がりそうである.
プログラミングの授業としてはベストな形だったと思う.
gistにあげた. https://gist.github.com/sykwer/c411327fab84473b3d293b6b55cc9c4d