[evan42781]

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

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

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

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

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

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;
	}
}