16年4个月前IP:未同步
258336
13楼
对于这种数组,和我们数学上的数组有些差异啊。

空棋盘时这个棋盘是四方对称的。

放第一个皇后的时候,只需判断1/4个象限(包括中心轴)。
第二个皇后,如果皇后1在中心点上,那么同样四方对称,只需穷举其1/4位置。
如果在轴上,那变成左右对称。这样要再对对称轴一半进行判断。
打破了对称性后才需要全部穷举。

你每次放入一个皇后,都可能形成对称条件,都能获得减少穷举次数的机会。当然,如果是2个以上形成对称条件,可以肯定不符合要求,也不需要再去穷举了。这样可以算的快一些。

不过还是第一次放可以减少的计算次数比较明显(大约缩短了总计算次数的75%)。之后的次数可以忽略。
评论
文号 / 258336

实习会员
名片发私信
学术分 0
总主题 0 帖总回复 13 楼拥有证书:笔友
注册于 2010/09/17 16:44:11最后登录 2018/01/10 01:11:18
主体类型:个人
所属领域:无
认证方式:邮箱
IP归属地:0

个人简介

暂未填写
笔记
{{note.content}}
{{n.user.username}}
{{fromNow(n.toc)}} {{n.status === noteStatus.disabled ? "已屏蔽" : ""}} {{n.status === noteStatus.unknown ? "正在审核" : ""}} {{n.status === noteStatus.deleted ? '已删除' : ''}}
  • 编辑
  • 删除
  • {{n.status === 'disabled' ? "解除屏蔽" : "屏蔽" }}
我也是有底线的