leedcode解析—Python3—Sudoku Solver—hard

  • Post author:
  • Post category:python



题目:


Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1.Each of the digits 1-9 must occur exactly once in each row.

2.Each of the digits 1-9 must occur exactly once in each column.

3.Each of the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid.

The ‘.’ character indicates empty cells.

Example 1:

Input: board = [[“5”,“3”,”.”,”.”,“7”,”.”,”.”,”.”,”.”],[“6”,”.”,”.”,“1”,“9”,“5”,”.”,”.”,”.”],[“.”,“9”,“8”,”.”,”.”,”.”,”.”,“6”,”.”],[“8”,”.”,”.”,”.”,“6”,”.”,”.”,”.”,“3”],[“4”,”.”,”.”,“8”,”.”,“3”,”.”,”.”,“1”],[“7”,”.”,”.”,”.”,“2”,”.”,”.”,”.”,“6”],[“.”,“6”,”.”,”.”,”.”,”.”,“2”,“8”,”.”],[“.”,”.”,”.”,“4”,“1”,“9”,”.”,”.”,“5”],[“.”,”.”,”.”,”.”,“8”,”.”,”.”,“7”,“9”]]

Output: [[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]]

Explanation: The input board is shown above and the only valid solution is shown below:


我的思路:


这道题其实就是写一个解数独的代码,但是我觉得是我刷leedcode以来遇到的最难的一题,花了我很久的时间(实际上95%的时间都在研究数独的高级解法,然而太抽象了,还是没能理解,并且高级解法的代码实现会非常复杂),因为首先要学会解数独,才能解决这道题。

我的代码采用的是主要是摒除法

cal()

,即数独某个空格的可能值用一个list来表示,这个list中的可能数字为[‘1’,‘2’,‘3’,‘4’,‘5’,‘6’,‘7’,‘8’,‘9’]去掉所在行已经确定的值,所在列已经确定的值,和所在宫(3X3)已经确定的值,空格list的生成由

function cal1()

表示,

board[i][j] = cal1(i,j)

,假如list中只包含一个值,那么这个空格的值就可以是确定的,可以直接返回该值,并且此时由于确定的值多了一个,可以对前面生成的list进行简化,所以从头开始运行一次

cal()



if type(board[i][j]) == str: return cal()

;每一行,每一列,每一宫算完之后,整合所有的list,在这些list中,如果一个值只出现在一个list中,那该list可以简化为该值,每当多一个确定的值,从头开始运行一次

cal()



到此,大部分的简单难度的数独都是可以解出来的,复杂数独此时也被简化到最简值,后面可以直接采用暴力试错法,直接对空格的list进行遍历,通过

function valid()

判断答案是否有效,当出现有效答案时,可以直接结束循环,获得正确答案。

由于这一题提交的是原始数独的链接,而不是return的值,所以最后一部分的代码用了两个for循环来复制数独,在leedcode中,为了体现题目所蕴含的算法,我一般不采用较为方便和复杂的内置方法来解题,并且做完的时候真的不想回头再优化代码,所以我的答案一般都会有点啰嗦,但是运行速度和占用的内存还算满意。

Runtime: 96 ms, faster than 91.85% of Python3 online submissions for Sudoku Solver.

Memory Usage: 14.3 MB, less than 72.29% of Python3 online submissions for Sudoku Solver.


我的解答:

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def cal1(x,y):
            n1 = ['1','2','3','4','5','6','7','8','9']
            x1 = 3 * (x//3)
            y1 = 3 * (y//3)
            b2 = [board[x1][y1], board[x1 +1][y1], board[x1 +2][y1], board[x1][y1 +1], board[x1 +1][y1 +1], board[x1 +2][y1 +1], board[x1][y1 +2], board[x1 +1][y1 +2], board[x1 +2][y1 +2]]
            for i in range(9):
                if board[x][i] != '.' and type(board[x][i]) == str:
                    if board[x][i] in n1:
                        n1.remove(board[x][i])
                if board[i][y] != '.' and type(board[i][y]) == str: 
                    if board[i][y] in n1:
                        n1.remove(board[i][y])
            for j in b2:
                if j != '.' and type(j) == str:
                    if j in n1:
                        n1.remove(j)
                
            if len(n1) == 1:
                return n1[0]
            else:
                return n1
            
        def cal():    
            for i in range(9):
                a = []               
                for j in range(9):
                    b = []
                    c = []
                    if board[i][j] == '.' or type(board[i][j]) == list:
                        board[i][j] = cal1(i,j)
                        if type(board[i][j]) == str:                            
                            return cal()
                    # while turn to the bottom and right side of 3x3, recalculate the lists of the 3X3    
                    if i%3 == 2 and j%3 == 2:
                        for i1 in range(9):
                            x2 = 3*(i//3)
                            y2 = 3*(j//3)
                            if type(board[x2+i1//3][y2+i1%3]) == list:
                                b += board[x2+i1//3][y2+i1%3]
                        
                        for i2 in range(9):
                            if type(board[x2+i2//3][y2+i2%3]) == list:
                                for m2 in board[x2+i2//3][y2+i2%3]:
                                    b2 = b[:]
                                    b2.remove(m2)
                                    if m2 not in b2:
                                        board[x2+i2//3][y2+i2%3] = m2
                                        return cal()
            
                    # while turn to the bottom side, recalculate the lists of the column 
                    if i == 8:
                        for j1 in range(9):
                            if type(board[j1][j]) == list:
                                c += board[j1][j]
                        for j2 in range(9):
                            if type(board[j2][j]) == list:
                                for m3 in board[j2][j]:
                                    c2 = c[:]
                                    c2.remove(m3)
                                    if m3 not in c2:
                                        board[j2][j] = m3
                                        return cal()
                    
                # while turn to the right side, recalculate the lists of the line            
                for k in range(9):
                    if type(board[i][k]) == list:
                        a += board[i][k]
 
                for l in range(9):                        
                    if type(board[i][l]) == list:
                        for m in board[i][l]:
                            a2 = a[:]
                            a2.remove(m)
                            if m not in a2:
                                board[i][l] = m
                                return cal()
        
        def valid():
            for i in range(9):
                for j in range(9):
                    if type(board[i][j]) == list:
                        return False               
            return True 
        
        cal()
        b2 = copy.deepcopy(board)
        v = False
        for nu1 in range(9):
            for nu2 in range(9):
                if type(b2[nu1][nu2]) == list:
                    for nu3 in b2[nu1][nu2]: 
                        for i in range(9):
                            for j in range(9):
                                board[i][j] = b2[i][j]                       
                        board[nu1][nu2] = nu3
                        cal()
                        if valid():
                            v = True
                            break
                if v:
                    break
            if v:
                break



版权声明:本文为weiwei_wan原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。