使用 C# Windows 应用程序的数独求解器
5.00/5 (8投票s)
数独问题编码解决方案概述
引言
数独是一款适合所有年龄段的有趣谜题，而且很容易获得。一旦我对数独产生了兴趣，我就一直想写一个程序来解决数独谜题。我曾短暂地在网上搜索过数独求解器，但它们大多基于暴力破解方法。我想以我手动解决问题的方式来编写代码。过去我曾尝试过两次，但只取得了部分成功。然后，在第三次尝试中，我设法将其完成到合理的程度。首先，这个程序一开始并没有进行任何猜测。如果它无法解决谜题，那么我将尝试使用获得的可能值来使用暴力破解方法解决。
背景
您需要对解决数独的基础知识有所了解。当您无需猜测即可解决代码时，该解决方案就能在很大程度上解决谜题。对于未解决的谜题，您可以使用日志找出可能的数值，这些数值可以作为输入进行进一步尝试。我已附上应用程序 (EXE) 的完整可运行版本和源代码，供您进一步开发。
Using the Code
在将解决方案移植到另一台计算机后，我遇到了由于 DPI 问题导致的窗体渲染问题。因此，我不得不使用以下代码来解决它。没有这些行，Winform 在不同的机器上看起来会很模糊。
static class Program
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main()
{
// ***this line is added***
if (Environment.OSVersion.Version.Major >= 6)
SetProcessDPIAware();
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new SudokuCSharp.Form1());
}
// ***also dllimport of that function***
[System.Runtime.InteropServices.DllImport("user32.dll")]
private static extern bool SetProcessDPIAware();
}
现在进入编码部分，我的解决方法如下：
为了存储问题陈述，我创建了一个结构，如下所示：
private struct mStruct
{
public bool isLocked; //To know whether it can be altered or not.
//If Locked, then it cannot be altered
public int curValue; //current value
public bool isSource; //To know whether this is the source data or not.
public string posValue;//to list down possible values it can hold
public int quarter; //to know which quarter the array belongs
public string rem; //remarks columns
}
然后，我创建了一个由该结构组成的数组来存储问题陈述。此处解释了 mstruct 的字段：
isLocked：布尔类型 - 用于了解值是否不能被修改。这可以是初始问题的一部分，也可以是迭代后找到的正确值。因此，一旦固定，就没有选项可以更改。curvalue：整数 - 单元格中的当前值。isSource：布尔类型 - 如果为true，则表示来自问题陈述。如果为false，则表示待找到的值。用于区分单元格值是来自问题陈述还是找到的值。posvalue：string- 包含单元格可以保存的所有可能值的逗号分隔列表。quarter：整数 - 我将整个 9x9 的单元格分割成 9 个区域。此值指示单元格属于哪个区域。rem：这是一个string，用于保存任何备注。
我使用上述 struct 创建了一个 9x9 的数组，并将问题陈述存储在其中。我称此数组为 playArray，因为我将使用它来寻找答案。
我还做了一个简单的方法来识别来自文本框控件名称的单元格。所有 textbox 控件都命名为：'txtq<quarter>r<row no>c<col no>'。例如，在文本框名称 'txtq2r0c7' 中 - txt 表示这是一个文本框，接下来的 2 个字母 'q2' 表示它属于哪个区域 - 这里是第二个区域。接下来的 4 个字母 'r0c7' 表示行和列的位置 - 第 0 行和第 7 列。通过这种方式，我可以识别值的来源，并且还可以轻松地将值赋回 textbox。请参阅下面的图片了解 textbox 的命名和区域命名。
将区域划分为四个区域的原因是为了解决每个区域的 3x3 单元格。如您所知，简单的数独规则是：一行、一列和一个区域中不能重复出现 1-9 的数字。
加载问题陈述
输入问题中的单元格值有些困难，因为我们需要使用 Tab 键在 textbox 之间移动。因此，我想出了一个简单的方法来做到这一点 - 在没有值的单元格中输入 0。
例如，问题陈述：000500809180400060000070010500000070649000000020010000090032000010005600700000480 加载如下。值是按行输入的，所有 0 都被假定为空白网格。这有助于更快地加载问题。
解决谜题
该谜题被迭代尝试，直到找到解决方案。关键函数是：
SolveHorizontalVerticalOrQuadrant("q"); //Solve for Quadrant
SolveHorizontalVerticalOrQuadrant("r"); //Solve for Row
SolveHorizontalVerticalOrQuadrant("c"); //Solve for Col
首先按区域、然后按行、最后按列进行解决。请注意，函数名称相同，只是参数 'q'、'r'、'c' 不同，以区分我们是按区域、按行还是按列进行求解。逻辑保持不变，只是根据发送的参数，相应地选择并处理数组。
一旦我知道数组中的值列表，我就会识别出没有值的单元格（需要解决的单元格）。然后使用以下方法为这些单元格分配所有可能的值。首先，它可以包含 1 到 9 的所有值。然后，我迭代剩余的有值的单元格，并从该单元格的可能值中删除这些值。
private readonly string possSolution = @"123456789"; //string that holds all possible values
//an empty cell can have
以下代码确定了单元格可以保存的所有可能值：
//Get possible solution in a line
for (int j = 0; j < noOfElementsInRowOrCol; j++)
{
if (lStruct[j].curValue > 0)
{
lPossSolution = lPossSolution.Replace(lStruct[j].curValue.ToString(),
"");//remove the values from possible solution
}
else
{
//Get the row and col where the value is 0
row = Int32.Parse(lStruct[j].rem.Substring(1, 1));//assuming r1c1
col = Int32.Parse(lStruct[j].rem.Substring(3, 1));//
zeroCells[k] = row * 10 + col;
k += 1;
}
}
有两种方法可以确定空单元格的正确值：
如果根据其余单元格只有一个可能值，或者如果可能值中只有一个唯一值（如果一个单元格的可能值如下：根据其余单元格为 1,2,3,2,3，这清楚地表明它可以是 1 或 2 或 3。由于 1 只出现一次，这清楚地表明它可以是该值）。这是通过以下函数实现的：
/// <summary>
/// All possible values are sent here from zero cells.
/// This checks for unique value and returns it which is the correct value
/// </summary>
/// <param name="lStr"></param>
private void GetUniqueValue(string lStr)
{
Array.Clear(lIntArray, 0, lIntArray.Length);//Clear the array
Array.Clear(ldoubleIntArray, 0, ldoubleIntArray.Length);//Clear the array
Array.Clear(ltripleIntArray, 0, ltripleIntArray.Length);//Clear the array
int i = 0;
int j = 0;
int k = 0;
Dictionary<char, int> dict = new Dictionary<char, int>();
try
{
foreach (char ch in lStr)
{
if (dict.ContainsKey(ch))
dict[ch] = dict[ch] + 1;
else
dict.Add(ch, 1);
}
foreach (KeyValuePair<char, int> m in dict)
{
if (m.Value == 1)// check for single occurence
{
//unique values in array is possible
if (m.Key.ToString() != ":")
{
lIntArray[i] = Int32.Parse(m.Key.ToString());
i++;
}
}
else if (m.Value == 2)//check for double occurence
{
if (m.Key.ToString() != ":")
{
ldoubleIntArray[j] = Int32.Parse(m.Key.ToString());
j++;
}
}
else if (m.Value == 3)//check for triple occurence
{
if (m.Key.ToString() != ":")
{
ltripleIntArray[k] = Int32.Parse(m.Key.ToString());
k++;
}
}
}
}
catch (Exception e)
{
HasChanged = false;
throw e;
}
}
使用以下两种方法更新空单元格上的可能值：
UpdatePossValues(lvalue.ToString(), row.ToString(), col, false); //To update the row
UpdatePossValues(lvalue.ToString(), col.ToString(), row, true); //To update the col
UpdatePossValuesInQuarter(lvalue.ToString(), playArray[row, col].quarter);//To update in a
//quarter
每次迭代后的可能值会在此处打印在富文本框中。请查看 if 条件 - isSource 字段用于选择待解决单元格的可能值。
/// <summary>
/// To print possible solution in the Rich text boxes
/// </summary>
private void PrintPossSolution()
{
for (int i = 0; i < noOfElementsInRowOrCol; i++)
{
for (int j = 0; j < noOfElementsInRowOrCol; j++)
{
if (!playArray[i, j].isSource)
{
richTextBox1.AppendText("R" + i.ToString() + "C" +
j.ToString() + ": " + playArray[i, j].posValue + Environment.NewLine);
}
}
}
}
我还添加了一些额外的方法，如果常规的解决方法不能给出完整答案，则可以使用这些方法进行解决。
SolvePossibleValuesRow2(); //check in Row for possible values with 2 occurences
SolvePossibleValuesCol2(); //check in Col for possible values with 2 occurences
例如，假设在 Q3 中，单元格 r4c0 和 r4c1 的可能值都是 2,3，那么这就表明 2 和 3 只能出现在该区域的第 4 行，而不能出现在该区域的任何其他行。有了这个线索，这两个数字就可以从该区域的 r3 和 r5 中删除。通过减少可能值，这将解决其他空单元格。同样的方法也适用于 column。这些被称为裸对。
对于一个区域中的 3 个单元格，按行和按列解决的方案可以进一步扩展，这为进一步开发提供了空间。
此处显示了一个完全解出的谜题。每行和每列后面的数字 45 显示了该行和列的计数。这用于检查程序是否已解决解决方案。
日志显示了解决迭代次数。此外，对于每个待解决的单元格，它会显示可能的数值。在这种情况下，由于已解决，每个单元格只有一个值。在程序无法解决的情况下，它会显示可能的数值 - 例如，R0C1: 5,6,7，这意味着 R0C1 可以是 5 或 6 或 7。
关注点
文本框的命名约定是获取值并将其赋回文本框的一种好方法。有关裸对的更多信息，请参阅以下链接：
- https://www.thonky.com/sudoku/naked-pairs-triples-quads#:~:text=In%20sudoku%2C%20a%20naked%20pair,pair%20has%20to%20be%203。
- http://hodoku.sourceforge.net/en/tech_intersections.php
历史
- 2020 年 6 月 8 日：版本 1.0 - 常规解决方法
- 2020 年 6 月 29 日：版本 1.0（无更改）- 实现隐藏裸对作为可能解决方案
- 2021 年 2 月 20 日：版本 1.1 - 实现暴力破解方法