diff options
Diffstat (limited to 'Algorithms')
| -rw-r--r-- | Algorithms/Part-I/4-Puzzle/Board.java | 73 |
1 files changed, 48 insertions, 25 deletions
diff --git a/Algorithms/Part-I/4-Puzzle/Board.java b/Algorithms/Part-I/4-Puzzle/Board.java index ffc8a7a..e4d9b11 100644 --- a/Algorithms/Part-I/4-Puzzle/Board.java +++ b/Algorithms/Part-I/4-Puzzle/Board.java @@ -1,6 +1,6 @@ /* vim: set expandtab tabstop=4 shiftwidth=4 : */ -class Board { +public class Board { private int d; private byte[][] blocks; @@ -21,13 +21,20 @@ class Board { { this.d = blocks[0].length; - this.openRow = this.d - 1; - this.openCol = this.d - 1; this.blocks = new byte[d][d]; for (int i = 0; i < d; i++) + { for (int j = 0; j < d; j++) + { this.blocks[i][j] = (byte) blocks[i][j]; + if (blocks[i][j] == 0) + { + this.openRow = i; + this.openCol = j; + } + } + } } // board dimension N @@ -79,19 +86,15 @@ class Board { return true; } - private Board swap(int r0, int c0, int r1, int c1) + private byte[][] copy() { - byte[][] blocks2 = new byte[d][d]; + byte[][] bytes = new byte[d][d]; for (int i = 0; i < d; i++) for (int j = 0; j < d; j++) - blocks2[i][j] = blocks[i][j]; - - byte tmp = blocks2[r0][c0]; - blocks2[r0][c0] = blocks2[r1][c1]; - blocks2[r1][c1] = tmp; + bytes[i][j] = blocks[i][j]; - return new Board(blocks2, openRow, openCol); + return bytes; } // a board obtained by exchanging two adjacent blocks in the same row @@ -100,7 +103,13 @@ class Board { int row = 0; if (openRow == 0) row = 1; - return swap(row, 0, row, 1); + byte [][]bytes = copy(); + + byte tmp = bytes[row][0]; + bytes[row][0] = bytes[row][1]; + bytes[row][1] = tmp; + + return new Board(bytes, openRow, openCol); } // does this board equal y? @@ -108,14 +117,27 @@ class Board { { if (y == null) return false; if (y.getClass() != this.getClass()) return false; - Board other = (Board) y; - if (d != other.dimension()) return false; + if (d != other.d) return false; for (int i = 0; i < d; i++) for (int j = 0; j < d; j++) - if (blocks[i][j] == other.blocks[i][j]) return true; - return false; + if (blocks[i][j] != other.blocks[i][j]) return false; + return true; + } + + private Board move(int rowDelta, int colDelta) + { + byte [][]bytes = copy(); + + int or = openRow + rowDelta; + int oc = openCol + colDelta; + + byte tmp = bytes[openRow][openCol]; + bytes[openRow][openCol] = bytes[or][oc]; + bytes[or][oc] = tmp; + + return new Board(bytes, or, oc); } // all neighboring boards @@ -123,13 +145,13 @@ class Board { { Queue<Board> q = new Queue<Board>(); if (openRow != 0) - q.enqueue(swap(openRow, openCol, openRow - 1, openCol)); + q.enqueue(move(-1, 0)); if (openRow < d - 1) - q.enqueue(swap(openRow, openCol, openRow + 1, openCol)); + q.enqueue(move(1, 0)); if (openCol != 0) - q.enqueue(swap(openRow, openCol, openRow, openCol - 1)); + q.enqueue(move(0, -1)); if (openCol < d - 1) - q.enqueue(swap(openRow, openCol, openRow, openCol + 1)); + q.enqueue(move(0, 1)); return q; } @@ -137,17 +159,18 @@ class Board { // string representation of the board public String toString() { - String out = ""; + String out = d+"\n"; + // out += "open "+openRow+" "+openCol+"\n"; + // out += "goal "+(isGoal() ? "OK" : "KO")+"\n"; + // out += "hamming "+hamming()+"\n"; + // out += "manhattan "+manhattan()+"\n"; for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) out += " "+(int) blocks[i][j]; out += "\n"; } - // out += "goal "+(isGoal() ? "OK" : "KO")+"\n"; - // out += "hamming "+hamming()+"\n"; - // out += "manhattan "+manhattan()+"\n"; - return out; + return out; //.substring(0, out.length() - 1); } } |