单选题
要在8×8的棋盘上摆放8个“皇后”,要求“皇后”之间不能发生冲突,即任何两个“皇后”不能在同一行、同一列和相同的对角线上,则一般采用______来实现。
A、
分治法
B、
动态规划法
C、
贪心法
D、
回溯法
【正确答案】
D
【答案解析】
[分析] 本题考查算法设计技术。
N-皇后问题是一个经典的计算问题,该问题基于一些约束条件来求问题的可行解。该问题不易划分为子问题求解,因此分治法不适用;由于不是要求最优解,因此不具备最优子结构性质,也不宜用动态规划法和贪心法求解。而系统搜索法——回溯法可以有效地求解该问题。
提交答案
关闭