AI 1 - Problem Solving (Artificial intelligence)

void gotoxy(int x, int y); // function prototype
// used to set cursor xy coordinates.

// enumerate search types
enum TYPE {BREADTH_FIRST, DEPTH_FIRST };

// enumerate possible A* heuristics (the second heuristic is
// depth, remember ???
enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES};
// include the header files we are going to need
#include<iostream.h> // for console i/o
#include<windows.h> // for sleep() and gotoxy()
#include"State.h" // for game state class
#include"Llist.h" // for a linked list class


CLList PrevStates; // Keep track of the poped states,
They must be kept in memory for tracing back the operators used to find the goal state,
But MUST be deleted whenthe program terminates to prevent memory leaks.
CLList MainQue; // Main Que, a list of states waiting there turn to be expanded.

SIDE PushSide;
SIDE PopSide;
// anouther function prototype, ignore this !
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic);

// number of states expanded (measure of efficiency
double Expanded = 0;

// when a solution state is found, pass it here.
// this will display it to screen.
void ShowSolution(CState* Solution) {

    // The solution is traced back, and therefore in reverse order.
    // Use a LIFO Stack to reverse them

    CLList Reverse;
    bool EndLoop=false;

    while(!EndLoop) {
        Reverse.Push(LEFT, Solution);
        if(Solution->GetPrevState() != 0) {
            Solution = Solution->GetPrevState();
        }
        else {
            EndLoop = true;
        }
    }

    int NewLine = 0;

    CState *Temp;

    cout << "\n";

    while(!Reverse.IsListEmpty()) {
        Temp = Reverse.Pop(LEFT);
        NewLine++;

        if(NewLine > 10) { cout << "\n"; NewLine=0;}

            switch(Temp->GetLastOperator()) {
            case NORTH:
                cout << "North, ";
                break;
            case EAST:
                cout << "East, ";
                break;
            case SOUTH:
                cout << "South, ";
                break;
            case WEST:
                cout << "West, ";
                break;
            }
        }

        cout << "\n\n" << "Expanded: " << Expanded << endl;
    }
}

    // sets the console i/o x,y coordinate.
    void gotoxy(int x, int y) {
        // SET CONSOLE CURSOR POSITION.

        COORD coord = {x,y};
        HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);

        SetConsoleCursorPosition(handle,coord);
    }

    // Sets up everything ready for the main loop.
void GeneralSearch(TYPE Type, HEURISTIC heuristic) {

    CState *Solution;
    int DepthLimit=0;

    switch(heuristic) {
    case NOT_USED:
        // Breadth First Queing Type
        if(Type == BREADTH_FIRST) {
            PushSide = RIGHT;
            PopSide = LEFT;
        }
        else {
            // Depth First Search
            cout << "Enter a Depth Limit :";
            cin >> DepthLimit;
            PushSide = RIGHT;
            PopSide = RIGHT;
        }
        break;
    case MANHATTAN_DISTANCE:
        PushSide = RIGHT;
        PopSide = RIGHT;
        break;
    case WRONG_TILES:
        PushSide = RIGHT;
        PopSide = RIGHT;

    }

    //Put the initial State onto the Que.
    // NO parameter constructor, creates the initial state
    MainQue.Push(PushSide, new CState());

    // Call the main Loop !!!!
    Solution = GeneralExpand(DepthLimit, heuristic);
    // returns pointer to soution.
    // or null pointer (failure)

    if(Solution != 0) {
        cout << "FOUND SOLUTION!" << endl;
        ShowSolution(Solution);
        cout << "DONE" << endl;
    }
    else {
        //Fail
        cout << "FAIL" << endl;
    }
}

    // THE MAIN LOOP, (YEP, it BITES !)
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic) {

    CState *CurrentState = 0;
    CState *TempState = 0;

    int LastDepth=-1;

    if(PushSide == PopSide) {cout << "THINKING...please wait." << endl;}
    // Main loop
    while(!MainQue.IsListEmpty()) {

        if(heuristic == NOT_USED) {
            CurrentState = MainQue.Pop(PopSide);
        }
        else {
            CurrentState = MainQue.PopBestByHeuristics(heuristic);
        }

        PrevStates.Push(RIGHT, CurrentState); // Keep track of poped states (Prevent memory leaks)

        // Give the user an idea of the level of completion. (works for breadth first only)
        if(LastDepth < CurrentState->GetDepth() && PushSide != PopSide) {
            LastDepth = CurrentState->GetDepth();
            cout << "EXPANDING LEVEL " << LastDepth << endl;
        }

        // only expand this node if it does not exceed the depth limit
        if((CurrentState->GetDepth() < DepthLimit) || (DepthLimit == 0 )) {

            if((CurrentState->CanBlankMove(NORTH)) && (CurrentState->GetLastOperator() != SOUTH)) {

                TempState = new CState(CurrentState, NORTH);
                MainQue.Push(PushSide, TempState);
                Expanded++;

                if(TempState->Solution()) {
                    return TempState;
                }
            }

            if((CurrentState->CanBlankMove(EAST)) && (CurrentState->GetLastOperator() != WEST)) {

                TempState = new CState(CurrentState, EAST);
                MainQue.Push(PushSide, TempState);
                Expanded++;

                if(TempState->Solution()) {
                    return TempState;
                }
            }

            if((CurrentState->CanBlankMove(SOUTH)) && (CurrentState->GetLastOperator() != NORTH)) {

                TempState = new CState(CurrentState, SOUTH);
                MainQue.Push(PushSide, TempState);
                Expanded++;

                if(TempState->Solution()) {
                    return TempState;
                }
            }

            if((CurrentState->CanBlankMove(WEST)) && (CurrentState->GetLastOperator() != EAST)) {

                TempState = new CState(CurrentState, WEST);
                MainQue.Push(PushSide, TempState);
                Expanded++;

                if(TempState->Solution()) {
                    return TempState;
                }
            }
        }
    }
    return 0;
}

Scared? Don’t worry, we've more or less finished now.