KK's blog

每天积累多一些

0%

LeetCode 037 Sudoku Solver

Posted on Disqus:

LeetCode

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: 1. Each of the digits 1-9 must occur exactly once in each row. 2. Each of the digits 1-9 must occur exactly once in each column. 3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. Example 1: 

Input: board = [[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
Output: [[“5”,”3”,”4”,”6”,”7”,”8”,”9”,”1”,”2”],[“6”,”7”,”2”,”1”,”9”,”5”,”3”,”4”,”8”],[“1”,”9”,”8”,”3”,”4”,”2”,”5”,”6”,”7”],[“8”,”5”,”9”,”7”,”6”,”1”,”4”,”2”,”3”],[“4”,”2”,”6”,”8”,”5”,”3”,”7”,”9”,”1”],[“7”,”1”,”3”,”9”,”2”,”4”,”8”,”5”,”6”],[“9”,”6”,”1”,”5”,”3”,”7”,”2”,”8”,”4”],[“2”,”8”,”7”,”4”,”1”,”9”,”6”,”3”,”5”],[“3”,”4”,”5”,”2”,”8”,”6”,”1”,”7”,”9”]]
Explanation: The input board is shown above and the only valid solution is shown below:




Constraints: board.length == 9 board[i].length == 9 board[i][j] is a digit or '.'. It is guaranteed that the input board has only one solution.

题目大意：

日本游戏。需要保证每行每列每个9个方块的数是1-9里唯一。

Global dict解题思路(推荐)：

DFS。利用DFS模板

解题步骤：

N/A

注意事项：

  1. 用三种全局性dict(row, col, box)来记录所有已填的数，方便dfs时候迅速判断是否合法。这是比算法II优胜的地方。Python中不存在list of set只能用list of dict： [collections.defaultdict(int) for _ in range(len(board))]
  2. 初始化要将棋局上所有已有的数加入到dict中。一开始是dfs时候才加，但这样填的数不知道后面的格是否已经存在。题意保证有解，所以这些数不需验证重复。
  3. for循环是1-9是数字但棋盘是字符，所以要字符和数字转化，选择统一转成数字，不转的话dict会实效。
  4. box_dict的id转换： i // 3 * 3 + j // 3
  5. 终止条件为start_x == len(board) - 1 and start_y == len(board[0])

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def solveSudoku(self, board: List[List[str]]) -> None:
	row_dict = [collections.defaultdict(int) for _ in range(len(board))] # remember
	col_dict = [collections.defaultdict(int) for _ in range(len(board))]
	box_dict = [collections.defaultdict(int) for _ in range(len(board))]

	for i in range(len(board)):
		for j in range(len(board[0])):
			if board[i][j] != '.':
				self.add_to_dict(board, i, j, row_dict, col_dict, box_dict) # rememeber
	return self.dfs(board, 0, 0, row_dict, col_dict, box_dict)

def dfs(self, board, start_x, start_y, row_dict, col_dict, box_dict):
	if start_x == len(board) - 1 and start_y == len(board[0]):
		return True
	if start_y == len(board[0]):
		start_x += 1
		start_y = 0
	if board[start_x][start_y] != '.':
		return self.dfs(board, start_x, start_y + 1, row_dict, col_dict, box_dict) # guarantee solution
	for k in range(1, 10):
		if not self.is_valid(board, k, start_x, start_y, row_dict, col_dict, box_dict):
			continue
		board[start_x][start_y] = str(k)
		self.add_to_dict(board, start_x, start_y, row_dict, col_dict, box_dict)
		if self.dfs(board, start_x, start_y + 1, row_dict, col_dict, box_dict):
			return True
		self.remove_from_dict(board, start_x, start_y, row_dict, col_dict, box_dict)
		board[start_x][start_y] = '.'
	return False

def add_to_dict(self, board, i, j, row_dict, col_dict, box_dict):
	row_dict[i][int(board[i][j])] = 1 # remember
	col_dict[j][int(board[i][j])] = 1
	box_dict[i // 3 * 3 + j // 3][int(board[i][j])] = 1

def remove_from_dict(self, board, i, j, row_dict, col_dict, box_dict):
	row_dict[i].pop(int(board[i][j]))
	col_dict[j].pop(int(board[i][j]))
	box_dict[i // 3 * 3 + j // 3].pop(int(board[i][j]))

def is_valid(self, board, k, i, j, row_dict, col_dict, box_dict):
	if k in row_dict[i] or k in col_dict[j] or k in box_dict[i // 3 * 3 + j // 3]: # remember
		return False
	return True

算法分析：

三重循环，时间复杂度为O(9n*n)，空间复杂度O(n)，n为边长

常量空间算法II解题思路：

我一开始的方法，每填一位就验证。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def solveSudoku2(self, board: List[List[str]]) -> None:
	return self.dfs2(board, 0, 0)

def dfs2(self, board, start_x, start_y):
	if start_x == len(board) - 1 and start_y == len(board[0]):
		return True
	if start_y == len(board[0]):
		start_x += 1
		start_y = 0
	if board[start_x][start_y] != '.':
		return self.dfs2(board, start_x, start_y + 1) # guarantee solution
		'''
		if self.is_sudoku(board, start_x, start_y):
			return self.dfs(board, start_x, start_y + 1)
		else:
			return False
		'''
	for k in range(1, 10):
		board[start_x][start_y] = str(k)
		if self.is_sudoku2(board, start_x, start_y) and self.dfs2(board, start_x, start_y + 1):
			return True
		board[start_x][start_y] = '.'
	return False

def is_sudoku2(self, board, x, y):
	# row, # col, # square
	if self.is_valid(board, x, 0, x, len(board[0]) - 1) and self.is_valid(board, 0, y, len(board) - 1, y) and \
			self.is_valid(board, x // 3 * 3, y // 3 * 3, x // 3 * 3 + 2, y // 3 * 3 + 2):
		return True
	else:
		return False

def is_valid(self, board, start_x, start_y, end_x, end_y):
	num_set = set()
	for i in range(start_x, end_x + 1):
		for j in range(start_y, end_y + 1):
			val = board[i][j]
			if val == '.':
				continue
			if int(val) in num_set:
				return False
			num_set.add(int(val))
	return True

算法分析：

三重循环，时间复杂度为O(81n*n)，空间复杂度O(1)，n为边长

Free mock interview