import orbital.algorithm.template.*; import orbital.logic.functor.Function; import orbital.logic.functor.MutableFunction; import orbital.math.*; import java.util.*; /** * For 8-puzzle the goal is to place (n^2-1)=8 (or 15,...) tiles in * the right order on an (n x n) sliding puzzle by moving tiles next * to the single empty tile. *
Note that the generalization of * 6-puzzle to n-puzzle is NP-complete.
*/ public class EightPuzzle implements GeneralSearchProblem { public static final int MAX_STEPS = 12; public static void main(String arg[]) { Function h = createHeuristic(); GeneralSearch s; // here we decide which exact search algorithm to use // the single difference in using another search algorithm // would only concern the constructor call s = new AStar(h); // really solve our problem State solution = (State) s.solve(new EightPuzzle(8)); System.out.println("Found solution:\n" + solution); } protected static final Function createHeuristic() { return new Function() { public Object apply(Object n) { State o = (State) n; int[][] s = o.slides; int pos[] = o.tileMoved; // no action yet? then initial state "is for free" if (pos == null) return Values.getDefaultInstance().valueOf(0); else return Values.getDefaultInstance().valueOf(manhattan(pos, s[pos[0]][pos[1]])); /* * note that a better heuristic would be a pairwise manhattan distance * adding +2 to the distance if two pieces need to pass each other * in order to get to their destination (because they are on the same * row or column, but in the wrong order) */ } }; } /** * Get the manhattan distance d1. * Where d1 is the metric induced by the 1-norm. * Visually speaking, the manhatten distance is the distance following * the rectangular streets of manhattan * = delta x + delta y. */ private static int manhattan(int[] pos, int tile) { int[] dest = new int[] { (tile - 1) % size, (tile - 1) / size }; return Math.abs(dest[0] - pos[0]) + Math.abs(dest[1] - pos[1]); } /** * direction enumeration */ public static final int LEFT = 0; public static final int RIGHT = 1; public static final int UP = 2; public static final int DOWN = 3; public static final int MAX_MOVE = DOWN; /** * empty tile */ public static final int EMPTY = 0; private static int size; private int[][] goal; public EightPuzzle(int tiles) { EightPuzzle.size = (int) Math.ceil(Math.sqrt(tiles + 1)); if (tiles != size * size - 1) throw new IllegalArgumentException("no such n-puzzle with n=" + tiles + " which is not a k^2-1"); this.goal = goalState(size); } public Object getInitialState() { State r = new State(shuffle(goalState(size)), null, 0.0); System.out.println(r + " to be solved\n"); return r; } public boolean isSolution(Object n) { int[][] s = ((State) n).slides; System.out.println(n + "\n"); for (int i = 0; i < s.length; i++) for (int j = 0; j < s[i].length; j++) if (s[i][j] != goal[i][j]) return false; return true; } public Iterator actions(Object n) { State s = (State) n; int empty[] = indexOf(s.slides, EMPTY); List ex = new LinkedList(); for (int dir = 0; dir <= MAX_MOVE; dir++) { int[] pos = nextOf(empty, dir); if (pos != null) ex.add(pos); } return ex.iterator(); } public Iterator states(Object action, Object n) { State s = (State) n; int empty[] = indexOf(s.slides, EMPTY); int[] pos = (int[]) action; //@todo could assert that pos is really a neighbour of empty // but we simply believe that since actions(Object) constructs that // we remember the the old position of the empty tile (which // is the new position of the tile moved) in the state, // because our heuristic performs calculations with that return Collections.singletonList(new State(swap(s.slides, empty, pos), empty)).iterator(); } public TransitionModel.Transition transition(Object action, Object state, Object statep) { // uniform cost 1 return new Transition(action, 1); } public MutableFunction getAccumulatedCostFunction() { return _accumulatedCostFunction; } private static final MutableFunction _accumulatedCostFunction = new MutableFunction() { public Object apply(Object state) { return ((State)state).accumulatedCost; } public Object set(Object state, Object newAccumulatedCost) { Object old = ((State)state).accumulatedCost; ((State)state).accumulatedCost = (Real)newAccumulatedCost; return old; } public Object clone() { throw new UnsupportedOperationException(); } }; // implementation helpers /** * search for the specified tile. * @return indices of the tile in the puzzle. */ static int[] indexOf(int[][] s, int tile) { int e[] = new int[2]; for (e[0] = 0; e[0] < s.length; e[0]++) for (e[1] = 0; e[1] < s[e[0]].length; e[1]++) if (s[e[0]][e[1]] == tile) return e; return null; } /** * get a new array like s with the element at i and j swapped. */ static int[][] swap(int[][] s, int[] i, int[] j) { int[][] n_s = new int[s.length][]; for (int k = 0; k < s.length; k++) n_s[k] = (int[]) s[k].clone(); n_s[i[0]][i[1]] = s[j[0]][j[1]]; n_s[j[0]][j[1]] = s[i[0]][i[1]]; return n_s; } /** * Get the indices of the tile next to i, ornull
if that is
* not on the sliding puzzle.
*/
static int[] nextOf(int[] i, int direction) {
int[] r = (int[]) i.clone();
switch (direction) {
case LEFT:
r[0]--;
break;
case RIGHT:
r[0]++;
break;
case UP:
r[1]--;
break;
case DOWN:
r[1]++;
break;
default:
throw new IllegalArgumentException();
}
return 0 <= r[0] && r[0] < size && 0 <= r[1] && r[1] < size ? r : null;
}
/**
* Get the indices of any tile around i.
* Guarantee that the position is on the sliding puzzle.
*/
private static int[] anyOf(int[] i) {
List dirs = new ArrayList(4);
for (int dir = 0; dir <= MAX_MOVE; dir++) {
int[] t = nextOf(i, dir);
// use the old position of the empty tile (is the new position of the tile moved)
// as the action
if (t != null)
dirs.add(t);
}
// chose one of them at random
int chosen = (int) (Math.random() * dirs.size());
return (int[]) dirs.get(chosen);
}
/**
* Shuffles a sliding puzzle by making several random moves.
* @param probability is the probability of continuing the shuffling moves after each step.
*/
private static int[][] shuffle(int[][] r) {
int[] e = indexOf(r, EMPTY);
for (int i = (int) (MAX_STEPS / 2 + Math.random() * MAX_STEPS / 2); i >= 0; i--) {
r = swap(r, e, e = anyOf(e));
}
return r;
}
/**
* Get the goal state of size.
*/
private static int[][] goalState(int size) {
int[][] r = new int[size][size];
for (int i = 0; i < r.length; i++)
for (int j = 0; j < r[i].length; j++)
r[i][j] = i * size + j + 1;
r[r.length - 1][r[r.length - 1].length - 1] = EMPTY;
return r;
}
static class State {
int[][] slides;
Real accumulatedCost;
/**
* just jor easying the work of our heuristic.
*/
int[] tileMoved;
public State(int[][] slides, int[] tileMoved) {
this(slides, tileMoved, Values.getDefault().NaN());
}
public State(int[][] slides, Real accumulatedCost) {
this(slides, null, accumulatedCost);
}
private State(int[][] slides, int[] tileMoved, Real accumulatedCost) {
this.slides = slides;
this.tileMoved = tileMoved;
this.accumulatedCost = accumulatedCost;
}
private State(int[][] slides, int[] tileMoved, double accumulatedCost) {
this(slides, tileMoved, Values.getDefaultInstance().valueOf(0));
}
Real getAccumulatedCost() {
return accumulatedCost;
}
public String toString() {
return MathUtilities.format(slides) + "(" + getAccumulatedCost() + ")";
}
}
}