不必先去弄最优解啊~弄个其中一个解出来就已经很强大了~~我在你的另一个贴说了一下简单的设想~这只是我的设想而已~现阶段实现不了就不要强求~当我什么都没有说~

https://bbs.bccn.net/thread-455109-1-1.html
搜了个A*算法解八数码~

那个代码要用后缀.cpp运行
为了支持某些旧版编译器我把代码修改了一下(我已经说明了出处)~~

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#define NUM 5 
typedef struct bgMatrix 
{ 
    int v, w; 
    char matrix[NUM][NUM]; 
    int pre; 
    int f; 
    int g; 
    bool isVisited; 
}Matrix; 
typedef struct bgQueue 
{ 
    Matrix* data; 
    int length; 
    int maxLength; 
    int head; 
    int tail; 
}BGQueue; 
typedef BGQueue* Queue; 
typedef struct bgStack 
{ 
    Matrix* data; 
    int top; 
}BGStack; 
typedef BGStack* Stack; 
char srcMatrix[NUM][NUM] = 
{ 
    {'*', '*', '*', '*', '*'}, 
    {'*', '2', '8', '3', '*'}, 
    {'*', '1', '6', '4', '*'}, 
    {'*', '7', '0', '5', '*'}, 
    {'*', '*', '*', '*', '*'} 
}; 
char dstMatrix[NUM][NUM] = 
{ 
    {'*', '*', '*', '*', '*'}, 
    {'*', '1', '2', '3', '*'}, 
    {'*', '8', '0', '4', '*'}, 
    {'*', '7', '6', '5', '*'}, 
    {'*', '*', '*', '*', '*'} 
}; 
int dx[4] = {0, 0, -1, 1}; 
int dy[4] = {1, -1, 0, 0}; 
int cnt = -1; 
Queue queue; 
Stack stack; 
bool astar(Matrix matrix); 
int getG(Matrix matrix); 
void initQueue(int length); 
void putQueue(Matrix matrix); 
Matrix getQueue(void); 
int isQueueEmpty(void); 
int isQueueFull(void); 
void initStack(int length); 
void pushStack(Matrix matrix); 
Matrix popStack(void); 
int isStackEmpty(void); 
int matrixCmp(char src[][NUM], char dst[][NUM]); 
void matrixCpy(char dst[][NUM], char src[][NUM]); 
void matrixPrint(char matrix[][NUM]); 
int main(int argc, char *argv[]) { 
   
    Matrix src; 
   
    initQueue(3628800+1); 
    initStack(3628800+1); 
   
    src.v = 3; 
    src.w = 2; 
    matrixCpy(src.matrix, srcMatrix); 
    src.pre = cnt; 
    src.f = 0; 
    src.g = getG(src); 
    astar(src); 
    return 0; 
} 
bool astar(Matrix matrix) 
{ 
    Matrix t, s; 
   
    int v, w; 
   
    int direction; 
   
    putQueue(matrix); 
   
    while (!isQueueEmpty()) 
    { 
        s = getQueue(); 
       
        cnt++; 
       
        for (direction = 0; direction < 4; direction++) 
        { 
            t = s; 
            v = t.v + dx[direction]; w = t.w + dy[direction]; 
           
            if (srcMatrix[v][w] != '*') 
            { 
                char c = t.matrix[t.v][t.w]; 
                t.matrix[t.v][t.w] = t.matrix[v][w]; 
                t.matrix[v][w] = c; 
               
                t.v = v; 
                t.w = w; 
                t.pre = cnt; 
                t.f = s.f + 1; 
                t.g = getG(t); 
                t.isVisited = false; 
               
                int h = 0;
                for (; h < queue->tail; h++) 
                { 
                    if (matrixCmp(queue->data[h].matrix, t.matrix)) 
                    { 
                        break; 
                    } 
                } 
               
                if (h == queue->tail) 
                { 
                    putQueue(t); 
                   
                    if (matrixCmp(t.matrix, dstMatrix)) 
                    { 
                        pushStack(t); 
                       
                        for (int father = t.pre; !matrixCmp(queue->data[father].matrix, srcMatrix); father = queue->data[father].pre) 
                        { 
                            pushStack(queue->data[father]); 
                        } 
                       
                        puts("PathFind = "); 
                       
                        matrixCpy(t.matrix, srcMatrix); 
                        pushStack(t); 
                       
                        while (!isStackEmpty()) 
                        { 
                            s = popStack(); 
                            matrixPrint(s.matrix); 
                        } 
                       
                        return true; 
                    } 
                } 
            } 
        } 
    } 
   
    return false; 
} 
int getG(Matrix matrix) 
{ 
    int g = 0; 
   
    for (int i = 0; i < NUM; i++) 
    { 
        for (int j = 0; j < NUM; j++) 
        { 
            if (matrix.matrix[i][j] != '*' && matrix.matrix[i][j] != dstMatrix[i][j]) 
            { 
                g++; 
            } 
        } 
    } 
   
    return g; 
} 
void initQueue(int length) 
{ 
    queue =(bgQueue* ) malloc(sizeof(BGQueue)); 
   
    queue->data =(bgMatrix* ) malloc(sizeof(Matrix) * length); 
    queue->length = 0; 
    queue->maxLength = length; 
    queue->head = 0; 
    queue->tail = 0; 
} 
void putQueue(Matrix matrix) 
{ 
    queue->data[queue->tail++] = matrix; 
    queue->tail = queue->tail % queue->maxLength; 
    queue->length++; 
   
    Matrix* a =(bgMatrix* ) malloc(sizeof(Matrix) * queue->maxLength); 
    Matrix* b =(bgMatrix* ) malloc(sizeof(Matrix) * queue->maxLength); 
   
    int an = 0; 
    int bn = 0;
    int i=0;
   
    for (i = 0; i < queue->length; i++) 
    { 
        if (queue->data[i].isVisited) 
        { 
            a[an++] = queue->data[i]; 
        } 
        else 
        { 
            b[bn++] = queue->data[i]; 
        } 
    } 
    for (i = 0; i < bn-1; i++) 
    { 
        for (int j = bn-1; j > i; j--) 
        { 
            int h1 = b[j-1].f + b[j-1].g; 
            int h2 = b[j].f + b[j].g; 
           
            if (h1 > h2) 
            { 
                Matrix t = b[j-1]; 
                b[j-1] = b[j]; 
                b[j] = t; 
            } 
        } 
    } 
   
    for (i = 0; i < an; i++) 
    { 
        queue->data[i] = a[i]; 
    } 
   
    for (i = 0; i < bn; i++) 
    { 
        queue->data[an+i] = b[i]; 
    } 
    free(a); 
    free(b); 
} 
Matrix getQueue(void) 
{ 
    queue->data[queue->head].isVisited = true; 
   
    Matrix ret; 
    ret = queue->data[queue->head++]; 
    queue->head = queue->head % queue->maxLength; 
   
    return ret; 
} 
int isQueueEmpty(void) 
{ 
    return queue->head == queue->tail; 
} 
int isQueueFull(void) 
{ 
    return ((queue->tail+1) % queue->maxLength) == queue->head; 
} 
void initStack(int length) 
{ 
    stack = (bgStack* )malloc(sizeof(BGStack)); 
   
    stack->data =(bgMatrix* ) malloc(sizeof(Matrix) * length); 
    stack->top = 0; 
   
} 
void pushStack(Matrix matrix) 
{ 
    stack->data[stack->top++] = matrix; 
} 
Matrix popStack(void) 
{ 
    Matrix ret; 
    ret = stack->data[--stack->top]; 
   
    return ret; 
} 
int isStackEmpty(void) 
{ 
    return (stack->top == 0); 
} 
int matrixCmp(char src[][NUM], char dst[][NUM]) 
{ 
    int i, j, s, t, ret; 
   
    char srcString[30] = {0}; 
    char dstString[30] = {0}; 
   
    s = 0; 
    t = 0; 
   
    for (i = 0; i < NUM; i++) 
    { 
        for (j = 0; j < NUM; j++) 
        { 
            srcString[s++] = src[i][j]; 
            dstString[t++] = dst[i][j]; 
        } 
    } 
   
    ret = !strcmp(srcString, dstString); 
   
    return ret; 
} 

 
void matrixCpy(char dst[][NUM], char src[][NUM]) 
{ 
    int i, j; 
   
    for (i = 0; i < NUM; i++) 
    { 
        for (j = 0; j < NUM; j++) 
        { 
            dst[i][j] = src[i][j]; 
        } 
    } 
} 
void matrixPrint(char matrix[][NUM]) 
{ 
    char s[60] = {0}; 
   
    int i, j, k; 
   
    k = 0; 
   
    for (i = 0; i < NUM; i++) 
    { 
        for (j = 0; j < NUM; j++) 
        { 
            s[k++] = matrix[i][j]; 
        } 
       
        s[k++] = '\r'; 
        s[k++] = '\n'; 
    } 
   
    s[k++] = '\r'; 
    s[k++] = '\n'; 
   
    puts(s); 
   
}  

[此贴子已经被作者于2017-6-10 04:22编辑过]

八数码和数字16完全不在一个数量级好不！8数码只有40320种组合，我一个深度搜索就可以达到目的，如果要得到最优解，我只要写一个4叉树（0的4个方向的运动），留下得到正确结果的路径，找最少节点的那个，很容易实现的，我要写这个，肯定比楼上的代码少且优（捂脸）
数字16有20922789888000种组合，20T的数据容量，即使用虚拟内存，也没有哪个家用级的电脑硬盘存的下，遍历、树是无法完成的，只能是设计一个智能算法，摒弃那些完全达不到目的的树节点，这个智能算法我想不出来。

我的天哪~认真看这个打着A*算法的名义~实质是普通的广搜~~~
运行了那个代码3*3的跑了两三秒才跑出来~
这个数量级别正常的A*算法能在0.1s内跑出答案~虽然不一定是最优解~~~~

高手

学习了。。

非常不错   很不错的帖子

我复制后发现这一步报错了：void drawmap(unsigned _int64 a,int x,int y)

你可能用的是gcc编译，把代码中的所有“_int64”用“long long”替代即可。

谢谢