c语言15-puzzle解法,15 Puzzle (4乘4谜题) IDA*(DFS策略与曼哈顿距离启发) 的C语言实现...

以下是C语言实现15 Puzzle问题的IDA*(DFS策略与曼哈顿距离启发)的代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAXN 16

//目标状态
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};
char dir[4]={'u','r','d','l'};

//启发函数，曼哈顿距离
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;
}

//深度优先搜索
int dfs(int dep,int last,int *state,int limit,char *path){
    int f=dep+h(state);
    if(f>limit)return f;
    if(memcmp(state,goal,sizeof(goal))==0)return 0;
    int x,y,tx,ty;
    x=last/4,y=last%4;
    for(int i=0;i<4;i++){
        tx=x+dx[i],ty=y+dy[i];
        if(tx<0||tx>=4||ty<0||ty>=4)continue;
        //剪枝
        if(dep>0&&path[dep-1]==dir[i])continue;
        int t=tx*4+ty;
        swap(state[last],state[t]);
        path[dep]=dir[i];
        int d=dfs(dep+1,t,state,limit,path);
        if(d==0)return 0;
        swap(state[last],state[t]);
    }
    return f;
}

int main(){
    int state[MAXN];
    char path[MAXN];
    for(int i=0;i<16;i++){
        scanf("%d",&state[i]);
        if(state[i]==0)state[i]=16;
    }
    int limit=h(state);
    while(dfs(0,0,state,limit,path)!=0){
        limit++;
    }
    path[limit]='\0';
    printf("%s\n",path);
    return 0;
}

这个程序使用深度优先搜索算法来解决15 Puzzle问题，并且使用曼哈顿距离作为启发函数来帮助加速搜索。在搜索过程中，使用剪枝来避免重复搜索。最后，程序输出解决问题的路径。