魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 116726|回复: 14

隔空棋 [复制链接]

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-10-10 00:11:13 |显示全部楼层
n*n的棋盘,甲乙玩一种游戏,规则如下:
1. 甲乙两人轮流往棋盘上放棋子,每次放一个棋子在格子上。
2. 放棋子的位置不限,但不能和棋盘上已放的棋子相邻(前后左右斜角一步的地方都算相邻),也不能放在有棋子的格子上。
3.谁最后无棋可放就算输。
------------------
请问:对于特定的n,先行方胜,还是后手方胜?有没有什么规律?
显然n=2,n=3都是先先行方胜。

Rank: 7Rank: 7Rank: 7

积分
2520
帖子
3072
精华
7
UID
62890
性别

中国纪录 八年元老

发表于 2009-10-10 00:29:05 |显示全部楼层
这道题还是挺简单的,把棋盘扩充为(n+2)×(n+2)的,
然后每个棋子看成是3×3大小的,就简单多了,其他就不用多说了
19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群:RP与公式的绝佳配合QQ群5652935

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-10-10 00:34:22 |显示全部楼层
当把棋子看成3*3的时候对自己不利,他可以把棋子放到只相当于2*3,或2*2的位置;
还是有变数的。

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

发表于 2009-10-10 00:45:46 |显示全部楼层
当n为奇数的时候,先行方把棋子放在棋盘的正中,然后后手方每放一个棋子,先行方都在其中心对称的地方放一个,这样,先行方必胜。
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-10-10 00:54:17 |显示全部楼层
noski火眼金睛。
n为偶数呢?

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

发表于 2009-10-10 01:04:19 |显示全部楼层

回复 5# 的帖子

偶数的没看出来规律,感觉先下会输,明天再想。。
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
2520
帖子
3072
精华
7
UID
62890
性别

中国纪录 八年元老

发表于 2009-10-10 01:54:09 |显示全部楼层
原帖由 noski 于 2009-10-10 01:04 发表
偶数的没看出来规律,感觉先下会输,明天再想。。


已经是1点了...
19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群:RP与公式的绝佳配合QQ群5652935

使用道具 举报

Rank: 4

积分
2315
帖子
2249
精华
0
UID
110000
性别
发表于 2009-10-10 07:01:11 |显示全部楼层
为啥要扩大到(n+2)*(n+2)?

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2009-10-11 17:00:38 |显示全部楼层
对于n=4,先手方败。
直接在棋盘上试,很容易就可解出。
第一步(先手方)根据对称性只有3种放法,后手方接着都可以走成使:  剩下互不相关的全等的两段,稳稳获胜。
但若用状态的递推或Nim值法,觉得解出n=4都异常麻烦。不知有没有好的方法。

使用道具 举报

Rank: 1

积分
80
帖子
65
精华
0
UID
107099
性别
保密
发表于 2009-10-11 21:06:18 |显示全部楼层
nim值法的优势在于,通过子游戏的值能很快得到母游戏的值。
在两维的情况下,一次操作并不一定会把整个棋盘变成两个或多个互不相关的子游戏。
所以计算nim值的计算量并不小,可能仅比穷举稍微少一点点。

但是nim值法仍然有其优势,就是当两个人用多个棋盘下棋时,直接把nim值异或就可以解决。

考虑了一下两维甚至多维的编程:把棋盘上的一格对应到两进制数的一位,如果允许下在某格,那么该位为1;如果不允许下在某格,那么该位为0;这样,任何棋盘状态都能一一对应到非负整数。每下一手,是把数字中若干位从1变成0。

用这个状态编码的方式编程,应该并不困难,也不容易出错。

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 16:23

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部