8数码和15数码算法结论和延展

发表于 更新于 分类于 阅读次数：
8数码和15数码算法结论和延展 **那么就要在初始状态的逆序数上面 加上 0值在初始状态移动到最后一行产生的逆序数奇偶性的变化值**仍为偶数则有解

此类问题是否有解

定义一个东西

先定义此类问题矩阵的逆序数的和值为除去0以外其他数的排列(把二维一行行地读取的循序的排列)的逆序数和

发现一

我们可以发现排列中相邻的两个数交换位置会它们两相互之间的逆序数值,而其他部分以及他们各自和其他部分的逆序数值都不变,所以矩阵的逆序数+1或-1,也就是矩阵的逆序数的奇偶性发生了改变

发现二

我们还可以发现0左右移动不影响矩阵的逆序数的奇偶性，然而如果是上(下)移动的话，就想到于一个数连续和左(右)边3个数进行了交换位置，所以矩阵的逆序数的奇偶性会变

发现三

矩阵的改变只能通过与0变换位置，所以只有在与0上下交换的时候才会产生矩阵的逆序数的奇偶性的变化

结论

所以我们知道最终状态逆序数为0,且最后0在最后一行(高中学化学经常讲终态法)，也就是矩阵要有解，最终逆序数的奇偶性为偶，那么就要在初始状态的逆序数上面 加上 0值在初始状态移动到最后一行产生的逆序数奇偶性的变化值仍为偶数则有解

题目

有解性

题

HDU-6620 2019杭电多校4

手写AC代码

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
#include<bits/stdc++.h>
using namespace std;
int T,a[16];

int main(){
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        int cnt = 0;
        for(int i=0;i<16;i++) cin>>a[i];
        for(int i=0;i<16;i++){
            if(!a[i]){
                cnt+=3-i/4;
            }
            else{
                for(int j=0;j<i;j++){
                    if(a[j] && a[j]>a[i])
                        cnt++;
                }
            }
        }
        if(cnt&1) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
    return 0;
}

求最少步数

如果我们要求解步数的话,我们首先是用逆序数进行判定是否有解，有解才进行搜索

使用曼哈顿距离递减 和 IDA*(迭代层数达到120层就放弃) 的方式
曼哈顿是初始排列到目标排列每个数字abs(x1-x2)+abs(y1+y2)的和值

给个板子

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
/*
先用结论判断是否有解呀！不然没解跑这个会死循环，燃烧你的CPU的话我不背锅哦
 */

#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
//limit全部的曼哈顿距离之和
int map[4][4], map2[16], limit;
int flag, length;
//各个数字应在位置(i,j)对照表,比如0在位置(3,3)
int goal[16][2] = {{3,3},{0,0},{0,1},{0,2},
                   {0,3},{1,0},{1,1},{1,2},
                   {1,3},{2,0},{2,1},{2,2},
                   {2,3},{3,0},{3,1},{3,2}};

int nx[4][2] = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };


//估价函数,曼哈顿距离,小于等于实际总步数
int hv(int a[][4]){
    int cost = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int w = map[i][j];
            // 不算0
            if (w != 0)
                cost += abs(i - goal[w][0]) + abs(j - goal[w][1]);
        }
    }
    return cost;
}

/* x,y起始坐标，len是已经走过的长度,pre_move是上次走的方向 */
void dfs(int x, int y, int len, int pre_move){
    if (flag) return;
    int dv = hv(map);
    if (len == limit) {
        //成功 退出
        if (dv == 0){
            flag = 1;
            length = len;
            return;
        } else
            //超过预设长度 回退
            return;
    }

    for (int i = 0; i < 4; i++) {
        //不和上一次移动方向相反,对第二步以后而言
        if (i + pre_move == 3 && len > 0) continue;
        int tx = x + nx[i][0];
        int ty = y + nx[i][1];
        if (tx >= 0 && tx < 4 && ty >= 0 && ty < 4) {
            swap(map[x][y], map[tx][ty]);
            int p = hv(map);
            if (p + len <= limit && flag == 0) {
                dfs(tx, ty, len + 1, i);
                if (flag)
                    return;
            }
            /* 递归回来后恢复现场 */
            swap(map[x][y], map[tx][ty]);
        }
    }
}

int main(){
    int t; cin>>t;
    while (t--) {
        int x1, y1;
        //map2一维 map二维
        for (int i = 0; i < 16; i++){
            scanf("%d", &map2[i]);
            if (map2[i] == 0) {
                x1 = i/4; y1 = i%4;
                map[x1][y1] = 0;
            } else {
                map[i/4][i%4] = map2[i];
            }
        }

        /* 曼哈顿长度要递减的 */
        limit = hv(map);
        flag = 0;
        length = 0;
        //要求120步之内到达,其实如果可以的话最多80多步就可以走完
        while (flag == 0 && length <= 90){
            //得到的是最小步数
            dfs(x1, y1, 0, 0);
            /* 加大初始额曼哈顿距离的限制，让递归的行走能不曼哈顿距离递减得多试探几步 */
            if (flag == 0) limit++;
        }
        // if (flag)
        //     printf("%d\n", length);
        if(flag) cout<<"Yse"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

后续

不好意思，写完后才发现重复造轮子了，不过应该我写得应该算比较简单，可以立马用上吧