Results 1 to 13 of 13

Thread: N-Puzzle Help!

  1. #1
    evan42781 is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default N-Puzzle Help!

    Hey guys this is my first time posting here and I like the help you can get on this forum. So i need yall's help on a particular problem that I am having. Im going to go ahead and say this now this IS a HWK problem. So i am not asking for you to write my code or answer but I am asking for some kinda pseudo code or basic outline with my problem. What I am having trouble with is understanding how to take my single or double array (i can use either) to implement a BFS and a A* search on the N-puzzle. I have read multiple threads and articles on what these searches do but I dont understand is how are the trees created with possible moves and then how are they searched? Can someone help me? Here is what I have written so far.

    Java Code:
    import java.util.*;
    
    public class N_Puzzle
    {
    	public static void main(String[] args)
    	{
    		//This asks the user for what size puzzle do they want to solve. 
    		KeyboardInputClass PuzzleInput = new KeyboardInputClass();
    		int PuzzleSize;
    		PuzzleSize = PuzzleInput.getInteger(false, 8, 0, 36, "What size puzzle do you want to solve(ex: 8...15...24...35)");
    
    		//This Ask the user how many times they want to shuffle the board.
    		KeyboardInputClass ShuffleBoard = new KeyboardInputClass();
    		int NumberOfShuffles;
    		NumberOfShuffles = ShuffleBoard.getInteger(false, 0, 0, 1000, "How many times do you want to shuffle the board?");
    
    		//This creates a starting puzzle and goal board (dependent on size of puzzle) in a single array then converst both to a double array.
    		int[] Board = PuzzleSingleArray(PuzzleSize, NumberOfShuffles);
    		int[] GoalBoard = GoalState(PuzzleSize);
    		int[][] Board2D = PuzzleDoubleArray(PuzzleSize, Board);
    		int[][] GoalBoard2D = PuzzleDoubleArray(PuzzleSize, GoalBoard);
    
    		//This is the staring puzzle configration
    		PrintPuzzle(Board2D);
    		
    
    		//This ask the user what algotithum they want to preform. 
    		KeyboardInputClass TestInput = new KeyboardInputClass();
    		char TestMethod;
    		TestMethod = TestInput.getCharacter(true, 'b', "a" + "b", 0, "What Algoritum do you want to preform b = breadth-first or a = A*");
    
    		PrintPuzzle(GoalBoard2D);
    	}
    
    	public static int[] PuzzleSingleArray(int Size, int Shuffle)
    	{
    		int puzzle[] = new int[Size+1];  //this makes the size of the single array
    		int index;
    		int Shuffles = Shuffle;  //This is the input for number of shuffles
    
    		// Put all numbers into the array
    		for (index = 0; index <= Size; index++)
    			puzzle[index] = index;
    
    		// Make random numbers
    		for (int i = 0; i < Shuffles; i++)  //this for loop runs for the amount of times the user wanted to shuffle
    		{
    			for (index = 0; index < Size; index++)
    			{
    				int randomIndex = (int)Math.floor(Math.random() * Size);
    				int temp = puzzle[index];
    				puzzle[index] = puzzle[randomIndex];
    				puzzle[randomIndex] = temp;
    			}
    		}
    		return puzzle;
    	}
    
    	//load single aray into double array
    	public static int[][] PuzzleDoubleArray(int Size, int[] puzzle)
    	{
    		int[][] board = new int[1][1];
    		if (Size == 8)
    		{
    			board = new int[3][3];
    			int k = 0;
    			for (int i = 0; i < 3; i++)
    			{
    				for (int j = 0; j < 3; j++)
    				{
    					board[i][j] = puzzle[k];
    					k++;
    				}
    			}
    			return board;
    		}
    		else if (Size == 15)
    		{
    			board = new int[4][4];
    			int k = 0;
    			for (int i = 0; i < 4; i++)
    			{
    				for (int j = 0; j < 4; j++)
    				{
    					board[i][j] = puzzle[k];
    					k++;
    				}
    			}
    			return board;
    		}
    		else if (Size == 24)
    		{
    			board = new int[5][5];
    			int k = 0;
    			for (int i = 0; i < 5; i++)
    			{
    				for (int j = 0; j < 5; j++)
    				{
    					board[i][j] = puzzle[k];
    					k++;
    				}
    			}
    			return board;
    		}
    		else if (Size == 35)
    		{
    			board = new int[6][6];
    			int k = 0;
    			for (int i = 0; i < 6; i++)
    			{
    				for (int j = 0; j < 6; j++)
    				{
    					board[i][j] = puzzle[k];
    					k++;
    				}
    			}
    			return board;
    		}
    		return board;
    	}
    
    	public static int[] GoalState(int Size)
    	{
    		int[] Goal = new int[1];
    		if (Size == 8)
    		{
    			Goal = new int[9];
    			for (int i = 0; i < 9 - 1; i++)
    				Goal[i] = i + 1;
    			Goal[9 - 1] = 0;
    			return Goal;
    		}
    		else if (Size == 15)
    		{
    			Goal = new int[16];
    			for (int i = 0; i < 16 - 1; i++)
    				Goal[i] = i + 1;
    			Goal[16 - 1] = 0;
    			return Goal;
    		}
    		else if (Size == 24)
    		{
    			Goal = new int[25];
    			for (int i = 0; i < 25 - 1; i++)
    				Goal[i] = i + 1;
    			Goal[25 - 1] = 0;
    			return Goal;
    		}
    		else if (Size == 35)
    		{
    			Goal = new int[36];
    			for (int i = 0; i < 36 - 1; i++)
    				Goal[i] = i + 1;
    			Goal[36 - 1] = 0;
    			return Goal;
    		}
    		return Goal;
    	}
    
    	public static void PrintPuzzle(int[][] Board)
    	{
    		for (int i = 0; i < Board.length; i++)
    		{
    			for (int j = 0; j < Board[0].length; j++)
    			{
    				System.out.print(" " + Board[i][j]);
    			}
    			System.out.println();
    		}
    	}

  2. #2
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    7

    Default

    can you explain what "BFS and a A* search on the N-puzzle" means?
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  3. #3
    evan42781 is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default

    well from what I understand BFS will search as wide as possible of the tree looking fore the best option to solve the puzzle using queues. With A* it will use a combination of parent and child nodes along with city-block heuristic to figure out the best possible solution. If i am looking at this wrong please tell me however i just gave a basic description on this....no reason for me to write an article on it...there's plenty of those online :)

  4. #4
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    7

    Default

    there is no need to create a tree for searching a graph. a tree is already a graph. just take note of which nodes you have already visited and do not traverse those multiple times.

    bfs: visit all children at a tier before continuing to next tier. algorithm: given the next node in the queue check if it is what you want. if not, add any unvisited neighbors (children in a tree) to the end of the queue. and keep doing it.

    a*: tricky one. won't go into detail as it'd require as much research for me as it would for you. it's been a couple years since i learned about this. but basically it's a least cost path algorithm as you described.

    definitely tackle breadth first search before trying a*, though.

  5. #5
    evan42781 is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default

    so im confused. am i supposed to make a check to find the blank space and then move the blank space depending where its at? then once it makes the new possible moves what do i do then?

  6. #6
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    7

    Default

    Is the A* similar to the old traveling sales person puzzle where he has to find the most efficient route to visit a certain number of cities without visiting a city twice?
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  7. #7
    evan42781 is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default

    ok so i have gotten a lot of code written and need help...i cant get my a* to run...but i have been writing forever and prob making a stupid mistake.

    n-puzzle
    Java Code:
    import java.util.*;
    
    public class N_Puzzle
    {
    	public static void main(String[] args)
    	{
    		Solver s1 = new Solver();
    		GameBoardActions b1 = new GameBoardActions();
    		KeyboardInputClass k1 = new KeyboardInputClass();
    
    		//This asks the user for what size puzzle do they want to solve.
    		int PuzzleSize = k1.getInteger(false, 8, 0, 36, "What size puzzle do you want to solve(ex: 8...15...24...35)");
    
    		//This Ask the user how many times they want to shuffle the board.
    		int NumberOfShuffles = k1.getInteger(false, 0, 0, 1000, "How many times do you want to shuffle the board?");
    
    		//This creates a starting puzzle and goal board (dependent on size of puzzle) in a single array then converts both to a double array.
    		int[] StartBoard1 = b1.PuzzleSingleArray(PuzzleSize, NumberOfShuffles);
    		int[][] StartBoard2D = b1.PuzzleDoubleArray(PuzzleSize, StartBoard1);
    		int[][] GoalBoard = b1.GoalState(PuzzleSize);
    
    		//This is the staring puzzle configration
    		b1.PrintPuzzle(StartBoard2D);
    
    		//This ask the user what algotithum they want to preform. 
    		int TestMethod = k1.getInteger(false, 1, 1, 2, "What Algoritum do you want to preform 1 = breadth-first or 2 = A*");
    		
    
    		if (TestMethod == 1)
    		{
    		}
    
    		else if (TestMethod == 2)
    		{
    			b1.GoalState(PuzzleSize);
    			s1.AStar(StartBoard2D);
    			s1.StartBoard = StartBoard2D;
    		}
    	}
    }
    index location
    Java Code:
    public class IndexPosition
    {
    	int x;
    	int y;
    
    	IndexPosition(int a, int b)
    	{
    		x = a;
    		y = b;
    	}
    
    	int getX()
    	{
    		return x;
    	}
    
    	int getY()
    	{
    		return y;
    	}
    
    }
    game board actions
    Java Code:
    import java.util.*;
    
    class GameBoardActions
    {
    	//Makes a single array of the starting board
    	int[] PuzzleSingleArray(int Size, int Shuffle)
    	{
    		int puzzle[] = new int[Size+1];  //this makes the size of the single array
    		int index;
    		int Shuffles = Shuffle;  //This is the input for number of shuffles
    
    		// Put all numbers into the array
    		for (index = 0; index <= Size; index++)
    			puzzle[index] = index;
    
    		// Make random numbers
    		for (int i = 0; i < Shuffles; i++)  //this for loop runs for the amount of times the user wanted to shuffle
    		{
    			for (index = 0; index < Size; index++)
    			{
    				int randomIndex = (int)Math.floor(Math.random() * Size);
    				int temp = puzzle[index];
    				puzzle[index] = puzzle[randomIndex];
    				puzzle[randomIndex] = temp;
    			}
    		}
    		return puzzle;
    	}
    	
    	//load single aray into double array
    	int[][] PuzzleDoubleArray(int Size, int[] puzzle)
    	{
    		int[][] board = new int[1][1];
    		if (Size == 8)
    		{
    			board = new int[3][3];
    			int k = 0;
    			for (int i = 0; i < 3; i++)
    			{
    				for (int j = 0; j < 3; j++)
    				{
    					board[i][j] = puzzle[k];
    					k++;
    				}
    			}
    			return board;
    		}
    		else if (Size == 15)
    		{
    			board = new int[4][4];
    			int k = 0;
    			for (int i = 0; i < 4; i++)
    			{
    				for (int j = 0; j < 4; j++)
    				{
    					board[i][j] = puzzle[k];
    					k++;
    				}
    			}
    			return board;
    		}
    		else if (Size == 24)
    		{
    			board = new int[5][5];
    			int k = 0;
    			for (int i = 0; i < 5; i++)
    			{
    				for (int j = 0; j < 5; j++)
    				{
    					board[i][j] = puzzle[k];
    					k++;
    				}
    			}
    			return board;
    		}
    		else if (Size == 35)
    		{
    			board = new int[6][6];
    			int k = 0;
    			for (int i = 0; i < 6; i++)
    			{
    				for (int j = 0; j < 6; j++)
    				{
    					board[i][j] = puzzle[k];
    					k++;
    				}
    			}
    			return board;
    		}
    		return board;
    	}
    	
    	//Makes the goal configiration of the board
    	int[][] GoalState(int Size)
    	{
    		int[][] Goal = new int[1][1];
    		if (Size == 8)
    		{
    			Goal = new int[3][3];
    			int start = 1;
    			for (int x = 0; x < Goal.length; x++)
    				for (int y = 0; y < Goal.length; y++)
    				{
    					Goal[x][y] = start;
    					start++;
    				}
    			Goal[3 - 1][3 - 1] = 0;
    			return Goal;
    		}
    		else if (Size == 15)
    		{
    			Goal = new int[4][4];
    			int start = 1;
    			for (int x = 0; x < Goal.length; x++)
    				for (int y = 0; y < Goal.length; y++)
    				{
    					Goal[x][y] = start;
    					start++;
    				}
    			Goal[4 - 1][4 - 1] = 0;
    			return Goal;
    		}
    		else if (Size == 24)
    		{
    			Goal = new int[5][5];
    			int start = 1;
    			for (int x = 0; x < Goal.length; x++)
    				for (int y = 0; y < Goal.length; y++)
    				{
    					Goal[x][y] = start;
    					start++;
    				}
    			Goal[5 - 1][5 - 1] = 0;
    			return Goal;
    		}
    		else if (Size == 35)
    		{
    			Goal = new int[6][6];
    			int start = 1;
    			for (int x = 0; x < Goal.length; x++)
    				for (int y = 0; y < Goal.length; y++)
    				{
    					Goal[x][y] = start;
    					start++;
    				}
    			Goal[6 - 1][6 - 1] = 0;
    			return Goal;
    		}
    		return Goal;
    	}
    
    	//prints the boards
    	 void PrintPuzzle(int[][] Board)
    	{
    		for (int i = 0; i < Board.length; i++)
    		{
    			for (int j = 0; j < Board[0].length; j++)
    			{
    				System.out.print(" " + Board[i][j]);
    			}
    			System.out.println();
    		}
    	}
    
    	//This makes it look like the puzzle piece has moved.
    	int[][] MovePiece(int CurrentBoard[][], IndexPosition PieceMoving)
    	{
    		int TempBoard[][] = new int[CurrentBoard.length][CurrentBoard.length];
    		for (int i = 0; i < TempBoard.length; i++)
    			for (int j = 0; j < TempBoard.length; j++)
    				TempBoard[i][j] = CurrentBoard[i][j];
    
    		IndexPosition emptyPosition = FindIndex(-1, TempBoard);
    		TempBoard[emptyPosition.getX()][emptyPosition.getY()] = TempBoard[PieceMoving.getX()][PieceMoving.getY()];
    		TempBoard[PieceMoving.getX()][PieceMoving.getY()] = -1;
    
    		return TempBoard;
    	}
    
    	//finds the index location of the piece
    	IndexPosition FindIndex(int Piece, int CurrentBoard[][])
    	{
    		IndexPosition Index = null;
    		for (int x = 0; x < CurrentBoard.length; x++)
    			for (int y = 0; y < CurrentBoard.length; y++)
    			{
    				if (CurrentBoard[x][y] == Piece)
    				{
    					Index = new IndexPosition(x, y);
    				}
    			}
    		return Index;
    	}
    
    	//Calculates the possible moves in the board
    	IndexPosition[] CalculateMoves(int CurrentBoard[][], IndexPosition LastMove)
    	{
    		ArrayList PreviousMoves = new ArrayList(4);
    		IndexPosition emptyPosition = FindIndex(-1, CurrentBoard);
    
    		if (emptyPosition.getX() - 1 >= 0)
    		{
    			if ((LastMove != null && emptyPosition.getX() - 1 != LastMove.getX()) || LastMove == null)
    				PreviousMoves.add(new IndexPosition(emptyPosition.getX() - 1, emptyPosition.getY()));
    		}
    
    		if (emptyPosition.getX() + 1 < CurrentBoard.length)
    		{
    			if ((LastMove != null && emptyPosition.getX() + 1 != LastMove.getX()) || LastMove == null)
    				PreviousMoves.add(new IndexPosition(emptyPosition.getX() + 1, emptyPosition.getY()));
    		}
    
    		if (emptyPosition.getY() - 1 >= 0)
    		{
    			if ((LastMove != null && emptyPosition.getY() - 1 != LastMove.getY()) || LastMove == null)
    				PreviousMoves.add(new IndexPosition(emptyPosition.getX(), emptyPosition.getY() - 1));
    		}
    
    		if (emptyPosition.getY() + 1 < CurrentBoard.length)
    		{
    			if ((LastMove != null && emptyPosition.getY() + 1 != LastMove.getY()) || LastMove == null)
    				PreviousMoves.add(new IndexPosition(emptyPosition.getX(), emptyPosition.getY() + 1));
    		}
    
    		if (PreviousMoves.size() < 4)
    			PreviousMoves.trimToSize();
    
    		Object objectMoves[] = PreviousMoves.toArray();
    		IndexPosition moves[] = new IndexPosition[objectMoves.length];
    
    		for (int i = 0; i < moves.length; i++)
    			moves[i] = (IndexPosition)objectMoves[i];
    
    		return moves;
    	}
    
    	//returns city distance from current state to goal state
    	int CityDistance(int CurrentBoard[][], int GoalState[][])
    	{
    		int distance = 0;
    		for (int x = 0; x < CurrentBoard.length; x++)
    			for (int y = 0; y < CurrentBoard.length; y++)
    			{
    				if (CurrentBoard[x][y] != GoalState[x][y])
    				{
    					IndexPosition GoalPoint = FindIndex(CurrentBoard[x][y], GoalState);
    
    					int tempX = x;
    					int tempY = y;
    
    					while (tempX < GoalPoint.getX())
    					{
    						distance++;
    						tempX++;
    					}
    
    					while (tempX > GoalPoint.getX())
    					{
    						distance++;
    						tempX--;
    					}
    
    					while (tempY < GoalPoint.getY())
    					{
    						distance++;
    						tempY++;
    					}
    
    					while (tempY > GoalPoint.getY())
    					{
    						distance++;
    						tempY--;
    					}
    
    				}
    			}
    		return distance;
    	}
    
    	// campares boards
    	boolean CompareBoard(int Board1[][], int Board2[][])
    	{
    		for (int x = 0; x < Board1.length; x++)
    			for (int y = 0; y < Board1.length; y++)
    			{
    				if (Board1[x][y] != Board2[x][y])
    					return false;
    			}
    
    		return true;
    	}
    }
    implement board actions
    Java Code:
    public class ImplementBoardActions extends GameBoardActions
    {
    	ImplementBoardActions ParentNode;
    	IndexPosition LastMove;
    	IndexPosition AllowedMove[];
    	int CurrentBoard[][];
    	int ManhattanDistance;
    	int Depth;
    	int Search = Depth + ManhattanDistance;
    
    	ImplementBoardActions(ImplementBoardActions Parent, int[][] CurrentBoardI, IndexPosition Move)
    	{
    		ParentNode = Parent;
    		CurrentBoard = CurrentBoardI;
    		LastMove = Move;
    		AllowedMove = CalculateMoves(CurrentBoard, LastMove);
    	}
    
    	public int GetSearch()
    	{
    		return Search;
    	}
    
    	public int GetDepth()
    	{
    		return Depth;
    	}
    
    	public void SetDepth(int depth1)
    	{
    		Depth = depth1;
    	}
    
    	public int GetDistance()
    	{
    		return ManhattanDistance;
    	}
    
    	public void SetDistance(int Distance)
    	{
    		ManhattanDistance = Distance;
    	}
    
    	public void SetParent(ImplementBoardActions Node)
    	{
    		ParentNode = Node;
    	}
    
    	public ImplementBoardActions GetParent()
    	{
    		return ParentNode;
    	}
    
    	public IndexPosition GetLastMove()
    	{
    		return LastMove;
    	}
    
    	public IndexPosition[] GetAllowedMove()
    	{
    		return AllowedMove;
    	}
    
    	public int[][] GetCurrentBoard()
    	{
    		return CurrentBoard;
    	}
    
    	public void SetSearch()
    	{
    		Search = Depth + ManhattanDistance;
    	}
    
    	public void PrintCurrentBoard()
    	{
    		PrintPuzzle(CurrentBoard);
    	}
    }
    solver
    Java Code:
    import java.util.*;
    
    class Solver extends GameBoardActions
    {
    	int[][] StartBoard;
    	int[][] GoalBoard;
    	int ListOfPreviousBoards;
    
    	//This checks to make sure that there is no duplicated boards.
    	boolean SameBoard(int CurrentBoard[][], ImplementBoardActions List[])
    	{
    		ListOfPreviousBoards = 0;
    		for (int i = 0; i < List.length; i++)
    		{
    			if (CompareBoard(CurrentBoard, List[i].GetCurrentBoard()))
    			{
    				ListOfPreviousBoards = i;
    				return true;
    			}
    		}
    		return false;
    	}
    
    	//this picks the point to move to that results in the smallest distance to the goal
    	IndexPosition GetShortestDistance(IndexPosition IndexMove[], int[][] CurrentBoard)
    	{
    		int StoredDistances[] = new int[IndexMove.length];
    		for (int i = 0; i < IndexMove.length; i++)
    		{
    			int TempBoard[][] = MovePiece(CurrentBoard, IndexMove[i]);
    			StoredDistances[i] = CityDistance(TempBoard, GoalBoard);
    		}
    
    		int LowestDistance = 0;
    		for (int i = 1; i < StoredDistances.length; i++)
    			if (StoredDistances[i] < StoredDistances[LowestDistance])
    				LowestDistance = i;
    
    		return IndexMove[LowestDistance];
    	}
    
    	Stack AStar(int StartingBoard[][])
    	{
    		ArrayList Open = new ArrayList();
    		ArrayList Closed = new ArrayList();
    
    		int GoalBoard[][] = GoalState(StartingBoard.length);
    		ImplementBoardActions CurrentNode = new ImplementBoardActions(null, StartingBoard, null);
    
    		CurrentNode.SetDepth(0);
    		CurrentNode.SetDistance(CityDistance(CurrentNode.GetCurrentBoard(), GoalBoard));
    		CurrentNode.SetSearch();
    
    		Open.add(CurrentNode);
    
    		while (!Open.isEmpty())
    		{
    			CurrentNode = (ImplementBoardActions)Open.remove(0);
    			Closed.add(CurrentNode);
    
    			if (CurrentNode.GetDistance() == 0)
    				break;
    
    			else
    			{
    				IndexPosition SuccessfulMoves[] = CurrentNode.GetAllowedMove();
    
    				// convert open to array
    				Object TempOpen[] = Open.toArray();
    				ImplementBoardActions OpenArray[] = new ImplementBoardActions[TempOpen.length];
    				for (int j = 0; j < TempOpen.length; j++)
    					OpenArray[j] = (ImplementBoardActions)TempOpen[j];
    
    				// convert closed to array
    				Object TempClosed[] = Closed.toArray();
    				ImplementBoardActions ClosedArray[] = new ImplementBoardActions[TempClosed.length];
    				for (int k = 0; k < ClosedArray.length; k++)
    					ClosedArray[k] = (ImplementBoardActions)TempClosed[k];
    
    				//check if the su states have been added to Open List and Closed List
    				for (int i = 0; i < SuccessfulMoves.length; i++)
    				{
    					int NewBoard[][] = MovePiece(CurrentNode.GetCurrentBoard(), SuccessfulMoves[i]);
    
    					ImplementBoardActions TempSuccessfulMoves = new ImplementBoardActions(CurrentNode, NewBoard, SuccessfulMoves[i]);
    					TempSuccessfulMoves.SetDepth(CurrentNode.GetDepth() + 1);
    					TempSuccessfulMoves.SetDistance(CityDistance(NewBoard, GoalBoard));
    					TempSuccessfulMoves.SetSearch();
    
    					boolean OnOpen = SameBoard(NewBoard, OpenArray);
    					if (OnOpen)
    					{
    						// check for which state is shorter in the tree
    						int OpenSearch = OpenArray[ListOfPreviousBoards].GetSearch();
    						if (TempSuccessfulMoves.GetSearch() < OpenSearch)
    						{
    							OpenArray[ListOfPreviousBoards].SetParent(CurrentNode);
    							OpenArray[ListOfPreviousBoards].SetDepth(CurrentNode.GetDepth() + 1);
    							OpenArray[ListOfPreviousBoards].SetSearch();
    						}
    					}
    
    					boolean OnClosed = SameBoard(NewBoard, ClosedArray);
    					if (OnClosed)
    					{
    						// check for which state is shorter in the tree
    						int ClosedSearch = ClosedArray[ListOfPreviousBoards].GetSearch();
    						if (TempSuccessfulMoves.GetSearch() < ClosedSearch)
    						{
    							ClosedArray[ListOfPreviousBoards].SetParent(CurrentNode);
    							ClosedArray[ListOfPreviousBoards].SetDistance(CurrentNode.GetDepth() + 1);
    							ClosedArray[ListOfPreviousBoards].SetSearch();
    
    							Closed.clear();
    							for (int m = 0; m < ClosedArray.length; m++)
    								Closed.add(ClosedArray[m]);
    						}
    					}
    
    					// add to open only if there not already
    					if (!OnOpen && !OnClosed)
    					{
    						Open.add(TempSuccessfulMoves);
    
    						TempOpen = Open.toArray();
    						OpenArray = new ImplementBoardActions[TempOpen.length];
    						for (int j = 0; j < TempOpen.length; j++)
    							OpenArray[j] = (ImplementBoardActions)TempOpen[j];
    					}
    				}
    
    				Arrays.sort(OpenArray);
    				Open.clear();
    				for (int i = 0; i < OpenArray.length; i++)
    					Open.add(OpenArray[i]);
    			}
    		}
    
    		// backtracking the solution
    		int Steps = 0;
    		Stack Solution = new Stack();
    		Solution.push(CurrentNode);
    		while (CurrentNode.GetParent() != null)
    		{
    			CurrentNode = CurrentNode.GetParent();
    			Solution.push(CurrentNode);
    			Steps++;
    		}
    
    		System.out.println("Number of steps in solution = " + Steps);
    		return Solution;
    	}
    }

  8. #8
    corlettk is offline Member
    Join Date
    Apr 2009
    Location
    Brisbane
    Posts
    86
    Rep Power
    0

    Default

    I strongly suggest that you start with a known-problem.

    Generating a random maze is insane because it's untestable... I mean how will you know if your algorithm is producing the correct result? Work it out by hand? Goodo. That won't take long.

    Here's one: Programming Challenge 12 - Find the Lowest Cost Route

    and here's the answer:
    Java Code:
    From A to B cost 210
    From B to C cost 289
    From C to D cost 275
    From D to E cost 280
    From F to G cost 297
    From E to F cost 388
    From G to H cost 379
    From H to I cost 387
    From I to J cost 296
    total cost 2801
    Just a suggestion. Cheers. Keith.

  9. #9
    corlettk is offline Member
    Join Date
    Apr 2009
    Location
    Brisbane
    Posts
    86
    Rep Power
    0

    Default

    Also I suggest you go read Code Conventions for the Java Programming Language

    variableName... ClassName... Yes, it is important, but only if you don't want to get turfed-out on your ear within hours of starting your first programming job.

    Cheers. Keith.

  10. #10
    evan42781 is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default

    ok so i put my own board in manually instead of random and i found out that it was trying to find -1 as the blank spot instead of 0. thats is fixed now. However its now throwing a classCast exception at the end of A* method right before it back tracks?? error is below.

    Java Code:
    java.lang.ClassCastException was unhandled
      Message="ImplementBoardActions@2b89eaa"
      Source="vjslib"
      StackTrace:
           at java.util.Arrays.__sort(Array array, Int32 from, Int32 to, IComparer comparer)
           at java.util.Arrays.sort(Object[] arr, Int32 fromIx, Int32 toIx, Comparator comp)
           at java.util.Arrays.sort(Object[] arr)
           at SolverAStar.AStar(Int32[][] StartingBoard) in C:\Users\Evan\Documents\Visual Studio 2005\Projects\8_puzzle\8_puzzle\Solver.jsl:line 132
           at N_Puzzle.main(String[] args) in C:\Users\Evan\Documents\Visual Studio 2005\Projects\8_puzzle\8_puzzle\N-Puzzle.jsl:line 41
           at System.AppDomain._nExecuteAssembly(Assembly assembly, String[] args)
           at System.AppDomain.ExecuteAssembly(String assemblyFile, Evidence assemblySecurity, String[] args)
           at Microsoft.VisualStudio.HostingProcess.HostProc.RunUsersAssembly()
           at System.Threading.ThreadHelper.ThreadStart_Context(Object state)
           at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
           at System.Threading.ThreadHelper.ThreadStart()

  11. #11
    corlettk is offline Member
    Join Date
    Apr 2009
    Location
    Brisbane
    Posts
    86
    Rep Power
    0

    Default

    Quote Originally Posted by evan42781 View Post
    However its now throwing a classCast exception at the end of A* method right before it back tracks??
    How to read a stacktrace: 0xCAFEFEED Of Thread dumps and stack traces …

    Also I notice you're using visual studio. Microsoft Java, succinctly sucks... MS Don't want to encourage people to use a language they (MS) don't control, hence there Java implementation is minimal, designed to specifically as bridge back to the MS glee club... not to facilitate escape.

    I recommend you use "the real" Java... Java SE Downloads - Sun Developer Network (SDN)... And I'd recommend ditching the IDE, any IDE, and just using the command line tools until you have mastered the Java classpath, and can therefore build, package, deploy, and run a Java application using just the raw O/S tools... Then it's time to checkout Eclipse, Netbeans, IntelliJ, or whatever.

  12. #12
    evan42781 is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default

    hey thanks for your help. I had to make a comparable method which fixed the problem.
    As for your thoughts on Visual Studio..sadly enough that.s what our teach makes us use :( Hes old and lives in the stoneage..lol. I wish I could use Netbeans but I cant.
    Now I need help trying to figure out how to solve the puzzle with BFS??

  13. #13
    evan42781 is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

Similar Threads

  1. Need help with Trees...(8-puzzle)
    By ventrue in forum New To Java
    Replies: 2
    Last Post: 03-23-2009, 11:04 PM
  2. 8-Square puzzle loop
    By SapphireSpark in forum New To Java
    Replies: 7
    Last Post: 12-04-2008, 07:21 PM
  3. Java Drawing PUZZLE
    By Cyorxamp in forum AWT / Swing
    Replies: 3
    Last Post: 06-09-2008, 10:35 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •