将数独求解器从 Excel 转换为 C#
5.00/5 (6投票s)
将数独求解器从 Excel 转换为 C#
引言
我对您 1 月 1 日发表的将 VB.Net 和 WinForms 中的数独程序转换为 C# 和 WPF 的文章很感兴趣 https://codeproject.org.cn/Articles/855699/Complete-Sudoku-Game-in-Csharp-WPF-Silverlight，因为几年前我也做过一个类似但可能更极端的转换。在我开始之前，我对 C# 或 WPF 一无所知——我甚至没听说过它们，而我对面向对象编程的经验仅限于在 Visual Basic for Excel 中创建简单的控件。我希望我的经验能说服其他人，学习 C# 并没有一开始看起来那么令人生畏。事实上，就像长跑一样，最难的部分是下定决心开始。
背景
当我第一次了解到数独时，我认为在计算机上自动化解决它将是一个有趣的挑战。由于我最近的编程经验是使用 Visual Basic 编写 Excel 宏，所以我决定使用 Excel 作为前端，并用 VB 编写所有代码。这进行得很顺利，但后来我发现这些工具不够用了。我见过其他具有不同几何形状的数独问题，比如武士数独，我想能够处理它们。这并不难，但我决定需要一个求解器来处理任何大小、几何形状或字符类型的数独问题。
我的 VB 代码将所有变量保存在全局数组中，这使得为不同问题重新定义这些数组变得非常麻烦，而且即使那样也不够通用。我需要一个更强大的编程语言，而且我需要某种方式摆脱 Excel 作为前端，因为它需要手动重绘每个新的几何形状。我决定改用 C#，没有更好的理由，只是因为我懂电脑的妹夫在我与他在 Tignes 的滑雪缆车上讨论这个问题时向我推荐了它。这是一个重要的时刻，所以我记得很清楚，但后来我得知他所有的编程都是用 C 完成的，而且他实际上从未使用过 C#（他本该是我的导师！）。我使用 WPF 而不是 WinForms，仅仅因为我不知道还有其他选择。这两个决定最终都非常幸运，我继续对这种工具组合的强大功能和灵活性印象深刻。
在 Excel 和 VB 之前，我曾用 Fortran IV 编程（主要是在 20 世纪 70 年代的核工程中进行科学计算），所以我当时倾向于创建大型共享数组——这在 C# 中我发现非常困难，甚至可能不可能。在多次尝试创建可变维度的全局数组失败后，我才开始理解类的概念，生活才变得更简单。
类的使用
我有一个名为“Cell”的类，它存储了问题中每个小方块的细节，例如哪些可能性仍然可用，以及这个 Cell 所属的更大的结构“Shapes”。我有一个名为“Shape”的类，它大致相当于我在其他几个数独程序中看到的行、列和框，尽管更通用一些。我对 Shape 的定义是任何包含一个或多个不一定连续的 Cell 的集合。一个数独 Shape 总是包含与问题中未知数相同数量的 Cell，并且每个 Cell 中的解必须不同。Killer 类型的数独问题使用不同类型的 Shape。
Cell 类和 Shape 类的编码包含在下面。
/// <summary>
/// Records all detail associated with a single Cell
/// including reference to all Shapes containing this Cell
/// </summary>
public class Cell
{
/*
* Records all detail associated with a single Cell
* including reference to all Shapes containing this Cell
* Calls are:
* Add(Tag) Creates a new, unsolved, Cell with identifier Tag
* AddShape(ShapeNum) Add the ID number of a Shape containing this Cell
* RemoveShape(ShapeNum) Reverses AddShape
* ForceSolve(n) Records the Cell as "Solved" with possibility n
* ForceUnSolve() Forces the Cell to an unsolved state, sets all possibilities = true
* NumSolvedCells static get Total number of Cells which have been Solved, includes fixed Cells
* ResetNumSolvedCells static Reset the counter of Solved Cells to zero
* Tag get Identifier of this Cell, RnCm
* Solved Returns true if Cell is solved, else returns false<
* NumPossibilities gets Number of possibilities remaining for this Shape, = 1 if Solved
* Solution gets the Solution index, i.e. number 0 through NChars - 1
* NumShapes gets Number of Shapes containing this Cell
* [] ShapeNums gets array of id#s of all Shapes containing this Cell
* SolOrder gets/sets Order in which each Cell is Solved, zero through NumSolvedCells - 1
* [] Possibilities gets a boolean array of remaining possibilities
* Cell[i] gets/sets possibility []
*/
private static int numSolvedCells;
string tag;
bool solved;
int solution;
int solOrder;
int nShape = 0;
int maxShape;
bool[] possibilities;
int[] shapeNums;
/// <summary>Creates a new, unsolved, Cell with identifier Tag</summary>
/// <param name="Tag">string, the identifier for the Cell</param>
public void Add(string Tag)
{
this.tag = Tag;
possibilities = new bool[Characters.NumChars];
maxShape = 5; //Initial value, will expand if necessary, see AddShape
shapeNums = new int[maxShape];
for (int nS = 0; nS < maxShape; nS++)
{
shapeNums[nS] = -1;
}
ForceUnSolve();
}
/// <summary>Add the ID number of a Shape containing this Cell</summary>
/// <param name="ShNum">The number of the Shape to be added</param>
public void AddShape(int ShNum)
{
if (!shapeNums.Contains(ShNum))
{
expandIfFull();
shapeNums[nShape++] = ShNum; //nShape counts # of Shapes for this Cell
}
}
/// <summary>Reverses AddShape</summary>
/// <remarks>The array, shapeNums, is reordered to bring active elements forward</remarks>
/// <param name="ShNum">Number of the Shape to be removed</param>
/// <returns>true if the Shape was removed, false if the Shape was not found</returns>
public bool RemoveShape(int ShNum)
{
bool found = false;
if (shapeNums.Contains(ShNum))
{
found = true;
for (int i = 0; i < nShape; i++)
{
if (shapeNums[i] == ShNum)
{
if (i + 1 < nShape)
{
//
// Move ShNum one place to the right in the array
int temp = shapeNums[i + 1];
shapeNums[i + 1] = shapeNums[i];
shapeNums[i] = temp;
}
//
// ShNum now at end of array, replace by -1
else shapeNums[i] = -1;
}
}
nShape--; //nShape counts # of Shapes for this Cell
}
return found;
}
/// <summary>Records the Cell as "Solved" with possibility n</summary>
/// <remarks>Sets possibilities[i] = (i == n)</remarks>
/// <param name="n">Number to record (index of possibilities array)</param>
/// <returns>Number of possibilities eliminated</returns>
public int ForceSolve(int n)
{
int possEliminated;
if ((n < 0) | (n >= Characters.NumChars))
{
InOutUtilities iO = new InOutUtilities();
iO.Display_And_Pause(
" Invalid n in ForceSolve, n= ",
n.ToString(), " Cell = ", this.tag.ToString());
return 0;
}
if (this.solved) return 0;
possEliminated = recalculateNumPossibilities() - 1;
this.solved = true;
this.solOrder = numSolvedCells++;
this.solution = n;
for (int nCh = 0; nCh < Characters.NumChars; nCh++)
{
possibilities[nCh] = (nCh == n);
}
return possEliminated;
}
/// <summary>Forces the Cell to an unsolved state, sets all possibilities = true</summary>
public void ForceUnSolve()
{
this.solved = false;
this.solOrder = 0;
this.solution = -1;
for (int nCh = 0; nCh < Characters.NumChars; nCh++)
{
this.possibilities[nCh] = true;
}
}
/// <summary>Total number of Cells which have been Solved, includes fixed Cells</summary>
public static int NumSolvedCells
{
get { return numSolvedCells; }
}
/// <summary>Reset the counter of Solved Cells to zero</summary>
public static void ResetNumSolvedCells()
{
numSolvedCells = 0;
}
/// <summary>Identifier of this Cell, RnCm</summary>
public string Tag
{
get { return this.tag; }
}
/// <summary>Returns true if Cell is solved, else returns false</summary>
public bool Solved
{
get { return this.solved; }
}
/// <summary>Number of possibilities remaining for this Shape, = 1 if Solved</summary>
public int NumPossibilities
{
get
{
return recalculateNumPossibilities();
}
}
private int recalculateNumPossibilities()
{
int n = 0;
for (int nCh = 0; nCh < Characters.NumChars; nCh++)
{
if (possibilities[nCh])
{
n++;
this.solution = nCh;
}
if (n > 1) solution = -1;
}
return n;
}
/// <summary>Returns the Solution index, i.e. number 0 through NChars - 1</summary>
/// <remarks>Use Characters.Chars[c.Solution] for display, Characters.Values[c.Solution] for value</remarks>
/// <returns>Solution index, number 0 through NChars - 1</returns>
public int Solution
{
get { return this.solution; }
}
/// <summary>Number of Shapes containing this Cell</summary>
public int NumShapes
{
get { return this.nShape; }
}
/// <summary>Id number of all Shapes containing this Cell</summary>
public int[] ShapeNums
{
get { return this.shapeNums; }
}
/// <summary>Order in which each Cell is Solved, zero through NumSolvedCells - 1</summary>
public int SolOrder
{
get { return this.solOrder; }
}
/// <summary>Array giving all possible solution for this Cell</summary>
public bool[] Possibilities
{
get { return this.possibilities; }
}
/// <summary>Get or Set a possibility for this Cell</summary>
public bool this[int Index]
{
get { return this.possibilities[Index]; }
set
{
this.possibilities[Index] = value;
}
}
private void expandIfFull()
{
if (nShape == maxShape)
{
maxShape += 5;
int[] newShapeNums = new int[maxShape];
this.shapeNums.CopyTo(newShapeNums, 0);
this.shapeNums = newShapeNums;
for (int nS = nShape; nS < maxShape; nS++)
{
shapeNums[nS] = -1;
}
}
}
}
/// <summary>Stores all information associated with a single Shape</summary>
public class Shape
{
private static int maxShapeNo = -1;
private static int numActiveShapes = 0;
private int num;
private ShapeType type;
private string label;
private int sum;
private int size;
private string[] cellTags;
private string identifier;
private int[,] partitions;
private int nPartition = 0;
private int nActivePartition;
private bool noRepeatSolns;
/// <summary>Add a new Shape</summary>
/// <param name="Type">Type of Shape, chose from enum ShapeType</param>
/// <param name="Label">Label of Shape - not validated</param>
/// <param name="Sum">Sum of Cell values</param>
/// <param name="CellTags">Array of all Cell Tags, No of Cell Tags sets Size</param>
/// <returns>Number of Shape, used as unique identifier</returns>
public int Add(ShapeType Type, string Label, int Sum, string[] CellTags)
{
this.num = ++maxShapeNo;
numActiveShapes++;
this.type = Type;
this.label = Label;
this.sum = Sum;
this.size = CellTags.Count();
this.cellTags = new string[size];
CellTags.CopyTo(cellTags, 0);
this.identifier = Shared.CreateShapeIdentifier(type, label, sum, cellTags);
switch (this.type)
{
case ShapeType.Sudoku:
case ShapeType.Killer:
noRepeatSolns = true;
break;
case ShapeType.Super:
case ShapeType.Created:
noRepeatSolns = false;
break;
}
return num;
}
/// <summary>Resets the number of Shapes to zero</summary>
public static void ResetShapeCount()
{
numActiveShapes = 0;
maxShapeNo = -1;
}
/// <summary>Returns the number of the last Shape added</summary>
public static int MaxShapeNo
{
get { return maxShapeNo; }
}
/// <summary>Returns the identification number of a given Shape</summary>
public int Num
{
get { return this.num; }
}
/// <summary>Returns the Type of a given Shape</summary>
public ShapeType Type
{
get { return this.type; }
}
/// <summary>Returns the Label of a given Shape</summary>
public string Label
{
get { return this.label; }
}
/// <summary>Returns the Sum of a given Shape</summary>
public int Sum
{
get { return this.sum; }
}
/// <summary>Returns the Size (# Cells) of a given Shape</summary>
public int Size
{
get { return this.size; }
}
/// <summary>Returns the Identifier (Type, Sum, Cell Tags) of a given Shape</summary>
public string Identifier
{
get { return this.identifier; }
}
/// <summary>Returns an Array of all Cell Tags for a given Shape</summary>
public string[] CellTags
{
get { return this.cellTags; }
}
/// <summary>Indicates if a value may be repeated in a given Shape</summary>
/// <remarks>
/// Always set true (No repeats) for Sudoku and Killer Shapes
/// Always set false (Repeats allowed) for Super Shapes
/// Set true for Created Shape iff wholely contained within a Sudoku or Killer Shape
/// </remarks>
public bool NoRepeatSolns
{
get { return this.noRepeatSolns; }
set { this.noRepeatSolns = value; }
}
}
代码的通用性
有了这两个类，编码就变得非常简单。例如，当我们解决一个 Cell 时，我们不必从包含该 Cell 的每一行、每一列和每一个框中消除该解，而只需从包含该 Cell 的每一个 Shape 中消除。
创建了上述类之后，下一步是将它们存储在排序列表中。这避免了对数组进行维度的需要，并使代码保持通用变得容易。这意味着解决 Samurai 问题（图 1）、常规 9X9 数独问题，或者数字不能在对角线上重复的 9X9X 问题（图 2），甚至是三维 Tredoku 问题（图 3），所使用的代码完全相同。在**绘制**图 3 时需要一点额外的代码，但在绘制和解决图 4 中所示的相同的二维映射问题时，则不需要额外的代码。
请注意，在 9X9X 和 Tredoku 问题中，Shapes 并不都包含连续的 Cells。事实上，“连续”这个词没有意义，因为上面的图只是将问题映射成我们能识别的东西的一种方式。对于程序来说，关键的理念是，Cells 只是可以包含多个可能解的类，而 Shapes 只是引用 Cell 集合的类。进一步的泛化允许未知数的数量成为一个输入参数，这定义了数独 Shapes 的大小（通常是行、列和框的大小）。然后，未知数可以映射到“任何”符号。我将其限制为任何可以表示为单个 Unicode 字符的符号，仅仅是为了能够在解决过程中显示标记，而无需分隔符（图 5）。
字符信息结构如下所示。这是程序中为数不多的几个数组之一。
Struct Characters
/// <summary>Information on Character set used to display the problem and solution</summary>
public struct Characters
{
/// <summary>Returns number of Characters in the Problem</summary>
public static int NumChars { get { return Chars.Count(); } }
/// <summary>Gets or Sets the Character set as a string[]</summary>
public static string[] Chars { get; set; }
/// <summary>Values associated with the Characters</summary>
public static int[] Values { get; set; }
}
算法
有了这些概念，编写实现大多数著名算法（表 1）来解决非常通用的数独问题就相对容易了。它不使用“X-Wing”算法，因为这似乎需要对问题的几何形状有所了解。
| 标准名称 | 我的程序 |
| 裸单 | Cell 中的单个字符 |
| 隐藏单 | Shape 中的单个字符 |
| 裸对/三/四 | N 个 Cell 中的 N 个可能性 |
| 隐藏对/三/四 | N 个 Cell 中的 N 个可能性 |
| 块/列/行 | 重叠 Shapes |
| X Wing | 未实现 |
下面我将提供裸对等代码的示例。这提供了一个例子，说明如果我们不受行、列和框的概念的束缚，代码可以有多么简单。事实上，我有这个代码的两个版本，这里显示的特殊版本速度很快，但要求至少有一个 Cell 包含精确匹配。通用版本允许诸如 (1,2)、(2,3)、(1,3) 等组合，但速度较慢，所以只在其他所有方法都失败时使用。
/// <summary>Check for sets of n Cells in this Shape containing exactly n possibilities
/// <para >Special method - requires one Cell in the subset contains exactly n possibilities,
/// i.e. one Cell has n possibilities and n-1 Cells have subsets</para></summary>
/// <param name="n">Looking for n Cells in Shape s which between them have n possibilities</param>
/// <param name="s">Shape to apply this logic to</param>
/// <returns>Number of possibilities eliminated</returns>
private int nPossInNCellsInShapeSSpecial(int n, Shape s)
{
int possibilitiesEliminated = 0;
string[] cellTags = getListOfSuitableCells(n, s);
if (cellTags != null)
{
//
// Find a Cell with exactly n possibilities
foreach (string tag in cellTags)
{
Cell c = (Cell)Collections.Cells[tag];
if (c.NumPossibilities == n)
{
//
// Find all Cells with a subset of these possibilities
List<string> selectedCells = new List<string>();
selectedCells.Add(tag);
foreach (string otherTag in cellTags)
{
if (otherTag != tag)
{
Cell otherC = (Cell)Collections.Cells[otherTag];
bool subset = true;
for (int ch = 0; ch < Characters.NumChars; ch++)
{
if (otherC[ch] && !c[ch])
{
subset = false;
break;
}
}
if (subset)
{
selectedCells.Add(otherTag);
}
}
}
if (selectedCells.Count == n)
{
possibilitiesEliminated += removePossibilitesFromRemainingCells(n, s, selectedCells);
}
}
}
}
return possibilitiesEliminated;
}
用户界面
编程的一个重要部分是开发用户界面。但大多数问题是由于我的无知和缺乏经验，而不是由于任务本身的固有难度。
最初选择 WPF 作为用户界面是一个错误。我甚至不知道还有其他选择——Windows Forms。每次我卡住并需要搜索帮助时，我的搜索都会找到一个 WinForms 解决方案（似乎 WinForms 的帮助比 WPF 多得多），我会不知不觉地尝试实现它，然后想知道为什么它不起作用。最终我明白了，现在总是在我的搜索字符串中包含“wpf”。但当时这并不明显，并且可能会让其他学习者感到困惑。如果能有关于它们之间的区别以及为什么两者都存在以及选择它们的理由更清晰的文档，那将很有帮助。我在某处读到 WPF 是微软的首选方向，但所有的帮助文档似乎都表明了相反的情况。上面图表中显示的实际解网格无法在 XAML 中生成，因为它需要是动态的，但相对容易创建 TextBoxes 数组，然后删除不需要的任何一个。编写生成 Shape 边界的代码很有趣，特别是对于 Killer 问题，我希望识别 Killer Shapes，并将总和放在左上角的 Cell 中（见图 6）。
用户界面的其余部分，包括所有控件，都是使用 XAML 编写的，这事实证明非常简单。我喜欢这样一种方式：如果我想移动控件，也许将一个控件放在另一个控件里面，我可以简单地剪切并粘贴 XAML 代码。
创建数独问题
我想添加创建数独问题的能力，为此我非常感谢这里发表的一篇题为“使用 Microsoft Solver Foundation 的数独”的文章 https://codeproject.org.cn/Articles/419389/Sudoku-using-MS-Solver-Foundation
我使用 MS Solver Foundation 来填充解决方案网格，然后逐个隐藏 Cell，直到剩下最小的数字仍然具有唯一的解决方案。这使得创建任何几何形状的新问题变得容易。
限制
所有这些都是为 PC 编写的。我没有尝试为手机编写，因为我对 Silverlight 一无所知。我也没尝试将其制作成交互式游戏程序，让用户直接在 PC 上尝试解决问题。手机和交互式游戏目前都超出了学习者的能力范围，所以我决定坚持做一个数独求解器和问题创建器。
结论和总结
总的来说，这是一次很棒的经历，它将我的编码能力从 Fortran IV 的非结构化代码提升到了现代面向对象语言的某种程度的熟练程度。我只包含了一些代码示例，因为它们说明了使用 C# 这样的语言的强大功能，而完整的代码相当长，并且主要涉及用户界面。我相信有经验的程序员可以比我写得更好。
我想强调的是 Shape 的通用定义，它消除了对行、列和框的单独编码的需求，以及使用 Cell 和 Shape 类来隐藏许多复杂性并使代码能够实现高度通用。