Skip to content

Instantly share code, notes, and snippets.

@gabu
Created September 12, 2011 07:35
Show Gist options
  • Save gabu/1210765 to your computer and use it in GitHub Desktop.
Save gabu/1210765 to your computer and use it in GitHub Desktop.
GDD2011 DevQuiz スライドパズルのすごく素直な反復深化(IDDFS)ソルバーです。
package net.gabuchan.devquiz.slidingpuzzle;
import java.util.Arrays;
public class Solver {
private static final char[] pieces =
new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
private static final char UP = 'U';
private static final char DOWN = 'D';
private static final char RIGHT = 'R';
private static final char LEFT = 'L';
private static final char SELF = '0';
private static final char WALL = '=';
private static final int MAX_LOOP_COUNT = 100000000;
private static final int DEPTH_LIMIT = 200;
private int width;
private int height;
private char[] start;
private char[] goal;
private char[] board;
private int self;
private int[] goalIndex;
private int loop = 0;
private int depth = 1;
private int depthStep = 2;
private String answer = null;
public String getAnswer() {
return this.answer;
}
public static void main(String[] args) {
Solver solver = new Solver(args[0]);
try {
if (solver.solve()) {
System.out.println(solver.getAnswer());
} else {
System.out.println("None answer");
}
} catch (Exception e) {
e.printStackTrace();
}
}
public Solver(String problem) {
setup(problem);
}
public boolean solve() throws Exception {
boolean result = false;
while (depth <= DEPTH_LIMIT) {
System.out.println("depth = " + depth);
if (result = solve(0, calcCost())) {
break;
} else {
depth += depthStep;
}
}
return result;
}
private boolean solve(int count, int distance) throws Exception {
if (Arrays.equals(board, goal)) {
answer = createAnswer();
System.out.println("Answer: " + answer + ", depth: " + depth + ", loop: " + loop);
return true;
}
if (depth == count++) return false;
if (depth < count + distance) return false;
if (loop++ > MAX_LOOP_COUNT) throw new Exception("Over the MAX_LOOP_COUNT");
char[] nexts = calcNexts();
for (int i = 0; i < 4; i++) {
char next = nexts[i];
if (next == 0) continue;
int newI = self;
int oldI = dst(next);
int oldDistance = distance(oldI, goalIndex[board[oldI]]);
move(board, next);
int newDistance = distance(newI, goalIndex[board[newI]]);
int dd = newDistance - oldDistance;
pushPath(next);
if (solve(count, distance + dd)) return true;
popPath();
back(board, next);
}
return false;
}
private boolean isBack(char last, char next) {
switch (last) {
case UP:
return next == DOWN;
case DOWN:
return next == UP;
case RIGHT:
return next == LEFT;
case LEFT:
return next == RIGHT;
}
return false;
}
private char[] calcNexts() {
char[] nexts = new char[4];
char last;
if (pathIndex == -1) {
last = 0;
} else {
last = lastPath();
}
if (self - width >= 0 && board[self - width] != WALL && !isBack(last, UP)) {
nexts[0] = UP;
}
if (self + width < board.length && board[self + width] != WALL && !isBack(last, DOWN)) {
nexts[1] = DOWN;
}
if ((self + 1) % width != 0 && board[self + 1] != WALL && !isBack(last, RIGHT)) {
nexts[2] = RIGHT;
}
if (self % width != 0 && board[self - 1] != WALL && !isBack(last, LEFT)) {
nexts[3] = LEFT;
}
return nexts;
}
private int calcCost() {
int cost = 0;
for (int i = 0; i < board.length; i++) {
if (board[i] == WALL || board[i] == SELF) {
continue;
} else {
cost += distance(i, goalIndex[board[i]]);
}
}
return cost;
}
private int distance(int start, int goal) {
int startX = start % width;
int startY = start / width;
int goalX = goal % width;
int goalY = goal / width;
return Math.abs(goalX - startX) + Math.abs(goalY - startY);
}
private void setup(String problem) {
String[] split = problem.split(",");
width = Integer.parseInt(split[0]);
height = Integer.parseInt(split[1]);
start = split[2].toCharArray();
board = start.clone();
self = charArrayIndexOf(board, SELF);
goal = createGoal();
goalIndex = new int[256];
for (int i = 0; i < goal.length; i++) {
goalIndex[goal[i]] = i;
}
depth = calcCost();
}
private int dst(char next) {
switch (next) {
case UP:
return self - width;
case DOWN:
return self + width;
case RIGHT:
return self + 1;
case LEFT:
return self - 1;
}
return -1;
}
private void move(char[] board, char path) {
int dst = dst(path);
transpose(board, self, dst);
self = dst;
}
private void back(char[] board, char path) {
switch (path) {
case UP:
move(board, DOWN);
break;
case DOWN:
move(board, UP);
break;
case RIGHT:
move(board, LEFT);
break;
case LEFT:
move(board, RIGHT);
break;
}
}
private char[] createGoal() {
char[] goal = new char[start.length];
for (int i = 0; i < start.length; i++) {
if (start[i] == WALL) {
goal[i] = WALL;
} else {
if (i == start.length - 1) {
goal[i] = SELF;
} else {
goal[i] = pieces[i + 1];
}
}
}
return goal;
}
private String createAnswer() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i <= pathIndex; i++) {
sb.append(pathStack[i]);
}
return sb.toString();
}
private int charArrayIndexOf(char[] cs, char search) {
for (int i = 0; i < cs.length; i++) {
if (cs[i] == search) return i;
}
return -1;
}
private void transpose(char[] cs, int src, int dst) {
char tmp = cs[src];
cs[src] = cs[dst];
cs[dst] = tmp;
}
private char[] pathStack = new char[DEPTH_LIMIT];
private int pathIndex = -1;
private void pushPath(char c) {
pathStack[++pathIndex] = c;
}
private char popPath() {
return pathStack[pathIndex--];
}
private char lastPath() {
return pathStack[pathIndex];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment