如何用回溯法实现数独求解器?
哪些公司问过
答案要点
- 用行、列、宫三组标记数组做常数时间冲突检测,宫号为 (i/3)*3 + j/3
- 收集所有空格,递归逐格尝试 1 到 9
- 合法则填入并标记,递归失败则撤销并恢复标记(回溯)
- 全部空格填完即找到解,返回成功终止搜索
- 优化:位掩码表示候选,优先选候选最少的格子;最坏为指数复杂度
易错点
- 回溯时忘记撤销标记,导致后续判断错误
- 宫号计算写错
- 找到解后没有及时返回,继续搜索把已填好的答案撤销掉
面试官常见追问
- 如何判断一个数独有唯一解?
- 位运算优化具体怎么做?
- 如果初始棋盘本身不合法怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。