0%

八数码难题

发表于 分类于 ，

前言

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

搜索方法的选择

emmm，我选择了最简单的BFS，当然我想过DFS，但是深度是无法确定的，所以不太适合用DFS，在别人的博客上我还看见过DBFS（即双向广度优先搜索），有空我要去万一下下。

怎么开始

  1. 每个状态都用3*3的数组表示，比较麻烦而且空间占用较大（后面想了想除非很复杂其实占用的空间也不会特别多）

  2. 所以进行了状态压缩，采用一个整数保存状态的数字序列，例如状态1表示为283104765,状态2表示为203184765

  3. 然后我在想除了存状态，我还需要存方向，因为避免遍历的下一步重复回到父节点我需要知道本次移动的方向

  4. 然后这是一个链表，是两个链表连在一起的（如图下），所以需要两个指针，分别指向按BFS搜索遍历出来的顺序（*next）和节点的父节点（*up）。1

  5. 然后一个结构体作为其节点就这么出来了。

    1
    2
    3
    4
    5
    6
    struct node {
        int move;//从上一次到本次所移动的方向
        int num;//本次数码排列顺序 1左 2右 3上 4下
        struct node *next;//BFS的下一个
        struct node *up;//父节点
    };

怎么判断

​ 我认为这是最好解决的问题了，刚刚开始还想懵了，后面发现直接判断整型是否相等不就好了吗。

流程图思路

2

代码实现

因为对C最熟练，所以无可救药的继续用C写没有用C++，然后发现数组转整型难用的事实，能用C++还是C++吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
//
// Created by ZhiNian on 2019/10/22.
//

#include <cstdio>
#include <cstdlib>

int ArrayFather[5][5];//用于存根节点的二维数组
int ArraySon[5][5];//用于存从根节点移动后的二维数组

int ZeroX, ZeroY;//用于存当前节点0的位置

struct node {
    int move;//从上一次到本次所移动的方向
    int num;//本次数码排列顺序 1左 2右 3上 4下
    struct node *next;//BFS的下一个
    struct node *up;//父节点
};

node *Creat(int num, int move, node *up) {//新建节点的函数，用于产生节点，可以 传入当前状态的num 本次移动的方向move 父节点的地址up 进行创建节点
    node *start;
    start = (struct node *) malloc(sizeof(struct node));
    start->num = num;
    start->move = move;
    start->next = NULL;
    start->up = up;
    return start;
}

void copy() {//将父节点的二维数组复制给子节点从而再进行移动操作
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            ArraySon[i][j] = ArrayFather[i][j];
        }
    }
}

void int2ArrayFather(int num) {//将所储存的整型数据变成二维数组便于操作
    //关键点在于一个3*3数组我转换为了5*5的数组，围绕在3*3数组的外围全为-1，从而在判断围墙的时候只需要判断需要移动的方向所存的数值是否为-1，为-1则不允许移动（即此面是墙）
    ArrayFather[0][0] = -1;
    ArrayFather[0][1] = -1;
    ArrayFather[0][2] = -1;
    ArrayFather[0][3] = -1;
    ArrayFather[0][4] = -1;

    ArrayFather[1][0] = -1;
    ArrayFather[2][0] = -1;
    ArrayFather[3][0] = -1;
    ArrayFather[4][0] = -1;

    ArrayFather[4][1] = -1;
    ArrayFather[4][2] = -1;
    ArrayFather[4][3] = -1;
    ArrayFather[4][4] = -1;

    ArrayFather[1][4] = -1;
    ArrayFather[2][4] = -1;
    ArrayFather[3][4] = -1;
    ArrayFather[4][4] = -1;
    //以下是整型把每一位数传入数组
    ArrayFather[1][1] = num / 100000000;
    num = num % 100000000;
    ArrayFather[1][2] = num / 10000000;
    num = num % 10000000;
    ArrayFather[1][3] = num / 1000000;
    num = num % 1000000;
    ArrayFather[2][1] = num / 100000;
    num = num % 100000;
    ArrayFather[2][2] = num / 10000;
    num = num % 10000;
    ArrayFather[2][3] = num / 1000;
    num = num % 1000;
    ArrayFather[3][1] = num / 100;
    num = num % 100;
    ArrayFather[3][2] = num / 10;
    num = num % 10;
    ArrayFather[3][3] = num;
    //记录下0所在的位置
    for (int i = 1; i < 4; ++i) {
        for (int j = 1; j < 4; ++j) {
            if (ArrayFather[i][j] == 0) {
                ZeroX = i;
                ZeroY = j;
            }

        }

    }

}

int ArraySon2int() {//将已产生的子节点转换为整型
    return ArraySon[1][1] * 100000000 + ArraySon[1][2] * 10000000 + ArraySon[1][3] * 1000000 + ArraySon[2][1] * 100000 +
           ArraySon[2][2] * 10000 + ArraySon[2][3] * 1000 + ArraySon[3][1] * 100 + ArraySon[3][2] * 10 + ArraySon[3][3];
}

//move标记量 1左 2右 3上 4下
node *Eight(int start, int end) {
    node *k = Creat(start, 0, NULL);//根节点，用creat产生根节点，因为根节点的up（父节点无）所以为NULL，move定义为0，即未移动也可以通过此标记知道是父节点
    node *p = k;//此节点开始先为根节点
    node *l;//新节点
    while (1) {//不等于则继续循环
        int2ArrayFather(k->num);
        if (k->move == 0) {//通过move是否等于0去判断是否是根节点（根节点move为0在上面备注已解释），根节点就不需要判断上一次所移动的方向，所以需要单独提出进行判断
            if (ArrayFather[ZeroX][ZeroY - 1] != -1) {//判断所要左移的方向是否是-1（即所移动的方向是否是墙）不是墙才能移动
                copy();//将父节点的数组复制给子节点的数组
                ArraySon[ZeroX][ZeroY] = ArraySon[ZeroX][ZeroY - 1];//进行移位操作
                ArraySon[ZeroX][ZeroY - 1] = 0;
                l = Creat(ArraySon2int(), 1, k);//通过create建立新的节点，传入ArraySon2int()即将当前子数组转化为int型记录，传入1表示当前是左移，传入k，表示此节点的父节点是k
                p->next = l;//将当前节点的next指向新节点
                p = l;//当前节点指向再跳到此节点
                if (p->num == end)//如果当前节点的num等于所到达的num
                    break;//那么就跳出循环结束程序
            }
            if (ArrayFather[ZeroX][ZeroY + 1] != -1) {//同上 右移动
                copy();
                ArraySon[ZeroX][ZeroY] = ArraySon[ZeroX][ZeroY + 1];
                ArraySon[ZeroX][ZeroY + 1] = 0;
                l = Creat(ArraySon2int(), 2, k);//传入2表示此次操作是右移
                p->next = l;
                p = l;
                if (p->num == end)
                    break;
            }
            if (ArrayFather[ZeroX - 1][ZeroY] != -1) {//同上 上移动
                copy();
                ArraySon[ZeroX][ZeroY] = ArraySon[ZeroX - 1][ZeroY];
                ArraySon[ZeroX - 1][ZeroY] = 0;
                l = Creat(ArraySon2int(), 3, k);//传入3表示此次操作是上移
                p->next = l;
                p = l;
                if (p->num == end)
                    break;
            }
            if (ArrayFather[ZeroX + 1][ZeroY] != -1) {//同上 下移动
                copy();
                ArraySon[ZeroX][ZeroY] = ArraySon[ZeroX + 1][ZeroY];
                ArraySon[ZeroX + 1][ZeroY] = 0;
                l = Creat(ArraySon2int(), 4, k);//传入4表示此次操作是下移
                p->next = l;
                p = l;
                if (p->num == end)
                    break;
            }
        } else {//当非头节点的时候，于头节点的第一个判断标准是一样的，即是否所移动的方向是墙，其次还需判断父节点所移动的方向，因为父亲节点移动的方向若是上，那么此次就不能下移动，否则会陷入死循环
            if (ArrayFather[ZeroX][ZeroY - 1] != -1 && k->move != 2) {//判断左移的方向是否是墙（即左边一个格子的值是否是-1）还需要判断父节点的上一次操作是否是右移（move！=2），若不是才能进行移位操作
                copy();//将父节点的数组复制给子节点的数组
                ArraySon[ZeroX][ZeroY] = ArraySon[ZeroX][ZeroY - 1];//进行移位操作
                ArraySon[ZeroX][ZeroY - 1] = 0;
                l = Creat(ArraySon2int(), 1, k);//通过create建立新的节点，传入ArraySon2int()即将当前子数组转化为int型记录，传入1表示当前是左移，传入k，表示此节点的父节点是k
                p->next = l;//将当前节点的next指向新节点
                p = l;//当前节点指向再跳到此节点
                if (p->num == end)//如果当前节点的num等于所到达的num
                    break;//那么就跳出循环结束程序
            }
            if (ArrayFather[ZeroX][ZeroY + 1] != -1 && k->move != 1) {//同上 判断能否右移
                copy();
                ArraySon[ZeroX][ZeroY] = ArraySon[ZeroX][ZeroY + 1];
                ArraySon[ZeroX][ZeroY + 1] = 0;
                l = Creat(ArraySon2int(), 2, k);
                p->next = l;
                p = l;
                if (p->num == end)
                    break;
            }
            if (ArrayFather[ZeroX - 1][ZeroY] != -1 && k->move != 4) {//同上 判断能否上移
                copy();
                ArraySon[ZeroX][ZeroY] = ArraySon[ZeroX - 1][ZeroY];
                ArraySon[ZeroX - 1][ZeroY] = 0;
                l = Creat(ArraySon2int(), 3, k);
                p->next = l;
                p = l;
                if (p->num == end)
                    break;
            }
            if (ArrayFather[ZeroX + 1][ZeroY] != -1 && k->move != 3) {//同上 判断能否下移动
                copy();
                ArraySon[ZeroX][ZeroY] = ArraySon[ZeroX + 1][ZeroY];
                ArraySon[ZeroX + 1][ZeroY] = 0;
                l = Creat(ArraySon2int(), 4, k);
                p->next = l;
                p = l;
                if (p->num == end)
                    break;
            }
        }
        k = k->next;//判断下一个节点去生成它的子节点
    }
    return p;//当找到结果break出来后返回最终得到的节点的地址
}


int main() {
    int temp[3][3];//用于格式化输出的缓存数组
    int output[100];//用于记录每一步结果数值实现堆栈功能的数组
//    int numStart = 283104765;//初态
//    int numEnd = 123804765;//终态
    int numStart;//初态
    int numEnd;//终态
    printf("请输入初态:");
    scanf("%d",&numStart);
    printf("请输入终态:");
    scanf("%d",&numEnd);
    int i = 0;//用于记录经历了多少个步骤的计数器
    node *answer = Eight(numStart, numEnd);//调用Eight函数进行计算出最终态的结果
    output[i]=answer->num;//将得到的最终结果的数值，首先赋值给堆栈数组（即入栈）
    while (answer->up != NULL) {//通过链表的up指针进行搜索到初态
        answer = answer->up;
        i++;//找到一个父节点，计数器加一，即进行了一个步骤
        output[i] = answer->num;//将此节点的数值，赋值给下一个堆栈数组（即继续入栈）
    }
    printf("\n所需要经历的最短步骤是：%d\n\n", i);//首先输出经历了几次步骤到达目标态
    for (int j = i ; j >= 0; --j) {//进行出栈和格式化输出
        //降int型转换为二维3*3的数组给入缓存数组
        temp[0][0] = output[j] / 100000000;
        output[j] = output[j] % 100000000;
        temp[0][1] = output[j] / 10000000;
        output[j] = output[j] % 10000000;
        temp[0][2] = output[j] / 1000000;
        output[j] = output[j] % 1000000;
        temp[1][0] = output[j] / 100000;
        output[j] = output[j] % 100000;
        temp[1][1] = output[j] / 10000;
        output[j] = output[j] % 10000;
        temp[1][2] = output[j] / 1000;
        output[j] = output[j] % 1000;
        temp[2][0] = output[j] / 100;
        output[j] = output[j] % 100;
        temp[2][1] = output[j] / 10;
        output[j] = output[j] % 10;
        temp[2][2] = output[j];
        for (int k = 0; k < 3; ++k) {//格式化输出
            for (int l = 0; l < 3; ++l) {
                printf("%d ",temp[k][l]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

最终的运行结果和手算结果对比

手算的思维图示

4

运行结果

3