主要观点:作者晚上无聊时想通过编程解决数独问题,介绍了数独规则,讲述自己通常解决数独的方法以及让计算机解决数独的思路,包括获取数独谜题的 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
使打印的数独更美观。 - 作者还制作了可视化求解的应用程序。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。