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.
A sudoku puzzle…
This problem is M^9 complexity m is the number of empty slots.
we can use DFS to solve this problem with backtracking.
class Solution:# @param board, a 9×9 2D array# Solve the Sudoku by modifying the input board in-place.# Do not return any value.def check(self, x, y, board):tmp = board[x][y]board[x][y] = '.'for row in range(9):if board[row][y] == tmp:return Falsefor col in range(9):if board[x][col] == tmp:return Falsefor row in range(3):for col in range(3):if board[(x / 3) * 3 + row][(y / 3) * 3 + col] == tmp:return Falseboard[x][y] = tmpreturn Truedef dfs(self, board):for row in range(9):for col in range(9):if board[row][col] == '.':for char in '123456789':board[row][col] = charif self.check(row, col, board) and self.dfs(board):return Trueboard[row][col] = '.'return Falsereturn Truedef solveSudoku(self, board):self.dfs(board)
，背着背包的路上，看过许多人，
