上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.1 MB, 提交时间: 2022-12-04 18:15:29
class Solution {
private int[] line = new int[9];
private int[] column = new int[9];
private int[][] block = new int[3][3];
private boolean valid = false;
private List<int[]> spaces = new ArrayList<int[]>();
public void solveSudoku(char[][] board) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] != '.') {
int digit = board[i][j] - '0' - 1;
flip(i, j, digit);
}
}
}
while (true) {
boolean modified = false;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
if ((mask & (mask - 1)) == 0) {
int digit = Integer.bitCount(mask - 1);
flip(i, j, digit);
board[i][j] = (char) (digit + '0' + 1);
modified = true;
}
}
}
}
if (!modified) {
break;
}
}
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
spaces.add(new int[]{i, j});
}
}
}
dfs(board, 0);
}
public void dfs(char[][] board, int pos) {
if (pos == spaces.size()) {
valid = true;
return;
}
int[] space = spaces.get(pos);
int i = space[0], j = space[1];
int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
for (; mask != 0 && !valid; mask &= (mask - 1)) {
int digitMask = mask & (-mask);
int digit = Integer.bitCount(digitMask - 1);
flip(i, j, digit);
board[i][j] = (char) (digit + '0' + 1);
dfs(board, pos + 1);
flip(i, j, digit);
}
}
public void flip(int i, int j, int digit) {
line[i] ^= (1 << digit);
column[j] ^= (1 << digit);
block[i / 3][j / 3] ^= (1 << digit);
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-04 18:15:13
func solveSudoku(board [][]byte) {
var line, column [9]int
var block [3][3]int
var spaces [][2]int
flip := func(i, j int, digit byte) {
line[i] ^= 1 << digit
column[j] ^= 1 << digit
block[i/3][j/3] ^= 1 << digit
}
for i, row := range board {
for j, b := range row {
if b != '.' {
digit := b - '1'
flip(i, j, digit)
}
}
}
for {
modified := false
for i, row := range board {
for j, b := range row {
if b != '.' {
continue
}
mask := 0x1ff &^ uint(line[i]|column[j]|block[i/3][j/3])
if mask&(mask-1) == 0 { // mask 的二进制表示仅有一个 1
digit := byte(bits.TrailingZeros(mask))
flip(i, j, digit)
board[i][j] = digit + '1'
modified = true
}
}
}
if !modified {
break
}
}
for i, row := range board {
for j, b := range row {
if b == '.' {
spaces = append(spaces, [2]int{i, j})
}
}
}
var dfs func(int) bool
dfs = func(pos int) bool {
if pos == len(spaces) {
return true
}
i, j := spaces[pos][0], spaces[pos][1]
mask := 0x1ff &^ uint(line[i]|column[j]|block[i/3][j/3]) // 0x1ff 即二进制的 9 个 1
for ; mask > 0; mask &= mask - 1 { // 最右侧的 1 置为 0
digit := byte(bits.TrailingZeros(mask))
flip(i, j, digit)
board[i][j] = digit + '1'
if dfs(pos + 1) {
return true
}
flip(i, j, digit)
}
return false
}
dfs(0)
}
python3 解法, 执行用时: 52 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-04 18:14:57
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def flip(i: int, j: int, digit: int):
line[i] ^= (1 << digit)
column[j] ^= (1 << digit)
block[i // 3][j // 3] ^= (1 << digit)
def dfs(pos: int):
nonlocal valid
if pos == len(spaces):
valid = True
return
i, j = spaces[pos]
mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
while mask:
digitMask = mask & (-mask)
digit = bin(digitMask).count("0") - 1
flip(i, j, digit)
board[i][j] = str(digit + 1)
dfs(pos + 1)
flip(i, j, digit)
mask &= (mask - 1)
if valid:
return
line = [0] * 9
column = [0] * 9
block = [[0] * 3 for _ in range(3)]
valid = False
spaces = list()
for i in range(9):
for j in range(9):
if board[i][j] != ".":
digit = int(board[i][j]) - 1
flip(i, j, digit)
while True:
modified = False
for i in range(9):
for j in range(9):
if board[i][j] == ".":
mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
if not (mask & (mask - 1)):
digit = bin(mask).count("0") - 1
flip(i, j, digit)
board[i][j] = str(digit + 1)
modified = True
if not modified:
break
for i in range(9):
for j in range(9):
if board[i][j] == ".":
spaces.append((i, j))
dfs(0)
python3 解法, 执行用时: 100 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-04 18:14:41
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def flip(i: int, j: int, digit: int):
line[i] ^= (1 << digit)
column[j] ^= (1 << digit)
block[i // 3][j // 3] ^= (1 << digit)
def dfs(pos: int):
nonlocal valid
if pos == len(spaces):
valid = True
return
i, j = spaces[pos]
mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
while mask:
digitMask = mask & (-mask)
digit = bin(digitMask).count("0") - 1
flip(i, j, digit)
board[i][j] = str(digit + 1)
dfs(pos + 1)
flip(i, j, digit)
mask &= (mask - 1)
if valid:
return
line = [0] * 9
column = [0] * 9
block = [[0] * 3 for _ in range(3)]
valid = False
spaces = list()
for i in range(9):
for j in range(9):
if board[i][j] == ".":
spaces.append((i, j))
else:
digit = int(board[i][j]) - 1
flip(i, j, digit)
dfs(0)
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-04 18:14:26
func solveSudoku(board [][]byte) {
var line, column [9]int
var block [3][3]int
var spaces [][2]int
flip := func(i, j int, digit byte) {
line[i] ^= 1 << digit
column[j] ^= 1 << digit
block[i/3][j/3] ^= 1 << digit
}
for i, row := range board {
for j, b := range row {
if b == '.' {
spaces = append(spaces, [2]int{i, j})
} else {
digit := b - '1'
flip(i, j, digit)
}
}
}
var dfs func(int) bool
dfs = func(pos int) bool {
if pos == len(spaces) {
return true
}
i, j := spaces[pos][0], spaces[pos][1]
mask := 0x1ff &^ uint(line[i]|column[j]|block[i/3][j/3]) // 0x1ff 即二进制的 9 个 1
for ; mask > 0; mask &= mask - 1 { // 最右侧的 1 置为 0
digit := byte(bits.TrailingZeros(mask))
flip(i, j, digit)
board[i][j] = digit + '1'
if dfs(pos + 1) {
return true
}
flip(i, j, digit)
}
return false
}
dfs(0)
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.2 MB, 提交时间: 2022-12-04 18:14:03
class Solution {
private int[] line = new int[9];
private int[] column = new int[9];
private int[][] block = new int[3][3];
private boolean valid = false;
private List<int[]> spaces = new ArrayList<int[]>();
public void solveSudoku(char[][] board) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
spaces.add(new int[]{i, j});
} else {
int digit = board[i][j] - '0' - 1;
flip(i, j, digit);
}
}
}
dfs(board, 0);
}
public void dfs(char[][] board, int pos) {
if (pos == spaces.size()) {
valid = true;
return;
}
int[] space = spaces.get(pos);
int i = space[0], j = space[1];
int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
for (; mask != 0 && !valid; mask &= (mask - 1)) {
int digitMask = mask & (-mask);
int digit = Integer.bitCount(digitMask - 1);
flip(i, j, digit);
board[i][j] = (char) (digit + '0' + 1);
dfs(board, pos + 1);
flip(i, j, digit);
}
}
public void flip(int i, int j, int digit) {
line[i] ^= (1 << digit);
column[j] ^= (1 << digit);
block[i / 3][j / 3] ^= (1 << digit);
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 39.2 MB, 提交时间: 2022-12-04 18:13:43
class Solution {
private boolean[][] line = new boolean[9][9];
private boolean[][] column = new boolean[9][9];
private boolean[][][] block = new boolean[3][3][9];
private boolean valid = false;
private List<int[]> spaces = new ArrayList<int[]>();
public void solveSudoku(char[][] board) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
spaces.add(new int[]{i, j});
} else {
int digit = board[i][j] - '0' - 1;
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
}
}
}
dfs(board, 0);
}
public void dfs(char[][] board, int pos) {
if (pos == spaces.size()) {
valid = true;
return;
}
int[] space = spaces.get(pos);
int i = space[0], j = space[1];
for (int digit = 0; digit < 9 && !valid; ++digit) {
if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
board[i][j] = (char) (digit + '0' + 1);
dfs(board, pos + 1);
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
}
}
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-04 18:13:14
func solveSudoku(board [][]byte) {
var line, column [9][9]bool
var block [3][3][9]bool
var spaces [][2]int
for i, row := range board {
for j, b := range row {
if b == '.' {
spaces = append(spaces, [2]int{i, j})
} else {
digit := b - '1'
line[i][digit] = true
column[j][digit] = true
block[i/3][j/3][digit] = true
}
}
}
var dfs func(int) bool
dfs = func(pos int) bool {
if pos == len(spaces) {
return true
}
i, j := spaces[pos][0], spaces[pos][1]
for digit := byte(0); digit < 9; digit++ {
if !line[i][digit] && !column[j][digit] && !block[i/3][j/3][digit] {
line[i][digit] = true
column[j][digit] = true
block[i/3][j/3][digit] = true
board[i][j] = digit + '1'
if dfs(pos + 1) {
return true
}
line[i][digit] = false
column[j][digit] = false
block[i/3][j/3][digit] = false
}
}
return false
}
dfs(0)
}
python3 解法, 执行用时: 132 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-04 18:12:55
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def dfs(pos: int):
nonlocal valid
if pos == len(spaces):
valid = True
return
i, j = spaces[pos]
for digit in range(9):
if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:
line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
board[i][j] = str(digit + 1)
dfs(pos + 1)
line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False
if valid:
return
line = [[False] * 9 for _ in range(9)]
column = [[False] * 9 for _ in range(9)]
block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
valid = False
spaces = list()
for i in range(9):
for j in range(9):
if board[i][j] == ".":
spaces.append((i, j))
else:
digit = int(board[i][j]) - 1
line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
dfs(0)
