Iterative Vertiefung und A *

  • Ich arbeite an einem fünfzehn Puzzle und habe es endlich fertiggestellt. Mein nächster Schritt besteht darin, eine iterative Deepening-Suche im Puzzle zu implementieren, um es zu lösen >

    Ich gehe davon aus, dass Sie Spalte für Spalte, Zeile für Zeile mit einer Schleife gehen, bis die Checkwin-Funktion abgeschlossen ist. Ich würde wirklich alle möglichen Hinweise oder Anweisungen lieben, die gegeben werden können Code sein.

    (A * ist enthalten, da dies der nächste Schritt meines Projekts zur Implementierung von IDA * ist)

    Hier ist mein 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;
        }
     

    Jede Hilfe, die Sie geben können, wäre fantastisch!

    09 November 2011
1 answer
  • Ich sehe, dass Ihre Verwendung von system("PAUSE") alles einwandfrei funktioniert, aber hinter den Kulissen entsteht ein zusätzlicher Aufwand, der durch standardmäßige C ++ - Aufrufe vermieden werden könnte.

    Lesen Sie diesen Artikel, um weitere Informationen darüber zu erhalten.

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

    Wenn Sie es durch cin.get(); ersetzen, hat dies den gleichen Effekt ... es ist nur eine Frage der Eingabetaste, um fortzufahren. Auch wenn Sie diese Anwendung nach Unix oder Mac os x portieren möchten, würde die Systempause nicht funktionieren: Sie würden eines davon bekommen "dieser Befehl ist nicht erkennbar "messages. so ... abschließend ist das Ändern der system('PAUSE') 's in cin.get();' s der richtige Weg.

    auch die Lesbarkeit der Codes könnte von Nutzen sein Wenn Sie die Funktionsimplementierungen in einer separaten Datei ablegen,

    hoffen Sie, dass dies geholfen hat

    09 November 2011