8-puzzle puzzler!

[viphilar]

Hello all -

I am writing a Depth First Search program in java for the eight puzzle problem. I have completed the coding but for some reason I am not able to print the exact depth at which nodes are being searched. Here is two of the methods that does majority of the processing in my code:

This code is the main function which has a hash table (closedList) that holds all the nodes that have been visited. The openList Stack class object holds all the nodes that currently need to be expanded.
The given criteria is that the traversals have to be done strictly in the UP, LEFT, RIGHT and DOWN directions. In DFS, calling the functions up(), left(), right() and down() in reverse directions will help me in getting the desired output.

The functions down(), right(), left() and up(), call the addNewNode() function to add the newly created nodes into the openList stack so that the nodes can be traversed by popping out elements.

I am pointing to the following line:

System.out.print(", depth: " + storeDepth);

Can someone please help me out?

    poppedNode = state;
    addNewNode(state, 0);
    closedList.put(poppedNode, 0);

    while (!openList.isEmpty())
    {   
        poppedNode = openList.pop();
        linearList.add(poppedNode);

        if(!closedList.containsKey(poppedNode)) 
            closedList.put(poppedNode, storeDepth);

        int nodeSearched = closedList.size()-1; 

        if ((verbosity == 0) || (nodeSearched%verbosity == 0))
        {
            System.out.print("{time: " +time);
            System.out.print(", depth: " + storeDepth);
            System.out.print(", nodes searched: " + nodeSearched);      
            System.out.print(", current: " + "\"");
            for (int i=0; i<poppedNode.length(); i++)
                System.out.print(poppedNode.substring(i,i+1) + ",");
            System.out.println("\"}");
        }

        if(poppedNode.equals(goalNode)) 
            goal(linearList);

        down(poppedNode);
        right(poppedNode);
        left(poppedNode);
        up(poppedNode);
    }


void addNewNode(String newStr, int depth)
{                           
    // If duplicate node, then return without adding
    if(closedList.containsKey(newStr))
        return;

    openList.add(newStr);
    storeDepth = depth;
}

[JamesCherrill]

Just before starting the search, create a "global" int depth = 0;
Increment it in the "down" method and decrement it in the "up" method.

[rahmet]

here is my answer for your puzzle
compile all this classes I send to you and you will si the result

import javax.swing.*;
import java.awt.event.*;
/** PuzzleButton implements a button controller for a puzzle game */
public class CalcButton extends JButton implements ActionListener
{ private SlidePuzzleBoard puzzle; // address of the SlidePuzzle model
private Calculator view; // address of Frame that displays this button
/** Constructor PuzzleButton builds the button
* @param my puzzle - the address of the puzzle model object
* @param my view - the address of the puzzle's view */
public CalcButton(SlidePuzzleBoard my_puzzle, Calculator my_view)
{ super(""); // set label to nothing, but this will be repainted by the view
puzzle = my_puzzle;
view = my_view;
addActionListener(this);
}
/** actionPerformed processes a move of the slide puzzle */
public void actionPerformed(ActionEvent evt)
{ String s = getText(); // get the number on the face of this button
if ( !s.equals("") ) // it's not the blank space, is it?
{ boolean ok = puzzle.move(new Integer(s).intValue()); // try to move
if ( ok ) { view.update(); }
}
}
}



import java.awt.*; import javax.swing.*;
import java.awt.event.*;
/** PuzzleFrame shows a slide puzzle */
public class Calculator extends JFrame
{ 
private CalcButton[][] button; // the buttons on the face of the view
private SlidePuzzleBoard board;

private JLabel label = new JLabel("res = 0");

public Calculator(int board_size, SlidePuzzleBoard b)
{

button = new CalcButton[3][3];
Container cp = getContentPane();

JPanel p1 = new JPanel(new FlowLayout());
p1.add(label);
cp.add(p1, BorderLayout.NORTH);
JPanel p2 = new JPanel(new GridLayout(3, 3));


//cp.setLayout(new GridLayout(size, size));
// create the button-controllers and insert them into the layout:
for ( int i = 0; i != 3; i = i+1 )
{ for ( int j = 0; j != 3; j = j+1 )
{ button[i][j] = new CalcButton(board, this);
p2.add(button[i][j]);
}
}

cp.add(p2, BorderLayout.CENTER);

update(); // initialize the pieces with their numbers
//addWindowListener(new ExitController()); // activates X-button; see Fig. 15
setTitle("Calculator");
setSize(200, 300);
setVisible(true);
}
/** update consults the model and repaints each button */
public void update()
{ 
int k=0;
//PuzzlePiece[][] r = board.contents(); // get contents of the puzzle
for ( int i = 0; i != 3; i = i+1 ) // redraw the faces of the buttons
{ for ( int j = 0; j != 3; j = j+1 )
{ 
{ 
button[i][j].setBackground(Color.white);
button[i][j].setText("" + k); 
k++;
}
}
}
}
}



public class CalculatorTest
{ public static void main(String[] args)
{ int size = 3; // a 4 x 4 slide puzzle
   SlidePuzzleBoard board = new SlidePuzzleBoard(size); 
  Calculator cc=new Calculator( size,board);
}
}


class Counter
{ private int count; // the count
/** Constructor Counter initializes the counter
* @param start - the starting value for the count */
public Counter(int start)
{ count = start; }
/** increment updates count. */
public void increment()
{ count = count + 1; }
/** countOf accesses count.
* @return the value of count */
public void decrement()
{ count = count - 1; }



public int countOf()
{ return count; }
}

/** example of button's table - rebus*/
public class Puzzle
{ public static void main(String[] args)
{ int size = 4; // a 4 x 4 slide puzzle
SlidePuzzleBoard board = new SlidePuzzleBoard(size); // see Fig. 10, Ch. 8
PuzzleFrame frame = new PuzzleFrame(size, board);
}
}


public class Puzzle1
{ public static void main(String[] args)
{ int size = 4; // a 4 x 4 slide puzzle
Counter c=new Counter(0);
SlidePuzzleBoard1 board = new SlidePuzzleBoard1(size); 
PuzzleFrame1 frame = new PuzzleFrame1(size, board, c);
}
}

import javax.swing.*;
import java.awt.event.*;
/** PuzzleButton implements a button controller for a puzzle game */
public class PuzzleButton extends JButton implements ActionListener
{ private SlidePuzzleBoard puzzle; // address of the SlidePuzzle model
private PuzzleFrame view; // address of Frame that displays this button
/** Constructor PuzzleButton builds the button
* @param my puzzle - the address of the puzzle model object
* @param my view - the address of the puzzle's view */
public PuzzleButton(SlidePuzzleBoard my_puzzle, PuzzleFrame my_view)
{ super(""); // set label to nothing, but this will be repainted by the view
puzzle = my_puzzle;
view = my_view;
addActionListener(this);
}
/** actionPerformed processes a move of the slide puzzle */
public void actionPerformed(ActionEvent evt)
{ String s = getText(); // get the number on the face of this button
if ( !s.equals("") ) // it's not the blank space, is it?
{ boolean ok = puzzle.move(new Integer(s).intValue()); // try to move
if ( ok ) { view.update(); }
}
}
}



import javax.swing.*;
import java.awt.event.*;

public class PuzzleButton1 extends JButton implements ActionListener { 
    private SlidePuzzleBoard1 puzzle; // address of the SlidePuzzle model
    private PuzzleFrame1 view; // address of Frame that displays this button
    private Counter model;

public PuzzleButton1(SlidePuzzleBoard1 my_puzzle, PuzzleFrame1 my_view ,Counter c) { 
    super(""); // set label to nothing, but this will be repainted by the view
    puzzle = my_puzzle;
    view = my_view;
    model =c;
    addActionListener(this);
}

public void actionPerformed(ActionEvent evt)
{ 
    String s = getText(); // get the number on the face of this button
    if ( !s.equals("") ) // it's not the blank space, is it?
    { boolean ok = puzzle.move(new Integer(s).intValue()); // try to move
    if ( ok ) { model.increment(); view.update(); }
    }
}

}


import java.awt.*; import javax.swing.*;
/** PuzzleFrame shows a slide puzzle */
public class PuzzleFrame extends JFrame
{ private SlidePuzzleBoard board; // the model; see Fig. 10, Ch. 8
private int size; // the board's size
private int button_size = 60; // width/height of each button
private PuzzleButton[][] button; // the buttons on the face of the view

private JLabel label = new JLabel("count = 0");

/** Constructor PuzzleFrame builds the view
* @param board size - the width and depth of the puzzle
* @param b - the model, a slide puzzle board */
public PuzzleFrame(int board_size, SlidePuzzleBoard b)
{ size = board_size;
board = b;
button = new PuzzleButton[size][size];
Container cp = getContentPane();


cp.setLayout(new GridLayout(size, size));
// create the button-controllers and insert them into the layout:
for ( int i = 0; i != size; i = i+1 )
{ for ( int j = 0; j != size; j = j+1 )
{ button[i][j] = new PuzzleButton(board, this);
cp.add(button[i][j]);
}
}


update(); // initialize the pieces with their numbers
//addWindowListener(new ExitController()); // activates X-button; see Fig. 15
setTitle("PuzzleFrame");
setSize(size * button_size + 10, size * button_size + 20);
setVisible(true);
}
/** update consults the model and repaints each button */
public void update()
{ PuzzlePiece[][] r = board.contents(); // get contents of the puzzle
for ( int i = 0; i != size; i = i+1 ) // redraw the faces of the buttons
{ for ( int j = 0; j != size; j = j+1 )
{ if ( r[i][j] != null )
{ button[i][j].setBackground(Color.white);
button[i][j].setText("" + r[i][j].valueOf()); }
else { button[i][j].setBackground(Color.black);
button[i][j].setText( "" );
}
}
}
}
}


import java.awt.*; import javax.swing.*;

public class PuzzleFrame1 extends JFrame { 
    private SlidePuzzleBoard1 board; // the model; see Fig. 10, Ch. 8
    private int size; // the board's size
    private int button_size = 60; // width/height of each button
    private PuzzleButton1[][] button; // the buttons on the face of the view

    private JLabel label = new JLabel("count = 0");
    private Counter count;

    public PuzzleFrame1(int board_size, SlidePuzzleBoard1 b, Counter c) { 
        size = board_size;
        board = b;
        count = c;
        button = new PuzzleButton1[size][size];
        Container cp = getContentPane();

        JPanel p1 = new JPanel(new FlowLayout());
        p1.add(label);
        cp.add(p1, BorderLayout.NORTH);
        JPanel p2 = new JPanel(new GridLayout(size, size));


        //cp.setLayout(new GridLayout(size, size));
        // create the button-controllers and insert them into the layout:
        for ( int i = 0; i != size; i = i+1 )
        { for ( int j = 0; j != size; j = j+1 )
            { button[i][j] = new PuzzleButton1(board, this, count);
            p2.add(button[i][j]);
            }
        }

        cp.add(p2, BorderLayout.CENTER);

        update(); // initialize the pieces with their numbers
        //addWindowListener(new ExitController()); // activates X-button; see Fig. 15
        setTitle("PuzzleFrame");
        setSize(size * button_size + 10, size * button_size + 20);
        setVisible(true);
}

public void update() { 

    label.setText("count = " + count.countOf());

    PuzzlePiece[][] r = board.contents(); // get contents of the puzzle
    for ( int i = 0; i != size; i = i+1 ) // redraw the faces of the buttons
    { for ( int j = 0; j != size; j = j+1 )
        { if ( r[i][j] != null )
        { button[i][j].setBackground(Color.white);
        button[i][j].setText("" + r[i][j].valueOf()); }
        else { button[i][j].setBackground(Color.black);
        button[i][j].setText( "" );
        }
        }
    }
    }
}


/** PuzzlePiece defines a slide-puzzle playing piece */
public class PuzzlePiece
{ private int face_value; // the value written on the piece's face
/** Constructor PuzzlePiece creates a piece
* @param value - the value that appears on the face of the piece */
public PuzzlePiece(int value)
{ face_value = value; }
/** valueOf returns the face value of the piece */
public int valueOf()
{ return face_value; }
}


/** SlidePuzzleBoard models a slide puzzle. */
public class SlidePuzzleBoard
{ private int size; // the board's size
private PuzzlePiece[][] board; // the array that holds the pieces
// one position on the board must be an empty space:
private int empty_row;
private int empty_col;
// representation invariant: board[empty row][empty col] == null
/** Constructor SlidePuzzleBoard constructs the initial puzzle, which has
* the pieces arranged in descending numerical order.
* @param s - the size of the puzzle, a positive integer (e.g., s==4 means
* the puzzle is 4 x 4 and will have pieces numbered 15, 14, ..., 1) */
public SlidePuzzleBoard(int s)
{ size = s;
board = new PuzzlePiece[size][size];
// create the individual pieces and place on the board in reverse order:
for ( int num = 1; num != size * size; num = num + 1 )
{ PuzzlePiece p = new PuzzlePiece(num);
int row = num / size;
int col = num % size;
// set p in a ``reversed position'' on the board:
board[size - 1 - row][size - 1 - col] = p;
}
// remember the location on the board where initially there is no piece:
empty_row = size - 1;
empty_col = size - 1;
}
/** contents returns the current state of the puzzle
* @return a matrix that contains the addresses of the pieces */
public PuzzlePiece[][] contents()
{ PuzzlePiece[][] answer = new PuzzlePiece[size][size];
for ( int i = 0; i != size; i = i + 1 )
{ for ( int j = 0; j != size; j = j + 1 )
{ answer[i][j] = board[i][j]; }
}
return answer;
}

/** move moves a piece into the blank space, provided it is a legal move.
* @param w - the face value of the piece that one wishes to move
* @return true, if the piece labelled w was moved into the empty space;
* return false if the piece cannot be moved into the empty space */
public boolean move(int w)
{ int NOT_FOUND = -1;
int row = NOT_FOUND; // row and col will remember where piece w lives
int col = NOT_FOUND;
// try to find w adjacent to the empty space on the board:
if ( found(w, empty_row - 1, empty_col) )
{ row = empty_row - 1;
col = empty_col;
}
else if ( found(w, empty_row + 1, empty_col) )
{ row = empty_row + 1;
col = empty_col;
}
else if ( found(w, empty_row, empty_col - 1) )
{ row = empty_row;
col = empty_col - 1;
}
else if ( found(w, empty_row, empty_col + 1) )
{ row = empty_row;
col = empty_col + 1;
}
if ( row != NOT_FOUND )
{ // move the piece into the empty space:
board[empty_row][empty_col] = board[row][col];
// mark the new empty space on board:
empty_row = row;
empty_col = col;
board[empty_row][empty_col] = null;
}
return row != NOT_FOUND;
}
/** found returns whether the piece at position row, col is labeled v */
private boolean found(int v, int row, int col)
{ boolean answer = false;
if ( row >= 0 && row < size && col >= 0 && col < size )
{ answer = ( board[row][col].valueOf() == v ); }
return answer;
}
}




public class SlidePuzzleBoard1 { 
    private int size; // the board's size
    private PuzzlePiece[][] board; // the array that holds the pieces
    // one position on the board must be an empty space:
    private int empty_row;
    private int empty_col;
    // representation invariant: board[empty row][empty col] == null
/** Constructor SlidePuzzleBoard constructs the initial puzzle, which has
* the pieces arranged in descending numerical order.
* @param s - the size of the puzzle, a positive integer (e.g., s==4 means
* the puzzle is 4 x 4 and will have pieces numbered 15, 14, ..., 1) */
public SlidePuzzleBoard1(int s) { 
    size = s;
    board = new PuzzlePiece[size][size];
    // create the individual pieces and place on the board in reverse order:
    for ( int num = 1; num != size * size; num = num + 1 )
    { PuzzlePiece p = new PuzzlePiece(num);
    int row = num / size;
    int col = num % size;
    // set p in a ``reversed position'' on the board:
    board[size - 1 - row][size - 1 - col] = p;
    }
    // remember the location on the board where initially there is no piece:
    empty_row = size - 1;
    empty_col = size - 1;
}

/** contents returns the current state of the puzzle
* @return a matrix that contains the addresses of the pieces */
public PuzzlePiece[][] contents() { 
    PuzzlePiece[][] answer = new PuzzlePiece[size][size];
    for ( int i = 0; i != size; i = i + 1 )
    { for ( int j = 0; j != size; j = j + 1 )
    { answer[i][j] = board[i][j]; }
    }
    return answer;
}

/** move moves a piece into the blank space, provided it is a legal move.
* @param w - the face value of the piece that one wishes to move
* @return true, if the piece labelled w was moved into the empty space;
* return false if the piece cannot be moved into the empty space */
public boolean move(int w) { 
    int NOT_FOUND = -1;
    int row = NOT_FOUND; // row and col will remember where piece w lives
    int col = NOT_FOUND;
    // try to find w adjacent to the empty space on the board:
    if ( found(w, empty_row - 1, empty_col) )
    { row = empty_row - 1;
    col = empty_col;
    }
    else if ( found(w, empty_row + 1, empty_col) )
    { row = empty_row + 1;
    col = empty_col;
    }
    else if ( found(w, empty_row, empty_col - 1) )
    { row = empty_row;
    col = empty_col - 1;
    }
    else if ( found(w, empty_row, empty_col + 1) )
    { row = empty_row;
    col = empty_col + 1;
    }
    if ( row != NOT_FOUND )
    { // move the piece into the empty space:
    board[empty_row][empty_col] = board[row][col];
    // mark the new empty space on board:
    empty_row = row;
    empty_col = col;
    board[empty_row][empty_col] = null;
    }
    return row != NOT_FOUND;
}

/** found returns whether the piece at position row, col is labeled v */
private boolean found(int v, int row, int col) { 
    boolean answer = false;
    if ( row >= 0 && row < size && col >= 0 && col < size )
    { answer = ( board[row][col].valueOf() == v ); }
    return answer;
    }
}

[viphilar]

Thanks a lot both of you. I found another way of finding the right depth. I created a separate class that held parent, child and its corresponding depth and manipulated (incremented/decremented depth by one) this structure whenever an up, down, left or right function was called.

Cheers!
Vik.

[taimoor18]

The functions down(), right(), left() and up(), call the addNewNode() function to add the newly created nodes into the openList stack so that the nodes can be traversed by popping out elements.

I am pointing to the following line:

System.out.print(", depth: " + storeDepth);

Can someone please help me out?

poppedNode = state;
addNewNode(state, 0);
closedList.put(poppedNode, 0);

while (!openList.isEmpty())
{ 
poppedNode = openList.pop();
linearList.add(poppedNode);

if(!closedList.containsKey(poppedNode)) 
closedList.put(poppedNode, storeDepth);

int nodeSearched = closedList.size()-1; 

if ((verbosity == 0) || (nodeSearched%verbosity == 0))
{
System.out.print("{time: " +time);
System.out.print(", depth: " + storeDepth);
System.out.print(", nodes searched: " + nodeSearched); 
System.out.print(", current: " + "\"");
for (int i=0; i<poppedNode.length(); i++)
System.out.print(poppedNode.substring(i,i+1) + ",");
System.out.println("\"}");
}

if(poppedNode.equals(goalNode)) 
goal(linearList);

down(poppedNode);
right(poppedNode);
left(poppedNode);
up(poppedNode);
}


void addNewNode(String newStr, int depth)
{ 
// If duplicate node, then return without adding
if(closedList.containsKey(newStr))
return;

openList.add(newStr);
storeDepth = depth;
}

[maxbummber]

Could I see the complete code?

[JamesCherrill]

From 3-4 years ago? Seems unlikely.

[maxbummber]

Easy peasy, depends on the person if they keep evidence.