解数独
Sudoku Solver
题目详情
问题：解数独
考察：数组、哈希表、回溯
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/sudoku-solver
英文原题
Problem: Sudoku Solver
Patterns: Array, Hash Table, Backtracking
Recency: 2yr
Link: https://leetcode.com/problems/sudoku-solver
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：回溯填空格。用行、列、宫三个集合记录已有数字，每次选择一个空格尝试 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.