知识卡片
逐行放皇后用占用表剪枝
每行恰放一后,先把同一行多次放置从选择空间去掉;列占用表阻止同列,row-col与row+col标识两类对角线,放置前统一检查这三项。
选择后更新棋盘和占用表,返回后同时恢复,并在完整解时复制棋盘。原书n需至少1,零会分配负长度对角数组;记录解后最好明确结束当前分支。成本还应计列扫描与每解棋盘复制,不能把n!当精确全部工作。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
对角线上所有格子的行索引减列索引都相等,即对角线上所有格子的 为恒定值 。 也就是说,如果两个格子满足 ,则它们一定处在同一条主对角线上。利用该 规律,我们可以借助图13‑18 所示的数组diags1 记录每条主对角线上
参考来源
- 位置:《Hello 算法--Go版本》第13章《回溯》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[3935,4045))
- 结论依据:实际皇后逐行策略/对角索引/状态配对/逐行快照,补充n和成本。
- 原始内容:对角线上所有格子的行索引减列索引都相等,即对角线上所有格子的 为恒定值 。 也就是说,如果两个格子满足 ,则它们一定处在同一条主对角线上。利用该 规律,我们可以借助图13‑18 所示的数组diags1 记录每条主对角线上