Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:


       Each of the digits 1-9 must occur exactly once in each row.
       Each of the digits 1-9 must occur exactly once in each column.
       Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.


Empty cells are indicated by the character '.'.


A sudoku puzzle...


...and its solution numbers marked in red.

Note:


       The given board contain only digits 1-9 and the character '.'.
       You may assume that the given Sudoku puzzle will have a single unique solution.
       The given board size is always 9x9.

Difficulty: interview

Starter code:

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        

Solutions:
class Solution:
     def FindValid(self):
         a="123456789"
         d,val={},{}
         for i in range(9):
             for j in range(9):
                 temp=self.board[i][j]
                 if temp!='.':
                     d[("r",i)]=d.get(("r",i),[])+[temp]
                     d[("c",j)]=d.get(("c",j),[])+[temp]
                     d[(i//3,j//3)]=d.get((i//3,j//3),[])+[temp]
                 else:
                     val[(i,j)]=[]
         for (i,j) in list(val.keys()):
             invalid=d.get(("r",i),[])+d.get(("c",j),[])+d.get((i//3,j//3),[])
             val[(i,j)]=[ele for ele in a if  ele not in invalid]
         return val
     def CheckingSolution(self,ele,Pos,Updata):
         self.board[Pos[0]][Pos[1]]=ele
         del self.val[Pos]
         i,j=Pos
         for invalid in list(self.val.keys()):
             if ele in self.val[invalid]:
                 if invalid[0]==i or invalid[1]==j or (invalid[0]//3,invalid[1]//3)==(i//3,j//3):
                     Updata[invalid]=ele
                     self.val[invalid].remove(ele)
                     if len(self.val[invalid])==0:
                         return False
         return True
     def Sudo(self,Pos,Updata):
         self.board[Pos[0]][Pos[1]]="."
         for i in Updata:
             if i not in self.val:
                 self.val[i]=Updata[i]
             else:
                 self.val[i].append(Updata[i])
     def FindSolution(self):
         if len(self.val)==0:
             return True
         Pos=min(list(self.val.keys()),key=lambda x:len(self.val[x]))
         nums=self.val[Pos]
         for ele in nums:
             updata={Pos:self.val[Pos]}
             if self.CheckingSolution(ele,Pos,updata):
                 if self.FindSolution():
                     return True
             self.Sudo(Pos,updata)
         return False
 
     def solveSudoku(self, board):
         """
         :type board: List[List[str]]
         :rtype: void Do not return anything, modify board in-place instead.
         """
         self.board=board
         self.val=self.FindValid()
         self.FindSolution()


import random
 
 
 class Solution:
 
     def readSudoku(self, board):
         """
         :type board: List[List[str]]
         :rtype: bool
         """
         line = [set(['1', '2', '3', '4', '5', '6', '7', '8', '9']) for _ in range(9)]
         row = [set(['1', '2', '3', '4', '5', '6', '7', '8', '9']) for _ in range(9)]
         box = [set(['1', '2', '3', '4', '5', '6', '7', '8', '9']) for _ in range(9)]
         unfilled = []
         for x in range(9):
             for y in range(9):
                 data = board[x][y]
                 z = x // 3 + 3 * (y // 3)
                 if data != '.':
                     line[x].remove(data)
                     row[y].remove(data)
                     box[z].remove(data)
                 else:
                     unfilled.append((x, y))
         return line, row, box, unfilled
 
     def solveSudoku(self, board):
         """
         :type board: List[List[str]]
         :rtype: void Do not return anything, modify board in-place instead.
         """
         line, row, box, unfilled = self.readSudoku(board)
         possible = {}
         guess = {}
         i = 0
         while 0 <= i < len(unfilled):
             (x, y) = unfilled[i]
             z = x // 3 + 3 * (y // 3)
             if (x, y) not in possible:
                 possible[(x, y)] = line[x] & row[y] & box[z]
             if possible[(x, y)]:
                 guess[(x,y)] = random.choice(list(possible[(x, y)]))
                 board[x][y] = guess[(x,y)]
                 line[x].remove(guess[(x,y)])
                 row[y].remove(guess[(x,y)])
                 box[z].remove(guess[(x,y)])
                 i += 1
             else:
                 del possible[unfilled[i]]
                 i -= 1
                 (x, y) = unfilled[i]
                 z = x // 3 + 3 * (y // 3)
                 possible[(x, y)].remove(guess[(x,y)])
                 line[x].add(guess[(x,y)])
                 row[y].add(guess[(x,y)])
                 box[z].add(guess[(x,y)])

class Solution(object):
     def __init__(self):
         self.filled = []
 
     def solveSudoku(self, board):
         """
         :type board: List[List[str]]
         :rtype: void Do not return anything, modify board in-place instead.
         """
         pln = []
         for i in range(9):
             pln.append([])
             self.filled.append([])
             for j in range(9):
                 if board[i][j].isdigit():
                     self.filled[-1].append(True)
                     pln[i].append([])
                 else:
                     self.filled[-1].append(False)
                     pln[i].append([k for k in range(10)])
                     pln[i][-1].remove(0)
 
         for i in range(9):
             for j in range(9):
                 if board[i][j].isdigit():
                     self.updatePln(pln, int(board[i][j]), i, j)
 
         result = self.loopSolution(pln, board)
         return
     
     def updatePln(self, pln, temp, i, j):                    
         for k in range(9):
             a= pln[i][k]
             if temp in pln[i][k]: 
                 pln[i][k].remove(temp)
             if temp in pln[k][j]: 
                 pln[k][j].remove(temp)
             num = int(i/3)*3+int(j/3)
             if temp in pln[int(num/3)*3+int(k/3)][num%3*3+k%3]:
                 pln[int(num/3)*3+int(k/3)][num%3*3+k%3].remove(temp)
 
     def loopSolution(self, pln, board):
         while True:
             row, column, minSize = 10, 10, 10
             for i in range(9):
                 for j in range(9):
                     if not self.filled[i][j] and len(pln[i][j])==0: 
                         return False
                     if len(pln[i][j])>0 and len(pln[i][j])<minSize:
                         row, column = i, j
                         minSize = len(pln[i][j])
             if minSize == 10:
                 return True
             else:
                 for i in range(minSize):
                     self.filled[row][column] = True
                     temp_pln = []
                     for ele in pln:
                         temp_pln.append([])
                         for ele2 in ele:
                             temp_pln[-1].append(ele2[:])
                     self.updatePln(temp_pln, temp_pln[row][column][i], row, column)
                     temp_pln[row][column] = []
                     if self.loopSolution(temp_pln, board):
                         board[row][column] = str(pln[row][column][i])
                         return True
                     self.filled[row][column] = False
                 return False

# Solution! DFS
 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):
         res = self.dfs(board)
         # board = copy.copy(res)
         for n, row in enumerate(res):
             board[n] = row #''.join(row)
 
     def dfs(self, board):
         stack = [board]
         while stack:
             s = stack.pop()
             result = self.fill_board(s)
             if result == 'complete':
                 return s
             for r in result:
                 stack.append(r)
             
     def fill_board(self, board):
         digits = set('123456789')
         choice, best = {}, []
         for j in range(9):
             for i in range(9):
                 if board[j][i] == '.':
                     square = {board[j//3*3+y][i//3*3+x]
                               for y in range(3) for x in range(3)}
                     row = {board[j][x] for x in range(9)}
                     col = {board[y][i] for y in range(9)}
                     rest = digits.difference(square, row, col)
                     if len(rest) == 1:
                         board[j][i] = rest.pop()
                         return self.fill_board(board)
                     elif len(rest) == 0:
                         return ''
                     else:
                         choice[(j, i)] = rest
         if not choice:
             return 'complete'
         y, x = min(choice, key=lambda k: len(choice[k]))
         for n in choice[(y, x)]:
             b = copy.deepcopy(board)
             b[y][x] = n
             best.append(b)
         return best

class Solution:
     def reduceSingleOption(self, board, emptyGrid, valid):
         m = 1
         while m == 1:
             m = 10
             for k in range(len(emptyGrid) - 1, -1, -1):
                 i, j = emptyGrid[k]
                 option = set.intersection(valid[i],
                                           valid[j + 9],
                                           valid[(i // 3) * 3 + j // 3 + 18])
                 if not option:
                     return
                 if len(option) < m:
                     m = len(option)
                 if len(option) == 1:
                     option = option.pop()
                     board[i][j] = str(option)
                     emptyGrid.pop(k)
                     valid[i].remove(option)
                     valid[j + 9].remove(option)
                     valid[(i // 3) * 3 + j // 3 + 18].remove(option)
 
     def dfs(self, board, emptyGrid, valid, ans):
         if len(ans) == len(emptyGrid):
             return
         i, j = emptyGrid[len(ans)]
         options = set.intersection(valid[i],
                                    valid[j + 9],
                                    valid[(i // 3) * 3 + j // 3 + 18])
         if len(options) == 0:
             return
         else:
             for temp in options:
                 print(i, j, temp)
                 ans.append(temp)
                 valid[i].remove(temp)
                 valid[j + 9].remove(temp)
                 valid[(i // 3) * 3 + j // 3 + 18].remove(temp)
                 self.dfs(board, emptyGrid, valid, ans)
                 if len(ans) == len(emptyGrid):
                     break
                 temp = ans.pop()
                 valid[i].add(temp)
                 valid[j + 9].add(temp)
                 valid[(i // 3) * 3 + j // 3 + 18].add(temp)
 
 
     def solveSudoku(self, board):
         """
         :type board: List[List[str]]
         :rtype: void Do not return anything, modify board in-place instead.
         """
         valid = [set(range(1, 10)) for _ in range(27)]
         emptyGrid = []
         for i in range(9):
             for j in range(9):
                 c = board[i][j]
                 if c != '.':
                     n = int(c)
                     valid[i].remove(n)
                     valid[j + 9].remove(n)
                     valid[(i // 3) * 3 + j // 3 + 18].remove(n)
                 else:
                     emptyGrid.append((i, j))
         self.reduceSingleOption(board, emptyGrid, valid)
         ans = []
         self.dfs(board, emptyGrid, valid, ans)
         print(ans)
         for k in range(len(emptyGrid)):
             i, j = emptyGrid[k]
             board[i][j] = str(ans[k])

class Solution:
     full_values = set('123456789')
 
     def findValues(self, board, row, col):
         row_start = row // 3 * 3
         col_start = col // 3 * 3
         values = self.full_values - (set(board[row]) | {board[i][col] for i in range(9)} | \
                     {board[i][j] for i in range(row_start, row_start+3) for j in range(col_start, col_start+3)})
 
         return values
 
     def solver(self, board):
         
         done = True
         for row in board:
             if '.' in row:
                 done = False
         
         if done:
             return True
       
         row_num = len(board)
         col_num = len(board[0])
                 
         #candidate values of each pos
         candidates = [[0 for x in range(row_num)] for y in range(col_num)] 
         #number of candidates of each pos, key is num of candidates, values are list of (row, col)
         NumOfCandidatesDict = [[] for i in range(9)]
         
         for row in range(row_num):
             for col in range(col_num):
                 if board[row][col] == '.':
                     candidates[row][col] = self.findValues(board, row, col)
 
                     #Not able to solve it
                     if (len(candidates[row][col]) == 0):
                         return False
                     elif len(candidates[row][col]) == 1:
                         board[row][col] = candidates[row][col].pop()
                         ret = self.solver(board)
                         if ret:
                             return True
                         else:
                             board[row][col] = '.'
                             return False
                     else:
                         NumOfCandidatesDict[len(candidates[row][col])].append([row, col])
         
        
         for i in range(2, 10):
             if len(NumOfCandidatesDict[i]) > 0:
                 row, col = NumOfCandidatesDict[i][0]
 
                 for value in candidates[row][col]:
                     board[row][col] = value
                     if self.solver(board):
                         return True
                 board[row][col] = '.'
                 return False       
         
         return False
     
     def solveSudoku(self, board):
         """
         :type board: List[List[str]]
         :rtype: void Do not return anything, modify board in-place instead.
         """
         self.solver(board)

class Solution:
     def solveSudoku(self, board):
         """
         :type board: List[List[str]]
         :rtype: void Do not return anything, modify board in-place instead.
         """
         self.board = board
         self.val = self.PossibleValue()
         self.Solver()
     def PossibleValue(self):
         nums = "123456789"
         d,val={},{}
         for i in range(9):
             for j in range(9):
                 element = self.board[i][j]
                 if element!=".":
                     d[("r",i)]=d.get(("r",i),[])+[element]
                     d[("c",j)]=d.get(("c",j),[])+[element]
                     d[(i//3,j//3)]=d.get((i//3,j//3),[])+[element]
                 else:
                     val[(i,j)]=[]
         for (i,j) in val.keys():
             temp=d.get(("r",i),[])+d.get(("c",j),[])+d.get((i//3,j//3),[])
             val[(i,j)]=[x for x in nums if x not in temp]
         return val
     def Solver(self):
         if len(self.val)==0:
             return True
         kee = min(self.val.keys(),key=lambda x: len(self.val[x]))
         possible_nums = self.val[kee]
         #update = {}
         for n in possible_nums:
             update = {kee:self.val[kee]}
             if self.ValidOne(n,kee,update):
                 if self.Solver():
                     return True
             #self.val[kee]=possible_nums
             self.undo(kee,update)
         return False
     def ValidOne(self,n,kee,update):
         self.board[kee[0]][kee[1]]=n
         del self.val[kee]
         i,j = kee
         for index in self.val:
             if (i==index[0] or j==index[1] or (i//3,j//3)==(index[0]//3,index[1]//3)) and (n in self.val[index]):
                 update[index] = n
                 self.val[index].remove(n)
                 if len(self.val[index])==0:return False
         return True
     def undo(self,kee,update):
         self.board[kee[0]][kee[1]]="."
         for x in update:
             if x not in self.val:
                 self.val[x]= update[x]
             else:
                 self.val[x].append(update[x])
         return None