From b8887c752e9553dd1f51bcc8fcc876810a7457fc Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Thu, 21 Mar 2013 13:04:31 +0100
Subject: Algorithms-I : 4-Puzzle: add skeleton Solver and implemented Board
---
Algorithms/Part-I/4-Puzzle/Board.java | 153 +++++++++++++++++++++++++++++++++
Algorithms/Part-I/4-Puzzle/Solver.java | 53 ++++++++++++
2 files changed, 206 insertions(+)
create mode 100644 Algorithms/Part-I/4-Puzzle/Board.java
create mode 100644 Algorithms/Part-I/4-Puzzle/Solver.java
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);
+ }
+ }
+}
--
cgit v1.1-2-g2b99