力扣00037.解数独

发表于 分类于 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 10 分钟
解数独、数组、哈希表、回溯、矩阵、困难

题目描述

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
    数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1：

输入：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”]]
输出：[
[“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”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 ‘.’
  • 题目数据 保证 输入数独仅有一个解

解决方法

C++

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
class Solution {
public:
    void solveSudoku(std::vector<std::vector<char>>& board) {
        solve(board);
    }
private:
    bool solve(std::vector<std::vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (char num = '1'; num <= '9'; ++num) {
                        if (isValid(board, i, j, num)) {
                            board[i][j] = num;
                            if (solve(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    bool isValid(const std::vector<std::vector<char>>& board, int row, int col, char num) {
        for (int i = 0; i < 9; ++i) {
            if (board[row][i] == num || board[i][col] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
                return false;
            }
        }
        return true;
    }
};

结果

执行用时 : 11 ms, 击败 67.22% 使用 C++ 的用户

内存消耗 : 7.55 MB, 击败 20.50% 使用 C++ 的用户

Java

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
public class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (char num = '1'; num <= '9'; ++num) {
                        if (isValid(board, i, j, num)) {
                            board[i][j] = num;
                            if (solve(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; ++i) {
            if (board[row][i] == num || board[i][col] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
                return false;
            }
        }
        return true;
    }
}

结果

执行用时 : 10 ms, 击败 14.01% 使用 Java 的用户

内存消耗 : 40.18 MB, 击败 12.93% 使用 Java 的用户

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
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.solve(board)
    def solve(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in map(str, range(1, 10)):
                        if self.is_valid(board, i, j, num):
                            board[i][j] = num
                            if self.solve(board):
                                return True
                            board[i][j] = '.'
                    return False
        return True
    def is_valid(self, board, row, col, num):
        if num in board[row]:
            return False
        if num in [board[i][col] for i in range(9)]:
            return False
        start_row, start_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(3):
            for j in range(3):
                if board[start_row + i][start_col + j] == num:
                    return False
        return True

结果

执行用时 : 388 ms, 击败 59.52% 使用 Python 的用户

内存消耗 : 11.52 MB, 击败 95.24% 使用 Python 的用户

Python3

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
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.solve(board)
    def solve(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in map(str, range(1, 10)):
                        if self.is_valid(board, i, j, num):
                            board[i][j] = num
                            if self.solve(board):
                                return True
                            board[i][j] = '.'
                    return False
        return True
    def is_valid(self, board, row, col, num):
        if num in board[row]:
            return False
        if num in [board[i][col] for i in range(9)]:
            return False
        start_row, start_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(3):
            for j in range(3):
                if board[start_row + i][start_col + j] == num:
                    return False
        return True

结果

执行用时 : 325 ms, 击败 42.81% 使用 Python3 的用户

内存消耗 : 16.38 MB, 击败 40.06% 使用 Python3 的用户

C

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
void solveSudoku(char** board, int boardSize, int* boardColSize) {
    solve(board, boardSize, boardColSize);
}
int isValid(char** board, int row, int col, char num, int boardSize) {
    for (int i = 0; i < boardSize; ++i) {
        if (board[row][i] == num || board[i][col] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
            return 0;
        }
    }
    return 1;
}
int solve(char** board, int boardSize, int* boardColSize) {
    for (int i = 0; i < boardSize; ++i) {
        for (int j = 0; j < *boardColSize; ++j) {
            if (board[i][j] == '.') {
                for (char num = '1'; num <= '9'; ++num) {
                    if (isValid(board, i, j, num, boardSize)) {
                        board[i][j] = num;
                        if (solve(board, boardSize, boardColSize)) {
                            return 1;
                        }
                        board[i][j] = '.';
                    }
                }
                return 0;
            }
        }
    }
    return 1;
}

结果

执行用时 : 19 ms, 击败 6.45% 使用 C 的用户

内存消耗 : 5.71 MB, 击败 86.69% 使用 C 的用户

C#

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
public class Solution {
    public void SolveSudoku(char[][] board) {
        Solve(board);
    }
    private bool Solve(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (char num = '1'; num <= '9'; ++num) {
                        if (IsValid(board, i, j, num)) {
                            board[i][j] = num;
                            if (Solve(board)) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    private bool IsValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; ++i) {
            if (board[row][i] == num || board[i][col] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
                return false;
            }
        }
        return true;
    }
}

结果

执行用时 : 128 ms, 击败 88.89% 使用 C# 的用户

内存消耗 : 46.63 MB, 击败 15.87% 使用 C# 的用户

JavaScript

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
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
const solveSudoku = (board) => {
    const hasConflit = (r, c, val) => {
        for (let i = 0; i < 9; i++) {
            if (board[i][c] == val || board[r][i] == val) {
                return true;
            }
        }
        const subRowStart = Math.floor(r / 3) * 3;
        const subColStart = Math.floor(c / 3) * 3;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (val == board[subRowStart + i][subColStart + j]) {
                    return true;
                }
            }
        }
        return false;
    };
    const fill = (i, j) => {
        if (j == 9) {
            i++;
            j = 0;
            if (i == 9) return true;
        }
        if (board[i][j] != ".") return fill(i, j + 1);
        for (let num = 1; num <= 9; num++) {
            if (hasConflit(i, j, String(num))) continue;
            board[i][j] = String(num);
            if (fill(i, j + 1)) return true;
            board[i][j] = ".";
        }
        return false;
    };
    fill(0, 0);
    return board;
};

结果

执行用时 : 78 ms, 击败 84.59% 使用 JavaScript 的用户

内存消耗 : 50.79 MB, 击败 15.41% 使用 JavaScript 的用户

TypeScript

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
/**
 Do not return anything, modify board in-place instead.
 */
function solveSudoku(board: string[][]): void {
    const hasConflit = (r: number, c: number, val: string): boolean => {
        for (let i = 0; i < 9; i++) {
            if (board[i][c] === val || board[r][i] === val) {
                return true;
            }
        }
        const subRowStart = Math.floor(r / 3) * 3;
        const subColStart = Math.floor(c / 3) * 3;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (val === board[subRowStart + i][subColStart + j]) {
                    return true;
                }
            }
        }
        return false;
    };
    const fill = (i: number, j: number): boolean => {
        if (j === 9) {
            i++;
            j = 0;
            if (i === 9) return true;
        }
        if (board[i][j] !== ".") return fill(i, j + 1);
        for (let num = 1; num <= 9; num++) {
            const strNum = String(num);
            if (!hasConflit(i, j, strNum)) {
                board[i][j] = strNum;
                if (fill(i, j + 1)) return true;
                board[i][j] = ".";
            }
        }
        return false;
    };
    fill(0, 0);
}

结果

执行用时 : 82 ms, 击败 67.31% 使用 TypeScript 的用户

内存消耗 : 51.56 MB, 击败 13.46% 使用 TypeScript 的用户

PHP

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
45
46
47
class Solution {

    /**
     * @param String[][] $board
     * @return NULL
     */
    function solveSudoku(&$board) {
        $this->solve($board);
    }
    function hasConflit($board, $r, $c, $val) {
        for ($i = 0; $i < 9; $i++) {
            if ($board[$i][$c] === $val || $board[$r][$i] === $val) {
                return true;
            }
        }
        $subRowStart = floor($r / 3) * 3;
        $subColStart = floor($c / 3) * 3;
        for ($i = 0; $i < 3; $i++) {
            for ($j = 0; $j < 3; $j++) {
                if ($val === $board[$subRowStart + $i][$subColStart + $j]) {
                    return true;
                }
            }
        }
        return false;
    }
    function fill(&$board, $i, $j) {
        if ($j === 9) {
            $i++;
            $j = 0;
            if ($i === 9) return true;
        }
        if ($board[$i][$j] !== ".") return $this->fill($board, $i, $j + 1);
        for ($num = 1; $num <= 9; $num++) {
            $strNum = strval($num);
            if (!$this->hasConflit($board, $i, $j, $strNum)) {
                $board[$i][$j] = $strNum;
                if ($this->fill($board, $i, $j + 1)) return true;
                $board[$i][$j] = ".";
            }
        }
        return false;
    }
    function solve(&$board) {
        $this->fill($board, 0, 0);
    }
}

结果

执行用时 : 113 ms, 击败 50.00% 使用 PHP 的用户

内存消耗 : 20.03 MB, 击败 -% 使用 PHP 的用户

Swift

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
45
46
47
48
class Solution {
    var line = Array(repeating: Set<Int>(), count: 9)
    var column = Array(repeating: Set<Int>(), count: 9)
    var block = Array(repeating: Array(repeating: Set<Int>(), count: 3), count: 3)
    var valid = false
    var spaces = [[Int]]()
    func solveSudoku(_ board: inout [[Character]]) {
        initializeSets(with: board)
        DFS(&board, 0)
    }
    func initializeSets(with board: [[Character]]) {
        for i in 0..<9 {
            for j in 0..<9 {
                if board[i][j] == "." {
                    spaces.append([i, j])
                } else {
                    let digit = Int(String(board[i][j]))! - 1
                    line[i].insert(digit)
                    column[j].insert(digit)
                    block[i/3][j/3].insert(digit)
                }
            }
        }
    }
    func DFS(_ board: inout [[Character]], _ pos: Int) {
        if pos == spaces.count {
            valid = true
            return
        }
        let space = spaces[pos]
        let i = space[0]
        let j = space[1]
        var digit = 0
        while digit < 9 && !valid {
            if !line[i].contains(digit) && !column[j].contains(digit) && !block[i/3][j/3].contains(digit) {
                line[i].insert(digit)
                column[j].insert(digit)
                block[i/3][j/3].insert(digit)
                board[i][j] = Character(String(digit + 1))
                DFS(&board, pos + 1)
                line[i].remove(digit)
                column[j].remove(digit)
                block[i/3][j/3].remove(digit)
            }
            digit += 1
        }
    }
}

结果

执行用时 : 46 ms, 击败 13.33% 使用 Swift 的用户

内存消耗 : 16.30 MB, 击败 6.67% 使用 Swift 的用户

Kotlin

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
class Solution {
    fun solveSudoku(board: Array<CharArray>): Unit {
        solve(board)
    }
    private fun solve(board: Array<CharArray>): Boolean {
        for (i in 0 until 9) {
            for (j in 0 until 9) {
                if (board[i][j] == '.') {
                    for (num in '1'..'9') {
                        if (isValid(board, i, j, num)) {
                            board[i][j] = num
                            if (solve(board)) {
                                return true
                            }
                            board[i][j] = '.'
                        }
                    }
                    return false
                }
            }
        }
        return true
    }
    private fun isValid(board: Array<CharArray>, row: Int, col: Int, num: Char): Boolean {
        for (i in 0 until 9) {
            if (board[row][i] == num || board[i][col] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
                return false
            }
        }
        return true
    }
}

结果

执行用时 : 149 ms, 击败 92.86% 使用 Kotlin 的用户

内存消耗 : 34.05 MB, 击败 92.86% 使用 Kotlin 的用户

Dart

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
class Solution {
  void solveSudoku(List<List<String>> board) {
    solve(board);
  }
  bool solve(List<List<String>> board) {
    for (int i = 0; i < 9; ++i) {
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.') {
          for (int num = 1; num <= 9; ++num) {
            String strNum = num.toString();
            if (isValid(board, i, j, strNum)) {
              board[i][j] = strNum;
              if (solve(board)) {
                return true;
              }
              board[i][j] = '.';
            }
          }
          return false;
        }
      }
    }
    return true;
  }
  bool isValid(List<List<String>> board, int row, int col, String num) {
    for (int i = 0; i < 9; ++i) {
      if (board[row][i] == num || board[i][col] == num ||
          board[3 * (row ~/ 3) + i ~/ 3][3 * (col ~/ 3) + i % 3] == num) {
        return false;
      }
    }
    return true;
  }
}

结果

执行用时 : 289 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 145.09 MB, 击败 100.00% 使用 Dart 的用户

Go

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
func solveSudoku(board [][]byte) {
	solve(board)
}
func solve(board [][]byte) bool {
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] == '.' {
				for num := byte('1'); num <= '9'; num++ {
					if isValid(board, i, j, num) {
						board[i][j] = num
						if solve(board) {
							return true
						}
						board[i][j] = '.'
					}
				}
				return false
			}
		}
	}
	return true
}
func isValid(board [][]byte, row, col int, num byte) bool {
	for i := 0; i < 9; i++ {
		if board[row][i] == num || board[i][col] == num ||
			board[3*(row/3)+i/3][3*(col/3)+i%3] == num {
			return false
		}
	}
	return true
}

结果

执行用时 : 3 ms, 击败 70.00% 使用 Go 的用户

内存消耗 : 1.88 MB, 击败 86.32% 使用 Go 的用户

Ruby

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
# @param {Character[][]} board
# @return {Void} Do not return anything, modify board in-place instead.
def solve_sudoku(board)
  solve(board)
end
def solve(board)
  (0..8).each do |i|
    (0..8).each do |j|
      if board[i][j] == '.'
        ('1'..'9').each do |num|
          if is_valid(board, i, j, num)
            board[i][j] = num
            return true if solve(board)
            board[i][j] = '.'
          end
        end
        return false
      end
    end
  end
  true
end
def is_valid(board, row, col, num)
  num = num.to_s
  (0..8).each do |i|
    return false if board[row][i] == num || board[i][col] == num ||
                   board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num
  end
  true
end

结果

执行用时 : 548 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.85 MB, 击败 100.00% 使用 Ruby 的用户

Scala

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
object Solution {
  def solveSudoku(board: Array[Array[Char]]): Unit = {
    solve(board)
  }
  def solve(board: Array[Array[Char]]): Boolean = {
    for (i <- 0 until 9) {
      for (j <- 0 until 9) {
        if (board(i)(j) == '.') {
          for (num <- '1' to '9') {
            if (isValid(board, i, j, num)) {
              board(i)(j) = num
              if (solve(board)) {
                return true
              }
              board(i)(j) = '.'
            }
          }
          return false
        }
      }
    }
    true
  }
  def isValid(board: Array[Array[Char]], row: Int, col: Int, num: Char): Boolean = {
    for (i <- 0 until 9) {
      if (board(row)(i) == num || board(i)(col) == num ||
        board(3 * (row / 3) + i / 3)(3 * (col / 3) + i % 3) == num) {
        return false
      }
    }
    true
  }
}

结果

执行用时 : 637 ms, 击败 80.00% 使用 Scala 的用户

内存消耗 : 56.14 MB, 击败 100.00% 使用 Scala 的用户

Rust

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
impl Solution {
    pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
        Self::solve(board);
    }
    fn solve(board: &mut Vec<Vec<char>>) -> bool {
        for i in 0..9 {
            for j in 0..9 {
                if board[i][j] == '.' {
                    for num in '1'..='9' {
                        if Self::is_valid(board, i, j, num) {
                            board[i][j] = num;
                            if Self::solve(board) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        true
    }
    fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize, num: char) -> bool {
        let num = num as u8;
        for i in 0..9 {
            if board[row][i] as u8 == num || board[i][col] as u8 == num ||
               board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] as u8 == num {
                return false;
            }
        }
        true
    }
}

结果

执行用时 : 6 ms, 击败 13.89% 使用 Rust 的用户

内存消耗 : 2.06 MB, 击败 75.00% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户