Как решить проблему с 8 головоломками, используя поиск в ширину в C ++ - PullRequest
Новая
       22

Как решить проблему с 8 головоломками, используя поиск в ширину в C ++

0 голосов
/ 18 мая 2019

Я хочу создать программу на c ++, которая бы решала проблему из 8 задач с использованием BFS. Я хочу показать каждое сгенерированное состояние. Но проблема в том, что я не знаю, как создать государство. Я просто хочу некоторую чистую функцию, которая будет эффективно генерировать состояния, и будет массив Explored, который обеспечит отсутствие избыточного состояния.

Я изучил GitHub, но слишком много сложных решений

Я написал следующий код до сих пор 

#include<iostream>
#include<conio.h>
using namespace std;
class puzzle{
    private:
        int initial[3][3],goal[3][3] = {{1,2,3},{4,5,6},{7,8,0}};
        int queue[1000];
        string data;
    public:
        void genratePuzzle();
        void showState();
        bool check_goal(int initial);
};
void puzzle::genratePuzzle(){
    cout<<"\n***Create initial state 0-8***\n";
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cout<<"Insert at ["<<i<<"]["<<j<<"] : ";
            cin>>initial[i][j];
        }
    }
}
void puzzle::showState(){
    cout<<"\n***State***\n";
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cout<<initial[i][j]<<"  ";
        }
        cout<<endl;
    }
}
bool puzzle::check_goal(int initial){
    bool check = true;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(initial[i][j] != goal[i][j]){
                check = false;
            }
        }
    }
    return check;
}


int main(){
    puzzle p1;
    p1.genratePuzzle();
    p1.showState();
    getch();
}

Состояние цели 

1 2 3

4 5 6

7 8 0

1 Ответ

0 голосов
/ 18 мая 2019

Поместите ваше состояние в 

struct state {
    int data[3][3];
    bool operator < (const state & other) {
        for (int y=0; y<3; ++y) {
             for (int x=0; x<3; ++x) {
                 if (data[y][x] < other.data[y][x]) {
                     return true;
                 }
                 if (data[y][x] > other.data[y][x]) {
                     return false;
                 }
             }
        }
        return false; // all were equal
    }
}

Теперь вы можете использовать значения типа state в качестве ключей в std::map, например, сделать std::map<state, bool> explored, если хотите.Он ведет себя как массив, индексированный состояниями, поэтому: 

state a;
// do something to the state...

// and you can do this
explored[a] = true;

Как вы генерируете новые состояния?Вы начинаете с существующего состояния и пробуете на нем все допустимые ходы.Повторяйте, пока не закончите.

...