前回の「一人ゲーム」編に続き、今回のDevQuizの最難関であり、先週末の日本の消費電力量を数パーセント上げたと言われる(?)「スライドパズル」の解答を公開します。
「スライドパズル」のルールは、
- 幅3~6、高さ3~6マスのボードが与えられる
- ボードの各マスは、パネル、壁、空白のいずれか
- パネルは1-9およびA-Z、壁は=、空白は0で示される
- 空白は上下左右のパネルと入れ替えられるが、壁とは入れ替えられない
- 空白を上下左右のパネルと入れ替えることをそれぞれ”U”,”D”,”L”,”R”で示す
- 与えられた初期配置をゴール配置まで導く解を”U”,”D”,”L”,”R”の文字列で解答する
- ゴール配置は、左上から右下に向かって1→Zのパネルが順番に並び、右下隅が0となる
- 問題数は5000問で、一問解く毎に0.01点が与えられる
- 解答に使える”U”,”D”,”L”,”R”それぞれの総数には上限がある
というものです。つまり、様々なサイズの15パズルに”壁”というルールを加えたもの。
本格的に考え始めたのが締め切り前週の木曜(8日)の夜だったため、とりあえずは盤面のサイズが小さいものや短手数で解けるものを解いて点数を稼ごうという考えでコーディングを始めました。
私の考えた基本的な戦略は、
- ゴール配置からn手目の全盤面と、その盤面からゴールに到達する手順(寄せ手)のリストを作る
- スタート配置から一手ずつ全盤面を作り、寄せ手リストの盤面のどれかに一致すればゴール!
- スタートからの盤面数が肥大していくので、盤面がある程度の数以上になったら、「ゴールに近そうなもの」を残して切り捨てる
- 手数制限についてはオーバーしたときに考える
いわゆる双方向・幅優先探索＋評価値による枝刈りです。(この問題を考える以前は、こんな言葉は知らなかったわけですが)
ここで問題になるのは、3.の切り捨て時に何をもって「ゴールに近い」と判断するかです。私はとりあえずの評価値として各パネルのマンハッタン距離(=本来の位置に最低何手で移動できるか?)の合計と転倒数の合計を使うことにしました。マンハッタン距離の算出には、壁の存在も考慮に入れています。さらに、乱数でピックアップした盤面も少し混ぜ込んでいます。
それでは、以下がJavaのコードです。公開用に可読性を上げるためのリファクタリングをしていますが、ロジックは変更していません。
ファイルはこちらからダウンロードできます。
package jp.bitmeister.gdd;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class SlidePuzzle {
static int[] limits = new int[4]; // 手数制限
static int[] remains; // 残手数
static Puzzle[] puzzles;
static final char[] character = new char[] {'L', 'R', 'U', 'D'};
static final int[] direction = new int[] {0, 1, 2, 3}; // 方向リスト
static final int[] reverse = new int[] {1, 0, 3, 2}; // 逆方向リスト
static final int[] prime = new int[] {
37,41,43,47,53,59,61,67,71,73,79,83,
89,97,101,103,107,109,113,127,131,137,139,149,
151,157,163,167,173,179,181,191,193,197,199,211}; // ハッシュ算出用素数リスト
static int tried = 0;
static int solved = 0;
static int level;
public static void main(String[] args) {
try {
// 問題読込
BufferedReader rd = new BufferedReader(new FileReader("puzzle.txt"));
String[] nums = rd.readLine().split(" ");
for (int i = 0; i < 4; i++) {
limits[i] = Integer.valueOf(nums[i]);
}
remains = limits.clone();
puzzles = new Puzzle[Integer.valueOf(rd.readLine())];
List<Puzzle> list = new ArrayList<Puzzle>();
for (int i = 0; i < puzzles.length; i++) {
puzzles[i] = new Puzzle(rd.readLine().split(","));
list.add(puzzles[i]);
}
// 解答済みの結果を読込
if (new File("result.txt").exists()) {
rd = new BufferedReader(new FileReader("result.txt"));
for (Puzzle e: puzzles) {
String result = rd.readLine();
if (result.length() > 0) {
e.result = result;
tried++;
solved++;
}
}
}
// Exceptionで落ちても結果は保存
Runtime.getRuntime().addShutdownHook(new Thread(new ShutdownThread()));
level = 1;
if (args.length > 0) {
level = Integer.valueOf(args[0]);
}
int from = 0;
if (args.length > 1) {
from = Integer.valueOf(args[1]);
}
// ↓盤のサイズが小さいものから解いていたときの名残り
// Collections.sort(list);
for (int i = 0; i < list.size(); i++) {
Puzzle p = list.get(i);
if (p.result.length() > 0) {
System.out.println("No." + (i + 1) + " size:" + p.x * p.y);
System.out.println("ALREADY SOLVED : " + p.result);
minusRemains(p.result); // 既に答えが出ているものを残手数から引く
}
}
// パズルを解く
for (int i = from; i < list.size(); i++) {
Puzzle p = list.get(i);
if (p.result.length() == 0) {
System.out.println("No." + (i + 1) + " size:" + p.x * p.y);
byte[] result = new Solver(p).solve();
if (result != null) {
p.result = resultToString(result);
System.out.println("SOLVED! : " + p.result);
solved++;
}
System.out.println("solve: " + solved + " / try: " + tried);
System.out.println("L:" + remains[0] + "(" + ((float)remains[0] / limits[0]) * 100 + "%)"
+ " R:" + remains[1] + "(" + ((float)remains[1] / limits[1]) * 100 + "%)"
+ " U:" + remains[2] + "(" + ((float)remains[2] / limits[2]) * 100 + "%)"
+ " D:" + remains[3] + "(" + ((float)remains[3] / limits[3]) * 100 + "%)");
System.out.println();
}
}
}
catch (Exception e) {
e.printStackTrace();
}
}
// 終了時に結果をファイルに書き出すためのスレッド
static class ShutdownThread implements Runnable {
@Override
public void run() {
try {
FileWriter fw = new FileWriter("result.txt");
for (Puzzle p: puzzles) {
fw.write(p.result);
fw.write('\n');
}
fw.flush();
}
catch (Exception e) {
e.printStackTrace();
}
}
}
// 結果を文字列に変換
static String resultToString(byte[] result) {
StringBuilder builder = new StringBuilder();
for (byte e: result) {
if (e < 0) {
continue;
}
remains[e]--;
if (remains[e] == 0) {
throw new RuntimeException(String.valueOf(character[e]) + " reached limit.");
}
builder.append(character[e]);
}
return builder.toString();
}
static void minusRemains(String result) {
for (char c: result.toCharArray()) {
remains[charToDirection(c)]--;
}
}
static int charToDirection(char c) {
switch (c) {
case 'L':
return 0;
case 'R':
return 1;
case 'U':
return 2;
default:
return 3;
}
}
// 問題クラス
static class Puzzle implements Comparable<Puzzle> {
int x;
int y;
int size;
String start;
String result = "";
Puzzle(String[] args) {
x = Integer.valueOf(args[0]);
y = Integer.valueOf(args[1]);
size = x * y;
start = args[2];
}
@Override
public int compareTo(Puzzle o) {
return size - o.size;
}
}
// 解答探索クラス
static class Solver {
Puzzle p;
int[] distance;
boolean[] wall; // 壁
Board start; // 開始盤面
Board goal; // 終了盤面
int maxMd; // 寄せ手リスト中の最大マンハッタン距離値
int stepLimit; // 手数制限(これ以上の手数になったら諦める)
int goalMapSize; // 寄せ手リストのサイズ
int stepWidth; // スタートからの盤面数の制限値
byte[][] mdMap; // マンハッタン距離マップ
Map<Board, byte[]> goalMap; // 寄せ手リスト
Solver(Puzzle p) {
this.p = p;
distance = new int[] {-1, 1, -p.x, p.x}; // 一手で動く距離
// レベルに合わせて各制限値を設定
stepLimit = p.size * (2 + level);
goalMapSize = 10240 * (1 << level);
stepWidth = 2048 * level;
// スタート盤面、ゴール盤面、壁設定
wall = new boolean[p.size];
byte[] start = new byte[p.size];
byte[] goal = new byte[p.size];
char[] c = p.start.toCharArray();
for (int i = 0; i < c.length; i++) {
goal[i] = (byte)(i + 1);
if (c[i] == '=') {
start[i] = (byte)(i + 1);
wall[i] = true;
}
else if (c[i] <= '9') {
start[i] = (byte)(c[i] - '0');
}
else {
start[i] = (byte)(c[i] - 'A' + 10);
}
}
for (int i = goal.length - 1; i >= 0; i--) {
if (!wall[i]) {
goal[i] = 0;
break;
}
}
makeMdMap();
this.start = new Board(start);
this.goal = new Board(goal);
show(this.start);
}
// マンハッタン距離マップ作成
void makeMdMap() {
mdMap = new byte[p.size][];
mdMap[0] = new byte[p.size];
for (int i = 1; i < p.size; i++) {
byte[] m = new byte[p.size];
Arrays.fill(m, (byte)-1);
m[i - 1] = 0;
mdStep(m, i - 1);
mdMap[i] = m;
}
}
// 再帰で一手ずつ進んで各マスへの最短距離を出す
void mdStep(byte[] map, int pos) {
for (int i = 0; i < 4; i++) {
if (canMove(pos, i)
&& (map[pos + distance[i]] < 0 || map[pos + distance[i]] > map[pos] + 1)) {
map[pos + distance[i]] = (byte)(map[pos] + 1);
mdStep(map, pos + distance[i]);
}
}
}
// 移動可能チェック
boolean canMove(int pos, int i) {
return ((i == 0 && pos % p.x != 0)
|| (i == 1 && pos % p.x != p.x - 1)
|| (i == 2 && pos >= p.x)
|| (i == 3 && pos < p.size - p.x))
&& !wall[pos + distance[i]];
}
// 解答探索
byte[] solve() {
tried++;
byte[] result = null;
try {
result = goalMap();
if (result == null) {
result = fromStart();
goalMap = null;
}
} catch (Exception e) {
e.printStackTrace();
}
System.out.println();
if (result == null) {
System.out.println("UNSOLVED!");
}
else if (!checkResult(result)) {
System.out.println("INVALID RESULT!");
}
else {
result = checkLoop(result);
return result;
}
return null;
}
// 寄せ手リスト作成
byte[] goalMap() {
System.out.print("Making goal map : ");
// 既出盤面リスト
List<Set<Board>> g_appeared_list = new ArrayList<Set<Board>>();
g_appeared_list.add(new HashSet<Board>());
Set<Board> g_appeared = g_appeared_list.get(0);
g_appeared.add(goal);
// 一手前リスト
Map<Board, byte[]> g_last = new HashMap<Board, byte[]>();
g_last.put(goal, new byte[] {-1});
maxMd = 0;
for (int i = 0; g_last.size() < goalMapSize; i++) {
System.out.print(".");
goalMap = new HashMap<Board, byte[]>();
for (Entry<Board, byte[]> e: g_last.entrySet()) {
int z = posZero(e.getKey());
MLOOP : for (int j = 0; j < 4; j++) {
// 各方向に動いて盤面と手順をマップに保存
byte[] step = e.getValue();
Board moved = e.getKey().move(z, j, step[step.length - 1]);
if (moved == null) {
continue;
}
for (Set<Board> s: g_appeared_list) {
// 既出
if (s.contains(moved)) {
continue MLOOP;
}
}
if (moved.md > maxMd) {
maxMd = moved.md;
}
byte[] newStep = Arrays.copyOf(step, step.length + 1);
newStep[step.length] = (byte)j;
if (moved.equals(start)) {
// スタート盤面にヒット
return reverse(newStep);
}
g_appeared.add(moved);
goalMap.put(moved, newStep);
}
}
if (g_appeared_list.size() > 4) {
// 既出チェックは4手前ぐらいでOK?
g_appeared_list.remove(0);
}
g_appeared_list.add(g_appeared);
g_appeared = new HashSet<Board>();
g_last = goalMap;
}
System.out.println(" map size : " + goalMap.size());
return null;
}
// スタート盤面から探索
byte[] fromStart() {
System.out.print("From start : ");
// 既出リスト
List<Set<Board>> s_appeared_list = new ArrayList<Set<Board>>();
s_appeared_list.add(new HashSet<Board>());
Set<Board> s_appeared = s_appeared_list.get(0);
s_appeared.add(start);
// 一手前リスト
Map<Board, byte[]> s_last = new HashMap<Board, byte[]>();
s_last.put(start, new byte[] {-1});
for (int i = 0; i < stepLimit; i++) {
Map<Board, byte[]> current = new HashMap<Board, byte[]>(); // 一手後リスト
List<Board> list = new ArrayList<Board>(); // 枝刈り用リスト
MLOOP : for (Entry<Board, byte[]> e: s_last.entrySet()) {
int z = posZero(e.getKey());
for (int j = 0; j < 4; j++) {
// 各方向に動いて盤面と手順を保存
byte[] step = e.getValue();
Board moved = e.getKey().move(z, j, step[step.length - 1]);
if (moved == null) {
continue;
}
for (Set<Board> s: s_appeared_list) {
if (s.contains(moved)) {
continue MLOOP;
}
}
byte[] newStep = Arrays.copyOf(step, step.length + 1);
newStep[step.length] = (byte)j;
if (moved.md <= maxMd && goalMap.containsKey(moved)) {
// 寄せ手リストにヒットした
byte[] toGoal = reverse(goalMap.get(moved));
byte[] result = new byte[newStep.length + toGoal.length];
System.arraycopy(newStep, 0, result, 0, newStep.length);
System.arraycopy(toGoal, 0, result, newStep.length, toGoal.length);
return result;
}
s_appeared.add(moved);
current.put(moved, newStep);
list.add(moved);
}
}
if (list.size() > stepWidth * 3 * level) {
// スタートからの盤面を減らす(枝刈り)
Collections.sort(list);
s_last = new HashMap<Board, byte[]>();
for (int j = 0; j < stepWidth; j++) {
// マンハッタン距離が小さいものを残す
s_last.put(list.get(j), current.get(list.get(j)));
}
// 転倒数でもソート
Collections.sort(list, new Comparator<Board>() {
@Override
public int compare(Board arg0, Board arg1) {
if (arg0.rc != arg1.rc) {
return arg0.rc - arg1.rc;
}
return arg0.md - arg1.md;
}
});
for (int j = 0; j < stepWidth; j++) {
// マンハッタン距離は大きいが転倒数が小さいものがあれば残す
if (!s_last.containsKey(list.get(j))) {
s_last.put(list.get(j), current.get(list.get(j)));
}
}
for (int j = stepWidth; j < list.size(); j+=(int)(Math.random() * 128)) {
// ランダムにいくつか選んで残す
if (!s_last.containsKey(list.get(j))) {
s_last.put(list.get(j), current.get(list.get(j)));
}
}
}
else {
s_last = current;
}
if (s_appeared_list.size() > 4) {
// 既出チェックは4手前ぐらいでOK?
s_appeared_list.remove(0);
}
s_appeared_list.add(s_appeared);
s_appeared = new HashSet<Board>();
System.out.print(".");
}
return null;
}
int posZero(Board b) {
for (int i = 0; i < b.t.length; i++) {
if (b.t[i] == 0) return i;
}
throw new RuntimeException("no 0 found!!");
}
// ゴールからの手順をスタートからの手順に変換
byte[] reverse(byte[] src) {
byte[] dst = new byte[src.length];
for (int i = src.length - 1; i >= 0; i--) {
if (src[i] >= 0) {
dst[src.length - 1 - i] = (byte)reverse[src[i]];
}
else {
dst[src.length - 1 - i] = -1;
}
}
return dst;
}
// スタート盤面からゴール盤面に辿りつけるか答え合わせ
boolean checkResult(byte[] steps) {
Board b = start;
for (byte s: steps) {
if (s < 0) {
continue;
}
b = b.move(posZero(b), s, -1);
}
if (b.equals(goal)) {
return true;
}
return false;
}
// 手順の循環をチェックする
byte[] checkLoop(byte[] result) {
Map<Board, Integer> s = new HashMap<Board, Integer>();
boolean detected = false;
Board b = start;
byte pd = -1;
for (int i = 0; i < result.length; i++) {
if (result[i] < 0) {
continue;
}
s.put(b, i);
b = b.move(posZero(b), result[i], pd);
if (s.containsKey(b)) {
// 既出の局面が現れたら中間の手順を削除
for (int j = s.get(b); j <= i; j++) {
result[j] = (byte)-1;
}
detected = true;
}
pd = result[i];
}
if (detected) {
System.out.println("LOOP DETECTED!!");
if (!checkResult(result)) {
System.out.println("INVALID!");
return null;
}
}
return result;
}
// 盤面クラス
class Board implements Cloneable, Comparable<Board> {
byte[] t;
int md;
int rc;
int hash;
Board(byte[] t) {
this.t = t;
setMd();
setRc();
// 素数を使ってハッシュ生成
hash = 0;
for (int i = 0; i < t.length; i++) {
hash += t[i] * prime[i];
}
// マンハッタン距離と転倒数もハッシュに加える
hash += md * 10000;
hash += rc * 10000000;
}
// 一手移動後の盤面を生成する
Board move(int z, int d, int pd) {
if (reverse[d] == pd) {
return null;
}
if (!canMove(z, d)) {
return null;
}
byte[] moved = ((byte[])t).clone();
moved[z] = t[z + distance[d]];
moved[z + distance[d]] = t[z];
return new Board(moved);
}
void setMd() {
md = 0;
for (int i = 0; i < t.length; i++) {
md += mdMap[t[i]][i];
}
}
void setRc() {
rc = 0;
for (int i = 1; i <= t.length; i++) {
for (int j = 0; j < i - 1; j++) {
if (t[j] != 0 && t[j] > i) rc++;
}
for (int j = i; j < t.length; j++) {
if (t[j] != 0 && t[j] < i) rc++;
}
}
}
@Override
public boolean equals(Object obj) {
// 盤面の比較が大量に行われるので配列比較が回避できると高速化につながる
if (hash != ((Board)obj).hash) {
return false;
}
return Arrays.equals(t, ((Board)obj).t);
}
@Override
public int hashCode() {
return hash;
}
@Override
protected Object clone() {
return new Board(t.clone());
}
@Override
public int compareTo(Board o) {
if (md != o.md) {
return md - o.md;
}
return rc - o.rc;
}
}
// 盤面表示
void show(Board bd) {
System.out.println();
for (int y = 0; y < p.y; y++) {
for (int x = 0; x < p.x; x++) {
if (wall[y * p.x + x]) {
System.out.print("## ");
}
else {
System.out.printf("%2d ", bd.t[y * p.x + x]);
}
}
System.out.println();
}
System.out.println();
}
}
}
実行時に、VMの引数として -Xmx1g -Xms1g を指定しています。また、第一引数で探索レベル(デフォルト=1、上限はメモリと実行時間次第)、第二引数で探索を開始する問題の番号(デフォルト=0)を指定できます。
Core2Duo T7300 2.0GHz RAM2.0GBのLenovo ThinkPad X61 で実行したところ、
- Level-1 実行時間 3時間19分 解答数 4328/5000
- Level-2 実行時間 2時間56分 解答数 363/672(計4691/5000)
- Level-3 実行時間 3時間31分 解答数 123/309(計4814/5000)
という結果。適当な戦略で作ったわりにゴールまで辿り着けた数が多くて驚きました。どうやら”寄せ手リスト”が良い思いつきだった模様です。
実際のDevQuizの解答は、12日の朝までプログラムを実行し、4868/5000問正解というところで送信しました。実行時間がもう一日あれば、49点台は狙えたかも。
50点満点を狙うには、「盤の上端や左端が揃っている場合を高得点にする」とか、「壁で細い道が出来ている場合には壁を進む方向に動いてみる」といった局面毎の戦略も必要だったようです。盤面上に壁で島ができている(おそらくどこかの局面でゴールとは逆方向に壁の周りを回る必要がある)パターンを取りこぼしている状況で、運任せの乱数選択しか思いつかないようでは、満点は無理ですね…。盤面のハッシュコードについても、もう少し衝突(シノニム)回避の工夫で高速化ができたのではないかと悔やまれます。
CPU性能やRAM容量が10年前とは比べ物にならないほど潤沢になった現在では、1ステップ単位の性能や多少のメモリの無駄など気にせずコードを書いてしまうことも多いのですが、久しぶりのシビアな環境に心が躍りました。ハッシュ算出をちょっと改良しただけでスピードが目に見えて速くなったり、久しぶりにOutOfMemoryExeptionを見たりしたのは良い経験です。そして、普段から細かいノウハウやアルゴリズムの引き出しを沢山作っておくことの重要性を改めて感じました。
では、DevQuizに挑戦した皆様、お疲れ様でした。