Class State :
import java.util.Arrays;
public class State {
private int data[][];
public int[][] getData() {
return data;
}
public void setData(int[][] data) {
this.data = data;
}
public void swap(int row1, int col1, int row2, int col2){
int temp = this.data[row1][col1];
this.data[row1][col1] = this.data[row2][col2];
this.data[row2][col2] = temp;
}
public State copyState() {
int height = this.data.length;
int width = this.data[0].length;
int[][] temp = new int[height][width];
for (int i = 0; i < height; i++) {
for(int j=0; j< width; j++){
temp[i][j] = this.data[i][j];
}
}
State target = new State(temp);
return target;
}
public State(int[][] data) {
super();
this.data = data;
}
}
Class Node :
public class Node {
private State state;
private Node parent;
private ArrayList<Node> children;
public Node(State state){
this.state = state;
parent = null;
children = new ArrayList<>();
}
public State getState() {
return state;
}
public void setState(State state) {
this.state = state;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public ArrayList<Node> getChildren() {
return children;
}
public void addChild(Node node){
node.setParent(this);
this.children.add(node);
}
public ArrayList<Node> returnSuccessor(){ // generate all possible moves(has been tested - work well)
ArrayList<Node> result = new ArrayList<>();
int[][] matrix = this.getState().getData();
int row = matrix.length;
int col = matrix[0].length;
int rowX = 0;
int colX = 0;
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if ( matrix[i][j] == 0) {
rowX = i;
colX = j;
}
}
}
if( (colX-1) >= 0 ){
State temp = this.getState().copyState();
temp.swap(rowX, colX, rowX, colX-1);
Node left = new Node(temp);
result.add(left);
}
if ( (colX+1) < col ){
State temp = this.getState().copyState();
temp.swap(rowX, colX, rowX, colX+1);
Node right = new Node(temp);
result.add(right);
}
if ( (rowX-1) >= 0 ){
State temp = this.getState().copyState();
temp.swap(rowX, colX, rowX-1, colX);
Node top = new Node(temp);
result.add(top);
}
if ( (rowX+1) < row ){
State temp = this.getState().copyState();
temp.swap(rowX, colX, rowX+1, colX);
Node down = new Node(temp);
result.add(down);
}
return result;
}
public void printState(){
System.out.println(Arrays.deepToString(this.getState().getData()));
}
public boolean equal(Node node){ // check whether 2 nodes are the same
return Arrays.deepEquals(this.getState().getData(), node.getState().getData());
}
public boolean checkTree(Node node){ // check whether a node has been added into the tree or not
if (this.equal(node)) {
return true;
}
ArrayList<Node> children = this.getChildren();
boolean result = false;
if (children.size() > 0){
for(int i=0; result == false && i< children.size(); i++){
result = children.get(i).checkTree(node);
}
}
return result;
}
}
Class main :
public class main {
public static void BFS(Node root, Node goal) throws InterruptedException{
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while(queue.size()>0){
Node temp = queue.poll();
if (temp.equal(goal)) {
goal.setParent(temp.getParent());
break;
}
else{
ArrayList<Node> successor = temp.returnSuccessor();
for(int i=0; i< successor.size(); i++){
boolean check = root.checkTree(successor.get(i));
if (check == false){
queue.add(successor.get(i));
temp.addChild(successor.get(i));
}
}
}
}
}
public static void main(String[] args) throws InterruptedException {
int[][] initialState = { {2,1}, {3,0} };
int[][] goalState = { {0,1}, {2,3} };
Node root = new Node(new State(initialState));
Node goal = new Node(new State(goalState));
BFS(root,goal);
Node temp = goal;
if(temp.getParent() == null){
System.out.println("There is no such a way to go from the initial state to the goal state");
}
else{
ArrayList<Node> listSteps = new ArrayList<>();
while(temp != null){
listSteps.add(temp);
temp = temp.getParent();
}
for (int i=listSteps.size()-1; i>=0; i--){
listSteps.get(i).printState();
Thread.sleep(1000);
}
int numSteps = listSteps.size()-1;
System.out.println("Number of steps: " + numSteps);
}
}
I want to find the shortest path from the initial state to the goal state ( nearly the same as an n-puzzle game )
When I try running my program with a 2x2 size puzzle as an input, it works well.
For example with input :
int[][] initialState = { {2,1}, {3,0} };
int[][] goalState = { {0,1}, {2,3} };
The result will be:
[[2, 1], [3, 0]]
[[2, 1], [0, 3]]
[[0, 1], [2, 3]]
Number of steps: 2
However, it has an infinite loop with an nxn size(n>2)
Sample input:
int[][] initialState = { {7,2,4}, {5,0,6}, {8,3,1} };
int[][] goalState = { {0,1,2}, {3,4,5}, {6,7,8} };
It keeps adding nodes into the queue in DFS method
It makes me confused because the method checkTree in class Node has been written with the purpose to avoid loops which may happen when generating the states.
Can somebody figure out what my mistake is?
Back