知识卡片

普通读书笔记卡 · 5654.c.4.a.1

逐行放皇后用占用表剪枝

理解等级:中级

每行恰放一后,先把同一行多次放置从选择空间去掉;列占用表阻止同列,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 记录每条主对角线上