九宫格点灯谜题全状态通解

0 点赞
魔法工艺 Magicraft
转载

通过有限的步骤从任意状态转为全亮。 点亮单独的一盏灯 首先我们将九盏灯分别编号,位于角落的记为x_n,位于边缘的记为y_n,中央的记为z。并将点这盏灯的操作也编号,分别记为v_n,e_n,c。即: x1 y1 x2 v1 e1 v2 y4 z y2 e4 c e2 x4 y3 x3 v4 e3 v3 那么每一种点灯都对应灯的一种变化,记为: c = z y1 y2 y3 y4 e_n = z x_n x_n+1 y_n v_n = x_n y_n-1 y_n (这种表示法假设n=1时,x_n-1为x4,同理n=4时,x_n+1为x1。y亦同理。) 如图所示,红色的圆圈表示点灯位置,白色的圆圈表示将要点亮的灯:

显然,通过单独点击四条边或四个角,可以得到X形或菱形的灯;而菱形的灯只需点亮中心,就能单独点亮中央的灯。

记为: 4x = x1 x2 x3 x4 = v1 v2 v3 v4 4y = y1 y2 y3 y4 = e1 e2 e3 e4 z = c y1 y2 y3 y4 = c e1 e2 e3 e4 (= c e_n e_n+1 e_n+2 e_n+3) 可以单独点亮中央的灯即意味着我们可以忽略中央的灯带来的影响,比如联立e_n和v_n,以及e_n和v_n+1,再消除z,可得: x_n+1 y_n-1 = z e_n v_n = c e_n+1 e_n+2 e_n+3 v_n x_n y_n+1 = z e_n v_n+1 = c e_n+1 e_n+2 e_n+3 v_n+1 如图所示。如果我们忽略中央的点的变化,只看外围(此时只需e_n和v_n/v_n+1两步),那么这两种变换代表了在外围8个点上的“日”字形跳跃。

通过这种跳跃组合,外围任意两点都能同时点亮,这需要通过次数相等的e_n和v_n来实现。其中最为关键的是相邻两个x或两个y的同时点亮: x_n-1 x_n = x_n+3 y_n+1 x_n y_n+1 = c e_n+3 e_n e_n+1 v_n+2 c e_n+1 e_n+2 e_n+3 v_n+1 = e_n e_n+2 v_n+1 v_n+2 x_n x_n+1 = e_n+1 e_n+3 v_n+2 v_n+3 y_n-1 y_n+2 = x_n+1 y_n-1 x_n+1 y_n+2 = c e_n+1 e_n+2 e_n+3 v_n c e_n+2 e_n+3 e_n v_n+2 = e_n e_n+1 v_n v_n+2 y_n y_n+1 = e_n+2 e_n+3 v_n v_n+2 如图所示。这意味着当x和y的点亮数量均为偶数时,它们可以分别消除,并且无需考虑中央点的变化。

注意到,实际上此时我们已经可以点亮这两个灯中间的灯,来实现只点亮中间一个灯: x_n = v_n y_n-1 y_n = v_n e_n+1 e_n+2 v_n-1 v_n+1 = e_n+1 e_n+2 v_n-1 v_n v_n+1 y_n = e_n z x_n x_n+1 = c e_n+1 e_n+2 e_n+3 e_n+1 e_n+3 v_n+2 v_n+3 = c e_n+2 v_n+2 v_n+3 如图所示。至此,我们已经可以根据盘面上未点亮的灯的情况,逐个点亮它们。

根据整体状态点灯 通过这样的多次操作仅为了点亮一个灯还是太过繁琐,我们可以利用上述思路进行问题的转化: 1. **先计算外围8盏灯被点亮的个数**,如果为奇数则点亮除中央外任意一盏灯使其变为偶数。 2. **分别计算位于角落的灯(x)和位于边缘的灯(y)的个数**,因为前述操作它们要么同为奇数要么同为偶数,同为奇数则点亮除中央外任意相邻的两盏灯,使其均变为偶数。 3. **只看位于角落的灯(x)**,取相邻的两个未点亮的x灯,利用前述x_n x_n+1的点亮方式将其点亮。如果未点亮的灯是对角分布的,那么只需任取两盏相邻的x灯点亮,即可将未点亮的灯变为相邻。 4.只看位于边缘的灯(y),取相邻的两个未点亮的y灯,利用前述y_n y_n+1的点亮方式将其点亮。如果未点亮的灯是对角分布的,那么只需任取两盏相邻的y灯点亮,即可将未点亮的灯变为相邻。 5. 如果此时中央的灯未点亮,通过前述z的点亮方式将其点亮。 一个简单的例子如图所示:(白色圆圈是当前状态,红色圆圈是此时应当去点的灯。)

尽管通解是这样,但如果中间步骤出现可解的形式,就可以直接求解。