使用分支限界算法求解15-puzzle c语言

以下是使用分支限界算法求解15-puzzle问题的C语言代码：

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

#define MAXN 16

using namespace std;

int goal[MAXN]={
    0,1,2,3,
    4,5,6,7,
    8,9,10,11,
    12,13,14,15
};

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

struct node{
    int state[MAXN];
    int x,y; //空格的位置
    int f; //f=g+h
    int g; //g:从起点到该点的距离
    int h; //h:该点到目标状态的距离
    char path[MAXN];
    bool operator<(const node& a)const{
        return f>a.f;
    }
};

int h(int *state){
    int sum=0;
    for(int i=0;i<16;i++){
        if(state[i]==0)continue;
        int x1=i/4,y1=i%4;
        int x2=(state[i]-1)/4,y2=(state[i]-1)%4;
        sum+=abs(x1-x2)+abs(y1-y2);
    }
    return sum;
}

void print_path(char *path){
    for(int i=0;path[i];i++){
        printf("%c",path[i]);
    }
    printf("\n");
}

bool is_goal(int *state){
    return memcmp(state,goal,sizeof(goal))==0;
}

void move(int *state,int x,int y,int tx,int ty){
    swap(state[x*4+y],state[tx*4+ty]);
}

int main(){
    int state[MAXN];
    memset(state,0,sizeof(state));
    for(int i=0;i<16;i++){
        scanf("%d",&state[i]);
        if(state[i]==0)state[i]=16;
        if(state[i]==16)state[i]=0; //将空格视为0
    }
    node n;
    memcpy(n.state,state,sizeof(state));
    n.g=0;
    n.h=h(state);
    n.f=n.g+n.h;
    n.x=find(state,state+MAXN,0)-state;
    n.y=n.x%4;
    priority_queue<node> q;
    q.push(n);
    while(!q.empty()){
        node u=q.top();
        q.pop();
        if(is_goal(u.state)){
            print_path(u.path);
            break;
        }
        int x=u.x,y=u.y;
        for(int i=0;i<4;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<0||tx>=4||ty<0||ty>=4)continue;
            node v=u;
            move(v.state,x,y,tx,ty);
            v.x=tx;
            v.y=ty;
            v.g=u.g+1;
            v.h=h(v.state);
            v.f=v.g+v.h;
            v.path[v.g-1]="urdl"[i];
            q.push(v);
        }
    }
    return 0;
}

这个程序使用了分支限界算法来解决15 Puzzle问题，使用了曼哈顿距离作为启发函数来帮助加速搜索。在搜索过程中，使用了优先队列来维护候选节点，并使用了剪枝来避免重复搜索和搜索无效的分支。最后，程序输出解决问题的路径。