数独是一种小游戏。规则是在一个9*9或者其他型号的板子上填数字,必须满足三个要求:1.每一个横排的9个空格必须是1到9之间的互相不重复的一个数字。2.每一个竖排的9个空格必须是1到9之间的互相不重复的一个数字。3.每一个3*3的小单元(1~3,3~6,6~9)必须是1到9之间的互相不重复的一个数字。
下面是几个重要的定义:
定义1(Sudoku Solution): The solution of a Sudoku puzzle requires that every row, column, and box contain all the numbers in the set [1,2,...,9] and that every cell is occupied by one and only one number.
定义2(Preemptive Sets): A preemptive set is composed of numbers from the set [1,2,...,9] and is a set of size m, 2<= m <= 9, whose number are potential occupants of m cells exclusively, where exclusively means that no other numbers in the set [1,2,...,9] other than the members of those m cells.
解数独的算法:
第一步:找到所有forced numbers 在数独中的。(方法: 利用数独的定义,先全部markup,然后判断每一行,列和九宫格中是否只有唯一的数,如果有就标记为确定的forced)
第二步:Mark up 数独。(把所有的可能值分别填入不同的表格中)
第三步:迭代搜索preemptive sets(先发制人集合)在所有的行,列和九宫格中,划掉被排除的数。
第四步:(a)找到了结果
(b)必须随机选一个数继续往下找
第五步:如果4(a)成立,那么结束:如果4(b)成立,那么重新执行第三步。
网友评论