* Puzzle 15 using Breadth First Search
*************************************************/
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class puzzle15 {
// Use of Queue Implemented using LinkedList for Storing all the Nodes in
// BFS.
Queue
// HashMap is used to ignore repeated nodes
Map
// String Buffer to print the series of number stored in queue. It will
// display the order in which
// the space is moved
StringBuffer strBuffer = new StringBuffer();
public static void main(String args[]) {
// Input the 15 Puzzle State as a String with 0 as the Blank Space
// The inputs are 1, 2, 3, 4, 5, 6 ,7, 8, 9, A, B, C D ,E ,F, 0
// Input can be hardcoded in the code or read from the text file.
// Currently I am storing the input file in
// E: drive. In file, provide inputs without space and comma. One input
// at a time
String strInput = "0123456789ABCDEF";
/******************* START Read Input from text file ******************************/
// File file = new File("E:\\Input.txt"); //Comment this line if reading
// from argument
//
// //To read input from console please uncomment below code and comment
// above line
// //File file = new File(args[0]);
// FileInputStream fis = null;
// BufferedInputStream bis = null;
// DataInputStream dis = null;
// String strLineData = "";
//
// try {
// fis = new FileInputStream(file);
//
// // Here BufferedInputStream is added for fast reading.
// bis = new BufferedInputStream(fis);
// dis = new DataInputStream(bis);
//
// // dis.available() returns 0 if the file does not have more lines.
// while (dis.available() != 0) {
// // this statement reads the line from the file and print it to
// // the console.
// strLineData = dis.readLine() + "";
//
// }
// strInput = strLineData;
//
// //dispose all the resources after using them.
// fis.close();
// bis.close();
// dis.close();
//
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// } catch (IOException e) {
// e.printStackTrace();
// }
/******************* END Read Input from text file ******************************/
puzzle15 objPuzzle15 = new puzzle15(); // New Instance of the puzzle15
objPuzzle15.add(strInput, 0); // Add the Initial State
try {
// Breadth First Search Logic
while (objPuzzle15.q.peek() != null) {
// Move the blank space up and add new state to queue
objPuzzle15.upPuzzle(objPuzzle15.q.peek());
// Move the blank space down
objPuzzle15.downPuzzle(objPuzzle15.q.peek());
// Move left
objPuzzle15.leftPuzzle(objPuzzle15.q.peek());
// Move right and remove the current node
objPuzzle15.rightPuzzle(objPuzzle15.q.remove());
// from Queue
}
} catch (Exception ex) {
System.out.println("Exception: " + ex);
}
System.out
.println("Solution doesn't exist for the given Puzzle 15 problem");
}
// Add method to add the new modified string to the Map and Queue
void add(String str, int n) {
if (!map.containsKey(str)) {
map.put(str, n);
q.add(str);
// strBuffer.append(str + "\n");
}
}
/*
* Each methods below takes current state as string and if possible, task of
* moving thr blank space i.e., "0" is done. Then new modified string is add
* to the map and queue. Once Goal state is reached, the execution will be
* terminated.
*/
void upPuzzle(String str) {
String s = "";
try {
int a = str.indexOf("0");
if (a > 3) {
s = str.substring(0, a - 4) + "0" + str.substring(a - 3, a)
+ str.charAt(a - 4) + str.substring(a + 1);
add(s, map.get(str) + 1);
if (s.equals("123456789ABCDEF0")) {
System.out.println("Solution exists at Level " + map.get(s)
+ " of the tree");
// System.out.println("Solution seq " + strBuffer);
System.exit(0);
}
}
} catch (Exception ex) {
System.out.println("Exception: " + ex.getLocalizedMessage()
+ " at level " + map.get(s) + " of the tree");
}
}
void downPuzzle(String str) {
String s = "";
try {
int a = str.indexOf("0");
if (a < 12) {
s = str.substring(0, a) + str.substring(a + 4, a + 5)
+ str.substring(a + 1, a + 4) + "0"
+ str.substring(a + 4);
add(s, map.get(str) + 1);
if (s.equals("123456789ABCDEF0")) {
System.out.println("Solution exists at Level " + map.get(s)
+ " of the tree");
// System.out.println("Solution seq " + strBuffer);
System.exit(0);
}
}
} catch (Exception ex) {
System.out.println("Exception: " + ex.getLocalizedMessage()
+ " at level " + map.get(s) + " of the tree");
}
}
void leftPuzzle(String str) {
String s = "";
try {
int a = str.indexOf("0");
if (a != 0 && a != 4 && a != 8 && a != 12) {
s = str.substring(0, a - 1) + "0" + str.charAt(a - 1)
+ str.substring(a + 1);
add(s, map.get(str) + 1);
if (s.equals("123456789ABCDEF0")) {
System.out.println("Solution exists at Level " + map.get(s)
+ " of the tree");
// System.out.println("Solution seq " + strBuffer);
System.exit(0);
}
}
} catch (Exception ex) {
System.out.println("Exception: " + ex.getLocalizedMessage()
+ " at level " + map.get(s) + " of the tree");
}
}
void rightPuzzle(String str) {
String s = "";
try {
int a = str.indexOf("0");
if (a != 3 && a != 7 && a != 11 && a != 15) {
s = str.substring(0, a) + str.charAt(a + 1) + "0"
+ str.substring(a + 2);
add(s, map.get(str) + 1);
if (s.equals("123456789ABCDEF0")) {
System.out.println("Solution exists at Level " + map.get(s)
+ " of the tree");
// System.out.println("Solution seq " + strBuffer);
System.exit(0);
}
}
} catch (Exception ex) {
System.out.println("Exception: " + ex.getLocalizedMessage()
+ " at level " + map.get(s) + " of the tree");
}
}
}
Posts
