每小时解决一百万数独谜题 - 递归

主要观点:作者晚上无聊时想通过编程解决数独问题,介绍了数独规则,讲述自己通常解决数独的方法以及让计算机解决数独的思路,包括获取数独谜题的 API、数据结构、解析字符串、寻找空单元格、找出可能的数字、递归回溯求解等过程,并通过基准测试得出每小时可求解约 100 万个数独的结论。
关键信息

  • 数独是基于逻辑的数字填图游戏,目标是在 9x9 网格中填入 1-9 数字且每行、每列、每个子网格都包含 1-9 各一个。
  • 作者通常先找填数字最多的子网格、行或列,再找可填数字唯一的单元格,若找不到则尝试插入可能数字。
  • 让计算机解决数独时,先扫描每行找第一个空单元格,减少回溯风险,通过 API 获取数独谜题,解析字符串为二维整数数组,递归回溯求解,遇到错误回溯重试。
  • 基准测试 1000 个“困难”难度数独,平均求解时间约 2.926511ms,最快 0.554625ms,最慢 34.77025ms,中位数 1.7765ms,每小时约可求解 100 万个数独。
    重要细节
  • 使用的 API 是youdosudoku api,获取数独谜题的函数getSudokuField处理各种错误情况。
  • 解析字符串函数parseField将字符串转换为二维整数数组。
  • 递归回溯求解函数solve遇到空单元格找可能数字,尝试每个可能数字,出错回溯。
  • 基准测试函数benchmark预获取 1000 个“困难”难度数独,计算求解总时间、最快最慢及中位数时间。
  • 格式化函数format使打印的数独更美观。
  • 作者还制作了可视化求解的应用程序。
阅读 33
0 条评论