:

使用回溯法解决四皇后问题

song100e 发布于:2019-5-27 16:48  有 24 人浏览,获得评论 0 条  

        本人于2019年5月25日参加了上半年的软件设计师软考考试,在下午试题中再次出现了四皇后问题。

20190525.jpg


问题描述
在 4*4 的棋盘上无冲突的摆放 4 个皇后,无冲突是指一个皇后所在位置的水平、竖直以及斜线上不能出现其他的皇后,其他的 n 皇后问题以此类推。

解决方法:
所谓的回溯法就是按行来摆放棋子,下一行的摆放满足于与上一行的棋子没有冲突,否则就返回上一步走其他的路线。

wKiom1UvaAmiI54OAABV5z0XqIY574.jpg

详细说明
1,在第一行有四种可能,选择第一个位置放上皇后

4queen-1.png

2,第二行原本可以有四种可能摆放,但是第一第二个已经和第一行的皇后冲突了,因此只剩下第三第四个格子了,先选择第三个格子

2.png

3,接下来是第三行,根据规则可以看出,第三行已经没有位置放了,因为都跟第一第二行的皇后冲突,此时返回到第二行第四个

3.png

4,继续来到第三行,发现只有第二个满足条件

4.png

5,然后发现第四行已经不能放了,只能继续返回,返回到第一行,开始下一种可能

5.png

6,按照 1-5 的步骤,可以找到下面的其中一种解法
6.png

总而言之,回溯法就是开始一路到底,碰到南墙了就返回走另外一条路,有点像穷举法那样走遍所有的路。

综上,四皇后一共有 2 种排列方式。

代码略

赞助我,共同学习进步!