握住科学钥匙 打开科学之门

首页 > 正文

你知道“八皇后问题”吗?

2019-09-20 15:19  来源: 新华网

棋类游戏因变化无穷、富有趣味和益智功能,受到很多人的喜爱,国际象棋是其中一种。除了休闲娱乐,国际象棋中还有一些趣味知识,如八皇后问题。

提起八皇后问题,我们就要讲到一个人——高斯。高斯是德国著名的数学家、物理学家和天文学家。他的兴趣爱好十分广泛,常常在工作之余独自一人下棋。不过,他的下法与众不同,其规则多数与他自己设计的一些数学问题有关。1850年,高斯又给自己提出了一个象棋问题:在国际象棋棋盘,即8*8的棋盘上放8个“皇后”,保证它们之间不能互相攻击,换言之,任意两后不能位于棋盘的同一行、同一列或同一对角线上,满足条件的放法有多少种?

其实,八皇后问题是一个经典的回溯算法问题。回溯法也称为试探法,这种方法是指暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解。倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。换言之,回溯法就是允许在选择失败的情况下,系统地去尝试完所有可能的选择。

因而,在分析八皇后问题时,用回溯法来解决问题是很合适的:从一个给定的位置出发有多种选择,但不知道究竟哪种选择才能解决问题。由于每一个皇后摆放的位置都受到前一个皇后落子位置的限制,所以越是最先落子的皇后,可选择的位置就越多,越后放的皇后,可选择的范围就越小。当我们选择采用回溯的方法解决八皇后问题时,先在棋盘上放上第1个皇后,然后再放上第2个,并保证第二个皇后和第一个不互相攻击。再接着放上第3个皇后,并满足她与前两个皇后都不会相互攻击的条件,依此类推,直到所有的皇后都摆放上去。假如第7个皇后放上后,第8个皇后已经没有安全的位置了,则要试着调整第7个皇后的位置,并再次调整第8个皇后的位置,看是否有安全的位置;如果第7个皇后的位置都已经尝试过而第8个皇后还没有安全的位置,则应试着调整第6个皇后的位置,重新调整第7、第8个皇后的位置。依此类推,并且有可能倒退到调整第1个皇后的位置。

所以,采用回溯的方法来解决八皇后问题,看似实现形式非常简单,实际上这一过程的工作量十分巨大,尤其是当八皇后问题扩展到更多的时候。

本作品为“科普中国-科学原理一点通”原创,转载时务请注明出处。

作者: 朱寅莹   [责任编辑: 李浩]

相关稿件

象棋,数学