构建一个 React 应用程序来解决每个数独难题。

AWS 安全上线！

介绍

十年前，传奇的谷歌大亨兼人工智能巨头 Peter Norvig 写了一篇关于 Python 的文章，解答了所有数独难题。当时，他可能没想到自己的代码会启发如此多的文章，并被移植到如此多不同的语言中。对于 JavaScript，我找到的最新版本的解算器是2014 年的@einaregilsson/sudoku。

我认为创建一个使用 Peter Norvig 的求解器思想并在 UI 中添加一些学习层的反应应用程序会很有趣。

以下是我创建该应用时使用的设计文档中的一些细节。我们开始吧。

如果您想在阅读之前先了解一下，请前往现场演示

或者 github repo jsolano/react-sudoku-solver

计划和范围

1. 使用 React（带有钩子）设计和实现 HTML/JS/CSS Web 应用程序。
2. 设计并实现一个用 JavaScript 解决数独谜题的算法。（难度从简单到极难）

目标和非目标

目标：

1. 构建一个 HTML/JavaScript 应用程序来解决给定的数独难题。
2. 使用 React 组件和 React 钩子。
3. 涵盖美观性和可用性。
4. 支持以 Peter Norvig 的文章中描述的格式输入拼图字符串。
5. 涵盖算法的性能（简单、中等、困难、专家）。
6. 显示解决难题所需的时间。
7. 封面单元测试。

非目标：

1. UI 级别自动化测试。
2. 产生新的未解谜题。
3. 打印数独。
4. 存储任何会话数据（本地或远程）。
5. 接受用户对难题的解决方案。
6. 使求解器在特定步骤停止。

初步设计

这个想法是在 UI 中创造一种流动感，让用户可以轻松理解如何使用它。

系统环境图

该应用程序有两个主要模块：

首先，我制作了基本 JS 组件和实用程序的原始版本：

然后，我开始使用 JEST 对求解器服务进行测试。

后来，我实现了板、模态框、消息和按钮的反应组件，然后使用反应钩子与求解器服务集成。

学习层。

事情开始变得有趣起来。一方面，UI 学习栏帮助我理解了求解器的工作原理以及如何改进实现。但是，在我移植了 Peter Norvig 的算法（该算法使用回溯搜索策略并解决了所有数独问题）之后，我意识到学习栏毫无用处，因为在寻找解决方案的过程中，它创建了一些无效的临时步骤。我需要改变我的方法。

转折点

我本可以删除学习功能并仅使用一个简单的求解器，但我选择实施提供详细解决方案的其他求解策略。

我研究了数独的解题策略，发现有超过 38 种选择。我完全被迷住了。点击此处查看更多

但所有这些策略都有一个问题：即使你尝试实现某些策略，写了很多行代码，仍然无法解决所有难题。（我吃过不少苦头才明白这一点）。所以，我找到了一个解决方案：

创建一个使用人类解决策略的反应应用程序（用于学习目的和娱乐），并且只将回溯搜索作为最后的手段。

现在，该应用程序将应用以下策略：

1. 隐藏单身人士
2. 裸双/裸三
3. 指向对
4. 最后一个选项：回溯搜索

此外，它还配备了防止无限循环的功能以及在解决难题时的旋转器。

更新 #1：

• 添加了“仅选择一个”链接，用于加载随机谜题。（感谢 Andre 的建议！）

更新 #2：

• 在解析过程中，当输入的棋盘已解决时，添加了一条消息。（感谢 Andre 的提示！）这种情况可能发生在筛选单元格可能值并解决所有单元格之后。（这种情况并不常见，但可能存在，例如：..6.....2.81.4293.25...34..4.8.1..76..2...8..17..6.3.9..35...94.9732.51.5.....7..）

更新 #3：

• 增加了针对移动设备的响应式布局

更新 #4：

• 更改了 useReducer 的 useState 钩子，以将状态管理与组件分离，并添加了 localStorage 持久性。

如果你是数独爱好者，并且想与我们合作，请查看GitHub 仓库。和我一起实现剩下的 34 个策略吧！

/JP

那些秉持理念的人的敌人并非持反对观点的人，而是那些想要彻底禁止讨论的人。——保罗·格雷厄姆