返回题库

解数独

Sudoku Solver

专题
Algorithmic Programming / 算法编程
难度
L4
来源
Citadel

题目详情

问题：解数独

考察：数组、递归

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/sudoku-solver/

英文原题

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.
解析

思路：回溯填空格。用行、列、宫三个集合记录已有数字，每次选择一个空格尝试 1 到 9 中不冲突的数字；可优先选择候选数最少的空格加速。

复杂度：最坏指数级，实际由数独约束强剪枝。

英文解析

Approach: Use backtracking. Choose the next empty cell, try digits that are not present in its row, column, or box, and backtrack when no digit works. Bit masks can speed up legality checks.

Complexity: Exponential in the number of empty cells, with constant board size in the standard puzzle.