Databases
StackOverflow2013
Postsdbo
POJava 8-puzzle Depth first search issue with children nodes
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POJava 8-puzzle Depth first search issue with children nodes
    primarykey
    data
    text
    <p>I am creating a depth first search algorithm which will ultimately be able to solve a simple 8 puzzle. I am able to read in a file and a goal state and set these variables accordingly.</p> <p>The main issue i am receiving is that when i get the children of the current node being evaluated, i am getting 2 "empty" values in my 8 puzzle, and i am also getting an index out of bounds exception.</p> <p>In order to get a child node for a given parent, i first must make a valid move then update the state of the child node to reflect the results of the valid move.</p> <p>In order to perform a move, i check if it is do-able(if i move left will it still be within the bounds of the puzzle), see posted code.</p> <p>It functions correctly for the first 2 moves, left and down as it correctly print the expected result.</p> <p>Below is the output of my current codes execution, you can see it correctly moves left and down, then it starts encountering errors.</p> <pre><code> Start state: 120 345 678 after moving left 102 345 678 Parent: [[C@1b845568 after moving down 125 340 678 Parent: [[C@d032cf5 after moving left 102 340 678 Parent: [[C@d032cf5 after moving down 125 348 670 Parent: 125 340 678 after moving up 125 348 670 Parent: [[C@4b7c8f7f after moving left 125 304 670 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3 at dcs.aber.ac.uk.puzzle.PuzzleBoard.swapValues(PuzzleBoard.java:193) at dcs.aber.ac.uk.puzzle.PuzzleBoard.moveUp(PuzzleBoard.java:142) at dcs.aber.ac.uk.puzzle.DFSSolver.addChildren(DFSSolver.java:155) at dcs.aber.ac.uk.puzzle.DFSSolver.search(DFSSolver.java:85) at dcs.aber.ac.uk.puzzle.DFSSolver.&lt;init&gt;(DFSSolver.java:27) at dcs.aber.ac.uk.puzzle.Driver.main(Driver.java:86) </code></pre> <p>As you can see, after the first two the rest of the printed states are incorrect. I will post my code to show how i handle the swapping and updating of the board to see if you can identify where the complication arises.</p> <pre><code> public class Node { private Node parent; private char[][] state = new char[3][3]; private double cost; private double heurCost; private double funcCost; private int depth; public Node() { parent = null; } public Node(Node parent) { this.parent = parent; for(int i = 0; i &lt; 3; i++){ for(int j = 0; j&lt; 3; j++){ state[i][j] = parent.getState()[i][j]; } } } public void setParent(Node parent) { this.parent = parent; } public char[][] getState() { return state; } public char[][] copyState(){ char[][] a = new char[3][3]; for(int i = 0; i &lt; 3; i++){ for(int j = 0; j&lt; 3; j++){ a[i][j] = state[i][j]; } } return a; } } public class PuzzleBoard { private char[][] goalState; private char[][] currentBoard; private int emptyRow, emptyCol; private int outOfPlace; public PuzzleBoard(char[][] currentState, char[][] goal ){ this.setCurrentState(currentState); this.setGoalState(goal); trackEmptySqaure(); } public void setGoalState(char[][] goalState){ this.goalState = goalState; } public void setCurrentState(char[][] currentState){ this.currentBoard = currentState; } public char[][] getCurrentBoard() { return currentBoard; } public boolean checkIsGoal(char[][] board){ for(int i = 0; i &lt; 9; i ++){ for(int j = 0; j &lt; 3; j ++){ if(!(goalState[i][j] != (board[i][j]))){ return false; } } } return true; } public void trackEmptySqaure() { for(int i = 0; i &lt; 3; i ++){ for (int j = 0; j &lt; 3; j ++){ if(currentBoard[i][j] == '0'){ emptyCol = j; emptyRow = i; } } } } public int getemptyRow() { return emptyRow; } public int getemptyCol() { return emptyCol; } public Node moveLeft(Node parent){ currentBoard = parent.copyState(); Node result = new Node(parent); /* check you can move 'empty' left one space*/ if(getemptyCol() &gt; 0){ swapValues(result.getState(),emptyRow, emptyCol, 1); return result; } return null; } public Node moveDown(Node parent){ currentBoard = parent.copyState(); Node result = new Node(parent); /* check you can move 'empty' down one space*/ if(getemptyRow() &lt; 2){ swapValues(result.getState(),emptyRow, emptyCol,2); return result; } return null; } public Node moveUp(Node parent){ currentBoard = parent.getState(); Node result = new Node(parent); /* check you can move 'empty' up one space*/ if(getemptyRow() &gt; 0){ swapValues(result.getState(),emptyRow, emptyCol,2); return result; } return null; } public Node moveRight(Node parent){ currentBoard = parent.getState(); Node result = new Node(parent); /* check you can move 'empty' right one space*/ if(getemptyCol() &lt; 2){ swapValues(result.getState(),emptyRow, emptyCol,2); return result; } return null; } public void swapValues (char[][] c,int x, int y, int method){ char empty = '0'; char swapValue = '0'; // should never be kept as 0 if(method == 1){ // left swapValue= c[emptyRow][emptyCol -1]; c[emptyRow][emptyCol] = swapValue; c[emptyRow][emptyCol -1] = empty; trackEmptySqaure(); } else if(method == 2){ // down swapValue = c[emptyRow + 1][emptyCol]; c[emptyRow][emptyCol] = swapValue; c[emptyRow + 1][emptyCol] = empty; trackEmptySqaure(); } else if(method == 3){ // up swapValue = c[emptyRow -1][emptyCol]; c[emptyRow][emptyCol] = swapValue; c[emptyRow -1][emptyCol] = empty; trackEmptySqaure(); } else if(method == 4){// right swapValue = c[emptyRow][emptyCol + 1]; c[emptyRow][emptyCol] = swapValue; c[emptyRow ][emptyCol + 1] = empty; trackEmptySqaure(); } } public class DFSSolver { private ArrayList&lt;Node&gt; closed = new ArrayList&lt;Node&gt;(); private Stack&lt;Node&gt; open = new Stack&lt;Node&gt;(); private PuzzleBoard pb; private boolean solved; private int numberOfSteps; public DFSSolver(PuzzleBoard puzzle) { pb = puzzle; numberOfSteps = 0; solved = false; Node root = new Node(); root.setState(pb.getCurrentBoard()); addToOpen(root); checkIfSolved(root); search(); } public boolean inOpenList(Node n){ for(Node node: open){ if(node.equals(n)){ return true; } } return false; } public boolean inClosedList(Node n){ for(Node node: closed){ if(node.equals(n)){ return true; } } return false; } public void addToOpen(Node n){ open.push(n); } public void addToClosed(Node n){ closed.add(n); } public Node popOpen(){ return open.pop(); } public void removeFromClosed(Node n){ closed.remove(n); } public void search(){ while(!solved){ Node current = popOpen(); if(current != null){ if(!(inClosedList(current))){ // is it previously explored? checkIfSolved(current); addChildren(current); numberOfSteps++; } addToClosed(current); } } System.out.println("No of steps: " + numberOfSteps); } public void checkIfSolved(Node curr) { char[][] goal = pb.getGoal(); char[][] current = curr.getState(); for(int i = 0; i &lt; 3; i ++){ for(int j = 0; j &lt; 3; j ++){ char c = current[i][j]; char x = goal[i][j]; if(c != x){ return; } } } solved = true; } public void addChildren(Node parent){ Node newNode = new Node(parent); newNode = pb.moveLeft(parent); if(newNode != null){ System.out.println("Parent: " + parent.getState().toString()); System.out.println("atfer moving left"); System.out.println(newNode.toString()); addToOpen(newNode); } newNode = pb.moveDown(parent); if(newNode != null){ System.out.println("Parent: " + parent.getState().toString()); System.out.println("atfer moving down"); System.out.println(newNode.toString()); addToOpen(newNode); } newNode = pb.moveRight(parent); if(newNode != null){ System.out.println("Parent: " + parent.getState().toString()); System.out.println("atfer moving right"); System.out.println(newNode.toString()); addToOpen(newNode); } newNode = pb.moveUp(parent); if(newNode != null){ System.out.println("Parent:\n " + parent.toString()); System.out.println("atfer moving up"); System.out.println(newNode.toString()); addToOpen(newNode); } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USchris edwards
    1. USchris edwards
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POJava 8-puzzle Depth first search issue with children nodes
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POJava 8-puzzle Depth first search issue with children nodes
      1. This table or related slice is empty.
      1. VTUpMod
    1. COi can't find your `swapValues` method...
      singulars
      1. POJava 8-puzzle Depth first search issue with children nodes
      1. USEugen Halca
    2. CO@EugenHalca sorry about that, i have updated the source code.
      singulars
      1. POJava 8-puzzle Depth first search issue with children nodes
      1. USchris edwards
    3. COUse the debugger in your IDE to examine the values of the variables and you will certainly find out the bug.
      singulars
      1. POJava 8-puzzle Depth first search issue with children nodes
      1. USTarik
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload