五子棋问题

hhh168168

问题：

在五子棋棋盘（15X15）上布最少的黑子，保证纵横及斜向各子间空格数不大于4，求最少子数及布法。

解法：

第一步：先将各元素分别向左斜下方和右斜下方投影作为他们在新矩阵中的行号和列号（如图）,这么做的目的是把纵横关系与斜向关系分离，便于分别处理：

（图中有错误，新行标应为i+j-1）

如下矩阵（为简便起见以9X9棋盘为例）中a(2,3),在新矩阵中变为b(4,10)。

矩阵A：

000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000

000000000

可转化出另一个矩阵B：

****XX0****XX
****X000****X
****00000****
**XX0000000**XX
**X000000000**X
**00000000000**
XX0000000000000XX
X000000000000000X

00000000000000000
X000000000000000X
XX0000000000000XX
**00000000000**
**X000000000**X
**XX0000000**XX
****00000****
****X000****X

****XX0****XX  （这里老乱码，*同X）

其中0是原矩阵对应过来的元素，是未知数，X是新矩阵多出来的元素,均赋初值1作为已知数，如此已将问题转变为一个含不等式约束的最小值问题，只是未知数只能取0或1，对于m阶棋盘，矩阵b为2m-1阶，我们分析如下：

两矩阵中元素存在如下关系

a（i,j）=b(i+j-1,m-(i-j))；

并且各行各列应满足：

∏ (a(i,j)+ a(i,j+1)+ a(i,j+2)+ a(i,j+3)+ a(i,j+4))≠0
j=1to（m-4）；

∏ (a(i,j)+ a(i+1,j)+ a(i+2,j)+ a(i+3,j)+ a(i+4,j))≠0
i=1to（m-4）；

∏ (b(i,j)+ b(i,j+1)+ b(i,j+2)+ b(i,j+3)+ b(i,j+4))≠0
j=1to（2m-1-4）；

∏ (b(i,j)+ b(i+1,j)+ b(i+2,j)+ b(i+3,j)+ b(i+4,j))≠0
i=1to（2m-1-4）；

(即每行或列中任意相邻的5个元素不能全为0，其中加号也可以是“或”运算，连乘号可以是“与”运算)

使得以上约束成立并使f=∑∑a(i,j)  i=1to m j=1to m取最小值的解就是我们要的结果！

至于怎么解我还没想出来，哈！

一个结果，想出来的，不是解出来的啊。

有办法了！

将原来离散的代数数论问题转变为连续域上的约束优化问题：
将a(i,j)只能取0或1的要求改为等式约束：
a(i,j)*(a(i,j)-1)=o;
并将原∏ (a(i,j)+ a(i,j+1)+ a(i,j+2)+ a(i,j+3)+ a(i,j+4))≠0等改为：
∏ (a(i,j)+ a(i,j+1)+ a(i,j+2)+ a(i,j+3)+ a(i,j+4))>0;
于此便将问题转化为连续域上的约束优化问题，可解了！

那位愿意MATLAB一下，立等答案？

mnpfc

虽然matlab不行，还是顶下楼主
同求matlab高手实现

jtrbs

没有解决的怎么说解决了！？论坛系统要完善啊！！？
帮顶！！！！！

浪漫蜗牛

没有解决的怎么说解决了！？论坛系统要完善啊！！？
% [0 [1 }  a! K6 y; y" W帮顶！！！！！

gaobuzheng

孤寂冷逍遥