中国象棋马控制棋盘问题

mathe

http://tieba.baidu.com/f?kz=848740318 中国象棋中最少摆多少个马可以控制棋盘所有格子： 　　中国象棋的棋盘上最少摆上几只马，能控制住棋盘所有的格子？国棋象棋有这个问题。但中国象棋我好象没看到过。 　　一个空的中国象棋棋盘(9*10的格子)。“马”按中国象棋马走“日”的走法，有“蹩马腿”。假设可往上面摆放上很多的只马，最少摆放多少只马，使得摆放好后，无论棋盘上哪一个空格，都至少被其中一只马攻击到？(我把它叫做“中国象棋马控棋盘”)。 　　马走法是一直一斜，即先横着或直着走一格，然后再斜着走一个对角线，俗称“马走日”。马一次可走的选择点可以达到四周的八个点，故有八面威风之说。如果在要去的方向有别的棋子挡住，马就无法走过去，俗称“蹩马腿”。 　　用数学描述：若现在马的位置是(x,y)。它可以攻击到的点： (x±2,y±1) (当(x±1,y)有棋子时，攻击不到) (x±1,y±2) (当(x,y±1)有棋子时，攻击不到) 其中实际上有两个不同的问题: i)马所在的位置已经算控制 ii)马所在的位置不算被控制（还需要其它马攻击此位置） 根据上面的百度链接中结论，基本可以判定问题i)需要22只马，但是问题2的结论未知 此外，如果知道了最少的马的数目以后，请问，达到最小的马的数目的棋局有多少个呢？（如果对称的局面看成相同的又有多少个呢？）

风云剑

看起来像皇后问题，但是蹩马腿导致了不少麻烦。

hujunhua

第ii)问题，可能蹩死无解呢。可能有解的最小棋盘是3×4的，貌似无解。

hujunhua

4×n的棋盘无解，5×5也蹩死。 3×n的棋盘，有解的最小棋盘是3×8，并且只有两解。 ●┬●●●●┬●　●┬●●●┬●●　 ├┼●┼┼●┼┤　├┼●┼┼●┼┤ ●●┴●●┴●●　●●┴●●●┴●

hujunhua

从下棋的目的来看，马所在的位置已经是完成攻击了。但这不妨碍我们提出第ii)问。

056254628

以下是24匹马：

056254628

楼主要求的棋盘是9*10的。 以下是34匹马

056254628

30匹马：

056254628

28匹马：

hujunhua

我试排了一下，最少也是28匹马。不过我有一个附加要求，就是兵、炮位置和九宫中心不得被马占据。因为兵和炮的位置上有饰花，九宫中心是米花，偶是用制表符和特殊符号来“画图”的，这种位置一旦被马（●）所覆盖，饰花连角角都不会遗露一点（字符被替代），吾所不欲也。 ┏┯┯┯┯┯┯┯┓　┏┯●┯┯●┯●┓　┏●┯●┯┯●┯┓┏┯┯┯┯┯┯┯┓ ┠┼┼┼╳┼┼┼┨　┠┼●┼╳┼●┼┨　┠┼●┼╳┼●┼┨┠┼┼┼╳┼┼┼┨ ┠╬┼┼┼┼┼╬┨　●╬┼●●●┼╬●　●╬┼●●●┼╬●┠╬┼┼┼┼┼╬┨ ╠┼╬┼╬┼╬┼╣　╠┼╬┼╬┼╬●╣　╠●╬┼╬┼╬┼╣╠┼╬┼╬┼╬┼╣ ┠┴┴┴┴┴┴┴┨　┠┴●●┴┴●┴┨　┠┴●┴┴●●┴┨┠┴┴┴┴┴┴┴┨ ┠┬●┬┬┬┬┬┨　┠┬●●┬┬●┬┨　┠┬●●┬┬●┬┨┠┬┬┬┬┬┬┬┨ ╠┼╬┼╬┼╬┼╣　╠┼╬┼╬┼╬●╣　╠┼╬┼╬┼╬●╣╠┼╬┼╬┼╬┼╣ ●╬┼●●●┼╬●　●╬┼●●●┼╬●　●╬┼●●●┼╬●┠╬┼┼┼┼┼╬┨ ┠┼●┼╳┼●┼┨　┠┼●┼╳┼●┼┨　┠┼●┼╳┼●┼┨┠┼┼┼╳┼┼┼┨ ┗┷●┷┷●┷●┛　┗┷●┷┷●┷●┛　┗┷●┷┷●┷●┛┗┷┷┷┷┷┷┷┛ 图1 图2 镜像对称解 图3 中心对称解 图4 空棋盘 图1，半盘分析，这些点是必定有马的位置。 图2，两岸镜像对称 图3，两岸中心对称 符合附加要求的28马解仅此两图.