Algorithms-I : 4-Puzzle: add skeleton Solver and implemented Board

2 files changed, 206 insertions, 0 deletions

diff --git a/Algorithms/Part-I/4-Puzzle/Board.java b/Algorithms/Part-I/4-Puzzle/Board.java
new file mode 100644
index 0000000..ffc8a7a
--- /dev/null
+++ b/Algorithms/Part-I/4-Puzzle/Board.java
@@ -0,0 +1,153 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+class Board {
+
+    private int d;
+    private byte[][] blocks;
+    private int openRow;
+    private int openCol;
+
+    private Board(byte[][] blocks, int openI, int openJ)
+    {
+        this.d = blocks[0].length;
+        this.blocks = blocks;
+        this.openRow = openI;
+        this.openCol = openJ;
+    }
+
+    // construct a board from an N-by-N array of blocks
+    // (where blocks[i][j] = block in row i, column j)
+    public Board(int[][] blocks)
+    {
+
+        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];
+    }
+
+    // board dimension N
+    public int dimension()
+    {
+        return d;
+    }
+
+    // number of blocks out of place
+    public int hamming()
+    {
+        int k = 1;
+        int hamming = 0;
+
+        for (int i = 0; i < d; i++)
+            for (int j = 0; j < d; j++, k++)
+                if (blocks[i][j] != 0 && blocks[i][j] != k) hamming += 1;
+
+        return hamming;
+    }
+
+    // sum of Manhattan distances between blocks and goal
+    public int manhattan()
+    {
+        int manhattan = 0;
+
+        for (int i = 0; i < d; i++)
+            for (int j = 0; j < d; j++)
+            {
+                int v = blocks[i][j] -1;
+                if (v == -1) continue;
+                manhattan += Math.abs((v / d) - i) + Math.abs((v % d) - j);
+            }
+
+        return manhattan;
+    }
+
+    // is this board the goal board?
+    public boolean isGoal()
+    {
+        int k = 1;
+
+        if (blocks[d-1][d-1] != 0) return false;
+
+        for (int i = 0; i < d; i++)
+            for (int j = 0; j < d; j++)
+                if (blocks[i][j] != k++ && !((i == j) && (j == d - 1))) return false;
+
+        return true;
+    }
+
+    private Board swap(int r0, int c0, int r1, int c1)
+    {
+        byte[][] blocks2 = 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;
+
+        return new Board(blocks2, openRow, openCol);
+    }
+
+    // a board obtained by exchanging two adjacent blocks in the same row
+    public Board twin()
+    {
+        int row = 0;
+        if (openRow == 0) row = 1;
+
+        return swap(row, 0, row, 1);
+    }
+
+    // does this board equal y?
+    public boolean equals(Object y)
+    {
+        if (y == null) return false;
+        if (y.getClass() != this.getClass()) return false;
+
+        Board other = (Board) y;
+
+        if (d != other.dimension()) 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;
+    }
+
+    // all neighboring boards
+    public Iterable<Board> neighbors()
+    {
+        Queue<Board> q = new Queue<Board>();
+        if (openRow != 0)
+            q.enqueue(swap(openRow, openCol, openRow - 1, openCol));
+        if (openRow < d - 1)
+            q.enqueue(swap(openRow, openCol, openRow + 1, openCol));
+        if (openCol != 0)
+            q.enqueue(swap(openRow, openCol, openRow, openCol - 1));
+        if (openCol < d - 1)
+            q.enqueue(swap(openRow, openCol, openRow, openCol + 1));
+
+        return q;
+    }
+
+    // string representation of the board
+    public String toString()
+    {
+        String out = "";
+        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;
+    }
+}
+
diff --git a/Algorithms/Part-I/4-Puzzle/Solver.java b/Algorithms/Part-I/4-Puzzle/Solver.java
new file mode 100644
index 0000000..1f96098
--- /dev/null
+++ b/Algorithms/Part-I/4-Puzzle/Solver.java
@@ -0,0 +1,53 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+public class Solver {
+
+    // find a solution to the initial board (using the A* algorithm)
+    public Solver(Board initial)
+    {
+        // use MinPQ
+    }
+
+    // is the initial board solvable?
+    public boolean isSolvable()
+    {
+        return false;
+    }
+
+    // min number of moves to solve initial board; -1 if no solution
+    public int moves()
+    {
+        return 0;
+    }
+
+    // sequence of boards in a shortest solution; null if no solution
+    public Iterable<Board> solution()
+    {
+        return null;
+    }
+
+    // solve a slider puzzle (given below)
+    public static void main(String[] args)
+    {
+        // create initial board from file
+        In in = new In(args[0]);
+        int N = in.readInt();
+        int[][] blocks = new int[N][N];
+        for (int i = 0; i < N; i++)
+            for (int j = 0; j < N; j++)
+                blocks[i][j] = in.readInt();
+        Board initial = new Board(blocks);
+
+        // solve the puzzle
+        Solver solver = new Solver(initial);
+
+        // print solution to standard output
+        if (!solver.isSolvable())
+            StdOut.println("No solution possible");
+        else {
+            StdOut.println("Minimum number of moves = " + solver.moves());
+            for (Board board : solver.solution())
+                StdOut.println(board);
+        }
+    }
+}