java - Breadth First Search algorithm gets stuck in infinite loop -
i trying implement breadth first search algorithm 8puzzle. somehow not able in `is(requiredstate(see))` condition search terminates. program gets stuck in infinite loop. have put repeating states in state prevent getting stuck in loop, somehow program still gets stuck in loop. board.java public class board { public int[] square = new int[9]; board() { for(int i=0;i<9;i++) { square[i]=8-i; square[8] = 0; } } int findblankpos() { for(int i=0;i<square.length;i++) { if(square[i]==0) { return i; } } return 9; } static int size() { return 9; } void moveblankup(int blankpos) { square[blankpos] = square[blankpos-3]; square[blankpos-3] = 0; } void moveblankdown(int blankpos) { square[blankpos] = square[blankpos+3]; square[blankpos+3] = 0; } void moveblankright(int blankpos) { square[blankpos] = square[blankpos+1]; square[blankpos+1] = 0; } void moveblankleft(int blankpos) { square[blankpos] = square[blankpos-1]; square[blankpos-1] = 0; } boolean canmoveup(int blankpos) { if((blankpos==0)||(blankpos==1)||(blankpos==2)) return false; else return true; } boolean canmovedown(int blankpos) { if((blankpos==6)||(blankpos==7)||(blankpos==8)) return false; else return true; } boolean canmoveright(int blankpos) { if((blankpos==2)||(blankpos==5)||(blankpos==8)) return false; else return true; } boolean canmoveleft(int blankpos) { if((blankpos==0)||(blankpos==3)||(blankpos==6)) return false; else return true; } void display() { for(int i=0;i<square.length;i++) { if((i)%3==0) { system.out.println(); } system.out.print(square[i] + " "); } } integer getat(int pos) { return square[pos]; } void setat(int pos,int value) { square[pos] = value; } } puzzle.java import java.awt.list; import java.util.hashset; import java.util.linkedlist; import java.util.queue; import java.util.set; public class puzzle { public static void main(string[] args) { board b = new board(); set<board> set = new hashset<board>(); b.display(); queue<board> queue = new linkedlist<board>(); queue.add(b); /*b.setat(4,0); b.setat(8,4); b.display(); system.out.println(); addchildrentoqueue(queue,b);*/ //system.out.println(queue.); int itr=0; while(!queue.isempty()) { itr++; system.out.println(itr); board see = queue.peek(); //system.out.println(count); if(!(set.contains(see))) { set.add(see); //see.display(); //system.out.println(); if(isrequiredstate(see)) { queue.peek().display(); system.out.println("end bang"); break; } addchildrentoqueue(queue,queue.peek()); //system.out.println(queue.size()); if(itr==1) break; } queue.remove(); } //system.out.println(isrequiredstate(b)); } private static boolean isrequiredstate(board peek) { // todo auto-generated method stub string state=""; for(int i=0;i<peek.size();i++) { string temp = (string)peek.getat(i).tostring(); //system.out.println(temp); state = state + temp; } //system.out.println(state); if(state.equals("123456780")) { return true; } return false; } private static void addchildrentoqueue(queue<board> queue, board b) { // todo auto-generated method stub board d; if(b.canmoveup(b.findblankpos())) { d = getclone(b); d.moveblankup(b.findblankpos()); d.display(); system.out.println(); queue.add(d); } if(b.canmovedown(b.findblankpos())) { d = getclone(b); d.moveblankdown(b.findblankpos()); d.display(); system.out.println(); queue.add(d); } if(b.canmoveright(b.findblankpos())) { d = getclone(b); d.moveblankright(b.findblankpos()); d.display(); system.out.println(); queue.add(d); } if(b.canmoveleft(b.findblankpos())) { d = getclone(b); d.moveblankleft(b.findblankpos()); d.display(); system.out.println(); queue.add(d); } } static board getclone(board b) { board c = new board(); for(int i=0;i<c.size();i++) { c.setat(i,b.getat(i)); } return c; } } so how solved problem .as worked on problem found out when compared whether element checked in set or not,it compared address values not objects required , why unable come out of infinite loop because every time new address generated.hence instead of comparing objects using set,i created set of strings compared configuration of object stored strings , put in set.thanks lot making me find problem guyz..cheers!!!
import java.awt.list; import java.util.hashset; import java.util.linkedlist; import java.util.queue; import java.util.set; public class puzzle { public static void main(string[] args) { board b = new board(); set<string> set = new hashset<string>(); b.display(); queue<board> queue = new linkedlist<board>(); queue.add(b); /*b.setat(4,0); b.setat(8,4); b.display(); system.out.println(); addchildrentoqueue(queue,b);*/ //system.out.println(queue.); //int itr=0; while(!queue.isempty()) { //itr++; board see = queue.peek(); string check = getsequence(queue.peek()); //system.out.println(itr); //system.out.println(check); if(!(set.contains(check))) { set.add(check); //see.display(); //system.out.println(); if(isrequiredstate(see)) { queue.peek().display(); system.out.println("end bang"); break; } addchildrentoqueue(queue,queue.peek()); //system.out.println(queue.size()); } queue.remove(); } //system.out.println(isrequiredstate(b)); } private static boolean isrequiredstate(board peek) { // todo auto-generated method stub string state = getsequence(peek); //system.out.println(state); if(state.equals("123456780")) { return true; } return false; } private static string getsequence(board peek) { // todo auto-generated method stub string state=""; for(int i=0;i<peek.size();i++) { string temp = (string)peek.getat(i).tostring(); //system.out.println(temp); state = state + temp; } return state; } private static void addchildrentoqueue(queue<board> queue, board b) { // todo auto-generated method stub board d; if(b.canmoveup(b.findblankpos())) { d = getclone(b); d.moveblankup(b.findblankpos()); d.display(); system.out.println(); queue.add(d); } if(b.canmovedown(b.findblankpos())) { d = getclone(b); d.moveblankdown(b.findblankpos()); d.display(); system.out.println(); queue.add(d); } if(b.canmoveright(b.findblankpos())) { d = getclone(b); d.moveblankright(b.findblankpos()); d.display(); system.out.println(); queue.add(d); } if(b.canmoveleft(b.findblankpos())) { d = getclone(b); d.moveblankleft(b.findblankpos()); d.display(); system.out.println(); queue.add(d); } } static board getclone(board b) { board c = new board(); for(int i=0;i<c.size();i++) { c.setat(i,b.getat(i)); } return c; } }
the problem using hashing data structure without implementing hashcode() consistent equals() pointed out in comments, here's suggestion use hashcode(): consider cells of board number 0 <= <= 8 top left bottom right.
@override public int hashcode() { int hashcode = 0; for(int = 0; < square.size; i++) { hashcode += (square[i] << (3 + % 2)*i); } } you'll end int crudely, still sensibly derives state of board relevant concerns, , consistent equals() checks whether cells of 2 boards being compared hold same value. make sure if implement equals() , hashcode(), consistently, means
a.equals(b) -> a.hashcode() == b.hashcode()
where -> logical implication.
Comments
Post a Comment