diff options
Diffstat (limited to 'Week6 Sliding game solver/src/SlidingGame.java')
| -rw-r--r-- | Week6 Sliding game solver/src/SlidingGame.java | 205 |
1 files changed, 205 insertions, 0 deletions
diff --git a/Week6 Sliding game solver/src/SlidingGame.java b/Week6 Sliding game solver/src/SlidingGame.java new file mode 100644 index 0000000..0e80797 --- /dev/null +++ b/Week6 Sliding game solver/src/SlidingGame.java @@ -0,0 +1,205 @@ +import java.util.ArrayList;
+import java.util.Collection;
+
+/**
+ * @author Pieter Koopman, Sjaak Smetsers
+ * @author Camil Staps, s4498062
+ *
+ * A template implementation of a sliding game also
+ * implementing the Graph interface
+ */
+@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility.
+public class SlidingGame implements Configuration
+{
+ public static final int N = 3, SIZE = N * N, HOLE = SIZE;
+
+ /*
+ * The board is represented by a 2-dimensional array;
+ * The position of the hole is kept in 2 variables holeX and holeY
+ * We store the summed manhattan of all tiles and the hole in manhattan
+ */
+ private final int [][] board;
+ private int holeX, holeY;
+ private final int manhattan;
+
+ /*
+ * A constructor that initializes the board with the specified array
+ * @param start: a one dimensional array containing the initial board.
+ * The elements of start are stored row-wise.
+ */
+ public SlidingGame (int [] start) {
+ board = new int[N][N];
+
+ assert start.length == SIZE: "Length of specified board incorrect";
+
+ for( int p = 0; p < start.length; p++) {
+ board[p % N][p / N] = start[p];
+ if ( start[p] == HOLE ) {
+ holeX = p % N;
+ holeY = p / N;
+ }
+ }
+
+ manhattan = calculateManhattan();
+ }
+
+ /**
+ * A constructor that initialises the board with a specified 2D array
+ * @param board a 2D array containing the initial board
+ */
+ public SlidingGame (int[][] board) {
+ this.board = new int[N][N];
+
+ assert board.length == N: "Length of specified board incorrect";
+
+ for (int a = 0; a < N; a++) {
+ assert board[a].length == N: "Length of specified board incorrect";
+ for (int b = 0; b < N; b++) {
+ this.board[a][b] = board[a][b];
+ if (board[a][b] == HOLE) {
+ holeX = a;
+ holeY = b;
+ }
+ }
+ }
+
+ manhattan = calculateManhattan();
+ }
+
+ /**
+ * Calculate the summed Manhattan distance for all tiles and the hole
+ * @return the Manhattan distance
+ */
+ private int calculateManhattan() {
+ int result = 0;
+ for (int x = 0; x < N; x++) {
+ for (int y = 0; y < N; y++) {
+ int this_x = (board[x][y] - 1) % N;
+ int this_y = (board[x][y] - 1) / N;
+ result += Math.abs(this_x - x) + Math.abs(this_y - y);
+ }
+ }
+ return result;
+ }
+
+ public int getManhattan() {
+ return manhattan;
+ }
+
+ /**
+ * Attempt to move the hole in a specified direction
+ * @param d the direction in which to move
+ * @return A new instance of this class where the hole has moved
+ * @throws ArrayIndexOutOfBoundsException If the hole cannot be moved
+ */
+ private SlidingGame move(Direction d) throws ArrayIndexOutOfBoundsException {
+ int[][] newboard = new int[N][N];
+ for (int a = 0; a < N; a++)
+ System.arraycopy(board[a], 0, newboard[a], 0, N);
+
+ newboard[holeX][holeY] = newboard[holeX + d.GetDX()][holeY + d.GetDY()];
+ newboard[holeX + d.GetDX()][holeY + d.GetDY()] = HOLE;
+ return new SlidingGame(newboard);
+ }
+
+ /*
+ * Converts a board into a printable representation.
+ * The hole is displayed as a space.
+ * @return the string representation
+ */
+ @Override
+ public String toString() {
+ StringBuilder buf = new StringBuilder();
+ for (int row = 0; row < N; row++) {
+ for (int col = 0; col < N; col++) {
+ int puzzel = board[col][row];
+ // Using String.format to pad left as in http://stackoverflow.com/a/391978/1544337; provides better formatting for puzzles with N > 3
+ buf.append(String.format("%1$" + ((int) Math.log10(SIZE - 1) + 2) + "s", puzzel == HOLE ? " " : puzzel + " "));
+ }
+ buf.append("\n");
+ }
+ return buf.toString();
+ }
+
+ /*
+ * A standard implementation of equals checking whether 2 boards are filled
+ * in exactly the same way.
+ * @return true iff this object and o are equal
+ */
+ @Override
+ public boolean equals(Object o) {
+ if (o == null || o.getClass() != getClass()) {
+ return false;
+ } else {
+ SlidingGame other_puzzle = (SlidingGame) o;
+ for (int row = 0; row < N; row++) {
+ for (int col = 0; col < N; col++) {
+ if (board[col][row] != other_puzzle.board[col][row]) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+ }
+
+ @Override
+ public boolean isSolution () {
+ for( int p = 0; p < SIZE; p++) {
+ if (board[p % N][p / N] != p + 1) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public Collection<Configuration> successors () {
+ Collection<Configuration> successors = new ArrayList<Configuration>();
+ try {
+ successors.add(move(Direction.EAST));
+ } catch (ArrayIndexOutOfBoundsException e) {}
+ try {
+ successors.add(move(Direction.SOUTH));
+ } catch (ArrayIndexOutOfBoundsException e) {}
+ try {
+ successors.add(move(Direction.WEST));
+ } catch (ArrayIndexOutOfBoundsException e) {}
+ try {
+ successors.add(move(Direction.NORTH));
+ } catch (ArrayIndexOutOfBoundsException e) {}
+ return successors;
+ }
+
+ /**
+ * According to the assignment we should use:
+ * result += board[x][y] * Math.pow(31, x + N*y);
+ * However, this results for even small boards in INT_MAX, so this is not very useful.
+ *
+ * Giving every board a unique hash would be:
+ * result += board[x][y] * Math.pow(SIZE, x + N*y);
+ * However, already with N=4 that results in INT_MAX as well.
+ *
+ * The current implementation uses SIZE as base and subtracts n(n-1) from the exponent.
+ * This results in values well below INT_MAX for N up to 5 (and possibly higher).
+ * Of course, it also means that different puzzles may have the same value.
+ * For N>3 this is unavoidable since 16! > INT_MAX. For N <= 3 we are not too concerned
+ * since the program is fast enough for small programs for us to accept this imperfectness.
+ */
+ @Override
+ public int hashCode() {
+ int result = 0;
+ for (int x = 0; x < N; x++)
+ for (int y = 0; y < N; y++)
+ result += board[x][y] * Math.pow(SIZE, x + N*y - (N-1)*N);
+
+ return result;
+ }
+
+ @Override
+ public int compareTo(Configuration t) {
+ SlidingGame tsg = (SlidingGame) t;
+ return manhattan - tsg.getManhattan();
+ }
+
+}
|