注意:此答案假设您有兴趣寻找 有效的解决方案。如果您需要找到 解决方案,这将无济于事。
Russell和Norvig撰写的《人工智能:一种现代方法》第二版在第143页的第5章:约束满足问题中有一张表,比较了各种任务的各种约束满足问题算法。(最新版本是第三版,看起来约束约束问题现在是第6章。)
根据他们的结果,在针对 n -Queens问题测试的算法中,最小冲突局部搜索启发式算法得分最高,平均要求4K检查,而回溯和前向检查则需要> 40,000K。
该算法非常简单:
在最后一步中,我假设每个女王/王后都被限制在她的栏中,因此她只能更改该栏中的行。如果有几行将当前皇后区的冲突最小化,则可以在其中任意选择。