精确覆盖矩阵与数独 - 报告ppt.ppt

简单一点，且考虑3?3的。 精确覆盖问题与“数独” 那利用舞蹈链（Dancing Links）算法求解数独问题，实际上就是下面一个流程： 把数独问题转换为精确覆盖问题 设计出数据矩阵 用舞蹈链（Dancing Links）算法求解该精确覆盖问题 把该精确覆盖问题的解转换为数独的解 首先看看数独问题（9*9的方格）的规则： 每个格子只能填一个数字 每行每个数字只能填一遍 每列每个数字只能填一遍 每宫每个数字只能填一遍 精确覆盖问题与“数独” 在把数独问题转换为精确覆盖问题时把行当做是状态，把列当做是需要满足的条件。 那现在就是利用这个规则把数独问题转换为精确覆盖问题可是，直观上面的规则，发现比较难以转换为精确覆盖问题。因此，把上面的表述换个说法： 每个格子只能填一个数字 每行1-9的这9个数字都得填一遍（也就意味着每个数字只能填一遍） 每列1-9的这9个数字都得填一遍 每宫1-9的这9个数字都得填一遍 我们把矩阵的每个列都定义成一个约束条件： 精确覆盖问题与“数独” 第1列定义成：（1，1）填了一个数字 第2列定义成：（1，2）填了一个数字 …… 第9列定义成：（1，9）填了一个数字 第10列定义成：（2，1）填了一个数字 …… 第18列定义成：（2，9）填了一个数字 …… 第81列定义成：（9，9）填了一个数字 至此，用第1-81列完成了约束条件1：每个格子只能填一个数字 第N列（1≤N≤81）定义成：（X，Y）填了一个数字。 N、X、Y之间的关系是：N=（X-1）×9+Y ? 精确覆盖问题与“数独” 第82列定义成：在第1行填了数字1 第83列定义成：在第1行填了数字2 …… 第90列定义成：在第1行填了数字9 第91列定义成：在第2行填了数字1 …… 第99列定义成：在第2行填了数字9 …… 第162列定义成：在第9行填了数字9 至此，用第82-162列（共81列）完成了约束条件2：每行1-9的这9个数字都得填一遍 第N列（82≤N≤162）定义成：在第X行填了数字Y。 N、X、Y之间的关系是：N=（X-1）×9+Y+81 ? 精确覆盖问题与“数独” 第163列定义成：在第1列填了数字1 第164列定义成：在第1列填了数字2 …… 第171列定义成：在第1列填了数字9 第172列定义成：在第2列填了数字1 …… 第180列定义成：在第2列填了数字9 …… 第243列定义成：在第9列填了数字9 至此，用第163-243列（共81列）完成了约束条件3：每列1-9的这9个数字都得填一遍 第N列（163≤N≤243）定义成：在第X列填了数字Y。 N、X、Y之间的关系是：N=（X-1）×9+Y+162 ? 精确覆盖问题与“数独” 第244列定义成：在第1宫填了数字1 第245列定义成：在第1宫填了数字2 …… 第252列定义成：在第1宫填了数字9 第253列定义成：在第2宫填了数字1 …… 第261列定义成：在第2宫填了数字9 …… 第324列定义成：在第9宫填了数字9 至此，用第244-324列（共81列）完成了约束条件4：每宫1-9的这9个数字都得填一遍 第N列（244≤N≤324）定义成：在第X宫填了数字Y。 N、X、Y之间的关系是：N=（X-1）×9+Y+243 精确覆盖问题与“数独” 第244列定义成：在第1宫填了数字1 第245列定义成：在第1宫填了数字2 …… 第252列定义成：在第1宫填了数字9 第253列定义成：在第2宫填了数字1 …… 第261列定义成：在第2宫填了数字9 …… 第324列定义成：在第9宫填了数字9 至此，用第244-324列（共81列）完成了约束条件4：每宫1-9的这9个数字都得填一遍 第N列（244≤N≤324）定义成：在第X宫填了数字Y。 N、X、Y之间的关系是：N=（X-1）×9+Y+243 精确覆盖问题与“数独” 第244列定义成：在第1宫填了数字1 第245列定义成：在第1宫填了数字2 …… 第252列定义成：在第1宫填了数字9 第253列定义成：在第2宫填了数字1 …… 第261列定义成：在第2宫填了数字9 …… 第324列定义成：在第9宫填了数字9 至此，用第244-324列（共81列）完成了约束条件4：每宫1-9的这9个数字都得填一遍 第N列（244≤N≤324）定义成：在第X宫填了数字Y。 N、X、Y之间的关系是：N=（X-1）×9+Y+243 精确覆盖问题与“数独” 至此，用了324列完成了数独的四个约束条件，矩阵的列定义完成。那接下来，就是把数独转换为矩阵数独问题中，每个格子分两种情况： 有数字格子 以例子来说明，在（4，2）中填的是7 把（4，2）中填的是7，解释成4个约束条件 1、在（4