1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
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();
}
}
|
