解数独
4.63/5 (7投票s)
使用启发式搜索算法解数独。
引言
在计算机系统和第三个千年，速度至关重要。因此，算法旨在设计能够提高效率和速度的系统。在这种重要角色中，电脑游戏正在娱乐人们。
在该游戏的設計中，人工智能中使用了大部分算法，并且用户和系统之间的速度相互响应很重要。数独是其中一种拥有特定粉丝的游戏。这种游戏之所以特别，仅仅是因为重复失败会产生大量的排列组合和变化。报纸和杂志上都刊载了这些游戏的组成部分。
已经开发了许多用于生成 Othello 和回溯递归类型的算法，这些算法可以被提及和了解搜索，等等。实现这些算法，每种都有其局限性。本文提出的程序旨在处理不完整的数独，输入表格中缺乏解决方案，并提供唯一的解。该程序的输出速度为零点零一毫秒。
这次，系统结构不同。但总代码和提供的解决方案具有竞争力且速度很快。解决方案的示例在不同时间实现，这很明显。它通过使用二分查找等搜索方法来加快代码速度。本文尝试使用三维数组来存储数值，以帮助候选数知晓与其对应的表格，并填写在正确的位置。
原始的数独求解遵循以下三个条件：
- 每列的值都是唯一的
- 每行的值都是唯一的
- 每个 N * N 的方块内的值是唯一的
注意：数独的唯一性是不规则的，但在一和 N 之间不重复。（在此代码中，假设 N=3 的完整二维数组，表格为 81。）
每次搜索都会被评估。使用此技术可确保表格的唯一性。从何得知？使用算法来解决各种问题是解决每个问题的最困难的部分。了解情况的算法使用不同的解决方案是解决可见性有限和空间有限问题的最佳选择之一。
如果可以选择适当的方法即时访问您的选择，数独的短有限数字集将与上述条件组合重复出现。为此，可以使用二维数组作为显示空间。由于这些数字在这里是唯一的，因此算法所需的空间相当可观。即使是 N=4,5,6 的数组也可以轻松使用此方法。
建议避免使用无限数量的 N 来求解表格，因为辅助数组的空间将不足。该算法源于其速度特性。在其他程序中重复它是不恰当且不必要的，并且会降低速度。下面图表中给出了了解情况的搜索算法。
代码分析
它由两层组成。
- 表示层
- 业务层
演示层接收构造性输入，然后发送到数独的业务类。此代码将看到两个类。它使用二维数组来存储操作表，并使用数组内部方块的值，默认值为 3。
不同大小的表格，其数值各不相同。此外，还使用类型为Bool的内部数组来存储唯一数组。这些变量被定义为全局类，并具有可在此类值上执行的不同操作方法。以下代码插入了不完整的数独。输入字符串中的零表示表格中的空单元格。
数独为最终的准确性提供了输出。通过比较这些值，用户可以看到正确的答案。此代码是Sudoku类的一部分，并且Fill方法用于发送缺失的状态。此方法用于填充数独的内部数组。
演示层代码
Sudoku SUdok = new Sudoku();
string[] SolvedSudoku = new string[81];
string temp1 =
"219876435843591276765243891394157628127368954658429317482735169536914782971682543";
for (int i = 0; i < 81; i++)
{
SolvedSudoku[i] = Convert.ToString(temp1[i]);
}
SUdok.Fill(SolvedSudoku);
lblCompleteSudoko.Text = SUdok.Show();
for (int i = 0; i < 81; i++)
{
SolvedSudoku[i] = "0";
}
//entry sudoku
// value 0 is null in entry sudoku
string temp =
"219876435803591276065243891394150628127368954658429307482735169536914702970682543";
for (int i = 0; i < 81; i++)
{
SolvedSudoku[i] = Convert.ToString(temp[i]);
}
SUdok.Fill(SolvedSudoku);
这些变量由定义的变量的构造函数创建和初始化。
业务层代码
public class Sudoku
{
//N*N Board
int N = 3;
//Main Board
int[,] board = new int[9, 9];
//this array used by methods that
//Checked the value is unique in row and col and inner cubes
bool[] checkValue = new bool[10];
//constructor
public Sudoku()
{
//Fill main Array board by 0 value
for (int i = 0; i <= (N * N)-1; i++)
{
for (int j = 0; j <= (N * N)-1; j++)
{
board[i, j] = 0;
}
}
//fill check array with default value
for (int i = 0; i <= 9; i++)
{
checkValue[i] = true;
}
}
此方法可访问二维数组的i、j元素，该数组提供了主表。
// set value in main board
//i, j position of element array
//value i,j element array
public void setSquare(int i, int j, int value)
{
board[i, j] = value;
}
//get value for across row and col value
// i = row
// j = col
public int getSquare(int i, int j)
{
return board[i, j];
}
此方法显示二维表，使用三个主要字符 +、- 和 | 来表示数字。字符 - 用于行，| | 用于行和列的交叉点，以及行和列。
//this method Add "|" and "-" and "+" to show result in
//output.%3 put "|" in each ternary in row.
//
public string Show()
{
string Temp = string.Empty;
for (int i = 0; i <= (N * N)-1; i++)
{
for (int j = 0; j <= (N * N)-1; j++)
{
//this if dont allow to loop for input "|" at first
if (j % 3 == 0 && j != 0)
{
Temp += " | ";
}
else
{
//this if check for put "+" in out put at
//Confluence row and col in each cubes number
if (i % 3 == 0 && i != 0 && j == 0)
{
for (int k = 0; k < 18; k++)
{
if (k % 6 == 0 && k != 0)
{
Temp += "+";
}
else
{
Temp += "---";
}
}
Temp += "\r\n";
}
}
// insert dot Instead of zero
if (board[i, j] == 0)
{
Temp += " . ";
}
else
{
Temp += " " + board[i, j] + " ";
}
}
Temp += "\r\n";
}
return Temp;
}
上述方法用于插入 FILL，将不完整数组的输入值用于原始数组。FancyFill方法用于输入数组值，但超出不完整星期二。字符 +、- 和 | 用于显示。
//fill main board by input string array
public void Fill(string[] lines)
{
int k = 0;
for (int i = 0; i <= (N * N)-1; i++)
{
for (int j = 0; j <= (N * N)-1; j++)
{
board[i, j] = int.Parse(lines[k]);
k++;
}
}
}
//fill board by input string array and delete any + - | in input string
// this method for check two condition use peterson solution
public void FancyFill(string[] lines)
{
for (int i = 0; i <= (N * N)-1; i++)
{
for (int j = 0; j <= (N * N)-1; j++)
{
board[i, j] = 0;
}
}
int k = 0;
bool flag = true;
for (int i = 0; i <= (N * N)-1; i++)
{
for (int j = 0; j <= (N * N)-1; j++)
{
flag = true;
//peterson solution
for (int l = k; l < lines.Length && flag; l++)
{
if (char.IsDigit(char.Parse(lines[l])))
{
board[i, j] = int.Parse(lines[l]);
flag = false;
}
if (char.Parse(lines[l]) == '.')
{
board[i, j] = 0;
flag = false;
}
k++;
}
}
}
}
IsSolution()
检查数独是否已解决？为此，它使用了四个辅助函数。这四个方法的性能如下：
IsComplete()：此方法用于所有数组元素。isRowCheckUnique()：此方法用于原始数组的所有行进行唯一性检查。isColCheckUnique()：此方法用于原始数组的所有列进行唯一性检查。isCubeUnique()：此方法用于每个 3x3 的方块进行唯一性检查。
以上四个数独求解方法，如果答案为True。
// check sudoku is solved? if true return true
public bool isSolution()
{
if (isComplete() && isRowCheckUnique() && isColCheckUnique() && isCubeUnique())
{
return true;
}
return false;
}
//check board array is complete by number?
public bool isComplete()
{
for (int i = 0; i <= (N * N)-1; i++)
{
for (int j = 0; j <= (N * N)-1; j++)
{
if (!(board[i, j] <= 9 && board[i, j] >= 1))
{
return false;
}
}
}
return true;
}
//values in rows is unique? use check value array for true or false
public bool isRowCheckUnique()
{
for (int i = 0; i <= (N * N)-1; i++)
{
for (int j = 0; j <= (N * N)-1; j++)
{
//checkValue[0] = true;
if (checkValue[board[i,j]] == true)
{
checkValue[board[i,j]] = false;
}
else
{
return false;
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
}
return true;
}
//values in columns is unique? use check value array for true or false
public bool isColCheckUnique()
{
for (int i = 0; i <= (N * N)-1; i++)
{
for (int j = 0; j <= (N * N)-1; j++)
{
if (checkValue[board[i,j]] == true)
{
checkValue[board[i,j]] = false;
}
else
{
return false;
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
}
return true;
}
//this method check every 3*3 is 1..9 value?
//if is unique return true.
public bool isCubeUnique()
{
#region iscubeunique
//1,1
for (int i = 0; i <= 2; i++)
{
for (int j = 0; j <= 2; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
//1,2
for (int i = 0; i <= 2; i++)
{
for (int j = 3; j <= 5; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
//1,3
for (int i = 0; i <= 2; i++)
{
for (int j = 6; j <= 8; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
//2,1
for (int i = 3; i <= 5; i++)
{
for (int j = 0; j <= 2; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
//2,2
for (int i = 3; i <= 5; i++)
{
for (int j = 3; j <= 5; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
//2,3
for (int i = 3; i <= 5; i++)
{
for (int j = 6; j <= 8; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
//3,1
for (int i = 6; i <= 8; i++)
{
for (int j = 0; j <= 2; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
//3,2
for (int i = 6; i <= 8; i++)
{
for (int j = 3; j <= 5; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
//3,3,
for (int i = 6; i <= 8; i++)
{
for (int j = 6; j <= 8; j++)
{
checkValue[0] = true;
if (checkValue[board[i, j]] == true)
{
checkValue[board[i, j]] = false;
}
else
{
return false;
}
}
}
for (int k = 0; k <= 9; k++)
{
checkValue[k] = true;
}
return true;
#endregion
}
三维数组 InnerCandidateValue
此数组用于存储每个候选元素的值。考虑到原始的 81 个单元格，每个单元格都必须具有唯一的值，一个三维数组将这些值放置在正确的位置。
//candidate value global list
int[,,] InnerCandidateValue = new int[10, 10, 11];
FillCandidateValue()
此方法用于为候选值填充候选数组。
//inner candidate value fill
public void FillcandidateValue()
{
//fill candidate value in inner list
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
for (int k = 0; k < 11; k++)
{
InnerCandidateValue[i, j, k] = k;
}
}
}
}
SolvedSudoku()
此方法用于求解不完整的数独。这是程序的一部分。在该方法中，主数组中不完整元素的数量是候选数组的数量。主数独数组中的三个条件被用于将候选的正确值放在下一个空白处。需要再次检查以替换新值的候选数组。最后，在空白元素中找到正确的值，并利用有目标地搜索来求解数独。
//this method solve sudoku by Informed solution
public void SolvedSudoku()
{
FillcandidateValue();
//solve
for (int i = 0; i <= (N * N) - 1; i++)
{
for (int j = 0; j <= (N * N) - 1; j++)
{
if (board[i, j] == 0)
{
for (int l = 0; l <= 8; l++)
{
board[i, j] = InnerCandidateValue[i, j, l+1];
if ((isOneRowCheckUniqe(i) && isOneColCheckUniqe(j) && isCubeUnique()))
{
l = 10;
}
}
}
}
}
}
最后，演示层将显示完整的值。这与空数组一起显示。最后，将显示程序的解算数组。每个表格的IsSolution()函数用于检查并确保程序的正确性。此外，在开始和结束时，会以毫秒为单位显示系统处理该问题所需的时间。
OutPut.Text = SUdok.Show();
lblissolution.Text = Convert.ToString(SUdok.isSolution());
SUdok.SolvedSudoku();
lblissolution2.Text = Convert.ToString(SUdok.isSolution());
lblOutput2.Text = SUdok.Show();
Time = string.Empty;
Time = DateTime.Now.Minute.ToString() + " " +
DateTime.Now.Second.ToString() + " " + DateTime.Now.Millisecond.ToString();
lblTimeEnd.Text += Time;
Using the Code
要使用该代码，请创建一个 Windows Forms 项目，并将 Sudoku 类添加到其中。将类的输入值放入Temp变量中。例如，一个截断的数独已放入此变量。
输出格式如下所示：
历史
- 发布时间：2011 年 7 月 18 日，下午 13:00