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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

Complete search

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):
		self.board = board
		self.val = self.FindValid()
		self.FindSolution()


class Solution(object):

	def __init__(self):
		self.filled = []

	def solveSudoku(self, board):
		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


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):
		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])
		candidates = [[0 for x in range(row_num)] for y in range(col_num)]
		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)
					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):
		self.solver(board)


class Solution:

	def solveSudoku(self, board):
		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]
		for n in possible_nums:
			update = {kee: self.val[kee]}
			if self.ValidOne(n, kee, update):
				if self.Solver():
					return True
			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