東大2年工学部システム創成B課題. マインスイーパーを解くプログラム.

mimesAvatar.java

public class MimesAvatar extends PlayerEnforced {
	// Definition of element of cells
	// -2: Must be safe, but cell number not revealed.
	// -1: Unopened and not sure whether safe or not.
	// 0~: Open.
	private int[][] cells;

	private boolean[][] newlyOpenedSquarePositions;
	private int width;
	private int height;

	MimesAvatar(boolean[][] flags, MimesPlayer player) {
		this.flags = flags;
		this.cells = new int[player.wrappedGetWidth()][player.wrappedGetHeight()];
		this.newlyOpenedSquarePositions = new boolean[player.wrappedGetWidth()][player.wrappedGetHeight()];
		this.width = player.wrappedGetWidth();
		this.height = player.wrappedGetHeight();

		for (int x = 0; x < player.wrappedGetWidth(); x++) {
			for (int y = 0; y < player.wrappedGetHeight(); y++) {
				cells[x][y] = player.wrappedGetCell(x, y);
			}
		}
	}

	public void execute() {
		boolean anyUpdate;

		do {
			anyUpdate = false;
			anyUpdate = openAllSecureSquares();
			scanAndFlag();
		} while (anyUpdate);
	}

	public boolean[][] getNewlyOpenedSquarePositions() {
		return newlyOpenedSquarePositions;
	}

	@Override
	protected int wrappedGetWidth() {
		return width;
	}

	@Override
	protected int wrappedGetHeight() {
		return height;
	}

	@Override
	protected int wrappedGetCell(int x, int y) {
		return cells[x][y];
	}

	@Override
	protected void wrappedOpen(int x, int y) {
		cells[x][y] = -2;
		newlyOpenedSquarePositions[x][y] = true;
	}
}

mimesPlayer.java

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class MimesPlayer extends PlayerEnforced {

	@Override
	protected void start() {
		flags = new boolean[wrappedGetWidth()][wrappedGetHeight()];
		wrappedOpen(wrappedGetWidth() / 2, wrappedGetHeight() / 2);

		if (wrappedGetCell(wrappedGetWidth() / 2, wrappedGetHeight() / 2) == 1) {
			wrappedOpen(wrappedGetWidth() / 2 - 1, wrappedGetHeight() / 2);
		}

		LOOP: while (!isClear() && !isGameOver()) {
			scanAndFlag();

			if (openAllSecureSquares()) {
				continue;
			}

			if (openByTwoWorldsDeduction()) {
				continue;
			}

			if (openByThreeWorldsDeduction()) {
				continue;
			}

			System.out.println("Open randomly!!");

			for (int x = 0; x < wrappedGetWidth(); x++) {
				for (int y = 0; y < wrappedGetHeight(); y++) {
					
					// dirty
					if (wrappedGetCell(0, 0) > 0 && (openedCellsCount() == 3 || openedCellsCount()  == 2)) {
						wrappedOpen(wrappedGetWidth() * 3/4, wrappedGetHeight() * 3/4);
						
						int bombsCount = wrappedGetCell(wrappedGetWidth() * 3/4, wrappedGetHeight() * 3/4);
						if (bombsCount > 0) {
							wrappedOpen(wrappedGetWidth() * 1/4, wrappedGetHeight() * 1/4);
						}
						continue LOOP;
					}
					//
					
					if (wrappedGetCell(x, y) == -1 && !flags[x][y]) {
						wrappedOpen(x, y);			
						continue LOOP;
					}
				}
			}
		}
	}
	
	private boolean openByTwoWorldsDeduction() {
		boolean anyOpened = false;

		for (int x = 0; x < wrappedGetWidth(); x++) {
			for (int y = 0; y < wrappedGetHeight(); y++) {
				if (!(wrappedGetCell(x, y) > 0 && countUnopenedSquaresAround(x, y) == 2)) {
					continue;
				}

				List<boolean[][]> secureSquarePositions = new ArrayList<>();

				for (int i = -1; i <= 1; i++) {
					for (int j = -1; j <= 1; j++) {
						if (i == 0 && j == 0) {
							continue;
						}

						if (x + i > wrappedGetWidth() - 1 || x + i < 0) {
							continue;
						}

						if (y + j > wrappedGetHeight() - 1 || y + j < 0) {
							continue;
						}

						if (wrappedGetCell(x + i, y + j) == -1 && !flags[x + i][y + j]) {
							boolean[][] fakeFlags = new boolean[wrappedGetWidth()][wrappedGetHeight()];
							copyFlagsArray(flags, fakeFlags);
							fakeFlags[x + i][y + j] = true;
							MimesAvatar avatar = new MimesAvatar(fakeFlags, this);
							avatar.execute();
							secureSquarePositions.add(avatar.getNewlyOpenedSquarePositions());
						}
					}
				}

				for (int xx = 0; xx < wrappedGetWidth(); xx++) {
					for (int yy = 0; yy < wrappedGetHeight(); yy++) {
						if (secureSquarePositions.get(0)[xx][yy] && secureSquarePositions.get(1)[xx][yy]) {
							wrappedOpen(xx, yy);
							anyOpened = true;
						}
					}
				}
			}
		}

		return anyOpened;
	}

	private boolean openByThreeWorldsDeduction() {
		boolean anyOpened = false;

		for (int x = 0; x < wrappedGetWidth(); x++) {
			for (int y = 0; y < getHeight(); y++) {
				if (!(wrappedGetCell(x, y) > 0 && countUnopenedSquaresAround(x, y) == 3)) {
					continue;
				}

				List<Map<String, Integer>> unopenedRelativePositions = new ArrayList<>();

				for (int i = -1; i <= 1; i++) {
					for (int j = -1; j <= 1; j++) {
						if (i == 0 && j == 0) {
							continue;
						}

						if (x + i > wrappedGetWidth() - 1 || x + i < 0) {
							continue;
						}

						if (y + j > wrappedGetHeight() - 1 || y + j < 0) {
							continue;
						}

						if (wrappedGetCell(x + i, y + j) == -1 && !flags[x + i][y + j]) {
							Map<String, Integer> map = new HashMap<>();
							map.put("i", i);
							map.put("j", j);
							unopenedRelativePositions.add(map);
						}
					}
				}

				List<boolean[][]> secureSquarePositions = new ArrayList<>();
				
				if (wrappedGetCell(x, y) - countFlagsAround(x, y) == 1) { // flags count in unopened squares
					for (Map<String, Integer> flaggedPosition : unopenedRelativePositions) {
						boolean[][] fakeFlags = new boolean[wrappedGetWidth()][wrappedGetHeight()];
						copyFlagsArray(flags, fakeFlags);
						
						fakeFlags[x + flaggedPosition.get("i")][y + flaggedPosition.get("j")] = true;

						MimesAvatar avatar = new MimesAvatar(fakeFlags, this);
						avatar.execute();
						secureSquarePositions.add(avatar.getNewlyOpenedSquarePositions());
					}
				} else { // == 2
					for (Map<String, Integer> noflaggedPosition : unopenedRelativePositions) {
						boolean[][] fakeFlags = new boolean[wrappedGetWidth()][wrappedGetHeight()];
						copyFlagsArray(flags, fakeFlags);

						for (Map<String, Integer> urp : unopenedRelativePositions) {
							if (!(noflaggedPosition.get("i") == urp.get("i")
									&& noflaggedPosition.get("j") == urp.get("j"))) {
								fakeFlags[x + urp.get("i")][y + urp.get("j")] = true;
							}
						}

						MimesAvatar avatar = new MimesAvatar(fakeFlags, this);
						avatar.execute();
						secureSquarePositions.add(avatar.getNewlyOpenedSquarePositions());
					}
				}

				for (int xx = 0; xx < wrappedGetWidth(); xx++) {
					for (int yy = 0; yy < wrappedGetHeight(); yy++) {
						if (secureSquarePositions.get(0)[xx][yy] && secureSquarePositions.get(1)[xx][yy]
								&& secureSquarePositions.get(2)[xx][yy]) {
							wrappedOpen(xx, yy);
							anyOpened = true;
						}
					}
				}
			}
		}

		return anyOpened;
	}
	
	private void copyFlagsArray(boolean[][] flags, boolean[][] fakeFlags) {
		for (int i = 0; i < flags.length; i++) {
			for (int j = 0; j < flags[0].length; j++) {
				fakeFlags[i][j] = flags[i][j];
			}
		}
	}
	
	private int openedCellsCount() {
		return wrappedGetWidth() * wrappedGetHeight() - getMaskedCellCount();
	}
	
	@Override
	protected int wrappedGetWidth() {
		return getWidth();
	}
	
	@Override
	protected int wrappedGetHeight() {
		return getHeight();
	}
	
	@Override
	protected int wrappedGetCell(int x, int y) {
		return getCell(x, y);
	}

	@Override
	protected void wrappedOpen(int x, int y) {
		open(x, y);
	}
}

MimesProject.java

import jp.ne.kuramae.torix.lecture.ms.core.MineSweeper;
import jp.ne.kuramae.torix.lecture.ms.core.Player;

public class MimesProject {
	static public void main(String[] args) {
		int gamesCount = 1000;
		int clearedCount = 0;
		
		for (int i = 0; i < gamesCount; i++) {
			Player player = new MimesPlayer();
			MineSweeper mineSweeper = new MineSweeper(0);
			boolean cleared = mineSweeper.start(player);

			if (cleared) {
				clearedCount += 1;
			}
		}
		
		System.out.println("WinPercentage: " + clearedCount * 1.0 / gamesCount * 100 + "%");
	}
}

playerEnforced.java

import jp.ne.kuramae.torix.lecture.ms.core.Player;

abstract public class PlayerEnforced extends Player {
	protected boolean[][] flags;
	
	@Override
	protected void start() {}
	
	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) {
		boolean anyOpened = false;
		
		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				if (i == 0 && j == 0) {
					continue;
				}
				
				if (x + i > wrappedGetWidth() - 1 || x + i < 0) {
					continue;
				}

				if (y + j > wrappedGetHeight() - 1 || y + j < 0) {
					continue;
				}
				
				if (wrappedGetCell(x + i, y + j) == -1 && !flags[x + i][y + j]) {
					wrappedOpen(x + i, y + j);
					anyOpened = true;
				}
			}
		}
		
		return anyOpened;
	}
	
	protected boolean openAllSecureSquares() {
		boolean anyOpened = false;
		
		for (int x = 0; x < wrappedGetWidth(); x++) {
			for (int y = 0; y < wrappedGetHeight(); y++) {
				int bombsCount = wrappedGetCell(x, y);
				
				if (bombsCount > 0 && bombsCount == countFlagsAround(x, y)) {
					if (openAround(x, y)) {
						anyOpened = true;
					}
				}
			}
		}
		
		return anyOpened;
	}
	
	protected int countFlagsAround(int x, int y) {
		int flagsCount = 0;

		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				if (i == 0 && j == 0) {
					continue;
				}

				if (x + i > wrappedGetWidth() - 1 || x + i < 0) {
					continue;
				}

				if (y + j > wrappedGetHeight() - 1 || y + j < 0) {
					continue;
				}

				if (flags[x + i][y + j]) {
					flagsCount += 1;
				}
			}
		}

		return flagsCount;
	}
	
	protected void scanAndFlag() {
		for (int x = 0; x < wrappedGetWidth(); x++) {
			for (int y = 0; y < wrappedGetHeight(); y++) {
				int bombsCount = wrappedGetCell(x, y);

				if (bombsCount > 0 && bombsCount == countFlagsAround(x, y) + countUnopenedSquaresAround(x, y)) {
					putFlagsAround(x, y);
				}
			}
		}
	}
	
	protected void putFlagsAround(int x, int y) {
		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				if (i == 0 && j == 0) {
					continue;
				}

				if (x + i > wrappedGetWidth() - 1 || x + i < 0) {
					continue;
				}

				if (y + j > wrappedGetHeight() - 1 || y + j < 0) {
					continue;
				}

				if (wrappedGetCell(x + i, y + j) == -1) {
					flags[x + i][y + j] = true;
				}
			}
		}
	}
	
	protected int countUnopenedSquaresAround(int x, int y) {
		int squaresCount = 0;

		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				if (i == 0 && j == 0) {
					continue;
				}

				if (x + i > wrappedGetWidth() - 1 || x + i < 0) {
					continue;
				}

				if (y + j > wrappedGetHeight() - 1 || y + j < 0) {
					continue;
				}

				if (wrappedGetCell(x + i, y + j) == -1 && !flags[x + i][y + j]) {
					squaresCount += 1;
				}
			}
		}

		return squaresCount;
	}
}