解数独

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 中不冲突的数字；可优先选择候选数最少的空格加速。

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