转椅子——魔兽争霸之月纹传说

背景

前些天老葛玩魔兽争霸的时候,被一个叫做转椅子的游戏给拦住了去路。但是看见这一关,第一反应,我去,这不活生生一道OI题,作为一个曾经的OIer,我瞬间来了敲代码的欲望。

规则

如下图,椅子杂乱的摆放着,现在你每次可以选择一个椅子,使其顺(逆)时针转90°,同时其上、下、左、右的椅子(如果存在)也会顺(逆)时针旋转90°。

现在要求使用如上规则,将所有椅子转回原位(都向上)。

但既然都编程了,就不要之解决这一个特定的问题啦,我将题目修改为:

在x*y的方格上,每个格子里有一把椅子,方向是杂乱的,规则同上,输出如何将所有椅子转回原位(都向上)

寻找

对着题目想了许久,并没有什么思路,这种题搜索看起来不靠谱,动态规划?然而这种十字形状的规则实在找不到规律。

印象中自己曾经做过一道与之类似的题,也是上下左右,于是开始百度……

首先发现了知乎上的一篇文章:《点灯游戏:迟到8年的美丽,用数学绘制的“二维码”!》,这篇文章写的挺有意思,但真正我想要的还得是立面提到的一篇文章(不知道是不是论文):“Lights Out Puzzle.” From MathWorld

至此,终于找到了这个名叫Lights Out Puzzle的游戏

解决

看这个解决,请先看“Lights Out Puzzle.” From MathWorld

文章中将问题最终表示成在mod 2的前提下求解线性方程组。

其中灯的状态有两种可能,1代表亮,0代表灭,在应用规则A[i,j]时,格子L[x,y]的状态更新为(L[x,y]+A[i,j][x,y]) mod 2,(最后的线性方程组每个A都写在一行中,L写在一列中)

现在考虑转椅子,可以将规则(暂时)简化为只允许顺时针旋转,这并不影响解决问题。

椅子的状态有四种可能,规定0代表上(↑),1代表右(→),2代表下(↓),3代表左(←),规则A与点灯问题完全一致。于是仿照点灯问题,在应用规则A[i,j]时,格子L[x,y]的状态的状态更新为(L[x,y]+A[i,j][x,y] mod 4。这样就可以得到一个需要在mod 4的前提下求解的线性方程组。

例子

← ↓ ↑
→ ← ↓

L =

|320|
|132|

六个A分别是

|110| |111| |011|
|100| |010| |001|

|100| |010| |001|
|110| |111| |011|

于是得到线性方程组

|110100||x11| |3|
|111010||x12| |2|
|011001||x13|=|0|
|100110||x21| |1|
|010111||x22| |3|
|001011||x23| |2|

解得X =

|131310|'

即,答案为

|131|
|310|

意思是将L0 =

↑ ↑ ↑
↑ ↑ ↑

这个状态的六个位置分别顺时针旋转90°,270°,90°,270°,90°,0°即可得到L

游戏中的要求是想反的,从L到L0,只需将顺时针改为逆时针即可。至此,问题就解决了^_^

编程

最近在学Python的基础知识,就用Python实现了上述过程。

A矩阵的计算方法是在A[i,j]的点中,如果与(i,j)的曼哈顿距离(Taxicab geometry)小于等于1的点的值为1,否则为0。

求解线性方程组用的是高斯消元法(Gaussian elimination),但只是理解了思想,所以写的应该是很不标准的( ̄▽ ̄)”

接下来是源码(Python3.4.3)

def gcd(x, y):
    return x if y == 0 else gcd(y,x%y)

def lcm(x, y):
    return x*y//gcd(x,y)

def show(a):
    for i in a:
        print(i)
    print()

#to create matrix A[x,y]
def rule(width, height, x, y):
    return [1 if abs(x-i)+abs(y-j) <= 1 else 0 for j in range(height) for i in range(width)]

def gauss(a):
    for i in range(len(a)):
        if a[i][i] == 0:
            for j in range(i+1, len(a)):
                if a[j][i] != 0:
                    k = a[i]
                    a[i] = a[j]
                    a[j] = k
                    break
        if a[i][i] == 0:
            continue
        for j in range(i+1, len(a)):
            if a[j][i] == 0:
                continue
            m = lcm(a[i][i], a[j][i])
            n = m // a[j][i]
            m = m // a[i][i]
            a[j] = [(a[j][x]*n-a[i][x]*m) for x in range(len(a[i]))]
        show(a)
    for i in range(len(a)):
        a[i] = a[i][-2::-1] + [a[i][-1]]
    a = a[::-1]
    ans = []
    for i in range(len(a)):
        x = cal(a[i][i], a[i][-1])
        ans.append(x%4)
        for j in range(i+1, len(a)):
            a[j][-1] = (a[j][-1] - x*a[j][i])
    return ans[::-1]

#a not standard method to calculate x[i]
def cal(x, y):
    return 0 if x == 0 else y//x

x = int(input('Input the width:'))
y = int(input('Input the height:'))

a = []
for j in range(y):
    for i in range(x):
        a.append(rule(x, y, i, j))

for j in range(y):
    st = input(('Input the No.%d line(divided by space):' % (j+1)))
    i = 0
    for n in st.split(' '):
        a[j*x+i].append(int(n))
        i += 1

ans = gauss(a)
if(len(ans) == 0):
    print('No answer!')
else:
    for j in range(y):
        for i in range(x):
            print('%2d ' % ans[j*x+i], end='')
        print()

其他

通过点灯游戏再一次看到了百度百科和wikipedia的差距,可以自己感受一下(一个上来就暴力求解,另一个上来就跟你侃数学)(不算简介)。

点灯游戏-百度百科

Lights Out(game) from Wikipedia

上篇期中成绩爬虫
下篇Java实现Tupper自我指涉公式的计算