更快的解题程序 & 每关最优解

在论坛里有几个程序跑出了10000度的最优解，但似乎还没人跑出更难的题的一些解。所以我写了一个c++程序，把所有非随机题的解都求了出来。

写这个程序的原因是，之前一个Math Fans群里的大佬跟我讨论了这个游戏，并提出了一个算法的优化思路，利用了一个很巧妙的结论。说实在我之前也没有注意到这个结论，但事实上这个结论是对的，而且可以让搜索速度变快很多。

这个结论表述如下：

十步万度的最终局面、总度数只和每个圈的点击次数有关，而跟点击它们的顺序无关。也就是说，如果我先点圈a再点圈b，跟先点圈b再点圈a的结果是一模一样的。

是不是有点违反直觉？但经过一些尝试就能发现，确实是这样的。这个结论有一个严谨而巧妙的证明。有兴趣的同学可以思考一下。

根据上面这个定理，整个搜索空间就降了很多，即使对于最难的问题（15步20000度那题），总的搜索量也只有C(30+15-1, 15)，约为2299亿。c++实现的代码能做到在i7上单线程5秒内搜1亿步，所以求解时间不长。

最后求出的最优解如下：

10步1000度：最优解2070

10步3000度：最优解4410

10步3500度：最优解4320

10步4000度：最优解5040

10步4500度：最优解6480

10步5000度：最优解6570

10步6000度：最优解6930

10步6100度：最优解6390

10步6200度：最优解6390

10步6300度：最优解7740

10步6400度：最优解5670（无法过关）

10步7000度：最优解8100

10步8000度：最优解5940（无法过关）

10步8300度：最优解10530

10步8500度：最优解7830（无法过关）

10步9000度：最优解7380（无法过关）

10步10000度：最优解10800

15步11000度：最优解8820（无法过关）

15步13000度：最优解12060（无法过关）

15步14000度：最优解9000（无法过关）

15步15000度：最优解14130（无法过关）

15步16000度：最优解13410（无法过关）

15步18000度：最优解17100（无法过关）

15步20000度：最优解17280（无法过关）

可以看到有很多关卡中最优解比要求还要低，因此这些关卡是无解的。

有了上述的算法思路，有兴趣的同学应该不难把它实现出来并且搜索出每关的最优方案。当然如果有必要的话，我可以把我的程序和最优方案在这里公开给大家参考。