宽度优先遍历求解8数码问题

数据结构描述

typedef struct node {
    int a[3][3];
    struct node *pre;
    int x,y;
} *Pnode,Node;

a数组存放该节点的状态
pre指针指向该节点的父节点

queue<Pnode> open;

open表是一个先进先出的队列

问题是否有解的判断

    //判断是否有解
    int a[9],b[9];
    for(int i=0; i<9; i++) {
        a[i]=Phead->a[i/3][i%3] ;
        b[i]=target[i/3][i%3];
    }
    int t1=0,t2=0;
    for(int i=8; i>=0; i--)
        for(int j=i-1; j>=0; j--) {
            if(a[i]!=0)
                if(a[i]<a[j])
                    t1++;
            if(b[i]!=0)
                if(b[i]<b[j])
                    t2++;
        }

    printf("逆序数N1=%d 逆序数N2=%d\n",t1,t2);
    if(t1%2!=t2%2) {
        printf("该问题无解");
        return 0;
    }

其实状态和目标状态必须同为奇序列或同为偶序列（0不加入计算）

源代码

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<cstring>

using namespace std;
typedef struct node {
    int a[3][3];
    struct node *pre;
    int x,y;
} *Pnode,Node;


int Check(Pnode tem);
void bfs();
void up(Pnode tem);
void Right(Pnode ptm);
void Left(Pnode ptm);
void Down(Pnode ptm);
void Up(Pnode ptm);
void show(Pnode tem);

Pnode Phead;
queue<Pnode> open;


int flag=0;

int target[3][3]= {3,6,8,2,5,7,0,1,4};

int main() {

    Phead =(Pnode)malloc(sizeof(Node));
    Phead->pre =NULL;
    printf("请输入当前状态：\n");
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) {
            scanf("%d",&Phead->a[i][j]);
            if(Phead->a[i][j]==0) {
                Phead->x=i;
                Phead->y=j;
            }
        }
    printf("请输入目标：\n");
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) scanf("%d",&target[i][j]);

    //判断是否有解
    int a[9],b[9];
    for(int i=0; i<9; i++) {
        a[i]=Phead->a[i/3][i%3] ;
        b[i]=target[i/3][i%3];
    }
    int t1=0,t2=0;
    for(int i=8; i>=0; i--)
        for(int j=i-1; j>=0; j--) {
            if(a[i]!=0)
                if(a[i]<a[j])
                    t1++;
            if(b[i]!=0)
                if(b[i]<b[j])
                    t2++;
        }

    printf("逆序数N1=%d 逆序数N2=%d\n",t1,t2);
    if(t1%2!=t2%2) {
        printf("该问题无解");
        return 0;
    }
    bfs();
    return 0;
}

void bfs() {
    open.push(Phead);
    Check(Phead);
    while(!open.empty()&&flag==0) {
        Pnode tem=open.front();

        if(flag==0)
            Up(tem);
        if(flag==0)
            Down(tem);
        if(flag==0)
            Left(tem);
        if(flag==0)
            Right(tem);

        open.pop();
    }

}

void Up(Pnode ptm) {
    Pnode tem= (Pnode)malloc(sizeof(Node));
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)  tem->a[i][j]=ptm->a[i][j];
    tem->x=ptm->x;
    tem->y=ptm->y;
    int x=ptm->x,y=ptm->y;
    if(x==0) return ;
    int t=tem->a[x][y];
    tem->a[x][y]=tem->a[x-1][y] ;
    tem->a[x-1][y]=t;
    tem->x=x-1;
    int n=1;
    int index=0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) {
            index+=tem->a[i][j]*n;
            n=n*10;
        }

    tem->pre=ptm;
    if(Check(tem)==0) {
        open.push(tem);
    }


}

void Down(Pnode ptm) {
    Pnode tem= (Pnode)malloc(sizeof(Node));
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)  tem->a[i][j]=ptm->a[i][j];
    tem->x=ptm->x;
    tem->y=ptm->y;
    int x=ptm->x,y=ptm->y;
    if(x==2) return ;
    int t=tem->a[x][y];
    tem->a[x][y]=tem->a[x+1][y] ;
    tem->a[x+1][y]=t;
    tem->x=x+1;
    int n=1;
    int index=0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) {
            index+=tem->a[i][j]*n;
            n=n*10;
        }

    tem->pre=ptm;
    if(Check(tem)==0) {
        open.push(tem);
    }


}

void Left(Pnode ptm) {
    Pnode tem= (Pnode)malloc(sizeof(Node));
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)  tem->a[i][j]=ptm->a[i][j];
    tem->x=ptm->x;
    tem->y=ptm->y;
    int x=ptm->x,y=ptm->y;
    if(y==0) return ;
    int t=tem->a[x][y];
    tem->a[x][y]=tem->a[x][y-1] ;
    tem->a[x][y-1]=t;
    tem->y=y-1;
    int n=1;
    int index=0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) {
            index+=tem->a[i][j]*n;
            n=n*10;
        }

    tem->pre=ptm;
    if(Check(tem)==0) {
        open.push(tem);
    }


}

void Right(Pnode ptm) {
    Pnode tem= (Pnode)malloc(sizeof(Node));
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)  tem->a[i][j]=ptm->a[i][j];
    tem->x=ptm->x;
    tem->y=ptm->y;
    int x=ptm->x,y=ptm->y;
    if(y==2) return ;
    int t=tem->a[x][y];
    tem->a[x][y]=tem->a[x][y+1] ;
    tem->a[x][y+1]=t;
    tem->y=y+1;
    int n=1;
    int index=0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) {
            index+=tem->a[i][j]*n;
            n=n*10;
        }
    tem->pre=ptm;
    if(Check(tem)==0) {
        open.push(tem);
    }

}



int Check(Pnode tem) {

    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            if(tem->a[i][j]!=target[i][j]) {
                //  printf("falg=%d\n",flag);
                return 0;
            }
    flag=1;
    while(tem!=NULL&&flag==1) {
        show(tem);
        tem=tem->pre;
        //free(tem);
    }
    printf("找到解|");
    return 1;
}


void show(Pnode tem) {
    printf("---------\n");
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++)
            printf("%d ",tem->a[i][j]);
        printf("\n");
    }
    printf("---------\n");
}