java - AI: Graph search and A* implementation with Manhattan Heuristic -

this project ai course @ university of florence. have solve classic game: sliding puzzle 8 , 15 cell. implementation of general graph search algorithm:

public abstract class graphsearch implements searchalgorithm {  protected queue<node> fringe; protected hashset<node> closedlist;  public graphsearch() {     fringe = createfringe();     closedlist = new hashset<node>(100); }  protected abstract queue<node> createfringe();  public int getnodeexpanded() {     return closedlist.size(); }  @override public solution search(puzzle puzzle) {     fringe.add(new node(puzzle.getinitialstate(), null, null));     while (!fringe.isempty()) {         node selectednode = fringe.poll();         if (puzzle.getgoaltest().isgoalstate(selectednode.getstate())) {             return new solution(selectednode, getnodeexpanded());         }         closedlist.add(selectednode);         linkedlist<node> expansion = selectednode.expandnode();         (node n : expansion) {             if (!closedlist.contains(n) && !fringe.contains(n))                 fringe.add(n);         }     }     return new solution(null, getnodeexpanded()); }  } 

this a* code:

public class astar extends graphsearch implements informedsearch {  private heuristic heuristic;  public astar(heuristic heuristic) {     setheuristic(heuristic); }  public heuristic getheuristic() {     return heuristic; }  @override public void setheuristic(heuristic heuristic) {     this.heuristic = heuristic; }  @override protected queue<node> createfringe() {     return new priorityqueue<node>(1000, new comparator<node>() {          @override         public int compare(node o1, node o2) {             o1.seth(heuristic.h(o1));             o2.seth(heuristic.h(o2));             o1.setf(o1.getg() + o1.geth());             o2.setf(o2.getg() + o2.geth());             if (o1.getf() < o2.getf())                 return -1;             if (o1.getf() > o2.getf())                 return 1;             return 0;         }     }); }  } 

and manhattan heuristic code:

    @override public int h(node n) {     int distance = 0;     arraylist<integer> board = n.getstate().getboard();     int[][] multiboard = new int[n][n];     (int = 0; < n; i++) {         (int j = 0; j < n; j++) {             multiboard[i][j] = board.get(i * n + j);         }     }     (int = 0; < n; i++) {         (int j = 0; j < n; j++) {             int value = multiboard[i][j];             if (multiboard[i][j] != 0) {                 int targetx = (value - 1) / n;                 int targety = (value - 1) % n;                 distance += math.abs(i - targetx) + math.abs(j - targety);             }         }     }     return distance; } 

now, code works , found solution of puzzle (puzzle state array of n*n value , goalstate [1, 2, 3, 4, 5, 6, 7, 8, 9 ,0] (for n=3) blank cell = 0), comparing result other programs (same algorithm , same heuristic) program expands different number of nodes. think there problem in general graph search...any idea? :d thanks!!!

your heuristic calculation wrong. assume 9 located @ index 4 of board. calculate rowright value 3 instead of 2. result supoptimal performance of algorithm. row right calculation should be:

int rowright = (valuefound - 1) / n;