[问题] 有障碍物的八皇后问题

楼主: woody3724 (woody)   2017-09-03 14:45:48
在棋盘上放置障碍物,使得同列、同栏、同对角线的皇后不会互相攻击
例如: https://imgur.com/6t4JUor.jpg 在座标(3,f)和(4,h)放上障碍物
如此一来(3,e)和(3,h)不会打架,(3,h)和(5,h)也不会打架
Input是 1.放置了障碍物的棋盘,如图 https://imgur.com/iaggL3E.jpg
2.要摆到棋盘上的皇后的数量(大于等于1,当然也可能大于8)
若有解,则将其中一种解的棋盘印出
=====================================================================
一般的八皇后我是用backtracking解
我直接把我在LeetCode的解法贴上(因为是LeetCode,所以有用Solution包起来)
https://codeshare.io/29jRPM
我的解法中的第15行的循环是跑每列中可以摆放的栏
列放上旗子后,就进入下一列(第18行)
但可以放上障碍物的八皇后问题,变成在同一列上有可能放多个棋子
因此放上棋子后,似乎不能马上进入下一列,所以我这解法似乎就失败了
不知到各位有没有什么想法可以指点
谢谢
作者: s89162504 (阿本)   2017-09-03 19:59:00
是有可能放超过八个的意思吗?
作者: FRAXIS (喔喔)   2017-09-04 00:17:00
所以每一行多 try 几个? 一行有 k 个障碍物就顶多 k+1 个

Links booklink

Contact Us: admin [ a t ] ucptt.com