美文网首页
数独(Sudoku)问题的Python实现

数独(Sudoku)问题的Python实现

作者: KUI666 | 来源:发表于2017-10-17 17:18 被阅读0次

    数独是一种小游戏。规则是在一个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)成立,那么重新执行第三步。

    相关文章

      网友评论

          本文标题:数独(Sudoku)问题的Python实现

          本文链接:https://www.haomeiwen.com/subject/haocuxtx.html