让计算机解决和产生数独

人每天都得熬过一段时间,独自躲在密室中,扬起头45度角,眼神涣散地等待……在单调乏味的如厕时段,你不妨带上卷数独卫生纸。数独简单易玩,可以让你一边新陈代谢,一边训练大脑,人生大事、游戏通关两不误!

在开始阅读这篇文章之前,您可能需要对下列知识有所了解:

如何解数独

这,是一个数独,如果之前我们对数独有过了解的话,我们就会知道,要解出这样一个数独,就必须将数字填入这些方格内,并且使得每一行,每一列,每一个大方格都含且只含有一个数字,这自然不必多说,但是想要电脑高效地解决这个问题却无从下手。我们要解决的,就是这个令人无从下手的问题。

让计算机读懂数独

计算机并非天生就能读懂数独的,我们需要将所需要解的数独转换成计算机能够接受的格式,这里,我们有两种选择:一维数组,二维数组,或者字典(在phthon里的dic),在这里,我们选择二维数组的形式也就是下面这个样子:

[".....7..9",".4..812..","...9...1.","..53...72","293....5.",".....53..","8...23...","7...5..4.","531.7...."]

上面这个python二维数组代表了这样一个数独:

(当然,这是解出来以后的数独)

利用回溯

如果仅仅使用回溯算法的话,我们可以将代码控制在几十张之内,以为其思路之简单,仅仅是在每一个格子上尝试所有可能的数,每当尝试到非法的数时,就回溯,若合法,则继续在下一个格子上尝试所有可能的数,若下一个格子上所有数均为非法,则也回溯,就是这样简单的算法也足够解决大多数的问题。

class Solution:
    # @param board, a 9x9 2D array
    # Solve the Sudoku by modifying the input board in-place.
    # Do not return any value.
    def solveSudoku(self, board):
        if not board or len(board) != 9 or len(board[0]) != 9:return
        self.helper(board,0)
        return board
    def helper(self,board,i):
        if board[i / 9][i % 9] != '.':return self.helper(board,i + 1)
        for j in range(1,10):
            board[i / 9] = board[i / 9][:(i % 9)] + [str(j)] + board[i / 9][(i % 9 + 1):]
            if self.isValidSudoku(board) and (i == 80 or self.helper(board,i + 1)):
                return True
        board[i / 9] = board[i / 9][:(i % 9)] + ['.'] + board[i / 9][(i % 9 + 1):]
        return False
    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudoku(self, board):
        if not board or len(board) != 9 or len(board[0]) != 9:return False
        rows = [[False for var in range(9)] for var1 in range(9)]
        cols = [[False for var in range(9)] for var1 in range(9)]
        blocks = [[False for var in range(9)] for var1 in range(9)]
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    continue
                valueint = int(board[i][j]) - 1
                if rows[i][valueint] or cols[j][valueint] or blocks[i - i % 3 + j / 3][valueint]:
                    return False
                else:
                    rows[i][valueint] = cols[j][valueint] = blocks[i - i % 3 + j / 3][valueint] = True
        return True

但是这样做的后果是要解出一个数独通常要花5到10秒的时间—太久了,而且,这也不是我们一般的解决数独的方法,我们经常采用下面这些算法来解题:

唯一解法

当某行已填数字的宫格达到8个,那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为行唯一解。

唯余解法

唯余解法就是某宫格可以添入的数已经排除了8个,那么这个宫格的数字就只能添入那个没有出现的数字。

我们在进行猜测之前还会用一些其他的方法进行这些“预处理”,这些技巧并不总能帮助我们解出数独,但是却很有帮助。

一般的解题步骤

我们在做数独问题时,经常采用这样的方法:将某个格子的可能出现的数字(可以有很多歌)标在格子上,通过一些手段观察这些格子,从而确定某些格子的值,继而推导出其它格子的值。

推倒重来

无疑我们需要换一种思路,仅仅使用回溯是不够的。

首先,我们需要一个这样的·phthon数组:

possiblenumbers = [[[i for i in range(1,10)]for j in range(9) ]for k in range(9)]

这个数组是一个三维数组,它用来表示在每一个格子上的可能的数字,比如

possiblenumbers[0][0] = [1,2,3,4,5,6,7,8,9]表示数独坐标为(0,0)的格子的可能数字为1至9

同轴数

我们定义与一个数同行,同列,同格的数为这个数的同轴数,为了程序运行是快速地得到一个位置数字的同轴数,我们在预处理中完成这个工作。

我们定义一个python数组来分别存储同行,同列,同格的同轴数:

peercross = [[[[(j,i) for i in range(9)],[(i,k) for i in range(9)],[(j - j % 3 + i / 3,k - k % 3 + i % 3)for i in range(9)]] for k in range(9)]for j in range(9)]

这个数组分别存储了每个grid的同行,同列,同格的同轴数,比如,peercross[3][3]:

[

[(3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)],

[(0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3), (7, 3), (8, 3)],

[(3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)]

]

但是这个数据结构有时并不是非常实用,有时我们需要遍历一个grid的所有同轴数时,peercross数组并不能提供直接的遍历方法(由于其中有重复元素),所以我们设计了另一个数据结构peers:

peers = [[set(sum(peercross[j][k],[])) – set([(j,k)]) for k in range(9)] for j in range(9)]

peers 将所有同轴数一并存储,例如peers[3][3]就是这样的:

set([(7, 3), (3, 2), (1, 3), (5, 5), (3, 0), (5, 4), (3, 1), (8, 3), (3, 6), (6, 3), (4, 5), (2, 3), (4, 3), (3, 8), (3, 7), (0, 3), (3, 5), (3, 4), (4, 4), (5, 3)])

预处理

预处理的过程中,我们模仿大多数数独爱好者的解题方法,尽可能多的在格子上填充数字。预处理分为如下几步:

  1. 生成各格子的数据结构和相关存储同轴数的数组
    self.grids = [(i,j) for j in range(9) for i in range(9)]
    self.peercross = [[[[(j,i) for i in range(9)],[(i,k) for i in range(9)],[(j - j % 3 + i / 3,k - k % 3 + i % 3)for i in range(9)]] for k in range(9)]for j in range(9)]
    self.peers = [[set(sum(self.peercross[j][k],[])) - set([(j,k)]) for k in range(9)] for j in range(9)]
    
  2. 将题面数字填入格子中

  3. 依照唯一解法和唯余解法进行推理

其中,第二步和第三步其实并不应该分开,我们完全可以再讲数字填入格子的同时进行推理:

  1. 设每个格子的可能数字均为1~9

  2. 对于题面中的每一个数字,将其填进响应的格子,并且根据两个定理消去同轴的相应数字,当填入某一个格子的数字不在这个格子的可能数字范围中时,说明这个数独根本就没有可行解。

怎样消去一个可能的数字

如果是简单地消去一个可能的数字,那么这个过程会很简单,比如某个格子的所有可能数字是[1,2,3,4,5,6,7,8,9],呢么假如消去一个可能的数字8,那么很显然剩余的数字[1,2,3,4,5,6,7,9],这有并没有什么难度,可是不要忘记,我们在填入和消去数字的同时也在推理。

首选,我们应该考虑唯一解法,假如有这样一个格子,它可能的数字是[1,2],这是我们要是消去一个1,那么这个格子唯一可能的值就是2了,这时候,由于这个格子的值已经确定,我们就需要消去它所有同轴数中的2。

其次,我们需要考录唯余解法:当我们从[1,2]中消去一个2时,我们应该在这个数的同行,同列,和同大格中寻找是否存在一个格子,在这个格子的某一个轴中,仅有这个格子能够填下2,如果有这种格子存在,我们也需要将2填入。

经过上面的描述,我们可以很方便地看懂下面这几行代码:

    #@return whether elimatesuccess or not
    def eliminate(self,x,y,value,possiblenumbers):
        if value not in possiblenumbers[x][y]:
            return True
        if len(possiblenumbers[x][y]) == 1:
            return False
        possiblenumbers[x][y].remove(value)
        #stg1 策略一:唯一解法
        if len(possiblenumbers[x][y]) == 0 or len(possiblenumbers[x][y]) == 1 and  not all([self.eliminate(i,j,possiblenumbers[x][y][0],possiblenumbers) for (i,j) in self.peers[x][y] if (possiblenumbers[x][y][0]) in possiblenumbers[i][j]]):
             return False
        #stg2 策略2:唯余解法
        for k in self.peercross[x][y]:
            tem = [(i,j) for (i,j) in k if value in possiblenumbers[i][j]]
            if len(tem) == 1 and len(possiblenumbers[tem[0][0]][tem[0][1]]) > 1 and  not self.fill(tem[0][0],tem[0][1],value,possiblenumbers):
                return False
        return True

在预处理中究竟需要多少策略?

仅仅运用唯一解法和唯余解法已经能解出一些简单的数独题目,更多更高阶的策略能使在进行回溯遍历前确定的格子更多。但是,并没有证据显示在用回溯算法之前运用一些预处理策略能够提高多少回溯的效率,所以,在这里,我们认为这两种初等策略已经足够了。

填充一个数字

我们之所以将填充数字放在消去可能的数字之后是因为我们需要应用消去的的方法来填充数字,因为我们需要记住,我们之前假设过每一个格子一开始可能填入的数字是1到9,而设定一个格子的值无异于消去这个格子中所有其他可能的值:

def fill(self,x,y,value,possiblenumbers):
        if value not in range(1,10) and value not in "123456789":return True
        if int(value) not in possiblenumbers[x][y] or x not in range(9) or y not in range(9):return False
        if len(possiblenumbers[x][y]) == 1 or all([self.eliminate(x,y,i,possiblenumbers) for i in  [j for j in possiblenumbers[x][y] if j != int(value)]]):
            return True
        return False

到这里,我们终于可以写出预处理的代码了:

def preProcess(self,board,possiblenumbers):
        for i in range(81):
            if not self.fill(i / 9,i % 9,board[i / 9][i % 9],possiblenumbers):
                return False
        return True

很简单,是不是?

回溯的起点

预处理兵不解决数独,而仅仅只是能够填充一些未知的格子而已,然而我们的目的是填充出整个数独,这样的话我们不得不回到了那个原来的话题:回溯

但是从哪里开始回溯呢?我们的第一份代码是从第一个格子往下一路回溯,这样的回溯并没有什么技巧可言,我们需要精心挑选一些格子,这些格子的可能的数字的个数最少,从而我们蒙中的概率也就会更大,比如说,一个仅有两种可能取值的格子,我们蒙中的概率就有一半,而一个有三种可能取值的格子,我们蒙中的概率就仅仅有个三分之一而已。

在回溯的同时推理

回溯是一个不断在格子上蒙数字的过程,我们并不希望这个过程仅仅依靠猜想,而是有一部分推理的成分,怎样推理呢?我们在利用回溯法向一个不确定的格子中填入一个数字的时候,应该运用与预处理相同的方法,将填入的过程分解为排除每个其他可能数字的过程,也就是说,我们可以原封不动地照搬之前定义过的fill方法

多个解与没有解

一般来说,我们希望传入的数独至少有一个解,并且一旦我们找到一个解,其他的解就无关紧要,但是如果我们想进一步在这个程序的基础实现生成数独谜题的功能的话,判断一个数独书否有唯一解就是必须的了,所以我们的程序在搜索完全部解空间或者遇到两个不同的可行解之前并不能停止。

为了记录解,我们定义self.finalsolution 当他为False 是表示这个数独没有解,为True是表示数独有多个解,否则这个值为那个唯一的解。
说了这么多,其实递归求解的代码也没有多少:

def reSlove(self,possiblenumbers,deepth):
        if all(len(possiblenumbers[i][j]) == 1 for (i,j) in self.grids):
            if not self.finalsolution:
                self.finalsolution = copy.deepcopy(possiblenumbers)
            else:
                self.finalsolution = True
            return
        length,x,y = min((len(possiblenumbers[i][j]),i,j) for (i,j) in self.grids if len(possiblenumbers[i][j]) > 1)
        posibility = copy.copy(possiblenumbers[x][y])
        for i in posibility:
            copyindex = copy.deepcopy(possiblenumbers)
            if self.fill(x,y,i,copyindex) and self.finalsolution != True:
                self.reSlove(copyindex,deepth + 1)
        #print('deepth: %s ' %deepth)
        return

解数独所需要的所