背景
前些天老葛玩魔兽争霸的时候,被一个叫做转椅子的游戏给拦住了去路。但是看见这一关,第一反应,我去,这不活生生一道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的差距,可以自己感受一下(一个上来就暴力求解,另一个上来就跟你侃数学)(不算简介)。