接上篇文章最后的汉诺塔问题变种，是否存在一种合理状态使得将所有圆盘移动到右边柱子需要的步数大于$2^n-1$。直觉上我觉得不存在，但是不好说明，所以这篇文章就写一个程序来暴搜验证一下。
基本原理
先来大概说一下我的想法，
首先枚举出n个圆盘的所有合理状态，每个状态就是一个节点。
如果可以通过移动圆盘，从一个状态变成另一个状态，那么就在这两个节点之间连一条边。
对于每一个节点都找到能够与它建立连接的节点并连接，最后应该能够得到一个图。
对于这个图，从终止状态（即所有圆盘都在右边柱子的状态）进行广搜遍历整个图就能得到每个状态需要的移动步数了。
状态的表示
其实从汉诺塔的操作来看，最适合用来描述的结构应该是栈，用三个栈表示三根柱子，将圆盘从一根柱子移动到另一根柱子就是，从一根柱子出栈，然后将数据压入另一个栈这样就变成了另一个状态，非常的合理。
但是在编写程序的时候，我们需要用状态来作为索引，所以它需要尽可能简单并且可以在map或者unordered_map中作为key使用，当然不使用这两个结构我们自己实现索引和映射也行，但是这样会更加麻烦。
我的想法是，使用一个int来保存一根柱子上的圆盘，保存三根柱子的信息就是一个三元组tuple<int,int,int>。因为每根柱子上的圆盘都是有序的，即下面的圆盘一定大于上面的，所以可以用int的每个位来表示柱子上是否有这个圆盘，int是32位的，所以最大可以保存32个圆盘，我们测试应该够用了。
接下来说一下使用int的，移动操作的表示方法。每次移动圆盘移动的都是柱子上最小的圆盘，所以我们需要获取int的最低位，1
2
3int lowbit(int x){
return x&(-x);
}
假设要将A柱上的圆盘移动到C柱上只需要这样1
2
3int la=lowbit(a);
a-=la;
c+=la;
为了看起来更加直观我直接用了加减，没有使用位操作。
枚举状态
一种显然的枚举的方法，因为圆盘下面大上面小，即将n个圆盘从大到小依次放置在柱子上，所以枚举的过程也是仿照这个过程，递归的从大到小枚举每个圆盘分别在ABC柱上的状态。
为了防止污染全局空间，以及看起来美观，我把这些操作封装在了一个struct里面1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct HNT{
map<tuple<int,int,int>,int>
operator()(int n){
depth.clear();
dfs({0,0,0},1<<(n-1));
return depth;
}
private:
map<tuple<int,int,int>,int>depth;
void dfs(tuple<int,int,int> stat,int i){
if(i==0){
depth.emplace(stat,-1);
return;
}
auto [a,b,c]=stat;
dfs({a|i,b,c},i>>1);
dfs({a,b|i,c},i>>1);
dfs({a,b,c|i},i>>1);
}
};
深度初始化为-1，即不可达。现在先不考虑深度，可以写个主函数验证一下1
2
3
4
5
6
7
8
9
10
11
12int main(){
auto H=HNT{}(5);
for(auto e:H){
auto [t,h]=e;
auto [a,b,c]=t;
cout<<a<<" "
<<b<<" "
<<c<<" "
<<endl;
}
return 0;
}
广搜遍历
这里其实就是普通的广搜，值得注意的一点就是我在计算过程中把三元组转为数组，这样方便使用下标计算（用于移动圆盘），在计算完之后再把数组转为三元组。下面就不多解释了，直接贴完整的代码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
using namespace std;
int lowbit(int x){
return x&(-x);
}
array<int,3>t3toa3(tuple<int,int,int>t){
array<int,3>a;
tie(a[0],a[1],a[2])=t;
return a;
}
tuple<int,int,int>a3tot3(array<int,3>a){
return {a[0],a[1],a[2]};
}
struct HNT{
map<tuple<int,int,int>,int>
operator()(int n){
depth.clear();
dfs({0,0,0},1<<(n-1));
queue<tuple<int,int,int>>Q;
Q.push(depth.begin()->first);
depth.begin()->second=0;
while(!Q.empty()){
auto state=Q.front();Q.pop();
int d=depth[state];
array<int,3>h,l;
h=t3toa3(state);
transform(h.begin(),h.end(),l.begin(),lowbit);
for(int i=0;i!=3;++i){
for(int j=0;j!=3;++j){
if(l[i]==0||i==j)continue;
if(l[j]==0||l[i]<l[j]){
auto a=h;
a[i]-=l[i];
a[j]+=l[i];
auto t=a3tot3(a);
if(depth[t]==-1){
depth[t]=d+1;
Q.push(t);
}
}
}
}
}
return depth;
}
private:
map<tuple<int,int,int>,int>depth;
void dfs(tuple<int,int,int> stat,int i){
if(i==0){
depth.emplace(stat,-1);
return;
}
auto [a,b,c]=stat;
dfs({a|i,b,c},i>>1);
dfs({a,b|i,c},i>>1);
dfs({a,b,c|i},i>>1);
}
};
int main(){
auto H=HNT{}(5);
for(auto e:H){
auto [t,count]=e;
auto [a,b,c]=t;
cout<<a<<" "
<<b<<" "
<<c<<" "
<<count<<" "
<<endl;
}
return 0;
}
运行这段代码会输出5个圆盘的所有状态和它们到终止状态的最小步数。从结果来看，每种状态的步数都小于2^n-1次，而且没有不可达（即深度为-1）的节点。
数学证明
现在从答案推过程，已经知道从任意状态将n个圆盘移动到第三根柱子上最多需要$2^n-1$步。因为没有移动限制，所以可以说从任意状态将n个圆盘移动到任意一根柱子上最多需要$2^n-1$步。
考虑复原n+1个圆盘的情况，增加一个圆盘允许的最大步数从$2^n-1$变成了$2^{n+1}-1$，即我们可以多移动$2^n$步。
现在来考虑一下在n个圆盘的状态下多加第n+1个圆盘的情况，这个圆盘肯定是在任意柱子的最底层。
如果第n+1个圆盘在第三根柱子的最底层，那复原n+1个圆盘需要的步数和复原n个一样，即最多$2^n-1$步
如果第n+1个圆盘不在第三根柱子上，那我我们就需要把前面的n个圆盘复原到除了第三根和第n+1个圆盘所在的柱子以外的另一根柱子上，然后将第n+1个圆盘移动到第三根柱子上，最后将n个圆盘整塔移动到第三根柱子上。记将任意状态的n个圆盘移动到一根柱子上需要的步数为$g(n)$，设$g(n)<=2^n-1$，根据上面可以得到，
这样应该算是数学证明了。
小番外
之前说把状态作为节点，移动变换为边，构成一个图，然后我还想看看这个图长什么样，说不定还能看出什么关系，于是用Mathematica重新写了一遍并且画了图。
嗯，好像确实有规律。显然大三角形的三个顶点就是圆盘全部在同一根柱子上的状态。其实如果把它拉直，可以发现一个大三角形是由三个小三角形围成的，也就是说这个图像也是递归的，非常的奇妙。