面试题库 › C++ / 后端 › 如何用回溯法实现数独求解器?

如何用回溯法实现数独求解器?

难度 ★★☆在 3 场真实面经中被问到 方向:C++ / 后端考点:贪心与回溯

哪些公司问过

腾讯1美团1微软1

常见岗位:C/C++ 软件开发、推理部署与加速

答案要点

  1. 用行、列、宫三组标记数组做常数时间冲突检测,宫号为 (i/3)*3 + j/3
  2. 收集所有空格,递归逐格尝试 1 到 9
  3. 合法则填入并标记,递归失败则撤销并恢复标记(回溯)
  4. 全部空格填完即找到解,返回成功终止搜索
  5. 优化:位掩码表示候选,优先选候选最少的格子;最坏为指数复杂度

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题