# 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…
…and its solution numbers marked in red.
class Solution():
def solveSudoku(self, board):
def solver(board):
for i in range(9):
for j in range(9):
if board[i][j] == ".":
for k in range(1, 10):
board[i][j] = str(k)
if isValid(board, i, j) and solver(board):
return True
board[i][j] = "."
return False
return True
def isValid(board, x, y):
for i in range(9):
if (i != x and board[i][y] == board[x][y]) or (i != y and board[x][i] == board[x][y]):
return False
for i in range((x//3)*3, (x//3)*3+3):
for j in range((y//3)*3, (y//3)*3+3):
if (i != x or j != y) and board[i][j] == board[x][y]:
return False
return True
solver(board)
if __name__ == '__main__':
board = [[".",".","9","7","4","8",".",".","."],
["7",".",".",".",".",".",".",".","."],
[".","2",".","1",".","9",".",".","."],
[".",".","7",".",".",".","2","4","."],
[".","6","4",".","1",".","5","9","."],
[".","9","8",".",".",".","3",".","."],
[".",".",".","8",".","3",".","2","."],
[".",".",".",".",".",".",".",".","6"],
[".",".",".","2","7","5","9",".","."]]
Solution().solveSudoku(board)
assert board == [["5","1","9","7","4","8","6","3","2"],
["7","8","3","6","5","2","4","1","9"],
["4","2","6","1","3","9","8","7","5"],
["3","5","7","9","8","6","2","4","1"],
["2","6","4","3","1","7","5","9","8"],
["1","9","8","5","2","4","3","6","7"],
["9","7","5","8","6","3","1","2","4"],
["8","3","2","4","9","1","7","5","6"],
["6","4","1","2","7","5","9","8","3"]]