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.
Solution
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):
self.solveSudokuRec(board,0,0)
def solveSudokuRec(self, board,row,col):
if row == 9:
return True
if col == 8:
nextRow = row +1
nextCol = 0
else:
nextRow = row
nextCol = col+1
if board[row][col]!='.':
return self.solveSudokuRec(board,nextRow,nextCol)
for c in range(1,10):
if self.canPut(board,str(c),row,col):
board[row][col] = str(c)
if self.solveSudokuRec(board,nextRow,nextCol):
return True
board[row][col] = '.'
return False
def canPut(self, board, char, row, col):
for i in range(0,9):
if board[row][i] == char:
return False
if board[i][col] == char:
return False
rowGroup = (row//3) * 3
colGroup = (col//3) * 3
for i in range(rowGroup, rowGroup+3):
for j in range(colGroup, colGroup+3):
if board[i][j] == char:
return False
return True
No comments :
Post a Comment