数独解算器和生成器(译文)
By robot-v1.0
本文链接 https://www.kyfws.com/games/sudoku-solver-and-generator-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 7 分钟阅读 - 3359 个词 阅读量 0数独解算器和生成器(译文)
原文地址:https://www.codeproject.com/Articles/11983/Sudoku-Solver-and-Generator
原文作者:Jörgen Pramberg
译文由本站 robot-v1.0 翻译
前言
Solves and generates Sudokus
解决并生成数独
介绍(Introduction)
前一段时间,我的一位同事向我介绍了一款名为Sudoku的游戏.我对这个游戏一无所知,但是很快就解释了规则,然后很快意识到,为此编写程序比解决一个难题要快得多!(A while back, a colleague of mine introduced me to a game called Sudoku. I was totally ignorant of this game, but soon got the rules explained and then realized pretty quickly that it would be a lot faster to make a program for this than solve even one single puzzle!)
数独规则(Sudoku Rules)
Sudoku的规则很简单.您有一个具有9x9单元的电路板,该电路板又分为9个子正方形,每个子正方形具有3x3单元.在每个子正方形的垂直和水平线上,您都必须将数字1-9放置一次,并且只能放置一次.(The rules for Sudoku are simple. You have a board with 9x9 cells, the board is further divided into nine sub squares with 3x3 cells each. In every sub square, in vertical and horizontal lines, you have to put the numbers 1-9 once and only once.) 创建数独时,我们必须记住,只能有一个解决方案,否则就算不上真正的数独.(When creating a Sudoku, we must keep in mind that there can be only one solution for it, otherwise it is not considered a real Sudoku.)
解决难题(Solve the Puzzle)
当类被初始化并且数独难题已经设置好要解决时,我们可以让函数(When the class is initialized and a Sudoku puzzle has been set to solve, we can let the function) Solve()
开始业务.在每次迭代中,我们都希望在板上找到具有最大信息的位置.我们从初始设置开始(start its business. In each iteration, we want to locate the spot on the board with the maximum information. We start with an initial set) M
以及所有可能的解决方案:(with all possible solutions for the spot:)
// Set M of possible solutions
byte[] M = {0,1,2,3,4,5,6,7,8,9};
然后,我们在垂直方向上删除所有使用的出现:(We then remove all the used occurrences in the vertical direction:)
for(int a = 0; a < 9; a++)
M[m_sudoku[a,x]] = 0;
和水平方向:(and the horizontal direction:)
for(int b = 0; b < 9; b++)
M[m_sudoku[y,b]] = 0;
最后,我们删除子正方形中所有已使用的事件.为了加快可行性测试并简化代码,我决定为子正方形使用查找表.首先,通过使用将位置映射到子正方形的表,从当前位置获取子正方形表的索引:(Last, we remove all the used occurrences in the sub square. To speed up the feasibility test and simplify the code, I decided to use look-up tables for the sub squares. First, we get an index into the sub square table from our current position by using a table that maps locations to sub squares:)
int squareIndex = m_subSquare[y,x];
然后,使用子索引数组将实际位置放入二维数组中:(Then we get the actual position into the two-dimensional array by using a sub index array:)
EntryPoint p = m_subIndex[squareIndex,c];
最后一个代码段在循环中使用,该循环删除正方形中所有出现的事件:(This last code snippet is used inside a loop that removes all occurrences in the square:)
for(int c = 0; c < 9; c++)
{
EntryPoint p = m_subIndex[squareIndex,c];
M[m_sudoku[p.x,p.y]] = 0;
}
然后,我们计算集合的基数(We then calculate the cardinality of the set) M
:(:)
int cM = 0;
for(int d = 1; d < 10; d++)
cM += M[d] == 0 ? 0 : 1;
如果当前集合的基数小于之前的最小基数,则到目前为止,当前点是最佳评估的:(If the cardinality of the current set is less than the smallest before that, the current spot is the best evaluated so far:)
if(cM < cMp)
{
cMp = cM;
Mp = M;
xp = x;
yp = y;
}
最小基数(The smallest cardinality) cMp
最初设置为(was initially set to) 10
如果没有更改,我们可以确定板上没有空白点,我们可以成功退出:(and if that hasn’t been changed, we can be certain that there are no empty spots on the board and we can exit successfully:)
if(cMp == 10)
return true;
另一方面,如果最小集合的基数是(On the other hand, if the cardinality of the smallest set was) 0
,即有一个空集(, i.e., there was an empty set) M
对于可行的元素,我们可以确定没有解决方案,我们必须回溯:(of feasible elements, we can be sure that there isn’t a solution and we have to back track:)
if(cMp == 0)
return false;
当所有基本情况都考虑在内后,我们就可以开始尝试该过程中每个元素的迭代过程.(When all the base cases have been accounted for, we can start the iterative process that tries every element of) M
反过来:(in turn:)
for(int i = 1; i < 10; i++)
{
if(Mp[i] != 0)
{
m_sudoku[yp,xp] = Mp[i];
if(Solve())
return true;
}
}
// Restore to original state.
m_sudoku[yp,xp] = 0;
return false;
循环用的每个元素替换未使用的点(The loop replaces the unused spot with each element of) M
依次尝试以递归方式解决.什么时候(in turn and tries to solve in a recursive manner. When) M
精疲力尽,我们回来(gets exhausted, we return) false
表示没有解决方案.如果函数成功返回,则可以在(indicating there is no solution. If the function returned successfully, a solution can be read in the) Data
属性如示例所示:(property as in the example:)
...
Sudoku s = new Sudoku();
s.Data = SudokuToSolveFor;
if(s.Solve())
byte[,] SudokuSolved = s.Data;
else
// No solution
...
产生数独(Generate a Sudoku)
我很快意识到,手工输入Sudokus太无聊了,并开始执行生成它们的任务.我的要求是您应该能够指出应该填充多少点并给出可能的开始模式.如果可能的启动模式在第一次尝试中没有解决(I soon realized that it was too boring entering Sudokus by hand and set for the task to generate them. My requirements were that you should be able to indicate how many spots should be filled in and give a possible start pattern. If the possible start pattern didn’t work out on the first try)它可能会被丢弃,并会生成一个全新的模式,否则我们可能会陷入一个没有解决方案的模式,并考虑整个Sudoku空间的大小,这是非常糟糕的复杂性;(it could be thrown away and an entire new pattern could be generated, otherwise we might be stuck with a pattern that doesn’t have a solution, and considering the size of the entire Sudoku space that is quite bad complexity wise)程序将执行一定数量的重试.(the program does a set number of retries.)
功能(The function) Generate(int nodes, int numberOfTries = 1000000)
是所有功能所在的位置.我们首先计算当前数据集中使用了多少个斑点(is where all the functionality is located. We start by calculating how many spots are used in the current data set)然后决定我们是否要重新开始(and then decide whether we’ll start up fresh or)然后生成一个完整的新数独:(and then generate an entire new Sudoku:)
int num = GetNumberSpots();
if(!IsSudokuFeasible() || num > nodes)
{
// The supplied data is not feasible, clear data.
// - or -
// The supplied data has too many nodes set, clear data.
return Tuple.Create(0L, false);
}
生成设定数量的斑点,然后测试数独的唯一性:(The set number of spots are generated and then the Sudoku is tested for uniqueness:)
do
{
var originalData = Data;
long tries = 0;
for (; tries < numberOfTries; tries++)
{
// Try to generate spots
if (Gen(spots - num))
{
// Test if unique solution.
if (IsSudokuUnique())
{
return Tuple.Create(tries, true);
}
}
// Start over.
Data = originalData;
}
return Tuple.Create(tries, false);
这个循环继续(This loop goes on)直到找到解决方案(forever until a solution has been found)设定的迭代次数.如果我们想在搜索中途中止,这里还有改进的余地.的(for the set number of iterations. There is room for improvement here if we want to be able to abort in mid search. The) Gen(int spots)
功能通过在9x9板上产生随机斑点开始.为了在单元测试中获得确定性,随机生成器实现了(function starts by generating a random spot on the 9x9 board. To get determinism in the unit tests, the random generator implements the) IRandomizer
接口,在生产中不确定,但对于单元测试则是确定的.(interface and is nondeterministic in production but deterministic for unit tests.)
do
{
xRand = Randomizer.GetInt(9);
yRand = Randomizer.GetInt(9);
} while(m_sudoku[yRand,xRand] != 0);
对于每个随机点,我们都必须检查可行值,几乎采用与求解器相同的方式进行:(For each randomized spot, we have to check for the feasible values, pretty much done in the same style as in the solver:)
// Set M of possible solutions
byte[] M = {0,1,2,3,4,5,6,7,8,9};
// Remove used numbers in the vertical direction
for(int a = 0; a < 9; a++)
M[m_sudoku[a,xRand]] = 0;
// Remove used numbers in the horizontal direction
for(int b = 0; b < 9; b++)
M[m_sudoku[yRand,b]] = 0;
// Remove used numbers in the sub square.
int squareIndex = m_subSquare[yRand,xRand];
for(int c = 0; c < 9; c++)
{
point p = m_subIndex[squareIndex,c];
M[m_sudoku[p.x,p.y]] = 0;
}
int cM = 0;
// Calculate cardinality of M
for(int d = 1; d < 10; d++)
cM += M[d] == 0 ? 0 : 1;
如果基数大于零,我们从可行集中获得一个随机样本(If the cardinality is larger than zero, we get a random sample from the feasible set) M
:(:)
if(cM > 0)
{
int e = 0;
do
{
// Randomize number from the feasible set M
e = Randomizer.GetInt(1,10);
} while(M[e] == 0);
// Set number in Sudoku
m_sudoku[yRand,xRand] = (byte)e;
}
如果设置(If the set) M
为空,这不能是Sudoku,我们重新启动该过程,直到找到一个非空集(is empty, this can’t be a Sudoku and we restart the process until we find a non-empty set) M
.当所有给定的斑点都生成后,我们尝试功能的唯一性(. When all the given spots have been generated, we try for uniqueness in the function) TestUniquness()
.唯一性测试是通过尝试生成多个解决方案来完成的.一旦存在多个,则生成的集合将不可行,并且将生成一个新的集合:(. The test for uniqueness is done by trying to generate more than one solution; as soon as more than one exists, the generated set will not be feasible and a new one is generated:)
... // same as in Solve()
int success = 0;
for(int i = 1; i < 10; i++)
{
if(Mp[i] != 0)
{
m_sudoku[yp,xp] = Mp[i];
switch(TestUniqueness())
{
case Ret.Unique:
success++;
break;
case Ret.NotUnique:
return Ret.NotUnique;
case Ret.NoSolution:
break;
}
// More than one solution found?
if(success > 1)
return Ret.NotUnique;
}
}
...
switch(success)
{
case 0:
return Ret.NoSolution;
case 1:
return Ret.Unique;
default:
// Won't happen.
return Ret.NotUnique;
}
样品申请(Sample Application)
为了演示如何使用该类,我使用Windows窗体制作了一个小型的基本应用程序.由此,您可以生成,求解,打印,加载和保存Sudokus.(To demonstrate how to use the class, I have made a small, rudimentary application using Windows Forms. From this, you can generate, solve, print, load and save Sudokus.)
历史(History)
-
31(31)圣(st)2010年7月-文章更新(July, 2010 - Article update)
- 提交了已存在大约五年的错误修复程序(Submitted a bug fix that has been lying around for about five years)
- 迁移到Visual Studio 2010和.NET 4.0的解决方案(Migrated solution to Visual Studio 2010 and .NET 4.0)
- 将解决方案分为三个程序集(Split the solution in three assemblies)
- 添加了元组和可选参数(C#4.0)(Added tuples and optional parameters (C# 4.0))
- 添加了单元测试((Added unit tests ()
Microsoft.VisualStudio.TestTools.UnitTesting
)())
-
18(18)日(th)2005年10月-文章提交(October, 2005 - Article submission)
-
2(2)nd(nd)2005年10月-Windows Forms框架(October, 2005 - Windows Forms framework)
-
25(25)日(th)2005年9月-数独课(September, 2005 - Sudoku class)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
C# .NET .NET4 Windows VS2010 Visual-Studio Dev 新闻 翻译