八皇后问题

来自计算思维百科
跳转至: 导航搜索

回溯法的另一个经典案例是解八皇后'问题'('Eight Queens Problem')。 八皇后是一个古老而著名的问题,是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋的棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?

回溯法解八皇后问题的思路是:逐行摆放皇后。初始,第1行皇后放第1列;摆放第i(i=2,∧,8)行皇后时,从第1列开始,逐列判定是否与前i-1行皇后攻击,直到找到一个不攻击的摆放位置,继续第i+1行的摆放;若第i行无摆放位置,则拿掉该行皇后,回溯至第i-1行,第i-1行皇后从当前位置的下一列开始判定,继续搜索。当第1行皇后的摆放位置超出棋盘时,全部求解过程结束,可找到八皇后问题的92种摆法。显然,这是一个由部分解扩展为问题解的过程(按行扩展),在扩展中,加入了是否攻击的约束条件判定。

读者可以简单的四皇后问题(在4X4格的国际象棋的棋盘上摆放四个皇后,使其不能互相攻击)为例,练习上述回溯过程。

回溯法有通用解法之称,当一个问题没有显而易见的解法时,可尝试使用回溯法求解,这实际是与穷举法一致的,因其本质仍是穷举。需要注意,回溯和穷举虽然能解很多问题,但其算法效率可能很低。