|
棋类游戏因变化无穷、富有趣味和益智功能，受到很多人的喜爱，国际象棋是其中一种。除了休闲娱乐，国际象棋中还有一些趣味知识，如八皇后问题。 提起八皇后问题，我们就要讲到一个人——高斯。高斯是德国著名的数学家、物理学家和天文学家。他的兴趣爱好十分广泛，常常在工作之余独自一人下棋。不过，他的下法与众不同，其规则多数与他自己设计的一些数学问题有关。1850年，高斯又给自己提出了一个象棋问题：在国际象棋棋盘，即8*8的棋盘上放8个“皇后”，保证它们之间不能互相攻击，换言之，任意两后不能位于棋盘的同一行、同一列或同一对角线上，满足条件的放法有多少种？ 其实，八皇后问题是一个经典的回溯算法问题。回溯法也称为试探法，这种方法是指暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。换言之，回溯法就是允许在选择失败的情况下，系统地去尝试完所有可能的选择。 因而，在分析八皇后问题时，用回溯法来解决问题是很合适的：从一个给定的位置出发有多种选择，但不知道究竟哪种选择才能解决问题。由于每一个皇后摆放的位置都受到前一个皇后落子位置的限制，所以越是最先落子的皇后，可选择的位置就越多，越后放的皇后，可选择的范围就越小。当我们选择采用回溯的方法解决八皇后问题时，先在棋盘上放上第1个皇后，然后再放上第2个，并保证第二个皇后和第一个不互相攻击。再接着放上第3个皇后，并满足她与前两个皇后都不会相互攻击的条件，依此类推，直到所有的皇后都摆放上去。假如第7个皇后放上后，第8个皇后已经没有安全的位置了，则要试着调整第7个皇后的位置，并再次调整第8个皇后的位置，看是否有安全的位置；如果第7个皇后的位置都已经尝试过而第8个皇后还没有安全的位置，则应试着调整第6个皇后的位置，重新调整第7、第8个皇后的位置。依此类推，并且有可能倒退到调整第1个皇后的位置。 所以，采用回溯的方法来解决八皇后问题，看似实现形式非常简单，实际上这一过程的工作量十分巨大，尤其是当八皇后问题扩展到更多的时候。 来源：新华网 (责任编辑：admin) |