# Easy to understand - Text Book solution - Algorithm Design Manual :-)

• Nothing fancy - no bitsets, no claim of 0ms etc. But sticking to the basics of backtracking and other tricks given in Algorithm Design Manual. The code is my own implemented in python but complies Skiena's backtracking template -

``````class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""

def possible_values(board, m, n, row, col):
# get possible value for given cell
candidates = {str(x) for x in range(1, 10)}
for j in range(n):
if board[row][j] in candidates:
candidates.remove(board[row][j])

for i in range(m):
if board[i][col] in candidates:
candidates.remove(board[i][col])

top, left = (m // 3 * (row // 3), n // 3 * (col // 3))
for i in range(top, top + 3):
for j in range(left, left + 3):
if board[i][j] in candidates:
candidates.remove(board[i][j])
return candidates

def get_most_constrained(board, m, n):
most_constrained_possible = {}
maxlen = float('inf')
most_constrained = (None, None)
for i in range(m):
for j in range(n):
if board[i][j] == '.':
ijpossible = possible_values(board, m, n, i, j)
if len(ijpossible) < maxlen:
maxlen = len(ijpossible)
most_constrained_possible = ijpossible
most_constrained = (i, j)
# if maxlen is zero solution is not possible
return most_constrained, most_constrained_possible

def make_move(board, i, j, value):
board[i][j] = value

def unmake_move(board, i, j):
board[i][j] = '.'

if board:
self.finished = False
xboard = list(map(list, board))
m = len(xboard)    # expected 9
n = len(xboard[0]) # expected 9
open_cells = len([(i, j) for i in range(m) for j in range(n) if board[i][j] == '.'])

def is_solution(open_cells):
return open_cells == 0

def process_solution():
self.finished = True

def construct_candidates(xboard, m, n):
return get_most_constrained(xboard, m, n)

def backtrack(xboard, m, n, open_cells):
if is_solution(open_cells):
process_solution()
else:
(x, y), candidates = construct_candidates(xboard, m, n)
open_cells -= 1
for candidate in candidates:
make_move(xboard, x, y, candidate)
backtrack(xboard, m, n, open_cells)
if self.finished == True:
break
unmake_move(xboard, x, y)
open_cells += 1

backtrack(xboard, m, n, open_cells)
for i,row in enumerate(xboard):
board[i] = ''.join(row)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.