主题:[讨论]5*5的黑棋控制棋盘问题(属于回溯递归)
good2007
[专家分:0] 发布于 2008-01-19 16:58:00
最近无聊,翻起大学一年级时的一道题目,以前没有认真看过,现在竟然想不到解答
题目:
在一个5*5的方格棋盘中,如果在某一个方格子里放入一个黑棋子,则与该方格相邻的上下左右的方格都不能放白格子,现要求请设计一个程序,让计算机找出7个黑棋子就可以控制整个棋盘的方案....
请各为高手请教下,怎么样设置条件就可以解决这个问题?我找不到递归走来的最佳方案.
回复列表 (共7个回复)
沙发
plane [专家分:310] 发布于 2008-01-19 17:59:00
搜索吧,回朔的话找不到好的约束方程,其结果和穷举是一样的。
7C25=480700,可以接受的范围
板凳
good2007 [专家分:0] 发布于 2008-01-19 22:01:00
怎么样都要有个判断的范围..
假如黑棋为1,它的周围不能放其他的棋子为-1,其他空位为0,
难不成要判断25个空格不为0时才算一种结果..
3 楼
good2007 [专家分:0] 发布于 2008-01-19 22:07:00
主要是每一行有时不能一定要全部控制拉才算,有时是下行的棋子去控制上一行没有控制的格.
4 楼
nobush [专家分:390] 发布于 2008-01-23 18:10:00
[size=4]不難吧?人腦幾分鐘就解決的事情,就看怎麽歸納
* * 0 * *
0 * * * 0
* * 0 * *
0 * * * 0
* * 0 * *
[/size]
5 楼
scaredkinght [专家分:5310] 发布于 2008-01-23 19:10:00
这种也行
* * 0 * *
0 * * * 0
* * 0 * *
* * 0 * *
0 * * * 0
6 楼
good2007 [专家分:0] 发布于 2008-12-29 10:49:00
看来对于这种问题,主要是有经验的归纳才能做出比较优的解,本人对这中归纳欠缺.
7 楼
moke9 [专家分:30] 发布于 2010-09-02 07:52:00
你好.我是全职网赚工作者.
如果你有时间有电脑.
想在网络上创业.请联系我..
项目绝对真实.详情QQ空间资料
加盟请联系 QQ908889846
我来回复