Algorithms-I : 4-puzzle: rewrite the way swap is done in Board

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);
     }
 }