薅微软Rewards羊毛：更快的滑动拼图方法

Windows自带的Edge浏览器使用bing必应搜索的时候，会给你Rewards，如果你的Rewards积分积攒到一定程度（去年是17000+，现在是19000+）可以兑换肯德基/盒马生鲜等的百元代金券。这个积分主要通过你对必应的使用频率来给予积分，一般攒个半年就可以拿到这个大奖了，当然如果你还玩玩它的滑动拼图🧩小游戏（或者一些人喜欢叫它为数字华容道、八数码）的话，可能会攒的更快。

我自己不喜欢攒淘宝的淘金币，因为它的小游戏实在是太复杂了，但是这个bing的简单小游戏我还挺喜欢的，日常完成有5积分，有时候有活动完成可以获得40+积分。

手动解
#

参考：

你可以在这里在线开玩：在线数字华容道拼图

手动解和编程解的方式完全不一样，人不可能记住许多状态，只能走一个相对更容易理解的路径。

1、拼第一行
#

滑动九宫格可以看做若干个2*2的2宫格，每一步都是在一个独立的2*2宫格中移动。

首先，我们可以很简单的将1移动到它应该在的左上角，在第一个2*2中做转动即可。

接着，保持1不变，将2通过多个宫格移动到右上角。

接下来，我们需要将3移动到蓝色方框中，这里可以分两种情况讨论

（1）3在下面的2*3方格中，也即第二行到第三行这个范围内。

第一种情况很简单，通过第二行和第三行两个2*2方格的顺逆时针交换即可将3移动到蓝色方框中。

（2）3夹在1和2中间，也就是上图中8所占据的位置。

这种情况如下图所示，3和2在一个2*2方格的相邻位置。我们需要将这种麻烦的情况转换为3在下两行的情况。

我们首先需要将3和2换到一个2*2方格的对角位置，也即只在蓝色方框标注的两个2*2方格中变换

首先顺时针交换326方格，改成263布局，给下面的8腾出位置，即转换263为2683

接着，顺时针将2复原到右上角，此时3已经在下两行中，而8在1和2中间。

接着我们顺时针移动，即可拼完第一行：

2、转圈的准备工作
#

将6放在3的下面，8放在中间。

目标状态：

第一步是将6放在3的下面，这个如上在下两行的2*2中转圈圈即可。
8放在中间，其实就相当于将6和8放在一个2*2的顺序相邻位置“86”

我们这里只讨论顺序相邻位置为68的情况（请忽略这里的第一行）

将6和8在一行中用第三个数隔开，然后再做交换。

3、开转
#

逆时针转上两行，得到：

接着，顺时针转3*3的大外圈，得到12368的正确顺序：

4、左下方的`2*2`
#

接着左下方的2*2很好处理，顺逆时针转转就得到答案了。

不存在解的情况
#

将这个「数字华容道」从上到下，从左到右展开为一维序列后，如果其中的逆序对数量为偶数存在解，如果逆序对数量为奇数则不存在解。

什么是逆序对呢？比如${ 6,1,2,3 }$ ，在前面位置的值比在后面位置的值大，比如 $6>{1,2,3}$，这个序列中则存在3个逆序对。

编程解
#

如果使用编程解决，我们就不止需要找到一个解，而需要更进一步找到它的最优解，也就是可以解决八数码问题的最小步数。

BFS
#

说到最小步数，很容易想到使用BFS解决。

我们将起点（点Node对应的xy和数组str）加入Normal Queue，同时将「当前状态：数组str和对应步数」加入map（如果map中之前没有的话，也就是说我们第一次加入的时候就是最短step）。

在Queue不为空的时候，不断poll访问和将周围四向点加入即可，如果poll访问的Node中的str状态就是我们需要的end状态，那么直接返回对应step。

为了方便，将原来的二维矩阵转成字符串（一维矩阵）进行处理。

这样带来的好处直接可以作为哈希 Key 使用，也可以很方便进行「二维坐标」与「一维下标」的转换。

由于固定是 2∗3 的格子，因此任意的合法二维坐标 $(x,y)$ 和对应一维下标 $idx$ 可通过以下转换：

$$idx=x∗3+y$$

$$x=idx/3,y=idx%3$$

其余的就是常规的 BFS 过程了。

class Solution {

    int n = 2, m = 3;
    String e = "123450";
    String s = "";
    int x, y;
    int[] dx = {-1,0,0,1};
    int[] dy = {0,-1,1,0};

    /**
     * BFS解法
     * @param board
     * @return
     */
    public int slidingPuzzle(int[][] board) {
        //
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                s+=board[i][j];
                if(board[i][j] == 0){
                    // 起点
                    x = i; y = j;
                }
            }
        int ans = bfs();
        return ans;
    }

    class Node{ // 记录当前空格的位置
        int x;
        int y;
        String s;
        public Node(int _x, int _y, String _s){
            x = _x;
            y = _y;
            s = _s;
        }
    }

    public int bfs(){
        //
        Queue<Node> q = new ArrayDeque<>(); // bfs必须的queue
        q.add(new Node(x, y, s));
        HashMap<String, Integer> map = new HashMap<>(); // 记录某状态String的最小步数
        map.put(s, 0);

        // q不空时
        while(!q.isEmpty()){
            Node poll = q.poll();
            int old_x = poll.x, old_y = poll.y;
            int step = map.get(poll.s);
            // 如果poll的s为e，则直接返回step
            if(e.equals(poll.s)) return step;
            // 遍历四向
            for(int i=0;i<4;i++){
                // 四向合法性判断
                int new_x = old_x+dx[i], new_y = old_y + dy[i];
                if(new_x<0 || new_y<0 || new_x>=n || new_y>=m) continue;
                // 尝试更新
                String update = update(poll.s, old_x, old_y, new_x, new_y);
                if(!map.containsKey(update)){
                    // 如果map包含，则说明之前已经有过，不做处理
                    map.put(update, step + 1);
                    q.add(new Node(new_x, new_y, update));
                }
            }
        }
        return -1;
    }

    public String update(String str, int old_x, int old_y, int new_x, int new_y){
        // 更换old_x,old_y 和new_x,new_y 对应str位置的值
        char[] chars = str.toCharArray();
        int old_pos = old_x*m + old_y;
        int new_pos = new_x*m + new_y;
        char tmp = chars[old_pos];
        chars[old_pos] = chars[new_pos];
        chars[new_pos] = tmp;
        return String.valueOf(chars);
    }
}

A*搜索
#

1、什么是A*搜索

A*（A-star）是一种启发式搜索算法，用于在图中找到从起点到目标的最短路径。它结合了：

g(n)：从起点到当前节点 n 的实际代价（已经走过的步数）
h(n)：从当前节点 n 到目标节点的估计代价（启发式函数）

公式：

$$f(n)=g(n)+h(n)$$

f(n)：A* 在优先队列中排序的依据
g(n)：已经走的步数
h(n)：预计剩余步数（越准确越快）

我们使用数组转换的字符串表示此时八数组的状态，比如终止状态就是end=”123450”。

我们使用曼哈顿距离定义启发式函数h(n)，也就是当前节点与目标节点的二维坐标差的绝对值之和：

$$h(pos_{new}, pos_{old}) = abs(new[0]-old[0]) + abs(new[1]-old[1])$$

这表示着从当前坐标移动到目标坐标的最小估计代价。

而从一个华容道状态移动到另外一个华容道状态，需要同时计算所有非0/非占位符坐标的转换代价。

2、A*搜索的流程

使用基于启发式搜索代价f(n)的优先队列pq存储Node。

每次在队列非空的时候，访问q中最小f(n)的Node

如果node.s=end, 直接返回map中记录的step
否则，尝试添加node的四向节点
- 如果四向节点不在map中，添加到pq中
- 如果四向节点在map中，但是map中的四向节点对应状态的step>step+1, 则需要将代表新Node状态的加入q和map

3、代码

public class T0773_AStar {

    int n = 2, m = 3;
    String end = "123450";
    String start = "";
    int start_x, start_y;
    int[] dx = {-1,0,0,1};
    int[] dy = {0,-1,1,0};

    /**
     * BFS解法
     * @param board
     * @return
     */
    public int slidingPuzzle(int[][] board) {
        //
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                start +=board[i][j];
                if(board[i][j] == 0){
                    // 起点
                    start_x = i; start_y = j;
                }
            }
        if(!nixu(start)) return -1;
        int ans = astar();
        return ans;
    }

    class Node{
        int x;
        int y;
        int f_val; // f = g + h;
        String str; // 当前节点对应状态的str
        public Node(int _x, int _y, int _f_val, String _str){
            x = _x;
            y = _y;
            f_val = _f_val;
            str = _str;
        }
    }

    public int h(String str){
        // 从str转移为end的最小开销
        char[] from = str.toCharArray();
        char[] to = end.toCharArray();
        int res = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                //
                if(from[i*m+j] == '0' || to[i*m+j] == '0') continue;
                // 其实to[i*m+j]才是真正的起点，而from[i*m+j]是我们的目标点
                int st = to[i*m+j], ed = from[i*m+j];
                res += Math.abs( (st-1)/3 - (ed-1)/3 ) +
                        Math.abs( (st-1)%3 - (ed-1)%3 );
            }
        }
        return res;
    }

    public boolean nixu(String str){
        // 逆序对数量为偶数时有解
        char[] chars = str.toCharArray();
        // 过滤'0'占位符
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<chars.length;i++){
            if(chars[i] != '0') list.add(chars[i]-'0');
        }

        //
        int res = 0;
        for(int i=0;i<list.size();i++){
            for(int j=i+1; j<list.size();j++){
                //
                if(list.get(i)>list.get(j)) res++;
            }
        }
        return res%2==0;
    }

    public int astar(){
        // 按f值升序
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b)->a.f_val-b.f_val);
        pq.add(new Node(start_x, start_y, 0+h(start),start));
        HashMap<String, Integer> mp = new HashMap<>();
        mp.put(start, 0);

        //
        while(!pq.isEmpty()){
            //
            Node poll = pq.poll();
            int step = mp.get(poll.str);
            if(poll.str.equals(end)) return step;
            // 添加poll的四向节点
            int x = poll.x, y = poll.y;
            for(int k=0;k<4;k++){
                int new_x = x+dx[k], new_y = y+dy[k];
                if(new_x < 0 || new_y<0 || new_x>=n || new_y>=m) continue;
                //
                String update = update(poll.str, x, y, new_x, new_y);
                // mp.get(update)>step+1，在存在更优的step的时候，更新pq和mp
                if(!mp.containsKey(update) || mp.get(update)>step+1){
                    pq.add(new Node(new_x, new_y, step+1+h(update), update));
                    mp.put(update, step+1);
                }
            }
        }
        return -1;
    }

    public String update(String str, int old_x, int old_y, int new_x, int new_y){
        // 更换old_x,old_y 和new_x,new_y 对应str位置的值
        char[] chars = str.toCharArray();
        int old_pos = old_x*m + old_y;
        int new_pos = new_x*m + new_y;
        char tmp = chars[old_pos];
        chars[old_pos] = chars[new_pos];
        chars[new_pos] = tmp;
        return String.valueOf(chars);
    }

}

手动解 #

1、拼第一行 #

2、转圈的准备工作 #

3、开转 #

4、左下方的2*2 #

不存在解的情况 #

编程解 #

BFS #

A*搜索 #