This part doesn’t have much to do with AI, but, you cant code a AI program without one, so we have to do it. If you don’t know, a linked list is used to replace an array. Why don’t we use an array ? Well, because as array’s size is set at design time, and cannot be changed during run time, so, as soon as the program starts you would have an array of 6 million Cstates, wasting all that memory when you don't need it.

A linked list makes space for new states as and when it is used. I won't bother telling you how it works, there are plenty of examples all over the place. You just need to know that it does work, and its just a variable sized array! nothing more. The linked list will not actually hold the states, just pointers to states, this is because, the list will act as a queue for states waiting to be expanded, when a state is expanded, it is removed from the list. However, we need to keep expanded states in memory for when it comes to tracing back and reporting the path from initial state to solution state.

When we actually start coding the main loop, we will place expanded states on a second que, so that we keep track of where they are when its time to delete the states from memory (prevent memory leaks)

OKAY,, from now on, were back to C++ code, Make a new header file “Llist.h” and put the following in there.

// enum the ends of the list
enum SIDE { LEFT, RIGHT };

// the list is made up of the following Links.
struct Link {
   Link   *LeftLink; // pointer to link on left
   Link   *RightLink; // pointer to link on right
   CState *Data; // pointer to actual data, the state.
};

// the main list
class CLList {

private:

   Link* LeftPointer; // pointer to a perminant and BLANK link
   Link* RightPointer; // same as above, opposite end.
   double ListLen; // number of non-blank lists in list.
   
   // Removes EVERYTHING from memory
//(Links, AND the state data they point to)
   void EmptyUsedMemory() {
       CState *temp;
       while(!IsListEmpty()) {
           temp = Pop(LEFT);
           delete temp;
       }
   }

public:
   
   class ERROR_CANT_POP_EMPTY_LIST{}; // Error Exception

   CLList() {
       // initialise all private variables
       LeftPointer  = new Link;
       RightPointer = new Link;
       ListLen      = 0;

       LeftPointer->LeftLink = 0;
       LeftPointer->RightLink = RightPointer;
       RightPointer->RightLink = 0;
       RightPointer->LeftLink = LeftPointer;
   }

   ~CLList() {
       EmptyUsedMemory();
   }

   inline double GetListLen() {
       return ListLen;
   }
   
   inline bool IsListEmpty() {
       return (LeftPointer->RightLink == RightPointer);
   }

   CState* Pop(SIDE Side) {

       Link  ForReturn;
       Link* ForDelete;
           
       if (!IsListEmpty()) {

           ListLen--;
           if (Side == LEFT) {

               ForReturn                      = *(LeftPointer->RightLink);
               ForDelete                      = LeftPointer->RightLink;
               LeftPointer->RightLink         = ForReturn.RightLink;
               ForReturn.RightLink->LeftLink  = LeftPointer;

           }
           else {

               ForReturn                      = *(RightPointer->LeftLink);
               ForDelete                      = RightPointer->LeftLink;
               RightPointer->LeftLink         = ForReturn.LeftLink;
               ForReturn.LeftLink->RightLink  = RightPointer;
           }

           delete ForDelete;
           return ForReturn.Data;
       }
       return 0;
   }

   void Push(SIDE Side, CState* What) {
       Link* NewLink = new Link;
       NewLink->Data = What;
       ListLen++;

       if (Side == LEFT) {

           NewLink->RightLink           = LeftPointer->RightLink;
           NewLink->LeftLink            = LeftPointer;
           LeftPointer->RightLink       = NewLink;
           NewLink->RightLink->LeftLink = NewLink;
       }
       else {

           NewLink->RightLink           = RightPointer;
           NewLink->LeftLink            = RightPointer->LeftLink;
           RightPointer->LeftLink       = NewLink;
           NewLink->LeftLink->RightLink = NewLink;
       }
   }

   CState* PopBestByHeuristics(HEURISTIC heuristic) {

       int   BestValue=9999;
       int   Temp=0;
       Link* BestState = 0;
       Link* Current = LeftPointer;
       CState* ForReturn = 0;
       
       if(!IsListEmpty()) {

       // Find BEST State By Wrong tile number heuristic
           while(Current->RightLink != RightPointer) {

               Current = Current->RightLink;
               
               if(heuristic == MANHATTAN_DISTANCE) {
                   Temp = Current->Data->GetManhattanDistance();
               }
               else {
                   Temp = Current->Data->GetWrongTiles();
               }

               if(Temp < BestValue) {
                   BestValue = Temp;
                   BestState = Current;
               }
           }

           // POP the value out the List.
           // Make the link to the right's left pointer point to the link on the left.
           BestState->RightLink->LeftLink = BestState->LeftLink;
           BestState->LeftLink->RightLink = BestState->RightLink;

           ForReturn = BestState->Data;
           delete BestState;

           return ForReturn;
       }
       return 0;
   }

   CState* PeekByBestHueristics(HEURISTIC heuristic) {
   

       int   BestValue=9999;
       int   Temp=0;
       Link* BestState = 0;
       Link* Current = LeftPointer;
       CState* ForReturn = 0;
       
       if(!IsListEmpty()) {

       // Find BEST State By Wrong tile number heuristic
           while(Current->RightLink != RightPointer) {

               Current = Current->RightLink;
               
               if(heuristic == MANHATTAN_DISTANCE) {
                   Temp = Current->Data->GetManhattanDistance();
               }
               else {
                   Temp = Current->Data->GetWrongTiles();
               }

               if(Temp < BestValue) {
                   BestValue = Temp;
                   BestState = Current;
               }
           }

           ForReturn = BestState->Data;

           return ForReturn;
       }
       return 0;
   }

So, like I said. Hopefully you will know how linked lists work, if you don’t, here is a little explanation of what each function does…

• GetListLen() returns the number of NON blank links in the list
• IsListEmpty() returns true if there is no data in the list
• Pop(SIDE) removes a Cstate pointer from the list side, and returns it.
• Push(SIDE, WHAT) pushes the WHAT pointer onto the SIDE side of the list.
• PopBestByHeuristics(HEURISTIC heuristic) pops the link that scored highest using Heuristic HEURISTC, (which will be enumberated later)
• PeekByBestHueristics(HEURISTIC heuristic) does the same as above, except the data is not removed from the list, just returned.

OKAY… Now that we have the 2 main class’ here is the hard part. Writing the main loop !