4
\$\begingroup\$

I am working on a fifteen puzzle, and just got it working finally. My next step is to implement an Iterative Deepening search on the puzzle to solve it.

I assume you go column by column, row by row with a loop until the checkwin function is complete? I would really love any pointers or guidance that can be given. Does not have to be code.

(A* is included, as that is the next step of my project to implement IDA*)

Here is my Code:

#include <iostream>
#include <ctime>

enum EMove {    keUp = 'w',
                keDown = 's',
                keLeft = 'a',
                keRight = 'd'};

// Function declarations
void InitializeBoard(char[4][4]);
void PrintBoard(char[4][4]);
void LocateSpace(int&, int&, char[4][4]);
void Randomize(char[4][4]);
void Move(char[4][4], const EMove);
void InitializeTestBoard(char[4][4]);
char checkWin(char[4][4], char);

int main() {
    char fBoard[4][4];
    char mode;
    int boardStates;
    int depth;
    using namespace std;

    cout << "Would you like to do Test mode, Normal Mode, or Solve Mode? Type 't' or 'n' or 's'" << endl;
    cin >> mode;

    int counter = 0;
    char isComplete = ' ';

    if (mode == 't')  //Test Mode
        {
        InitializeTestBoard(fBoard);
        do {
            counter++;
            PrintBoard(fBoard);
            cout << endl << "w = Up, s = Down, a = Left, d = Right" << endl;
            cout << endl << "A = 10, B = 11, C = 12, D = 13, E = 14, F = 15" << endl;
            char cNextMove;
            cin >> cNextMove;
            EMove eNextMove = (EMove)cNextMove;
            Move(fBoard, eNextMove);
            cout << endl;
            checkWin(fBoard, isComplete);
        } while (isComplete == 'n');

            cout << "You Win!!" << endl;
            cout << "In " << counter << " moves"<< endl;
            cout << endl;
            system("PAUSE");
            return EXIT_SUCCESS;
        }
    else if (mode == 'n')  //Normal Mode
        {  
        InitializeBoard(fBoard);
        Randomize(fBoard);
        do {
            counter++;
            PrintBoard(fBoard);  
            cout << endl << "w = Up, s = Down, a = Left, d = Right" << endl;
            cout << endl << "A = 10, B = 11, C = 12, D = 13, E = 14, F = 15" << endl;
            char cNextMove;
            cin >> cNextMove;
            EMove eNextMove = (EMove)cNextMove;
            Move(fBoard, eNextMove);
            cout << endl;
            checkWin(fBoard, isComplete);
        } while (isComplete == 'n');

            cout << "You Win!!" << endl;
            cout << "In " << counter << " moves" << endl;
            cout << endl;
            system("PAUSE");
            return EXIT_SUCCESS;

        }
    else if (mode == 's')   //solve mode (Iterative Deepening Search)
        {   
        InitializeBoard(fBoard);
        Randomize(fBoard);
        do {
            PrintBoard(fBoard);  
            cout << endl << "Number of Board States: " << boardStates << endl;
            cout << endl << "Depth Level:"<< depth << endl;
            cout << endl;
            checkWin(fBoard, isComplete);
        } while (isComplete == 'n');

            cout << "Puzzle Has been solved" << endl;
            cout << "In " << boardStates << " Board States" << endl;
            cout << endl;
            system("PAUSE");
            return EXIT_SUCCESS;
}

void InitializeTestBoard(char fBoard[4][4]) {
    const char tInitial[4][4] = {
            {'1', '2', '3', '4'},
            {'5', '6', '7', '8'},
            {'9', 'A', 'B', 'C'},
            {'D', 'E', ' ', 'F'}
    };
    for (int iRow = 0; iRow < 4; ++iRow) {
        for (int iCol = 0; iCol < 4; ++iCol) {
            fBoard[iRow][iCol] = tInitial[iRow][iCol];

        }
    }
}

void InitializeBoard(char fBoard[4][4]) {
    const char fInitial[4][4] = {
            {'1', '2', '3', '4'},
            {'5', '6', '7', '8'},
            {'9', 'A', 'B', 'C'},
            {'D', 'E', 'F', ' '}
    };
    for (int iRow = 0; iRow < 4; ++iRow) {
        for (int iCol = 0; iCol < 4; ++iCol) {
            fBoard[iRow][iCol] = fInitial[iRow][iCol];

        }
    }
}

void PrintBoard(char fBoard[4][4]) {
    using namespace std;
    for (int iRow = 0; iRow < 4; ++iRow) {
        for (int iCol = 0; iCol < 4; ++iCol) {
            cout << fBoard[iRow][iCol];
        }
        cout << endl;
    }
}

void LocateSpace(int& irRow, int& irCol, char fBoard[4][4]) {
    for (int iRow = 0; iRow < 4; ++iRow) {
        for (int iCol = 0; iCol < 4; ++iCol) {
            if (fBoard[iRow][iCol] == ' ') {
                irRow = iRow;
                irCol = iCol;
            }
        }
    }
}

void Randomize(char fBoard[4][4]) {
    using namespace std;
    srand((unsigned int)time(0));
    for (int iIndex = 0; iIndex < 1000000; ++iIndex) {
        const int kiNextMove = (rand() % 4);
        switch (kiNextMove) {
            case 0:
                {
                    Move(fBoard, keUp);
                    break;
                }
            case 1:
                {
                    Move(fBoard, keDown);
                    break;
                }
            case 2:
                {
                    Move(fBoard, keLeft);
                    break;
                }
            case 3:
                {
                    Move(fBoard, keRight);
                    break;
                }
        }
    }
}

void Move(char fBoard[4][4], const EMove keMove) {
    int iRowSpace;
    int iColSpace;
    LocateSpace(iRowSpace, iColSpace, fBoard);
    int iRowMove(iRowSpace);
    int iColMove(iColSpace);
    switch (keMove) {
        case keUp:
            {
                iRowMove = iRowSpace + 1;
                break;
            }
        case keDown:
            {
                iRowMove = iRowSpace - 1;
                break;
            }
        case keLeft:
            {
                iColMove = iColSpace + 1;
                break;
            }
        case keRight:
            {
                iColMove = iColSpace - 1;
                break;
            }
    }
    // Make sure that the square to be moved is in bounds
    if (iRowMove >= 0 && iRowMove < 4 && iColMove >= 0 && iColMove < 4) {
        fBoard[iRowSpace][iColSpace]    = fBoard[iRowMove][iColMove];
        fBoard[iRowMove][iColMove]  = ' ';
    } 
}

char checkWin(char fBoard[4][4], char isComplete) 
    {
        const char fInitial[4][4] = {
            {'1', '2', '3', '4'},
            {'5', '6', '7', '8'},
            {'9', 'A', 'B', 'C'},
            {'D', 'E', 'F', ' '}
        };

        for (int i= 0; i < 5; i++)
        {
        if (fBoard[1][i] == fInitial[1][i] || fBoard[1][i] == fInitial[1][i] || fBoard[1][i] == fInitial[1][i] || fBoard[1][i] == fInitial[1][i])
        {
        isComplete = 'y';
        }
        else
        isComplete = 'n';

        if (fBoard[2][i] == fInitial[2][i] || fBoard[2][i] == fInitial[2][i] || fBoard[2][i] == fInitial[2][i] || fBoard[2][i] == fInitial[2][i])
        {
        isComplete = 'y';
        }
        else
        isComplete = 'n';

        if (fBoard[3][i] == fInitial[3][i] || fBoard[3][i] == fInitial[3][i] || fBoard[3][i] == fInitial[3][i] || fBoard[3][i] == fInitial[3][i])
        {
        isComplete = 'y';
        }
        else
        isComplete = 'n';

        if (fBoard[4][i] == fInitial[4][i] || fBoard[4][i] == fInitial[4][i] || fBoard[4][i] == fInitial[4][i] || fBoard[4][i] == fInitial[4][i])
        {
        isComplete = 'y';
        }
        else
        isComplete = 'n';
        }

        return isComplete;
    }

Any help you can give would be awesome!

\$\endgroup\$
1
  • \$\begingroup\$ Can you factorize a bit the code duplicated for Test Mode and Normal Mode ? \$\endgroup\$
    – SylvainD
    Jan 9 '12 at 14:24
2
\$\begingroup\$

I see that your using system("PAUSE") it works all fine and dandy but behind the scenes it creates some extra overhead that could be avoided using standard c++ calls

read this article for more info on it...

http://www.gidnetwork.com/b-61.html

anyway if you replace it with cin.get(); it has the same effect... it's just a matter of pressing enter to continue also if you wanted to port this application to unix or mac os x, the system pause wouldn't work: you would get one of those "this command is not recognizable" messages. so... in conclusion, changing the system('PAUSE')'s to cin.get();'s is the way to go

also the codes readability might benefit if you put the function implementations in a separate file

hope this helped

\$\endgroup\$
2
  • 2
    \$\begingroup\$ IMO it doesn't matter that there will be a pause (overhead) when performing system("pause"). \$\endgroup\$
    – Abyx
    Nov 29 '11 at 11:04
  • \$\begingroup\$ Why would anybody advocate using a system call if its only to pause a program? (The answer isn't exactly related to the questions asked but still...). \$\endgroup\$
    – JayC
    Feb 9 '12 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy