关于十字翻转棋的解法研究

    首先说什么是十字翻转棋,十字翻转棋又叫开窗游戏,游戏规则如下:

    在n*n的方格中随机分布着一些关着的窗子,当你打开或关闭一个窗子时,它的上下左右四个方向的窗子开关状态也会翻转。目标是将这些关着的窗子都打开,游戏结束。 

    这里有一个我自己编写的html5开窗游戏,大家可以先去玩一下:

    开窗游戏

    游戏相对还比较简单,只是一个3*3的难度,当游戏维度增加后,难度也会加大。下面我们来探讨一下如何快速找出一个最优解。

    玩几次游戏发现如下两个规律:

    1.任何一个位置我们点击1次和点击3次结果是相同的,因为每点一下,这个点击所影响的窗子是固定的,所以如果一个位置需要点击,我们只点击一下就可以了。

    2.任何一个位置的窗子状态只和它上中下左右5个位置的点击状态有关系,和他们的点击顺序无关。

    由1,2分析可知,在n*n的格子中,达到win状态时这n*n个格子每个格子只有是否被点击两种状态,而与达到这两种状态的点击次数无关,和点击顺序也无关。这个大家可以自己思考一下。

    也就是说最后我们只需确定哪些格子需要点,哪些格子不需要点。

    我们就拿3*3的难度来推理一下。

    c1

    c2

    c3

    c4

    c5

    c6

    c7

    c8

    c9

    假设格子的原始状态为 {cn}, cn有两个值 0代表开着的,1代表关着的 那么要把所有窗子都开着就是要把所有数字都变成0

    x1

    x2

    x3

    x4

    x5

    x6

    x7

    x8

    x9

    假设最终格子的点击状态为 {xn},xn也有两种状态 1代表要点击,0代表不点击

    我们假设 运算f(x,c)   {x=0,1}{c=0,1}  

    x表示是否受点击影响 0代表不受点击影响,1代表受点击影响

    c表示格子原始状态 0表示开启状态,1表示关闭状态

    f(x,c)    表示作用后对应格子的状态  

    经过分析, f有如下特点:

        f(1,0)=1;    //受点击影响 将原先1变为0

        f(1,1)=0;    //受点击影响 将原先0变成1

        f(0,1)=1;    //不受点击影响,保持原来的1

        f(0,0)=0;    //不受点击影响,保持原来的0

    聪明的你应该发现,这其实是异或运算^

    再来分析第一个格子,

    它的原始状态是c1,分析发现能够影响它的点击状态是x1,x2,x4 而其他x对它皆没有影响,而目标最终的状态是0,所以我们得到下面的式子:

    f(x4 , f(x2 , f(x1 , c1))) = 0 

    而我们又知道 f 是异或运算,所以上面的式子可以写成

    x4^x2^x1^c1=0

    又因为异或服从交换律,且两边同时异或c1 得到下面的变形

    x1^x2^x4=c1;

    依次类推我们可以写出其他的式子,最后整理好的式子如下:

    x1^x2^   x4                = c1
    
    x1^x2^x3^   x5             = c2
    
       x2^x3^      x6          = c3
       
    x1^      x4^x5^   x7       = c4
    
       x2^   x4^x5^x6^   x8    = c5
       
          x3^   x5^x6^      x9 = c6
          
             x4^      x7^x8    = c7
             
                x5^   x7^x8^x9 = c8
                
                   x6^   x8^x9 = c9

    将其写成矩阵形式:

     1 1 0 1 0 0 0 0 0    x1     c1      (1)
     1 1 1 0 1 0 0 0 0    x2     c2      (2)
     0 1 1 0 0 1 0 0 0    x3     c3      (3)
     1 0 0 1 1 0 1 0 0    x4     c4      (4)
     0 1 0 1 1 1 0 1 0    x5     c5      (5)
     0 0 1 0 1 1 0 0 1    x6     c6      (6)
     0 0 0 1 0 0 1 1 0    x7     c7      (7)
     0 0 0 0 1 0 1 1 1    x8     c8      (8)
     0 0 0 0 0 1 0 1 1    x9     c9      (9)

    最终问题划归为求解这个异或矩阵方程~

    我们把左边那个矩阵定义为A  使用向量的写法  

    AX=C 

    只不过这里矩阵乘法中对应的加法运算要改为异或运算。

    线性代数里面有一类问题叫线性方程组的求解,最终划归出来的矩阵形式和这个一模一样。所以我们可以采用解线性方程组的那套算法来解这个方程。


    最基本的原则是销元,算法描述如下:

    1.用 (1)^(2)  可以得到一个没有x1的等式替代(2),同样用(1)^(3)替代(3) 依次类推,可以得到8个没有x1的等式。

    2.再用(2)^(3) 可以得到一个没有x2的等式替代(3);

    3.照这样做下去,可以得到一组上三角矩阵。

    4.此时的(9)式就只有x9一个变量,而对应的c9则也就是x9的值。

    5.然后将x9代入(8)式可以解出x8

    6.继续将 x8,x9代入(7)式可以解出x7


    依次类推,可以解出xn  也就是我们要的解。

    还记得这种方法应该叫做 高斯消元法。


    另一种解法和这个解法类似,只是不用回代:

    1.用 (1)^(2)  可以得到一个没有x1的等式替代(2),同样用(1)^(3)替代(3) 依次类推,可以得到8个没有x1的等式。(第一步相同)

    2.用(2)^(1) 可以得到一个没有x2的等式替代(1),(2)^(3)-->(3);(2)^(4)-->(4);...(2)^(9)-->(9);   (第二步有所不同,是同样用(2)式将(1)式中的x2消除)

    3.同样的(3)^(1)-->(1);    (3)^(2)-->(2);   ...   (3)^(9)-->(9);

    照这样做下去,可以得到一组对角矩阵,或者可以说是单位矩阵

    而此时cn对应的就是方程组的解。


    扩展到n*n的规模,我们发现只是对应的矩阵A变化了,其他算法不变。

    针对问题本身,cn是一个参数,是传入值,矩阵A根据不同规模不同,但也是有规律的,可以用程序生成,具体的生成算法这里就不说了。


    以下是我用JavaScript写的一个算法,针对3*3的规模解法:

    var AI = AI||{};
    AI.resolve = function(cArray){
        var rect33 = [
            [1,1,0,1,0,0,0,0,0],
            [1,1,1,0,1,0,0,0,0],
            [0,1,1,0,0,1,0,0,0],
            [1,0,0,1,1,0,1,0,0],
            [0,1,0,1,1,1,0,1,0],
            [0,0,1,0,1,1,0,0,1],
            [0,0,0,1,0,0,1,1,0],
            [0,0,0,0,1,0,1,1,1],
            [0,0,0,0,0,1,0,1,1],
        ];
        function resolveRect(rect,cArray){
            var length = rect.length;
            for(var i=0;i<length;i++){
                for(var j=i+1;j<length;j++){
                    var r1 = rect[i];
                    var r2 = rect[j];
                    if(r2[i]==1){
                        if(r1[i]==1){//销元
                            addRect(r1,r2);
                            var c1 = cArray[i];
                            var c2 = cArray[j];
                            cArray[j] = addRect(c1,c2);
                        }else{//交换
                            var temp = rect[i];
                            rect[i]=rect[j];
                            rect[j]=temp;
                            temp = cArray[i];
                            cArray[i]=cArray[j];
                            cArray[j]=temp;
                        }
                    }
                }
                if(rect[i][i]!=1){
                    throw "无解!!";
                    return;
                }else{
                    for(var j=0;j<i;j++){
                        var r1 = rect[i];
                        var r2 = rect[j];
                        if(r2[i]==1){
                            addRect(r1,r2);
                            var c1 = cArray[i];
                            var c2 = cArray[j];
                            cArray[j] = addRect(c1,c2);
                        }
                    }
                }
            }
        }
        function addRect(r1,r2){
            if(typeof r2 == "number")return r2^r1;
            var len = r2.length;
            for(var i=0;i<len;i++){
                r2[i]=r2[i]^r1[i];
            }
        }
        resolveRect(rect33,cArray);
        console.log(rect33);
        console.log(cArray);
    }

    可以推算这个解法的时间复杂度是n^2  空间复杂度也是n^2 当然空间上是可以优化的,因为有大部分的0是不需要存储的,优化的问题就不讲了。

    顺带说一下,关于这个h5游戏是怎么做出来的,之后会有专门的文章或者视频来讲,敬请期待

    另外游戏的源码和解法的源码都可以访问github地址:git@github.com:gagaprince/gaga_c.git

    里面有一个叫 game_kaichuang 的分支。


    转载请注明出处:http://gagalulu.wang/blog/detail/10 您的支持是我最大的动力!