从数学角度分析bdpq

偶然在tap上翻到这个几年前的游戏，感觉还比较有趣，反正高三的暑假没事干，所以来分析一波，证明(瞎解释)放在最后。

1、bdpq可看作2个bd问题

这个，不需要解释了吧。

2、偶数N阶、可解的奇数N+1阶bd分别有2^(N*N)、2*(N*N+1)种状态，均连通。解释见后。

3、偶数阶解法唯2（全b全d各1种，同位置多2下为同一解法）。而且解法和问题共轭(这很优美的感觉）。

4、若奇数N阶中的N-1阶已解决，则只剩0或1次操作。（所以5阶还是只用看16格，可能最后再点1下） 由2可得

构造证明偶数阶：

如下面的操作可仅使黑体处改变。

下面的状态可经黑体处操作解决。

0 0 1 0

0 0 1 0

1 1 1 1

0 0 1 0

而总状态数与不重复操作序列均有2^(N*N)

所以每个位置的1唯一对应了一个操作序列，这些操作序列的异或和即为全b解，把1看成0即为全d解。

注意到操作序列（逐个翻第二行）

0 0 0

1 1 1

0 0 0

等效于全局bd互换

而且N行N纵均是如此，于是我们有了2N-1种独立操作(注意每格翻2次=0次)，他们至多让状态数*2

剩下的N*N-2N+1种独立操作至多链接2^((N-1)*(N-1))种状态。

而只在左上N-1阶操作就能达到2^((N-1)*(N-1))种状态了，有解时，右下角翻与不翻恰为''*2''

与前面的''至多''对上了，

时间空间复杂度均为O(N*N)的代码还是比较好写的，需要C++代码的可以私我。