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(object):
def validset(self ):
s=''
return set(s) def initTbl(self, tbl, board):
for i in range(9):
for j in range(9):
if board[i][j] == '.':
tbl[(i,j)]=[] def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
resultTbl={}
visited=[]
self.initTbl(resultTbl, board)
reuse=False
unvisited = resultTbl.keys()
unvisited.sort()
unvisited.reverse() while unvisited != []:
(x, y) = unvisited.pop()
if reuse==False:
resultTbl[(x,y)] = self.possibleValues((x,y), board)
if resultTbl[(x,y)] == None: # invalid sudoku
print False
break if len( resultTbl[(x,y)] ) == 0: # DEAD END, BACKTRACK
unvisited.append((x, y))
if visited != []:
reuse=True
prev=visited.pop()
unvisited.append(prev)
x=prev[0]
y=prev[1]
board[x][y]='.'
else:
break
continue
board[x][y]=resultTbl[(x,y)].pop()
visited.append((x,y))
reuse=False
for line in board:
if '.' in line:
print False def possibleValues(self, coord, board):
vals = {'.':0}
for i in range(1,10): #init
vals[str(i)]=0 for y in range(0,9):
node=board[coord[0]][y]
vals[node]+=1
if vals[node]>1 and node!='.': return None
for x in range(0,9):
node=board[x][coord[1]]
vals[node]+=1
if vals[node] > 2 and node!='.': return None
x = coord[0]/3*3
y = coord[1]/3*3
for i in range(x, x+3):
for j in range(y, y+3):
node=board[i][j]
vals[node]+=1
if vals[node]>3 and node!='.': return None
s = set()
for k in vals.keys():
if vals[k]>=1: s.add(k)
return self.validset() - s