[leetcode]Sudoku Solver @ Python

原题地址:https://oj.leetcode.com/problems/sudoku-solver/

题意:

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

Empty cells are indicated by the character ‘.‘.

You may assume that there will be only one unique solution.

[leetcode]Sudoku Solver @ Python

A sudoku puzzle...

 

[leetcode]Sudoku Solver @ Python

...and its solution numbers marked in red.

解题思路:使用dfs来解决问题。

代码:

[leetcode]Sudoku Solver @ 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):
        def isValid(x,y):
            tmp=board[x][y]; board[x][y]=D
            for i in range(9):
                if board[i][y]==tmp: return False
            for i in range(9):
                if board[x][i]==tmp: return False
            for i in range(3):
                for j in range(3):
                    if board[(x/3)*3+i][(y/3)*3+j]==tmp: return False
            board[x][y]=tmp
            return True
        def dfs(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j]==.:
                        for k in 123456789:
                            board[i][j]=k
                            if isValid(i,j) and dfs(board):
                                return True
                            board[i][j]=.
                        return False
            return True
        dfs(board)
[leetcode]Sudoku Solver @ Python

 

[leetcode]Sudoku Solver @ Python,布布扣,bubuko.com

[leetcode]Sudoku Solver @ Python

上一篇:我也来谈javascript高级编程之:javascript函数编译过程


下一篇:python中的编码问题:以ascii和unicode为主线