Flip游戏的解存在性和数量的讨论

规则描述:

Flip游戏是一个单人益智小游戏,游戏界面是n*n的方格,每格要么白色,要么黑色。当你按下一格时,这一格以及它上、下、左、右一共五格的颜色都会翻转(白变黑、黑变白)。初始颜色是杂乱分布的,玩家的目标是把所有格子都变成白色的。

以下是一个5*5阶 Flip的求解过程:

图:一个求解过程,红点为点击位置

定义“解”和“解数”:

我们不纠结于如何编写Flip游戏,而是讨论Flip游戏的解的存在性和数量问题。

首先定义什么是“解”。我们知道,对n*n的Flip游戏,可以用坐标(i,j)标识一个格子,那么,初状态可以用n*n的布尔矩阵表示,1表示这一格为黑,0表示这一格为白。称为“状态矩阵”

如果用坐标(i,j)表示点击了该格子,经过一番点击后出现了“全白”,那么这一序列的坐标就能称为一个“解”。

但是,考虑到两个规律:

  • 不重复性:点一个格子两遍相当于没有点,所有的格子,要么点一遍,要么不点,点1遍以上都是多余。
  • 无序性:点格子的顺序不影响结果,先点A后点B、和先点B后点A的结果完全一样。

考虑到不重复性和无序性,可以把解的形式变为一个n阶布尔矩阵。矩阵的(i,j)元素为1,说明需要在这里点一下;矩阵(i,j)元素为0,说明不需要在这里点。

“解”的定义

对于n阶的Flip,在给定某个初状态时,若有解,解的形式为一个或多个n阶布尔矩阵。

“解数”的定义:

对于n阶的Flip,在给定某个初状态时,它的解有多少种不同的n阶布尔矩阵。

 

数学抽象化:

现在把所有二维矩阵拉成一维,初始的状态矩阵,解矩阵都是n*n的,我们用行主序法把它变为m=n*n维的向量,设“初始状态向量”为b,“解向量”为x,他们都是m维布尔向量。

为了叙述方便,把Flip规则倒置:如何找到一个解,能把“全白”变成“初始的样子”。显然,这种改动完全不改变解(布尔矩阵)的形式。

在新规则下,初状态是“全白”,经过一番点击x后,状态变成了b,也就是说在x点击下产生了b状态。那么,x到b之间就是一种变换,这是变换一个m阶矩阵与m阶向量的乘法,结果是一个m阶向量x。

A x = b

A只和阶数m有关,A的内涵就是点击一个格子后,哪些格子会变色。有点晕?下面举个例子确定一下3*3阶Flip的A矩阵 (A为9阶矩阵)。

  • 若只点击了(1,1)格子,点击后(1,1),(1,2),(2,1)变黑,则x=(1,0,0,0,0,0,0,0,0),b=(1,1,0,1,0,0,0,0,0),根据Ax=b,A的第1列只能为(1,1,0,1,0,0,0,0,0)
  • 若只点击了(1,2)格子,点击后(1,1),(1,2),(1,3),(2,2)变黑,则x=(0,1,0,0,0,0,0,0,0),b=(1,1,1,0,1,0,0,0,0),根据Ax=b,A的第2列只能为(1,1,1,0,1,0,0,0,0)
  • 依次推出A的全部9列,为:
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

无论多少阶Flip,对应的A矩阵都是很有规律的对角阵。根据Ax=b,Flip问题就有了一个数学模型:已知A和初状态b,求x。那么显然这就是一个解方程组问题。而x可能无解,可能有不同的解形式,根据线性代数的知识,方程组的解可以由增广矩阵判断。需要注意的是,这些运算都是建立在布尔代数系统上的,而不是实数代数系统。在这个代数系统下,加法是异或,乘法是与。那么,无论是高斯消元求解还是求矩阵的秩,都需要用到的行变换都必须建立在布尔代数系统上,定义以下两种行变换:

  • 第一类行变换:行交换
  • 第二类行变换:行异或,A行的所有元素与B行的对应元素求异或

实数系统中行变换有3类,而布尔系统中只有两类。

 

结论:

记B={A,b},即A与b并在一起的增广矩阵。以下给出结论:

  • 若rank(B)>rank(A),则无解
  • 若rank(B)=rank(A),则解的个数为:N=2^(n*n-rank(A))

显然,只要有解,解数N只与阶数n有关,但是N和n之间找不到代数关系,我们只能编程实现一个求解数的程序,程序使用高斯消元法求A的秩rank(A),进而求得解数。
以下是程序求出Flip的阶数与解数的表格:

阶数 1 2 3 4 5 6 7 8 9 10
解数 1 1 1 16 4 1 1 1 256 1
阶数 11 12 13 14 15 16 17 18 19 20
解数 64 1 1 16 1 256 4 1 65536 1
阶数 21 22 23 24 25 26 27 28 29 30
解数 1 1 16384 16 1 1 1 1 1024 1048576
阶数 31 32 33 34 35 36 37 38 39 40
解数 1 1048576 65536 16 64 1 1 1 1 1

 

代码:

// Language : C
// Flip阶数与解数的关系

#include <stdio.h>
#include <stdlib.h>

int rank(int M){
    int i,j;
    const int N = M*M;
    // 申请N*N二维矩阵
    char **A = (char**)calloc(N,sizeof(char*));
    char  *p = (char *)calloc(N*N,sizeof(char));
    for(i=0;i<N;i++){
        A[i] = p + i*N*sizeof(char);
    }
    // 初始化N*N二维矩阵
    for(i=0; i<M; i++){
        for(j=0; j<M; j++){
            A[ i*M+j ][ i*M+j ] = 1;
            if(i>0)   A[ i*M+j ][ (i-1)*M+j ] = 1;
            if(i<M-1) A[ i*M+j ][ (i+1)*M+j ] = 1;
            if(j>0)   A[ i*M+j ][  i*M +j-1 ] = 1;
            if(j<M-1) A[ i*M+j ][  i*M +j+1 ] = 1;
        }
    }
    // 高斯消元
    for(i=0; i<N; i++){
        // 若对角元是0,就试图行交换
        if(A[i][i]==0){
            // 寻找元素为1的一行进行交换
            for(j=i+1; j<N && A[i][j]==0; j++);
            // 若找不到,说明rank = i,函数返回
            if(j==N){
                break;
            }else{
                // 若找到,进行行交换,使得A[i][i]=1
                int k;
                char tmp;
                for(k=0;k<N;k++){
                    tmp = A[k][i];
                    A[k][i] = A[k][j];
                    A[k][j] = tmp;
                }
            }
        }
        // 高斯消元,内循环
        for(j=i+1; j<N; j++){
            if(A[i][j]==1){
                int k;
                for(k=i;k<N;k++){
                    A[k][j] ^= A[k][i];
                }
            }
        }
    }
    free(A);
    free(p);
    return i;
}

int main(){
    int i;
    for(i=1;i<=20;i++){
        printf("%3d : %d\n", i, 1<<(i*i-rank(i)) );
    }
}

One thought on “Flip游戏的解存在性和数量的讨论

Comments are closed.