Google DevQuiz 回答アップ「スライドパズル編」

さてさて、最後にスライドパズル編です。
回答をアップする前に自分のスコアを教えておくと、
4740問回答でき、最終的な点数は147.4点でした。

260問残してしまいましたが、もう少し時間があれば、4800問まではいけたかも。
でも手数は残り4000位しかなかったので、満点は無理だったかな。

■スライドパズル

幅が 3 マスから 6 マスで、高さが 3 マスから 6 マスのボードが与えられます。 各マスは、パネルが置かれているか、壁があるか、空白であるかのいずれかです。 パネルには 1 から 9 あるいは A から Z のいずれかの文字が書かれており、同じ文字の書かれたパネルは存在しません。 壁は 0 個以上存在し、空白のマスはただ 1 つだけ存在します。 例えば、次のようなボードが与えられます。ここで、壁は = で、空白は 0 で表されています。

  4 0 =
  2 1 5
  = 8 6

空白は、上下左右のマスのパネルと入れ替えることができます。上のマスのパネルと入れ替えることを U とよび、同様に、下左右のマスのパネルと入れ替えることをそれぞれ D, L, R とよぶものとします。壁を空白やパネルと入れ替えることはできません。

パズルを解くというのは、与えられたボードの各マスを操作して、ゴール状態に持っていくことです。

ゴール状態とは、上の行から各行順番に、左から右に 1, 2, 3, 4, ..., 9, A, ..., Z という順にパネルが並び、最も右下のマスに空白が配置された状態のことです。壁のあるマスに対応するパネルは存在しません。例えば、左上のマスが壁であれば、ボード上に 1 のパネルは存在しません。

例えば、上で与えられたボードのパズルを解くと以下のようになります。

 4 0 =
 2 1 5
 = 8 6

 1 2 =
 4 5 6
 = 8 0

いま、使うことができる L, R, U, D それぞれの総数があたえられます。 この総数は全パズルで共有されています。 例えばあるパズルを解くために L を使い切ってしまった場合、 他のパズルでは L を使うことはできません。 この総数を超えないようにしながら、なるべくたくさんのパズルを解いてください。

という問題です。
典型的な8パズルと呼ばれる問題に壁があることで、少し複雑にしていますね。

さてさて、解法としてはそんな複雑なものではなく、これまたオーソドックスな幅優先探索 + 枝刈りでやっています。
双方向探査も試しましたが、そんなに正答率を上げるものではなかったですね。
工夫したところと言えるかわかりませんが、ダイクストラ法を利用して、壁を考慮した距離を実装しています。
さらに、なるべく距離を高速に計算できるように、あらかじめ全文字の全位置における距離を計算しておき、
移動したらその文字の移動した分の差分だけを更新するようにしています。

■距離関数実装クラス

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

/**
 * 距離関数の実装クラス
 * ダイクストラ法を実装し、壁を考慮した距離にしている。
 * @author yosuke
 *
 */
public class Distance {
	/** 距離を保持するマップ */
	private Map<Character, List<Integer>> distanceMap;
	private int width;
	private int height;
	/** まだ考慮されていない距離 */
	private static final int BLOCK_DISTANCE = 1000;
	public Distance(int width, int height, String correctStr) {
		this.width = width;
		this.height = height;
		distanceMap = new HashMap<Character, List<Integer>>();
		String correctString = Util.createAnswerPanel(correctStr);
		char[][] board = Util.createBoard(width, height, correctString);
		for (int y=0; y<height; y++) {
			for (int x=0; x<width; x++) {
				List<Integer> list = new ArrayList<Integer>();
				char c = board[y][x];
				int difference = 0;
                                //最初に自分のマス以外をBLOCK_DISTANCEにする。
				if (c != '=') {				
					for (int y1=0; y1<height; y1++) {
						boolean blocked = false;
						for (int x1=0; x1<width; x1++) {
							char difC = board[y1][x1];
							if (c == difC) {
								difference = 0;
							} else {
								difference = BLOCK_DISTANCE;
							}
							list.add(difference);
						}
					}
                                        //=以外のすべてのマスの距離が埋まるまで繰り返す
					while(!isFinished(board, list)) {
						for (int y2=0; y2<height; y2++) {
							for (int x2=0; x2<width; x2++) {
								int distance = list.get(x2 + y2 * width);
								char difC = board[y2][x2];
								int min = BLOCK_DISTANCE;
								if (difC != '=' && distance == BLOCK_DISTANCE) {
									if (y2 > 0) {
										int dist = list.get(x2 + (y2-1)*width);
										if (dist < min) {
											min = dist;
										}
									}
									if (y2 < height-1) {
										int dist = list.get(x2 + (y2+1)*width);
										if (dist < min) {
											min = dist;
										}
									}
									if (x2 > 0) {
										int dist = list.get((x2-1) + y2*width);
										if (dist < min) {
											min = dist;
										}
									}
									if (x2 < width-1) {
										int dist = list.get((x2+1) + y2*width);
										if (dist < min) {
											min = dist;
										}
									}
									if (min != BLOCK_DISTANCE) {
										list.set(x2+y2*width, min+1);
									}
								}
							}
						}
					}

					distanceMap.put(c, list);
				}
			}
		}
	}

	/**
	 * 距離の計測が終わったかどうか終わった場合はtrue
	 * @param board ボード
	 * @param distanceList 距離リスト
	 * @return
	 */
	private boolean isFinished(char[][] board, List<Integer> distanceList) {
		boolean result = true;
		for (int y=0; y<height; y++) {
			for (int x=0; x<width; x++) {
				char c = board[y][x];
				int distance = distanceList.get(x + y * width);
				if (c != '=' && distance == BLOCK_DISTANCE) {
					return false;
				}
			}
		}
		return result;
	}

	/**
	 * すべての距離を計測するメソッド
	 * @param board ボード
	 * @return 距離
	 */
	public int getAllDistance(char[][] board) {
		int difference = 0;
		for (int y=0; y<height; y++) {
			for (int x=0; x<width; x++) {
				char c = board[y][x];
				if (c != '=') {
					difference += getDistanceChar(c, x, y);
				}
			}
		}
		return difference;
	}

	/**
	 * 最大距離長
	 * @param board ボード
	 * @return 最大距離長
	 */
	public int getMaxDistance(char[][] board) {
		int max = 0;
		for (int y=0; y<height; y++) {
			for (int x=0; x<width; x++) {
				char c = board[y][x];
				if (c != '=') {
					int temp = getDistanceChar(c, x, y);
					if (temp > max) {
						max = temp;
					}
				}
			}
		}
		return max;
	}

	public int getNewDistance(char c, int oldX, int oldY, int newX, int newY, int currentDistance) {
		int distance = currentDistance;
		int oldDiff = getDistanceChar(c, oldX, oldY);
		int newDiff = getDistanceChar(c, newX, newY);
		distance = distance - oldDiff + newDiff;
		return distance;
	}

	public int getDistanceChar(char c, int x, int y) {
		int distance = 0;
		if (c == '=') {
			return 0;
		}
		List<Integer> list = distanceMap.get(c);
		distance = list.get(x + y * width);
		return distance;
	}

	public static void main(String[] args) {
		Distance distance = new Distance(4, 4, "12=45=789A=CDEF0");
		System.out.println(distance.distanceMap);
		char[][] chars = {{'1','4','=', '2'},{'5','=','7', '8'},{'9','A','=','C'},{'D','E','F','0'}};
		int dist = distance.getAllDistance(chars);
		int newDist = distance.getNewDistance('1', 2, 2, 1, 1, 20);

		System.out.println(dist);
		System.out.println(newDist);
		newDist = distance.getNewDistance('2', 2, 1, 1, 0, 20);
		System.out.println(newDist);
	}


}

ソルバーは先程も言ったように単なる幅優先探査です。
一応公開しておきます。

■ソルバー

import java.util.List;

/**
 * スライドパズルの本体
 * @author yosuke
 *
 */
public class SlidePuzzle {
	/** ボード */
	private Board board;
	private int width;
	private int height;
	/** パズル文字列 */
	private String puzzle;
	/** 正解パズル文字列 */
	private String correctPuzzle;
	/** 盤面のhistory */
	private History history;
	private Distance distance;
	private AnswerBoard answerBoard;
	
	
	private final static int UP_OP = 0;
	private final static int LEFT_OP = 1;
	private final static int RIGHT_OP = 2;
	private final static int DOWN_OP = 3;
	
	/** タイムアウト時間(秒) */
	private static long MAXTIME = 30;
	private static long startmills;
	/** 枝切りサイズ */
	private static int MAXSIZE = 5000;
	public SlidePuzzle(int width, int height, String puzzle) {
		history = new History();
		this.width = width;
		this.height = height;
		this.puzzle = puzzle;
		correctPuzzle = Util.createAnswerPanel(puzzle);
		distance = new Distance(width, height, correctPuzzle);
		char[][] chars = Util.createBoard(width, height, puzzle);
		board = new Board(width, height, puzzle);
		int distInt = distance.getAllDistance(chars);
		int maxDistInt = distance.getMaxDistance(chars);
		history.putHistory(puzzle, "", distInt, maxDistInt);
		answerBoard = new AnswerBoard();
		answerBoard.put(
				puzzle,
				distInt,
				distance.getMaxDistance(chars));
	}
	
	public void solvePuzzle() {
		startmills = System.currentTimeMillis();
		List<String> candidateList = null;
		while (true) {
			long time = System.currentTimeMillis();
			long duration = time - startmills;
			long secs = (duration / 1000);
			if (secs > MAXTIME) {
				break;
			}
			candidateList = answerBoard.getListFromCandidate(MAXSIZE);
//			Util.writeLog(candidateList.get(0));
			answerBoard = new AnswerBoard();
			for (String oldPazzle : candidateList) {
				String operationHistory = history.getOperationHistory(oldPazzle);
				int currentDistance = history.getDistanceHistory(oldPazzle);
				int currentMaxDistance = history.getMaxDistanceHistory(oldPazzle);
				for (int op = 0; op < 4; op++) {
					switch(op) {
					case UP_OP : 
						board = new Board(width, height, oldPazzle);
						if (board.up()) {
							MovedPosition position = board.getPosition();
							move(operationHistory + "U", position, currentDistance, currentMaxDistance);
						}
						break;
					case LEFT_OP: 
						board = new Board(width, height, oldPazzle);
						if (board.left()) {
							MovedPosition position = board.getPosition();
							move(operationHistory + "L", position, currentDistance, currentMaxDistance);
						}
						break;
					case RIGHT_OP:
						board = new Board(width, height, oldPazzle);
						if (board.right()) {
							MovedPosition position = board.getPosition();
							move(operationHistory + "R", position, currentDistance, currentMaxDistance);
						}
						break;
					case DOWN_OP:
						board = new Board(width, height, oldPazzle);
						if (board.down()) {
							MovedPosition position = board.getPosition();
							move(operationHistory + "D", position, currentDistance, currentMaxDistance);
						}
						break;
					}
					//解答があったら終了。
					if (answerBoard.contains(correctPuzzle)) {
						return;
					}
				}
			}
		}
	}
	
	/**
	 * 解答が出たかどうか
	 * 出た場合はtrue
	 * @return
	 */
	public boolean solved() {
		String operation = history.getOperationHistory(correctPuzzle);
		return operation != null;
	}
	
	/**
	 * 解答の操作文字列を得る。
	 * @return
	 */
	public String getSolvedString() {
		String historyOperation = history.getOperationHistory(correctPuzzle);
		if (historyOperation != null && !historyOperation.isEmpty()) {
			return historyOperation;
		} else {
			return "";
		}
	}
	
	public void printCurrentDistanceTop() {
		String top = history.getCurrentDistanceTop();
		System.out.println(top);
		Board board = new Board(width, height, top);
		board.printBoard();
	}
	
	public void printCurrentMaxDistanceTop() {
		String top = history.getCurrentMaxDistanceTop();
		Board board = new Board(width, height, top);
		board.printBoard();
	}
	
	public void printBoard() {
		board.printBoard();
	}
	
	/***
	 * 移動とその距離をhistoryに加える処理。
	 * @param operation
	 * @param position
	 * @param currentDistance
	 * @param currentMaxDistance
	 */
	private void move(String operation, MovedPosition position, int currentDistance, int currentMaxDistance) {
		String boardStr = board.getBoardString();
		char changedChar = position.getC();
		int oldX = position.getOldX();
		int oldY = position.getOldY();
		int newX = position.getNewX();
		int newY = position.getNewY();
		if (history.getOperationHistory(boardStr) == null) {
			char[][] c = Util.createBoard(width, height, boardStr);
			int newDistance = distance.getNewDistance(changedChar, oldX, oldY, newX, newY, currentDistance);
			int newMaxDistance = distance.getMaxDistance(c);
			
			answerBoard.put(boardStr, newDistance, newMaxDistance);
			history.putHistory(boardStr, operation, newDistance, newMaxDistance);
		}
	}

}

枝刈りに利用する優先順位を考慮するのは、下記のようにやりました。
距離が一緒だった場合に文字列同士を比較させ、1234・・・と順序良く若い順に並んでいる方を優先するように工夫しました。

■枝刈り

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * ボードの状況を記録して、評価するクラス
 * @author yosuke
 *
 */
public class AnswerBoard {
	
	/**
	 * 比較評価メソッド
	 * @param map
	 * @return
	 */
	static <K,V extends Comparable<? super V>>
	SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
	    SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
	        new Comparator<Map.Entry<K,V>>() {
	            @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
	            	//距離を計測
	                int compareto = e1.getValue().compareTo(e2.getValue());
	                if(compareto > 0) {
	    		    	return 1;
	    		    } else if(compareto == 0) {
	    		    	//計測した距離が同じ場合に、パズルが綺麗に並んでいる方を優先する
	    		    	String keyATemp = ((String)e1.getKey()).replace('0', 'z');
	    		    	String keyBTemp = ((String)e2.getKey()).replace('0', 'z');
	    		    	return keyATemp.compareTo(keyBTemp);
	    		    } else {
	    		    	return -1;
	    		    }
	            }
	        }
	    );
	    sortedEntries.addAll(map.entrySet());
	    return sortedEntries;
	}
	/**  keyにボードの文字列、valueに総合距離を持つマップ */
	private Map<String, Integer> answerDistanceMap = new TreeMap<String, Integer>();
	/** keyにボードの文字列、valueに文字間の最大距離長を持つマップ*/
	private Map<String, Integer> answerMaxDistanceCharMap = new TreeMap<String, Integer>();
	
	/**
	 * Historyに追加するメソッド
	 * @param key - ボードの文字列
	 * @param distance - 総合距離
	 * @param maxCharDistance - 文字間の最大距離長
	 */
	public void put(String key, Integer distance, Integer maxCharDistance) {
		answerDistanceMap.put(key, distance);
		answerMaxDistanceCharMap.put(key, maxCharDistance);
	}
	
	public int size() {
		return answerDistanceMap.keySet().size();
	}
	/** 距離に基づいて、解答候補リストを作成する */
	public List<String> getListFromCandidate(int size) {
		List<String> answerList = new ArrayList<String>();
		Set<Map.Entry<String, Integer>> ansSet = entriesSortedByValues(answerDistanceMap);
		int index = 0;
		for (Map.Entry<String, Integer> answer : ansSet) {
			if (index < size) {
				answerList.add(answer.getKey());
			} else {
				break;
			}
			index++;
		}
		return answerList;
	}
	
	public List<String> getListFromDistance(int distance) {
		List<String> answerList = new ArrayList<String>();
		Set<Entry<String, Integer>> ansSet = answerDistanceMap.entrySet();
		for (Entry<String, Integer> answerEntry : ansSet) {
			int value = answerEntry.getValue();
			if (value <= distance) {
				answerList.add(answerEntry.getKey());
			} else {
				break;
			}
		}
		return answerList;
	}
	
	public List<String> getListFromMaxCharDistance(int maxChardistance) {
		List<String> answerList = new ArrayList<String>();
		Set<Entry<String, Integer>> ansSet = answerMaxDistanceCharMap.entrySet();
		for (Entry<String, Integer> answerEntry : ansSet) {
			int value = answerEntry.getValue();
			if (value <= maxChardistance) {
				answerList.add(answerEntry.getKey());
			} else {
				break;
			}
		}
		return answerList;
	}
	
	public boolean contains(String key) {
		return answerDistanceMap.containsKey(key);
	}
}

これ以外にも色々試していますが、その詳細はGitHubにアップしてありますので、
そちらを参照してください。
gdd11jp/GoogleSlideGame/src at master · yosuke-furukawa/gdd11jp · GitHub