//////////////////
//FinalCode.cpp
//For: CSC 390 System Assignment 1 and 2
//By: Jesse Burant
//Purpose: This program is an 8 puzzle that can be solved by human interaction
//         or automatically via artificial intelligence using a distance from goal 
//         state heuristic.  Starting states can be generated automatically or entered
//         manually.  Automatically generated states are checked to ensure they are
//         solvable.
//!!!! Apologies in advance for not using object oriented C++ !!!!!

#include <iostream.h>
#include <string.h> //provides "string" data type capabilities
#include <stdlib.h> //provides a clear screen function
#include <cstdlib>   // for srand and rand
#include <ctime>     // for time

using namespace std; //Required for who knows why

struct Puzzle //Original intent was to use a struct with these 2 variables
			  //However, along the way I basically realized I didn't need
			  //the peice variable.  But instead of changing all my code, 
			  //I left it as a struct.  I basically use this struct as a regular
			  //array of integers.
	{
	int Location; //data here signifies a peice of the puzzle
	};
	
struct Node //data structure representing a node on a tree, although I'm not sure
 			//   if I am technically using a tree structure, as will be pointed out
 			//   later.
	{
	int Cost; //Heuristic value of given node
	int State[10]; //The arrangement of the peices 
	int Parent; //Which closed node did this one spawn from?
	int PeiceMoved; //Which peiced was last moved in order to get in this state?
	};

//NON AI FUNCTIONS
void ManualLoad(Puzzle []); //Enter starting state manually
void AutoLoad(Puzzle []);  //Automatically generate a starting state
void CheckForDuplicate(int &, int, Puzzle []); //Input validation
void DisplayPuzzle(Puzzle []); //Clears screen and displays current state
int CheckForLastValue(Puzzle []); //When manually creating starting state,
								  //this function automatically enters the 
								  //last peice for you
void SelectMove(Puzzle []);  //Shows user his options for all possible states
bool CheckGoalState(Puzzle []);  //After each move
void SwitchContents(int, int, Puzzle []); //Performs requested move
bool IsSolvable(Puzzle []);

//AI SPECIFIC FUNCTIONS
void EmployAI(string); //basically the main() function for the AI portion of the program
void SortOpenList(Node [], int); //Shell Sorts the Open Nodes from lowest heurictic "cost" to highest
void CreateNewNodes(int &, int, Node [], Node []);  //determines valid moves, performs all of them 
													//(if conditions are met)
bool CompareToClosedNodes(Node [], int, int, Node []); //Will prevent a new node from being created if it
													   //the same puzzle configuration is already in the closed
													   //nodes list
void SwitchContents(int, int, Node [], int); //Switches 2 peices of a node
void RemoveBestNode(Node [], Node [], int &, int &); //Takes BestNode out of Open list after it has been expanded and
													 //moved to the end of the closed nodes list
void CalculateCost(Node [], int); //determine heuristic cost of a given state
void CalculateCost(Node &); //remnant, not in use
bool CheckForGoal(Node []); //after every SortOpenList, it checks the BestNode for the goal state
void AIAutoLoad(Node &); //Automatically generates a puzzle configuration for the AI portion of the program
void AIManualLoad(Node &); //Allows user to maunally specify start state for the AI portion of the program
void CheckManualLoadAI(int &, int, Node &); //Check for duplicate/invalid entries
bool IsSolvable(Node &); //determines if the current allocated start state is even solvable.  Returns true if solvable.


void main ()

{
	string UserName; //Just for fun
	int MainMenuChoice = 0;
	
	Puzzle NewPuzz[9];//The core variable for the whole program.
					  //Each location in the array represents a square.
					  //For example, NewPuzz[1] represents the upper left
					  //position of the game board.  The contents of NewPuzz[1]
					  //tells you what peice is there.  For example: If
					  //NewPuzz[1].Location = 6, that means the 6 tile is in the 
					  //upper left hand corner.
	
	cout << "Welcome to the Magic 8 Puzzle Program\n";
	cout << "-------------------------------------\n"
		 << "About:\n"
		 << "The 8 Puzzle consists of 8 consecutively numbered tiles located in a \n"
		 << "3 x 3 grid. The object of the puzzle is to move the tiles within the grid\n"
		 << "so that each tile ends up at its correct location, as shown in the \n"
		 << "following diagram:\n\n"
		 << " 1 2 3 \n"
		 << " 4 5 6     (0 represents the blank space into which a peice can be moved) \n"
		 << " 7 8 0 \n\n"
		 << "This program allows you or the computer to solve a puzzle of your choice, \n"
		 << "or a \"randomly\" generated start state. Have fun!\n\n\n";
	cout << "Please enter your name (then press Enter):\n";
	cin >> UserName; 
	if (UserName == " ")
		UserName = "Player1";
		
	bool Flag5 = false;
		//allows for main menu to be redisplayed if given start state returns as unolvable
	while (Flag5 == false)
	{
	system("cls"); //clears the screen (via stdlib.h)
	
	cout << "*-----------------------------------------------*\n"
	     << "|                   MAIN MENU                   |\n"
	     << "*-----------------------------------------------*\n"
	     << "1) Enter starting state maunally                 \n"
	     << "2) Automatically generate starting state         \n"
	     << "3) Employ Artificial Intelligence to solve puzzle\n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "Select Menu Item: ";
	     
	cin >> MainMenuChoice;
	
	bool Check = false;
	//Main Menu with input checking via the default case
	while (Check == false)
	{
		switch (MainMenuChoice)
		{
			case 1:
				ManualLoad(NewPuzz);
				Check = true;
				break;
			case 2:
				AutoLoad(NewPuzz);
				Check = true;
				break;
			case 3:
				EmployAI(UserName);
				Check = true;
				Flag5 = true;
				break;
			default:	   
				cout << "Invalid Input.  Try Again.\n";
				cin >> MainMenuChoice;
				Check = false;
				break;
		}
	};  
	Flag5 = IsSolvable(NewPuzz); //while loop will continue "while" unsolvable
	if ((Flag5 == false) && (MainMenuChoice != 3))
		{
		cout << "Current puzzle configuration is not solvable.  Restarting...\n";
		system("PAUSE");
		}
	}; //END while
	
	
	
	if (MainMenuChoice != 3)//user wants to solve it manually
	{
	DisplayPuzzle (NewPuzz); //shows the currently assigned starting state
	
	bool Flag2 = false;	
	int MoveCount = 0;
	
	//The heart of the non-AI portion
	while (Flag2 == false)
		{
		SelectMove(NewPuzz);
		DisplayPuzzle(NewPuzz);
		Flag2 = CheckGoalState(NewPuzz);//If goal state is reached, a true is 
										//returned and the loop is broken
		MoveCount++; //lets you know how many moves youve made
		};
		
	DisplayPuzzle (NewPuzz); //shows puzzle in goal state
	
	cout << "CONGRATULATIONS " << UserName << "!  \nYou have successfully reached the goal state in " << MoveCount << " moves!\n " << endl;
		 
	system("PAUSE"); //Pauses System before closing, thanks to stdlib.h
	
	} 
	
	cout << "\nThanks for playing!  Goodbye!\n";
	system("PAUSE");
	return;
	
}

//--------------------------------------------------------------------
void ManualLoad(Puzzle NewPuzz[])

{
	system("cls");
	
	//cout << "Now entering Top Row from left to right\n(Enter a 0 for a blank)\n";
	
	cout << "Top Row Left = :"; 
	cin >> NewPuzz[1].Location; 
	CheckForDuplicate(NewPuzz[1].Location,0,NewPuzz);//data input validation
		
	cout << "Top Row Middle = :"; 
	cin >> NewPuzz[2].Location;
	CheckForDuplicate(NewPuzz[2].Location,1,NewPuzz); //data input validation
	
	cout << "Top Row Right = :"; 
	cin >> NewPuzz[3].Location;
	CheckForDuplicate(NewPuzz[3].Location,2,NewPuzz);
	
	//cout << "Now entering Top Row from left to right\n(Enter a 0 for a blank)\n";
	
	cout << "Middle Row Left = :"; 
	cin >> NewPuzz[4].Location;
	CheckForDuplicate(NewPuzz[4].Location,3,NewPuzz);
	
	cout << "Middle Row Middle = :"; 
	cin >> NewPuzz[5].Location;
	CheckForDuplicate(NewPuzz[5].Location,4,NewPuzz);
	
	cout << "Middle Row Right = :"; 
	cin >> NewPuzz[6].Location;
	CheckForDuplicate(NewPuzz[6].Location,5,NewPuzz);
	
	//cout << "Now entering Top Row from left to right\n(Enter a 0 for a blank)\n";
	
	cout << "Bottom Row Left = :"; 
	cin >> NewPuzz[7].Location;
	CheckForDuplicate(NewPuzz[7].Location,6,NewPuzz);
	
	cout << "Bottom Row Middle = :"; 
	cin >> NewPuzz[8].Location;
	CheckForDuplicate(NewPuzz[8].Location,7,NewPuzz);
	
	NewPuzz[0].Location = CheckForLastValue(NewPuzz);
	cout << "The last peice has been automatically determined." << endl;
	system("PAUSE");
	
}
	
//--------------------------------------------------------------------
void CheckForDuplicate(int &InputVal, int Depth, Puzzle NewPuzz[])

{
	//this while loop is to verify number is between 0 and 8
	while((InputVal > 8) || (InputVal < 0))
		{
		cout << "Please enter an integer from 0 to 8\n";
		cin >> InputVal;
		};
	//for loop checks previous entries into the Puzzle struct
	for (int i = 1; i <= Depth; i++)//Depth variable specifies 
									//how many previous entries to look at
		{
		if (InputVal == NewPuzz[i].Location)
			{
			//If duplicate is found, we go into this loop to get a new
			//value
			while ((InputVal == NewPuzz[i].Location) || (InputVal > 8) || (InputVal < 0))
				{
				cout << "You have entered a duplicate or out-of-range value. Try Again.\n";
				cin >> InputVal;
				};
			}
		}
}

//--------------------------------------------------------------------
void DisplayPuzzle(Puzzle NewPuzz[])

{
	//Straightforward I think
	system("cls");
	cout << " ----------------- \n"
		 << "|     |     |     |\n"
		 << "|  " << NewPuzz[1].Location << "  |  " << NewPuzz[2].Location << "  |  " << NewPuzz[3].Location << "  |\n"
		 << "|     |     |     |\n"
		 << "|-----------------|\n"
		 << "|     |     |     |\n"
		 << "|  " << NewPuzz[4].Location << "  |  " << NewPuzz[5].Location << "  |  " << NewPuzz[6].Location << "  |\n"
		 << "|     |     |     |\n"
		 << "|-----------------|\n"
		 << "|     |     |     |\n"
		 << "|  " << NewPuzz[7].Location << "  |  " << NewPuzz[8].Location << "  |  " << NewPuzz[0].Location << "  |\n"
		 << "|     |     |     |\n"
		 << " ----------------- \n" << endl;
		 		 
}

//----------------------------------------------------------------------
int CheckForLastValue(Puzzle NewPuzz[])

{
	//I'd like to be able to tell you what's going on here...
	//But I'm not 100% sure myself, even though I wrote it
	
	int LastPeice;
	int LookForA = 0; 
	int j = 1;
	int NotFoundCounter = 0;
			
	for (; NotFoundCounter != 9; LookForA++)//Outer loop represnts the Puzzle
											//peice we are looking for
		{
		NotFoundCounter = 0; //The inner loop is going to look for our requested
							 //peice in every element of the Puzzle array.  Every 
							 //time a match is NOT made, this variable is incremented
							 //by 1.  If this number ever reaches 9, we know our peice
							 //was not found in any of the 8 array locations
							 
		j = 0;//dont ask, it should be in the for loop, but... I'm afraid to change it
		for (;j < 9; j++)
			{
			if (NewPuzz[j].Location != LookForA) //Match NOT made
				{
				NotFoundCounter++;
				}
			}
		}
		LastPeice = (LookForA-1); //Our loop has exited because our NotFoundCounter
								  //reached 9, so whatever number we just searched for 
								  //is the last remaining number to be added to the
								  //Puzzle array.
		
	return LastPeice;
}
	
//-------------------------------------------------------------
void SelectMove(Puzzle NewPuzz[])

{
	//First determines the location of the 0 (the blank)
	//Based on location of the blank, it knows which peices are 
	//	legal moves and displays them to the user
	//User picks a move
	//Move is checked for legality
	//Selection of which two tiles the user wants to swap is sent to the 
	//	SwitchContents function.
	
	//Yes, I know it is not very elegant.  
	//I am open to ideas as to how to do this better
	
	int Option1;
	int Option2;
	int Option3;
	int Option4;
	int Selection;
	bool Flag1 = false; //for selection validation loop control
	
	cout << "Which peice do you want to move next?" << endl;
	
	if (NewPuzz[1].Location == 0)
		{
		cout << NewPuzz[2].Location << " or " << NewPuzz[4].Location << endl;
		Option1 = NewPuzz[2].Location;
		Option2 = NewPuzz[4].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(1,2,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(1,4,NewPuzz);
		}
	
	else
	if (NewPuzz[2].Location == 0)
		{
		cout << NewPuzz[1].Location << " or " << NewPuzz[3].Location << " or " << NewPuzz[5].Location << endl;
		Option1 = NewPuzz[1].Location;
		Option2 = NewPuzz[3].Location;
		Option3 = NewPuzz[5].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2) && (Selection != Option3))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(2,1,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(2,3,NewPuzz);
				else
				if (Selection == Option3)
					SwitchContents(2,5,NewPuzz);
		}
	
	else
	if (NewPuzz[3].Location == 0)
		{
		cout << NewPuzz[2].Location << " or " << NewPuzz[6].Location << endl;
		Option1 = NewPuzz[2].Location;
		Option2 = NewPuzz[6].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(3,2,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(3,6,NewPuzz);
		}
		
	else
	if (NewPuzz[4].Location == 0)
		{
		cout << NewPuzz[1].Location << " or " << NewPuzz[5].Location << " or " << NewPuzz[7].Location << endl;
		Option1 = NewPuzz[1].Location;
		Option2 = NewPuzz[5].Location;
		Option3 = NewPuzz[7].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2) && (Selection != Option3))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(4,1,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(4,5,NewPuzz);
				else
				if (Selection == Option3)
					SwitchContents(4,7,NewPuzz);
		}	
	
	else
	if (NewPuzz[5].Location == 0)
		{
		cout << NewPuzz[2].Location << " or " << NewPuzz[4].Location << " or " << NewPuzz[6].Location << " or " << NewPuzz[8].Location << endl;
		Option1 = NewPuzz[2].Location;
		Option2 = NewPuzz[4].Location;
		Option3 = NewPuzz[6].Location;
		Option4 = NewPuzz[8].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2) && (Selection != Option3) && (Selection != Option4))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(5,2,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(5,4,NewPuzz);
				else
				if (Selection == Option3)
					SwitchContents(5,6,NewPuzz);
					else
					if (Selection == Option4)
						SwitchContents(5,8,NewPuzz);
		}
	
	else
	if (NewPuzz[6].Location == 0)
		{
		cout << NewPuzz[3].Location << " or " << NewPuzz[5].Location << " or " << NewPuzz[0].Location << endl;
		Option1 = NewPuzz[3].Location;
		Option2 = NewPuzz[5].Location;
		Option3 = NewPuzz[0].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2) && (Selection != Option3))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(6,3,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(6,5,NewPuzz);
				else
				if (Selection == Option3)
					SwitchContents(6,0,NewPuzz);
		}	
	
	else
	if (NewPuzz[7].Location == 0)
		{
		cout << NewPuzz[4].Location << " or " << NewPuzz[8].Location << endl;
		Option1 = NewPuzz[4].Location;
		Option2 = NewPuzz[8].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(7,4,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(7,8,NewPuzz);
		}
	
	else
	if (NewPuzz[8].Location == 0)
		{
		cout << NewPuzz[7].Location << " or " << NewPuzz[5].Location << " or " << NewPuzz[0].Location << endl;
		Option1 = NewPuzz[7].Location;
		Option2 = NewPuzz[5].Location;
		Option3 = NewPuzz[0].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2) && (Selection != Option3))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(8,7,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(8,5,NewPuzz);
				else
				if (Selection == Option3)
					SwitchContents(8,0,NewPuzz);
		}	
	
	else
	if (NewPuzz[0].Location == 0)
		{
		cout << NewPuzz[6].Location << " or " << NewPuzz[8].Location << endl;
		Option1 = NewPuzz[6].Location;
		Option2 = NewPuzz[8].Location;
		while (Flag1 == false)
			{
			cin >> Selection;
			if ((Selection != Option1) && (Selection != Option2))	
				{
				cout << "Invalid Selection.  Try Again.";
				Flag1 = false;
				}
				else
					Flag1 = true;
			};
		if (Selection == Option1)
			SwitchContents(0,6,NewPuzz);
			else 
			if (Selection == Option2)
				SwitchContents(0,8,NewPuzz);
		}
	
}

//-------------------------------------------------------------
	
bool CheckGoalState (Puzzle NewPuzz[])

{
	//This is what the goal state will look like
	if ((NewPuzz[1].Location == 1) && 
	(NewPuzz[2].Location == 2) &&
	(NewPuzz[3].Location == 3) &&
	(NewPuzz[4].Location == 4) &&
	(NewPuzz[5].Location == 5) &&
	(NewPuzz[6].Location == 6) &&
	(NewPuzz[7].Location == 7) &&
	(NewPuzz[8].Location == 8) &&
	(NewPuzz[0].Location == 0))
		return true; //Game over, break out of loop
		else
			return false; //Do another loop iteration (another move)
}

//------------------------------------------------------------
void SwitchContents(int Cell1, int Cell2, Puzzle NewPuzz[])

{
	int TempStorage;
	
	//A plain old switching algorithm
	TempStorage = NewPuzz[Cell1].Location;
	NewPuzz[Cell1].Location = NewPuzz[Cell2].Location;
	NewPuzz[Cell2].Location = TempStorage;
	
}
//------------------------------------------------------------
void AutoLoad(Puzzle NewPuzz[])

{
	int BaseArray[9];    // array of peices;
    srand(time(0));  // initialize seed "randomly"
     
    for (int i=0; i<9; i++)
   		{
        BaseArray[i] = i;  // fill the array in order
        }
    
      
        //Shuffle elements by randomly exchanging each with one other.
        for (int i=0; i<9; i++) 
        	{
            int r = rand() % 9;  // generate a random position
            int temp = BaseArray[i]; 
            BaseArray[i] = BaseArray[r]; 
            BaseArray[r] = temp;
            }
        
        //Load Puzzle from randomized array
        for (int c=0; c<9; c++) 
        	{
            NewPuzz[c].Location = BaseArray[c];
       		}
   	
}
//--------------------------------------------------------------
bool IsSolvable(Puzzle NewPuzz[])

//Shout out to http://www.isle.org/~sbay/ics171/project/unsolvable
//for telling me how to determine if a given arrangement of an 8
//puzzle is solvable
{
	Puzzle TempPuzz[10];
	TempPuzz[9] = NewPuzz[0];
	for (int i=1; i<9; i++)
		TempPuzz[i] = NewPuzz[i];
	
	int SwapCount = 0;
	for (int x=1; x<10; x++)
		{
		for (int y=(x+1); y<10; y++)
			{
			if ((TempPuzz[x].Location > TempPuzz[y].Location) && (TempPuzz[x].Location != 0) && (TempPuzz[y].Location != 0))
				SwapCount++;
			}
		}
	if ((SwapCount % 2) == 0)
		return true;
		else
			return false;
}


///////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////// ALL CODE BELOW WAS ADDED LATER TO INCORPORATE ARTIFICIAL INTELLIGENCE ///////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Kinda like a program within a program.  Not very clean... but easy.  Ahem... easiER.
//Nothing about this program is easy!

bool IsSolvable (Node &Start)

//Shout out to http://www.isle.org/~sbay/ics171/project/unsolvable
//for telling me how to determine if a given arrangement of an 8
//puzzle is solvable
{
	int SwapCount = 0;
	for (int i=1; i<10; i++)
		{
		for (int j=(i+1); j<10; j++)
			{
			if ((Start.State[i] > Start.State[j]) && (Start.State[i] != 0) && (Start.State[j] != 0))
				SwapCount++;
			}
		}
	if ((SwapCount % 2) == 0)
		return true;
		else
			return false;
}

//-------------------------------------------------------------------------------------------------------------

void EmployAI (string User)

{
	//Here's how I set up my "tree" of nodes...
	//  USING THE A* ALGORITHM
	/*  A* maintains two lists, called open and closed. 
		At the beginning of the algorithm, the initial node is placed on the open list. The list is sorted 
		according to a heuristic function that measures how close the state of the node is to the goal state. 
		Thus, we are really dealing with (priority) queues. 
		At each step, bestNode is removed from the open list. In this case, bestNode is always the head of the 
		open list. If the state of bestNode is the goal state, then the algorithm terminates. Otherwise bestNode
		is expanded (we determine all the possible states that can be reached within a single move), 
		and bestNode is placed on the closed list. 
		Ideally the successors of bestNode should be placed on the open list if either: 
			-the successor is not already on the open or closed list, or 
			-the successor is already on the open or closed list but has a lower cost. 
		We, at NO TIME, want a duplicate node in either list, it would be a waste of cycles*/

	Node *OpenNodes;
	OpenNodes = (Node*) new Node[2000]; //in all my tests, I have never gone over 1000 nodes, 
									    //so hardcoding 2000 should be ok (avoiding linked lists at all 
									    //costs here!  Thanks to Bill Cumming.)
	Node *ClosedNodes;
	ClosedNodes = (Node*) new Node[2000];
	//Node OpenNodes[5000];
	//Node ClosedNodes[5000];
	
	int OpenIndex = 0;  //Points to the next available location in the array.  Also indicates list size.
	int ClosedIndex = 0; //Points to the next place to move the next BestNode from the OpenList
	
	//Initialize OPEN and CLOSED lists
	for (int i=0; i<2000; i++)
		{
		OpenNodes[i].Cost = NULL;
		ClosedNodes[i].Cost = NULL;
		OpenNodes[i].Parent = NULL;
		ClosedNodes[i].Parent = NULL;
		OpenNodes[i].PeiceMoved = NULL;
		ClosedNodes[i].PeiceMoved = NULL;
		for (int j=0; j<10; j++)
			{
			OpenNodes[i].State[j] = NULL;
			ClosedNodes[i].State[j] = NULL;
			}
		}
	
	Node Start; //Start State (root of figurative tree)
	
	int AIMenuChoice;
	bool Flag4 = false; 
		//allows AI menu to redisplay if allocated start state returns as unsolvable
	while (Flag4 == false)
	{
	
	system("cls");
	cout << "*-----------------------------------------------*\n"
	     << "|         ARTIFICIAL INTELLIGENCE MENU          |\n"
	     << "*-----------------------------------------------*\n"
	     << "1) Enter starting state maunally                 \n"
	     << "2) Automatically generate starting state         \n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "                                                 \n"
	     << "Select Menu Item: ";

	cin >> AIMenuChoice;
	
	bool Check2 = false;
	//Main Menu with input checking via the default case
	while (Check2 == false)
	{
		switch (AIMenuChoice)
		{
			case 1:
				AIManualLoad(Start);
				Check2 = true;
				break;
			case 2:
				AIAutoLoad(Start);
				Check2 = true;
				break;
			default:	   
				cout << "Invalid Input.  Try Again.\n";
				cin >> AIMenuChoice;
				Check2 = false;
				break;
		}
	};  
	
	Flag4 = IsSolvable(Start); //Sends the allocated start state to be checked for solvability
	if (Flag4 == false) //if IsSolvable returns false, meaning the start state is not solvable
		{
		cout << "Current puzzle configuration is not solvable.  Restarting...\n";
		system("PAUSE");
		} 
	}
	
	Start.Parent = NULL; //root has no parent obviously
	Start.PeiceMoved = NULL;
	
	OpenNodes[0] = Start; //Start off by putting the starting node into the beginning of the OPEN list
	CalculateCost(OpenNodes, OpenIndex);
	OpenIndex++;
		
	
	//SortOpenList(OpenNodes, OpenIndex);	
	
	//
	
	bool Flag3 = false;
	while (Flag3 == false)
	{
	cout << "SEARCHING FOR GOAL STATE...\n" << OpenNodes[0].State[0] << endl;
		
	CreateNewNodes(OpenIndex, ClosedIndex, OpenNodes, ClosedNodes);
	
	RemoveBestNode(OpenNodes, ClosedNodes, OpenIndex, ClosedIndex); //BestNode from OpenList is moved to ClosedList
	
	SortOpenList(OpenNodes, OpenIndex);	
		
	Flag3 = CheckForGoal(OpenNodes);
		
		
		
	//Find the BLANK (0) in the BestState
	for (int i=1; i<10; i++)
		{
		if (OpenNodes[0].State[i] == 0)
			OpenNodes[0].State[0] = i;
		}
			
	for (int k=1; k<10; k++)
		{
		if ((k==4) || (k==7))
			cout << " \n";
		cout << OpenNodes[0].State[k];
		}
		
	cout << "\n\nCOST=" << OpenNodes[0].Cost << endl;
	cout << " OpenIndex=" << OpenIndex << endl;
	cout << " ClosedIndex=" << ClosedIndex << endl;
	
	
	system("cls");
	};
	cout << "\nGOAL STATE FOUND!!!!" << endl;
	
	
	int MoveHistory[100];
	int MHIndex = 0;
	
	int TEMPX = 0;
	int TEMPY = 0;
	TEMPX = OpenNodes[0].PeiceMoved;
	TEMPY = OpenNodes[0].Parent;
	//cout << TEMPX << endl << TEMPY << endl;
	MoveHistory[MHIndex] = TEMPX;
	MHIndex++;
	
	while (TEMPX != NULL)
		{
		TEMPX = ClosedNodes[TEMPY].PeiceMoved;
		TEMPY = ClosedNodes[TEMPY].Parent;
	
		MoveHistory[MHIndex] = TEMPX;
		MHIndex++;
		};
	
	cout << "Open Nodes: " << OpenIndex << "\nClosed Nodes: " << ClosedIndex << endl;
	int CPUmoveCount = (MHIndex-1);
	/*while (MHIndex > 0)
		{
		MHIndex--;
		cout << MoveHistory[MHIndex] << endl;
		}
	*/
	
	system("PAUSE");
	
	Puzzle NewPuzz[9];
	//Load NewPuzz with Start.State
	NewPuzz[0].Location = Start.State[9];
	for (int i=1; i<10; i++)
		{
		NewPuzz[i].Location = Start.State[i];
		}
		
	MHIndex--;
	
	int LocationOf0 = 9;

	for (int i=0; i<9; i++)
		if (NewPuzz[i].Location == 0)
			LocationOf0 = i;
			
	DisplayPuzzle(NewPuzz);				
	while (MHIndex > 0)
		{
		for (int i=0; i<9; i++)
			if (NewPuzz[i].Location == 0)
				LocationOf0 = i;
		MHIndex--;		
		if (MoveHistory[MHIndex] == 9)
			MoveHistory[MHIndex] = 0;
		if (MHIndex > 0)
			cout << "\nThe computer will now move the " << NewPuzz[MoveHistory[MHIndex]].Location << endl;
			else
				cout << "\nThe computer will now move the " << NewPuzz[0].Location << endl;
		system("PAUSE");
		if (MHIndex > 0)
			SwitchContents(LocationOf0, MoveHistory[MHIndex], NewPuzz);
			else
				SwitchContents(LocationOf0, 0, NewPuzz);
		DisplayPuzzle(NewPuzz);
		};
	cout << "The computer reached the goal state in " << CPUmoveCount << " moves.  \nDo you think you could do better " << User << "?\n";
	char TryToBeat;
	cout << "(y/n) : ";
	cin >> TryToBeat;
	if (TryToBeat == 'y')
		{
		//Load NewPuzz with Start.State
		NewPuzz[0].Location = Start.State[9];
		for (int i=1; i<10; i++)
			{
			NewPuzz[i].Location = Start.State[i];
			}
		bool Flag2 = false;	
		int MoveCount = 0;
		DisplayPuzzle(NewPuzz);
		//The heart of the program
		while (Flag2 == false)
			{
			SelectMove(NewPuzz);
			DisplayPuzzle(NewPuzz);
			Flag2 = CheckGoalState(NewPuzz);//If goal state is reached, a true is 
											//returned and the loop is broken
			MoveCount++; //lets you know how many moves youve made
			};
			
		DisplayPuzzle (NewPuzz); //shows puzzle in goal state
		
		cout << "CONGRATULATIONS " << User << "!  \nYou have successfully reached the goal state in " << MoveCount << " moves!\n";
		//compare user's move count to the computer's
		if (CPUmoveCount<MoveCount)
			cout << "However, the computer beat you " << CPUmoveCount << " to " << MoveCount << endl;
			else
			if (CPUmoveCount == MoveCount)
				cout << "You tied the computer! " << CPUmoveCount << " moves each.\n";
				else
					cout << "And you BEAT THE COMPUTER! " << MoveCount << " to " << CPUmoveCount << endl;
			
		
		}
		
	
}

//------------------------------------------------------------------------------------------------------
void SortOpenList(Node OPEN[],int ListLength)

//Shell sorts open nodes from lowest heuristic cost to greatest
//Code modified from Dr. Menuge's sample at http://www.cs.cuw.edu/csc/csc250/shelsort.cpp
{
	
	bool Swap;
	int
  	 Gap,
  	 Limit,
  	 LastElement,
  	 I;
  	Node Temp;
  	 
  	 LastElement = (ListLength - 1);
  	 
  	 Gap = LastElement / 2;
  	 
  	 while (Gap > 0)
  	 	{
  	 	Swap = true;
  	 	while (Swap)
  	 		{
  	 		Swap = false;  //stays false until a swap occurs
  	 		Limit = (LastElement - Gap);
  	 		
  	 		for (I = 0; I <= Limit; I++)
  	 			if (OPEN[I].Cost > OPEN[I + Gap].Cost)
  	 				{
  	 				Temp        = OPEN[I];
  	 				OPEN[I]     = OPEN[I+Gap];
  	 				OPEN[I+Gap] = Temp;
  	 				Swap        = true;
  	 				}
  	 		} //END inner while loop
  	 		
  	 	Gap = Gap / 2;
  	 	
  	 	} //END outer while loop
  	 	
  	 	
}
  	 				
//----------------------------------------------------------------------------------------------------  	 				
  	 				
void CreateNewNodes(int &OpenIndex, int ClosedIndex, Node OpenNodes[], Node ClosedNodes[])

{

	bool Duplicate = false;
	//int TempStorage;
	
	//Will now attempt to expand BestNode (OpenNodes[0]).
	//First, the location of the 0 (blank) is determined.
	
	if (OpenNodes[0].State[1] == 0)
		{
		OpenNodes[OpenIndex] = OpenNodes[0]; //copies BestNode to the next open spot in the OpenList
		SwitchContents(1,2,OpenNodes, OpenIndex); //Performs one of the possible switches
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false) //if the result of the switch creates a duplicate node, OpenIndex is not
							    //incremented, meaning it will be overwritten when the next possible move
							    //is attempted.  If no duplicates, OpenIndex is incremented, meaning the change 
							    //is made permanent.  Parent Node is recorded as well as last peice moved and cost.
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 2;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(1,4,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 4;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		}  	 	
		
	else 
	if (OpenNodes[0].State[2] == 0)
		{
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(2,1,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 1;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(2,5,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 5;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(2,3,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 3;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		} 
	
	else
	if (OpenNodes[0].State[3] == 0)
		{
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(3,2,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 2;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(3,6,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 6;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		}  
		
	else
	if (OpenNodes[0].State[4] == 0)
		{
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(4,1,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 1;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(4,5,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 5;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(4,7,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 7;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		} 	
	
	else
	if (OpenNodes[0].State[5] == 0)
		{
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(5,2,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 2;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(5,4,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 4;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(5,6,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 6;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(5,8,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 8;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		}  
	
	else
	if (OpenNodes[0].State[6] == 0)
		{
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(6,3,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 3;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(6,5,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 5;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(6,9,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 9;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		} 				
  	 	
  	 else
  	 if (OpenNodes[0].State[7] == 0)
		{
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(7,4,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 4;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(7,8,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 8;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		}  		
		
	else
	if (OpenNodes[0].State[8] == 0)
		{
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(8,5,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 5;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(8,7,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 7;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(8,9,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 9;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		
		} 	
		
	else
	if (OpenNodes[0].State[9] == 0)
		{
		
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(9,6,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 6;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
			
		OpenNodes[OpenIndex] = OpenNodes[0];
		SwitchContents(9,8,OpenNodes, OpenIndex);
		Duplicate = CompareToClosedNodes(OpenNodes, OpenIndex, ClosedIndex, ClosedNodes);
		if (Duplicate == false)
			{
			
			OpenNodes[OpenIndex].Parent = ClosedIndex;
			OpenNodes[OpenIndex].PeiceMoved = 8;
			CalculateCost(OpenNodes, OpenIndex);
			cout << "Node " << OpenIndex << " created." <<endl;
			OpenIndex++;
			}
		}  	
}			
//----------------------------------------------------------------------------------------------------
void SwitchContents(int Cell1, int Cell2, Node OpenNodes[], int OpenIndex)

{
	int TempStorage;
	
	//A plain old switching algorithm
	TempStorage = OpenNodes[OpenIndex].State[Cell1];
	OpenNodes[OpenIndex].State[Cell1] = OpenNodes[OpenIndex].State[Cell2];
	OpenNodes[OpenIndex].State[Cell2] = TempStorage;
	
}  	 				
  	 				
//-----------------------------------------------------------------------------------------------------  	 				
bool CompareToClosedNodes(Node OpenNodes [], int OpenIndex, int ClosedIndex, Node ClosedNodes[])

//ALSO compares to all currently open nodes as well
//We want NO dupliacate nodes at ANY point
{
	int Counter1 = 0;
	int Counter2 = 0;
	
	for (int i=0; (i<ClosedIndex) && (Counter1 != 9); i++)
		{
		Counter1 = 0;
		for (int i2=1; i2<10; i2++)
			{
			if (OpenNodes[OpenIndex].State[i2] == ClosedNodes[i].State[i2])
				Counter1++; 
			}
		}
	for (int j=0; (j<OpenIndex) && (Counter2 != 9); j++)
		{
		Counter2 = 0;
			for (int j2=1; j2<10; j2++)
				{
				if (OpenNodes[OpenIndex].State == OpenNodes[j].State)
					Counter2++; 
				}
		}
			
	if ((Counter1 == 9) || (Counter2 == 9))
		return true; //duplicate found
		else
			return false; //no duplicate found
	
}
			  	 				
//-----------------------------------------------------------------------------------------------------
void RemoveBestNode(Node OpenNodes[], Node ClosedNodes[], int &OpenIndex, int &ClosedIndex)

{
	//Moves BestNode to end of ClosedNodes[], and then shifts all OpenNodes up 1 place,
	//overwriting OpenNodes[0] in the process
	ClosedNodes[ClosedIndex] = OpenNodes[0];
	  	 				
  	for (int i=0; i<=OpenIndex; i++)
  		{
  		OpenNodes[i] = OpenNodes[i+1];
  		}		
  	 
  	OpenIndex = OpenIndex-1;
  	ClosedIndex++; 
  	
} 	

//---------------------------------------------------------------------------------------------------- 
  	 
void CalculateCost (Node OpenNodes[], int OpenIndex)

{
	int Price = 0;
	
	if ((OpenNodes[OpenIndex].State[1] == 2) || (OpenNodes[OpenIndex].State[1] == 4))
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[1] == 3) || (OpenNodes[OpenIndex].State[1] == 5) || (OpenNodes[OpenIndex].State[1] == 7))
			Price = (Price + 2);
			else
			if ((OpenNodes[OpenIndex].State[1] == 6) || (OpenNodes[OpenIndex].State[1] == 8))
				Price = (Price + 3);
				//else
				//if (OpenNodes[OpenIndex].State[1] == 0)
					//Price = (Price + 4);
					
	if ((OpenNodes[OpenIndex].State[2] == 1) || (OpenNodes[OpenIndex].State[2] == 3) || (OpenNodes[OpenIndex].State[2] == 5))
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[2] == 4) || (OpenNodes[OpenIndex].State[2] == 6) || (OpenNodes[OpenIndex].State[2] == 8))
			Price = (Price + 2);
			else
			if ((OpenNodes[OpenIndex].State[2] == 7)/* || (OpenNodes[OpenIndex].State[2] == 0)*/)
				Price = (Price + 3);
				
	if ((OpenNodes[OpenIndex].State[3] == 2) || (OpenNodes[OpenIndex].State[3] == 6))
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[3] == 1) || (OpenNodes[OpenIndex].State[3] == 5)/* || (OpenNodes[OpenIndex].State[3] == 0)*/)
			Price = (Price + 2);
			else
			if ((OpenNodes[OpenIndex].State[3] == 4) || (OpenNodes[OpenIndex].State[3] == 8))
				Price = (Price + 3);
				else
				if (OpenNodes[OpenIndex].State[3] == 7)
					Price = (Price + 4);
					
	if ((OpenNodes[OpenIndex].State[4] == 1) || (OpenNodes[OpenIndex].State[4] == 5) || (OpenNodes[OpenIndex].State[4] == 7))
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[4] == 2) || (OpenNodes[OpenIndex].State[4] == 6) || (OpenNodes[OpenIndex].State[4] == 8))
			Price = (Price + 2);
			else
			if ((OpenNodes[OpenIndex].State[4] == 3)/* || (OpenNodes[OpenIndex].State[4] == 0)*/)
				Price = (Price + 3);
				
	if ((OpenNodes[OpenIndex].State[5] == 2) || (OpenNodes[OpenIndex].State[5] == 4) || (OpenNodes[OpenIndex].State[5] == 6) || (OpenNodes[OpenIndex].State[5] == 8))
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[5] == 1) || (OpenNodes[OpenIndex].State[5] == 3) || (OpenNodes[OpenIndex].State[5] == 7)/* || (OpenNodes[OpenIndex].State[5] == 0)*/)
			Price = (Price + 2);
			
	if ((OpenNodes[OpenIndex].State[6] == 3) || (OpenNodes[OpenIndex].State[6] == 5)/* || (OpenNodes[OpenIndex].State[6] == 0)*/)
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[6] == 2) || (OpenNodes[OpenIndex].State[6] == 4) || (OpenNodes[OpenIndex].State[6] == 8))
			Price = (Price + 2);
			else
			if ((OpenNodes[OpenIndex].State[6] == 1) || (OpenNodes[OpenIndex].State[6] == 7))
				Price = (Price +3);
				
	if ((OpenNodes[OpenIndex].State[7] == 4) || (OpenNodes[OpenIndex].State[7] == 8))
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[7] == 1) || (OpenNodes[OpenIndex].State[7] == 5)/* || (OpenNodes[OpenIndex].State[7] == 0)*/)
			Price = (Price + 2);
			else
			if ((OpenNodes[OpenIndex].State[7] == 2) || (OpenNodes[OpenIndex].State[7] == 6))
				Price = (Price + 3);
				else
				if (OpenNodes[OpenIndex].State[7] == 3)
					Price = (Price + 4);

	if ((OpenNodes[OpenIndex].State[8] == 7) || (OpenNodes[OpenIndex].State[8] == 5)/* || (OpenNodes[OpenIndex].State[8] == 0)*/)
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[8] == 4) || (OpenNodes[OpenIndex].State[8] == 2) || (OpenNodes[OpenIndex].State[8] == 6))
			Price = (Price + 2);
			else
			if ((OpenNodes[OpenIndex].State[8] == 1) || (OpenNodes[OpenIndex].State[8] == 3))
				Price = (Price +3);
				
	if ((OpenNodes[OpenIndex].State[9] == 6) || (OpenNodes[OpenIndex].State[9] == 8))
		Price++;
		else
		if ((OpenNodes[OpenIndex].State[9] == 3) || (OpenNodes[OpenIndex].State[9] == 5) || (OpenNodes[OpenIndex].State[9] == 7))
			Price = (Price + 2);
			else
			if ((OpenNodes[OpenIndex].State[9] == 2) || (OpenNodes[OpenIndex].State[9] == 4))
				Price = (Price + 3);
				else
				if (OpenNodes[OpenIndex].State[9] == 1)
					Price = (Price + 4);  	 
  	 OpenNodes[OpenIndex].Cost = Price;
  	 
}  	 
  	 
//----------------------------------------------------------------------------------------------------------
bool CheckForGoal (Node OpenNodes[])

{
	 if ((OpenNodes[0].State[1] == 1) && 
	(OpenNodes[0].State[2] == 2) &&
	(OpenNodes[0].State[3] == 3) &&
	(OpenNodes[0].State[4] == 4) &&
	(OpenNodes[0].State[5] == 5) &&
	(OpenNodes[0].State[6] == 6) &&
	(OpenNodes[0].State[7] == 7) &&
	(OpenNodes[0].State[8] == 8) &&
	(OpenNodes[0].State[9] == 0))
		return true; //Game over, break out of loop
		else
			return false;
}

//----------------------------------------------------------------------------------------------------------

void AIAutoLoad(Node &Start)

{
	int BaseArray[9];    // array of peices;
    srand(time(0));  // initialize seed "randomly"
     
    for (int i=0; i<9; i++)
   		{
        BaseArray[i] = i;  // fill the array in order
        }
    
      
        //Shuffle elements by randomly exchanging each with one other.
        for (int i=0; i<9; i++) 
        	{
            int r = rand() % 9;  // generate a random position
            int temp = BaseArray[i]; 
            BaseArray[i] = BaseArray[r]; 
            BaseArray[r] = temp;
            }
        
        //Load Puzzle from randomized array
        for (int c=1; c<10; c++) 
        	{
            Start.State[c] = BaseArray[c-1];
            cout << Start.State[c] << " ";
       		}
       	cout << " \n";
       	system("PAUSE");
}

//-------------------------------------------------------------------------------------------------------------
void CheckManualLoadAI(int &InputVal, int Depth, Node &Start)

{
	//this while loop is to verify number is between 0 and 8
	while((Start.State[Depth+1] > 8) || (Start.State[Depth+1] < 0))
		{
		cout << "Please enter an integer from 0 to 8\n";
		cin >> Start.State[Depth+1];
		};//END while
	//for loop checks previous entries into the Puzzle struct
	for (int i = 1; i <= Depth; i++)//Depth variable specifies 
									//how many previous entries to look at
		{
		if (InputVal == Start.State[i])
			{
			//If duplicate is found, we go into this loop to get a new
			//value
			while ((InputVal == Start.State[i]) || (InputVal > 8) || (InputVal < 0))
				{
				cout << "You have entered a duplicate or out-of-range value. Try Again.\n";
				cin >> InputVal;
				};
			}
		}
		
}	
//-----------------------------------------------------------------------------------------------------------

void AIManualLoad(Node &Start)

{
	system("cls");
	//Puzzle TempPuzz[9];
	cout << "Enter a 0 for the blank.\n";
	cout << "Top Row Left = :"; 
	cin >> Start.State[1];
	CheckManualLoadAI(Start.State[1],0,Start);//data input validation
	
	cout << "Top Row Middle = :"; 
	cin >> Start.State[2];
	CheckManualLoadAI(Start.State[2],1,Start);//data input validation
	
	cout << "Top Row Right = :"; 
	cin >> Start.State[3];
	CheckManualLoadAI(Start.State[3],2,Start);//data input validation
	
	cout << "Middle Row Left = :"; 
	cin >> Start.State[4];
	CheckManualLoadAI(Start.State[4],3,Start);//data input validation
	
	cout << "Middle Row Middle = :"; 
	cin >> Start.State[5];
	CheckManualLoadAI(Start.State[5],4,Start);//data input validation
	
	cout << "Middle Row Right = :"; 
	cin >> Start.State[6];
	CheckManualLoadAI(Start.State[6],5,Start);//data input validation
	
	cout << "Bottom Row Left = :"; 
	cin >> Start.State[7];
	CheckManualLoadAI(Start.State[7],6,Start);//data input validation
	
	cout << "Bottom Row Middle = :"; 
	cin >> Start.State[8];
	CheckManualLoadAI(Start.State[8],7,Start);//data input validation
	
	cout << "Bottom Row Middle = :"; 
	cin >> Start.State[9];
	CheckManualLoadAI(Start.State[9],8,Start);//data input validation
	
}