Project Euler 766

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

Project Euler 766

题目

Sliding Block Puzzle

A sliding block puzzle is a puzzle where pieces are confined to a grid and by sliding the pieces a final configuration is reached. In this problem the pieces can only be slid in multiples of one unit in the directions up, down, left, right.

A reachable configuration is any arrangement of the pieces that can be achieved by sliding the pieces from the initial configuration.

Two configurations are identical if the same shape pieces occupy the same position in the grid. So in the case below the red squares are indistinguishable. For this example the number of reachable configurations is \(208\).

Find the number of reachable configurations for the puzzle below. Note that the red L-shaped pieces are considered different from the green L-shaped pieces.

解决方案

令\(C=6,R=5\)。虽然题目允许一次滑动多格，但搜索时完全没必要直接枚举滑动 \(k\) 格。也就是说，只枚举每次滑动 \(1\) 格的操作，得到的可达状态集合与题目原定义完全相同。

原因在于，若某个拼块能沿某方向一次滑动 \(k\) 格（\(k\ge 2\)），这一步可以拆成 \(k\) 次合法的单位同方向滑动。反过来，若一连串单位滑动合法，那么显然也是题目允许的操作序列的一部分。

所以，题目可以等价改写为：从初始状态出发，反复执行某个拼块向上/下/左/右移动 \(1\) 格的合法操作，统计能到达的状态数。

这个等价化非常重要，因为它把转移形式固定成了常数种。

然而，棋盘有 \(30\) 个格子，拼块种类多、形状不一、且有同类不可区分约束。若直接用二维数组改动和字符串哈希的方式虽然也能做，但常数很大，状态数又在百万级，容易卡在状态表示与碰撞检测上。

因此需要更强的状态表示，核心目标是：快速判断某块能否移动（最好是位运算）；快速生成新状态；天然支持同类拼块不可区分（规范化）

那么我们考虑使用位运算解决。将 \(C\times R\) 棋盘按行优先编号为 \(0,\dots,RC-1\)，即第 \(r\) 行第 \(c\) 列对应格子编号 \(id=Cr+c.\)

这样一个拼块占据的所有格子，就可以表示成一个 \(30\) 位二进制掩码：第 \(id\) 位为 1 表示该拼块覆盖该格。例如：单格块占一个 \(1\) 位；骨牌占两个 \(1\) 位；\(L\) 块占三个 \(1\) 位；\(2\times 2\) 方块占四个 \(1\) 位。

因为编号是按行优先，向四个方向移动 \(1\) 格恰好对应固定的位移。向左：右移 1 位；向右：左移 1 位；向上：右移 \(C\) 位；向下：左移 \(C\) 位。

这意味着移动后拼块形状不需要重新构造，直接做一次位移即可。这一步把几何问题转化成了纯位运算问题。

然而，题目还需要同类拼块不可区分，因此必须规范化状态。也就是说，如果我们给每个拼块固定编号，那么当两个红 \(L\) 交换位置时，程序会把它们当作两个不同状态，导致重复计数。但题目明确说它们是相同配置。

因此，考虑按类型分组存储。把所有拼块按颜色和形状分组，每组保存若干个位掩码，并在每次转移后对该组排序，作为该组的规范表示。

本题可分为以下类型。红色 \(L\)：\(2\) 个，绿色 \(L\)：\(2\) 个，竖向长度为 \(2\) 的骨牌：\(2\) 个；横向长度为 \(2\) 的骨牌：\(1\) 个；\(2\times 2\) 方块：\(1\) 个；单格块：\(6\) 个；再加上两个空格（后面单独保存）。

可见组内排序就够了，因为同类型拼块之间唯一的区别只是命名顺序，而排序后这种标号差异就被消掉了。于是同类交换位置后的状态会映射到同一个规范表示；异类拼块仍然在不同组，不会误合并。

棋盘上恰好有两个空格。与其每次把所有拼块 OR 起来再取反，不如直接维护一个 OPEN 掩码（两个 \(1\) 位）。

这样判断某块能否移动会非常自然。设当前要移动的拼块掩码为 \(P\)，空白掩码为 \(E\)。对于这个拼块来说，允许被占据的位置是它自己当前的位置和空格位置，即：\(\text{occ}=P\cup E.\)如果朝某方向移动后得到 \(P'\)，那么合法当且仅当：不出界；\(P'\) 的所有格子都在 \(\text{occ}\) 中（即目标位置不是别的拼块）。也就是：\(P' \subseteq (P\cup E)\)这一步完全不需要遍历格子，只要用位运算做包含判定即可。

接下来说明合法移动判定的推导，以向右移动 \(1\) 格为例。如果某拼块在最右列上已经有格子，那么它不能右移。设最右列掩码为 \(\text{RM}\)，则条件为\(P \cap \text{RM} = \varnothing.\)右移后得到 P' = P << 1。要求目标位置只能落在 \(\text{occ}=P\cup E\) 上：\(P' \subseteq \text{occ}.\)等价于：\(P' \cap \overline{\text{occ}} = \varnothing.\)同理可得左、上、下三个方向。

当某个拼块从 \(P\) 移到 \(P'\) 后，除了这个拼块和空白外，其他拼块都不变。空白集合更新很简单：原来 \(P\) 占据的位置会腾空，新位置 \(P'\) 会被占用。

因此新空白为\(E' = E \oplus P \oplus P'.\)这里用异或是因为：\(P\) 中那些位原来不在 E，现在要加入；\(P'\) 中那些位原来在 E，现在要删去；其余位不变。然后对所属类型组做一次排序，得到新状态的规范表示，放入哈希集合去重即可。

综上，本题只需按照上述思路建立状态表示与转移规则，并在状态图上进行 BFS，即可统计所有可达配置数。

代码

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
#include <bits/stdc++.h>
using namespace std;

using U = uint32_t;

static const int W = 6, H = 5;
static const U LFT = (1u << 0) | (1u << 6) | (1u << 12) | (1u << 18) | (1u << 24);
static const U RGT = (1u << 5) | (1u << 11) | (1u << 17) | (1u << 23) | (1u << 29);
static const U TOP = ((1u << 6) - 1);
static const U BOT = (((1u << 6) - 1) << 24);

inline U B(int p) { return 1u << p; }
inline U M1(int a) { return B(a); }
inline U M2(int a, int b) { return B(a) | B(b); }
inline U M3(int a, int b, int c) { return B(a) | B(b) | B(c); }
inline U M4(int a, int b, int c, int d) { return B(a) | B(b) | B(c) | B(d); }

inline U mvL(U x) { return x >> 1; }
inline U mvR(U x) { return x << 1; }
inline U mvU(U x) { return x >> W; }
inline U mvD(U x) { return x << W; }

inline bool canL(U p, U occ) { return !(p & LFT) && ((mvL(p) & ~occ) == 0); }
inline bool canR(U p, U occ) { return !(p & RGT) && ((mvR(p) & ~occ) == 0); }
inline bool canU(U p, U occ) { return !(p & TOP) && ((mvU(p) & ~occ) == 0); }
inline bool canD(U p, U occ) { return !(p & BOT) && ((mvD(p) & ~occ) == 0); }

struct State
{
    array<U, 2> g;
    array<U, 2> r;
    array<U, 2> y;
    array<U, 6> p;
    array<U, 1> b;
    array<U, 1> c;
    U open;

    bool operator==(const State &o) const
    {
        return g == o.g && r == o.r && y == o.y && p == o.p && b == o.b && c == o.c && open == o.open;
    }
};

struct HashState
{
    size_t operator()(const State &s) const noexcept
    {
        uint64_t h = 1469598103934665603ull;
        auto mix = [&](U x)
        {
            h ^= (uint64_t)x + 0x9e3779b97f4a7c15ull + (h << 6) + (h >> 2);
        };
        for (auto x : s.g)
            mix(x);
        for (auto x : s.r)
            mix(x);
        for (auto x : s.y)
            mix(x);
        for (auto x : s.p)
            mix(x);
        for (auto x : s.b)
            mix(x);
        for (auto x : s.c)
            mix(x);
        mix(s.open);
        return (size_t)h;
    }
};

template <size_t N>
inline void relax_group(const State &cur, array<U, N> State::*mem, vector<State> &out)
{
    const auto &a = cur.*mem;
    for (size_t i = 0; i < N; ++i)
    {
        U pos = a[i];
        U occ = pos | cur.open;

        if (canL(pos, occ))
        {
            State nx = cur;
            U dst = mvL(pos);
            (nx.*mem)[i] = dst;
            nx.open = cur.open ^ pos ^ dst;
            sort((nx.*mem).begin(), (nx.*mem).end());
            out.push_back(nx);
        }
        if (canR(pos, occ))
        {
            State nx = cur;
            U dst = mvR(pos);
            (nx.*mem)[i] = dst;
            nx.open = cur.open ^ pos ^ dst;
            sort((nx.*mem).begin(), (nx.*mem).end());
            out.push_back(nx);
        }
        if (canU(pos, occ))
        {
            State nx = cur;
            U dst = mvU(pos);
            (nx.*mem)[i] = dst;
            nx.open = cur.open ^ pos ^ dst;
            sort((nx.*mem).begin(), (nx.*mem).end());
            out.push_back(nx);
        }
        if (canD(pos, occ))
        {
            State nx = cur;
            U dst = mvD(pos);
            (nx.*mem)[i] = dst;
            nx.open = cur.open ^ pos ^ dst;
            sort((nx.*mem).begin(), (nx.*mem).end());
            out.push_back(nx);
        }
    }
}

inline State start_state()
{
    State s;
    s.g = {M3(3, 8, 9), M3(23, 28, 29)};
    s.r = {M3(1, 2, 7), M3(4, 5, 10)};
    s.y = {M2(11, 17), M2(16, 22)};
    s.p = {M1(12), M1(13), M1(18), M1(19), M1(24), M1(25)};
    s.b = {M4(14, 15, 20, 21)};
    s.c = {M2(26, 27)};
    s.open = M2(0, 6);
    sort(s.g.begin(), s.g.end());
    sort(s.r.begin(), s.r.end());
    sort(s.y.begin(), s.y.end());
    sort(s.p.begin(), s.p.end());
    return s;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    State st = start_state();
    unordered_set<State, HashState> vis;
    vector<State> stk;
    vis.insert(st);
    stk.push_back(st);
    vector<State> nxt;
    while (!stk.empty())
    {
        State cur = stk.back();
        stk.pop_back();

        nxt.clear();
        relax_group(cur, &State::g, nxt);
        relax_group(cur, &State::r, nxt);
        relax_group(cur, &State::y, nxt);
        relax_group(cur, &State::p, nxt);
        relax_group(cur, &State::b, nxt);
        relax_group(cur, &State::c, nxt);

        for (auto &s : nxt)
        {
            if (vis.insert(s).second)
                stk.push_back(s);
        }
    }

    cout << vis.size() << '\n';
    return 0;
}