8-puzzle problem

Modify the program code BFS, and change the original 3x3 puzzle into a 4x4 version.

BFS.java:

import java.util.ArrayList;

import java.util.HashSet;

import java.util.LinkedList;

import java.util.Queue;

public class BFS

{

public static void main(String[] args)

{

Queue queue = new LinkedList();

Config.generatedBoard = new HashSet();

Config.solutionPath = new ArrayList();

Node root = new Node();

root.genRandBoard();

root.printBoard();

Config.generatedBoard.add(root.hashBoard(root.board));

queue.add(root);

while(queue.size() > 0)

{

Node n = queue.poll();

n.genChildren();

for (int i=0; i

{

if (isEndGame(n.children.get(i)))

{

findSolution(n.children.get(i));

printSolution();

return;

}

else

{

queue.add(n.children.get(i));

}

}

}

System.out.println("No solution");

}

private static void printSolution() {

System.out.println("Solution:");

for (int i=Config.solutionPath.size()-2; i>=0; i--)

{

Config.solutionPath.get(i).printBoard();

System.out.println();

}

System.out.println("Total " + (Config.solutionPath.size()-1) + " steps");

}

private static void findSolution(Node node) {

Config.solutionPath.add(node);

if (node.parent != null)

{

findSolution(node.parent);

}

}

private static boolean isEndGame(Node node) {

if (node.isGoalBoard())

{

return true;

}

return false;

}

}

Node.java:

import java.util.ArrayList;

class Node

{

Node parent = null;

ArrayList children = new ArrayList();

int[][] board = new int[3][3];

Move move = null;

public int genChildren()

{

Move emptyCell = searchEmptyCell(board);

ArrayList neighbors = emptyCell.getAllNeighbors();

for (int i=0; i

{

Move m = neighbors.get(i);

Node newNode = new Node();

newNode.parent = this;

newNode.setBoard(board);

newNode.board = newNode.makeMove(m);

newNode.move = m;

if (!Config.generatedBoard.contains(newNode.hashBoard()))

{

children.add(newNode);

Config.generatedBoard.add(newNode.hashBoard());

}

}

return children.size();

}

public int[][] makeMove(Move m)

{

int[][] resultBoard = new int[3][3];

for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

resultBoard[i][j] = board[i][j];

}

}

for (int i=0; i<4; i++)

{

Move nb = m.getNeighbor(i);

if (nb != null)

{

int nb_x = nb.getX();

int nb_y = nb.getY();

if (nb_x >= 0 && nb_x <= 2 && nb_y >= 0 && nb_y <= 2)

{

if (resultBoard[nb_x][nb_y] == 0)

{

resultBoard[nb_x][nb_y] = resultBoard[m.getX()][m.getY()];

resultBoard[m.getX()][m.getY()] = 0;

break;

}

}

}

}

return resultBoard;

}

public boolean isGoalBoard()

{

boolean ans = true;

L1: for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

if (board[i][j] != Config.GOALBOARD[i][j])

{

ans = false;

break L1;

}

}

}

return ans;

}

public void genRandBoard()

{

ArrayList numbers = new ArrayList();

for (int i=0; i<=8; i++)

{

numbers.add(i);

}

for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

int index = (int) (Math.random() * numbers.size());

board[i][j] = numbers.get(index);

numbers.remove(index);

}

}

}

public void setBoard(int[][] b)

{

for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

board[i][j] = b[i][j];

}

}

}

private static Move searchEmptyCell(int[][] b) {

Move m = null;

for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

if (b[i][j] == 0)

{

return new Move(i,j);

}

}

}

return m;

}

String hashBoard(int [][] b)

{

String code = "";

for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

code = code + b[i][j];

}

}

return code;

}

String hashBoard()

{

String code = "";

for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

code = code + board[i][j];

}

}

return code;

}

public void printBoard()

{

for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

System.out.print(board[i][j] + " ");

}

System.out.println();

}

}

public void printBoard(int[][] b)

{

for (int i=0; i<3; i++)

{

for (int j=0; j<3; j++)

{

System.out.print(b[i][j] + " ");

}

System.out.println();

}

}

}