Javascript data structures and algorithms

# 有效的数独（36）

# 题目

判断一个 9x9 的数独是否有效。

只需要根据以下规则，验证已经填入的数字是否有效即可。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 '.' 表示。

# 示例

输入:

[
  ["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"]
]
1
2
3
4
5
6
7
8
9
10
11

输出: true

输入:

[
  ["8","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"]
]
1
2
3
4
5
6
7
8
9
10
11

输出: false

解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

# 说明

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 给定数独序列只包含数字 1-9 和字符 '.' 。
  • 给定数独永远是 9x9 形式的。

# 算法

# 暴力法

分别判断行、列、3x3宫格内有没有重复数字出现，使用set来判断是否出现了重复的数字

export const isValidSudoku = (board) => {
  // 判断行
	for (let i = 0; i < 9; i++) {
		const set = new Set();
		for (let j = 0; j < 9; j++) {
			if (set.has(board[i][j])) {
				return false;
			} else if (board[i][j] !== ".") {
				set.add(board[i][j]);
			}
		}
  }
  // 判断列
	for (let i = 0; i < 9; i++) {
		const set = new Set();
		for (let j = 0; j < 9; j++) {
			if (set.has(board[j][i])) {
				return false;
			} else if (board[j][i] !== ".") {
				set.add(board[j][i]);
			}
		}
  }
  // 判断3x3宫格
	for (let row = 0; row < 7; row += 3) {
		for (let col = 0; col < 7; col += 3) {
			const set = new Set();
			for (let i = 0; i < 3; i++) {
				for (let j = 0; j < 3; j++) {
					if (set.has(board[i + row][j + col])) {
						return false;
					} else if (board[i + row][j + col] !== ".") {
						set.add(board[i + row][j + col]);
					}
				}
			}
		}
	}
	return true;
};
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

# 一次遍历

对于board[i][j]，使用i来标记该数字属于第i行，使用j来标记该数字属于第j列，使用Math.floor(i/3)*3 + Math.floor(j/3)来标记该数字属于第Math.floor(i/3)*3 + Math.floor(j/3)个宫格

// 宫格顺序，表示第几个宫格
[
  [0, 1, 2],
  [3, 4, 5],
  [6, 7, 8],
]
1
2
3
4
5
6

我们建立三个9*9的数组用来记录对应位置是否出现过数字（第一个下标表示行、列、宫格、第二个下标表示数字），默认填充0表示没有出现

然后我们一次遍历数独，根据对应的行、列、宫格来判断是否重复出现了该数字（因为使用下标来指代数字，所以每个遍历到的数字board[i][j]都需要-1），如果重复了则返回false

export const isValidSudoku = (board) => {
	const row = new Array(9);
	const col = new Array(9);
	const cell = new Array(9);
	for (let i = 0; i < 9; i++) {
		row[i] = new Array(9).fill(0);
		col[i] = new Array(9).fill(0);
		cell[i] = new Array(9).fill(0);
	}
	for (let i = 0; i < 9; i++) {
		for (let j = 0; j < 9; j++) {
			if (board[i][j] !== ".") {
				const number = board[i][j] - 1;
				if (row[i][number] !== 0) return false;
				else row[i][number] = 1;
				if (col[j][number] !== 0) return false;
				else col[j][number] = 1;
				if (cell[~~(i / 3) * 3 + ~~(j / 3)][number] !== 0) return false;
				else cell[~~(i / 3) * 3 + ~~(j / 3)][number] = 1;
			}
		}
	}
	return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

← 子集（78） →