具有一些高级功能的数独程序
4.93/5 (21投票s)
Sudoku 是一个用 C# 编写并带有 WPF 用户界面的程序。
引言
Sudoku 是一个用 C# 编写并带有 WPF 用户界面的程序。它可以生成 9x9 或 16x16 的数独棋盘，难度级别分为简单、中等或高级。我多年前就编写了它，最后决定发布，因为其中包含了一些在其他帖子中找不到的功能。
特点
这款数独程序特色
- 9x9 或 16x16 棋盘，不同难度级别
- 解决任何 9x9 或 16x16 的数独谜题
- 可自定义字体和颜色
- 可自定义用于表示值的符号（数字、字母或符号）
- 输入模式选择：单元格切换或数值选择器
- 输入值模式：仅接受有效值或接受任何值
- 打印数独棋盘（当前棋盘或批量打印）
- 设计你自己的数独（设计模式）
- 保存或加载数独棋盘
- 撤销/重做功能
- 不同类型的提示
- 等等。
使用符号而非数字的数独棋盘
使用字母而非数字的 16x16 数独棋盘
版本控制
| 版本 2.01 |
原始发布版本。 |
提供演示
提供的演示是带有 WPF 界面的 C# 数独程序。
提供源码
除了提供的演示源码外，我还包含了一个使用 Windows Forms 编写的该程序早期版本。此后者版本不受支持。
需要改进的地方？
- 如果能够注释棋盘就好了。
- 我在其他数独游戏中看到了有趣的输入方法，可以添加到此版本中。
- 难度级别可以更精细。
- 在游戏中添加帮助文件会很受欢迎。
源码说明
项目中包含的主要类有
引擎类
- CellPos: 单元格位置 (x,y)
- SudBoard: 实现数独棋盘的抽象类
- SudBoard9: 9x9 棋盘的 SudBoard 实现
- SudBoard16: 16x16 特定功能的 SudBoard 实现
- SudBoardGenerator: 同步或异步生成 9x9 或 16x16 棋盘
- ValCount: 实现计数器的抽象类，用于计算某类型区域（行、方块或列）的每个可能值的数量
- ValCount9: 9x9 棋盘的 ValCount 实现
- ValCount16: 16x16 棋盘的 ValCount 实现
WPF 和用户界面类
- app: 应用程序
- dlgAbout: 关于框
- dlgBoardAppearance: 用于更改绘制界面的字体和颜色的对话框
- dlgGenerateABoard: 处理棋盘生成的对话框
- SudControl: 继承自 UserControl 的可视化控件，包含一个数独棋盘 (SudBoard)
- ValPickerControl: 实现用于选择要播放的值的数值选择器。由 SudControl 使用
- wndMain: 主窗口
1. 数据结构
值存储在一维数组 int[] m_arrBoardVal 中。使用一维数组而不是二维数组可以显著提高性能。数组中的值范围是 0 到 9（对于 9x9 棋盘）或 0 到 16（对于 16x16 棋盘）。值 0 表示一个空单元格。数组的第一个值用于存储左上角单元格的值，最后一个值用于存储右下角单元格的值。
存储在一维数组 ValueTypeE[] m_arrBoardValType 中的值的范围
| None (0) | 空单元格 |
| Fix (1) | 固定值。用户无法更改 |
| User (2) | 用户可以更改的值 |
ValCount 类旨在计算行、列和方块中每个可能值的计数。每次更新单元格值时，都会相应更新该单元格所在行、列和方块的 ValCount。
| m_LineValCount | 记录每行每个可能值的计数 |
| m_ColValCount | 记录每列每个可能值的计数 |
| m_SqrValCount | 记录每个方块每个可能值的计数 |
程序需要将线性位置转换为行/列和方块位置。这些转换使用非常频繁，必须进行优化（尤其是在 16x16 棋盘上）。在 16x16 棋盘上的转换是通过乘以 16 和取模 16 来完成的。这些操作是使用位移和 '&' 运算符完成的。这就是为什么存在 SudBoard9/16 和 ValCount9/16 类。
从方块位置到线性位置的转换是通过这两个数组完成的
| m_arrPosToSqr | 线性位置 -> 方块位置 |
| m_arrSqrToPos | 方块位置 -> 方块的第一个线性位置 |
数独棋盘类支持撤销或重做移动。为此，两个堆栈用于存储可以撤销或重做的移动
| Stack<Move> m_stackUndoMoves |
| Stack<Move> m_stackRedoMoves |
2. 移动
当输入的值在其列、行和方块中唯一时，该移动被定义为有效。
更改单元格值的最主要方法是 PlayAt。该方法更新 m_arrBoardVal 和 m_arrBoardValType 数组。它更新相应的方块、行和列的 ValCount 实例。如果指定，会更新撤销和重做堆栈。
3. 求解棋盘
给定的数独棋盘可能没有解、有一个解或有多个解。求解方法必须能够找到棋盘的解，并指明是否存在多个解。
简单的回溯法足以求解 9x9 棋盘。
while No Solution Found
Find the first empty cell
For each possible value in this cell
Play it
Call recursively
If Solved
Solution Found, exit
Else
Undo the move
EndIf
Next
Oops, bad board!
wend
然而，使用这种简单的方法来求解 16x16 棋盘速度太慢（至少在生成数独棋盘时需要多次调用 Solve 方法）。更好的方法是使用改进的回溯法。
do {
Fill the obvious cells
If solution not found,
Find the first empty cell
For each possible value in this cell
Play it
Call recursively
If solve
Solution Found, exit
Else
Undo the move
EndIf
Next
Oops, bad board!
EndIf
} while No solution found
进一步提高性能的一种方法是提前计算可能移动的列表。问题现在是如何实现“填充显而易见单元格”。在此上下文中，“显而易见”意味着
- 在一个方块、一行或一列中只能在一个单元格中播放的值。
- 在一个单元格中只能播放一个值的单元格。
| FillListOfValidValuesForEmptyCells | 填充一个数组，其中包含可能移动的列表 |
| FillValueWhichCanBePlayedInSingleCellOfAZone | 填充只能在一个行、列或方块中播放值的单元格。 |
| FillObviousCells | 填充所有显而易见的值 |
| SolveBacktrack | 改进的回溯方法 |
| Solve | 求解棋盘 |
4. 生成数独棋盘
此棋盘生成器的不同目标是
- 生成一个有效的、只有一个解的棋盘。
- 生成 9x9 或 16x16 棋盘。
- 生成不同难度的棋盘（简单、中等和困难）。
计算机使用三种策略来求解棋盘
- 用只能在一个方块、一行或一列中播放的值填充单元格。
- 填充只有一个值可以播放的单元格。
- 暴力破解（一个接一个地尝试排列）
对人类来说，第一种方法最简单，第二种更难，第三种最难。一个简单的棋盘只需要第一种方法就能解决。中等难度的棋盘需要前两种方法，而困难的棋盘则需要三种方法来解决。
该程序生成棋盘的通用方法是
- 生成一个完整的棋盘
- 逐个删除值，只要
- 棋盘只有一个解决方案
- 只使用与难度级别兼容的策略
棋盘生成由 SudBoardGenerator 类完成。棋盘可以在主线程或工作线程上生成。
4.1 生成完整棋盘
可以使用简单的回溯方法填充棋盘
Fill(iPos)
If Board Filled,
Return
ForEach Value
If Value is valid at this position
Play it
If Fill(iPos+1) = Filled
Return
Else
Undo the move
EndIf
EndIf
Next
<Must never get here>
这种方法总是会生成相同的棋盘。为了实现随机棋盘生成，我们只需打乱填充位置的顺序。
总的来说，使用这种方法生成完整棋盘速度很快。但是，有时某些 16x16 棋盘可能需要很长时间才能完成。发生这种情况时，取消此生成并重新开始会更快。
4.2 削减棋盘（挖洞）
一旦生成了完整的棋盘，我们只需从随机单元格中删除值。
ForEach Pos in Random Order
Set the position value to 0
If Solve doesn't give 1 solution or used strategies not compatible with the expected difficulty level
Restore the value
EndIf
Next
在 16x16 棋盘上，此例程可能需要相对较长的时间。因此，可以提供超时。如果达到超时，棋盘仍然有效，但会包含更多已完成的单元格。
5 数独控件
SudControl 实现了一个继承自 System.Windows.Controls.UserControl 的可视化控件。它用于玩数独。