search - Java: Trouble when using BFS to find a shortest path -

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];     (int = 0; < 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 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 same     return arrays.deepequals(this.getstate().getdata(), node.getstate().getdata()); } public boolean checktree(node node){ // check whether node has been added 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 no such way go initial state goal state");     }     else{         arraylist<node> liststeps = new arraylist<>();         while(temp != null){             liststeps.add(temp);             temp = temp.getparent();     }         (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 find shortest path initial state goal state ( same n-puzzle game )

when try running program 2x2 size puzzle input, works well.

for example input :

int[][] initialstate = { {2,1}, {3,0} }; int[][] goalstate = { {0,1}, {2,3} }; 

the result be:

[[2, 1], [3, 0]] [[2, 1], [0, 3]] [[0, 1], [2, 3]] number of steps: 2 

however, has infinite loop 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 queue in dfs method

it makes me confused because method checktree in class node has been written purpose avoid loops may happen when generate states.

can figure out mistake is?