|
摘 要 回溯法通过问题中的约束条件以试探-回溯-试探的筛选方式，将所有解的范围中不符合约束条件的解予以排除，从而达到快速求解的目的。本文以数独问题为模型，论述了回溯法在数独问题解法中的运行原理。
关键词 数独；回溯法；高维数组；C#
一、数独
数独是18世纪瑞士数学家发明的一种数字游戏。如图1示，数独共由9个小的3×3格组成。预先在其中的某些空格中填有一些数字，要求游戏者按照规则填完其他的空格。
图1
规则如下：
（1）每个空格内所填的数字只限于1-9之间
（2）每个数字在每一个行中只能出现一次
（3）每个数字在每一个列中只能出现一次
（4）每个数字在每一个同底色区域内(3×3的小九宫)只能出现一次
二、回溯法
回溯法是一种搜索算法，其基本思路是：在一个问题中，根据题意给出的边界条件划定出所有可能解的范围（称为可能解），根据题意确定出约束条件。利用程序顺次在所有可能解中,搜索时按照深度搜索的方式进行。即在第一层选定一个满足约束条件的解，然后以该可能解为出发点，搜索第二层的一个可能解（试探）。如果搜索到第二层的一个可能解，则继续搜索第三层的一个可能解。依次类推，直到所有层的可能解都被找到，则得到了该问题的一个完整解。如果第二层所有的可能解都不满足约束条件，则返回第一层，放弃原有的可能解，使用第一层的下一个可能解（回溯）。以此类推，寻找第二层的一个可能解。
由于回溯法是在不断地试探和回溯中运算，因此也可以称为试探法或者试探——回溯法。
从上面的描述中可知，回溯法得到的问题的解只是根据不同的初始条件获得的第一个完全满足所有约束条件的解，因此该解的获得和初始条件有关。如果想要获得该问题的全部解，则需要遍历所有的可能的初始条件，也就是遍历所有的第一层的可能解。
回溯法相对于其他穷举的特点在于，不必把问题的每一层的所有的可能解都遍历一遍，只要当前的可能解不满足约束条件就抛弃该解，寻求下一个可能解，而不必求解其余的下层解。当当前层的所有可能解都不满足约束条件，则回溯到上一层，抛弃上一层的当前可能解。
从以上分析中结合数独问题的规则，得出数独问题的约束条件为：
（1）每一格的数值范围仅限于1-9。
（2）每一格内的数字在当前行不允许重复。
（3）每一格内的数字在当前列不允许重复。
（4）每一格内的数字在当前小九宫内不允许重复。
三、数独解法
1.变量设置
由于数独表由大九宫和小九宫两部分组成，且考虑到在运算中需要比较小九宫内数字的重复情况，因此将一个数独设置成一个4维数组。其中4维数组的前2维表示该数字在大九宫中所处的位置，而4维数组的后2维则表示了该数字在当前的小九宫中所处的位置。
/// <summary>
/// 数字表格
/// </summary>
private int[, , ,] sd;
为了在运算中保持原始数独题目的原貌，因此，设置一个和sd相同的数组process_sd，将所有的解题运算放置到该变量中。
/// <summary>
/// 处理表格
/// </summary>
private int[, , ,] process_sd;
由于在回溯中，已经给定的初始值不允许被回溯，为了防止题目中给定的初始值被回溯或者试探掉，因此设置一个bool型的4维数组bk_sd，大小和sd相同。bk_sd中每个位置的每一个值和sd对应位置的值对应，如果是初始状态中给定的值，则将bk_sd中该位置设置成true，在今后的试探或者回溯运算中凡是遇到该值，则一律跳过不予试探或者回溯。
/// <summary>
/// 背景表格
/// </summary>
private bool[, , ,] bk_sd;
在回溯中需要判断合适到达出口或者如果问题无解则何时回溯到初始状态，因此在本问题中设置一个步骤计数器step，初始值为0。每次成功在数组中设置了一个满足约束条件的数时，则step+1，如果本层所有的试探都不成功，需要返回溯到上一层，重新设置上一层的数字，则step-1。由此我们可以知道，当除初始状态中已经设置过的值外，step达到81-1-初始状态个数时，数组内的所有元素内均已被设置了符合约束条件，则说明找到了问题的出口。反之当所有的第一层初始条件均已被试探过后，程序将会回溯到比第一层更上层的情况时，此时step小于初始值0，则说明该问题无解。
由于问题获得解的step的值和初始状态的个数有关，因此在对象初始化时，另设一个初始状态个数init_count。
/// <summary>
/// 数独问题初始固定的个数
/// </summary>
private int init_count = 20;
2.约束条件（约束函数）
根据前面的分析，在本问题中共有4个约束条件，即：
（1）每一格的数值范围仅限于1-9。
（2）每一格内的数字在当前行不允许重复。
（3）每一格内的数字在当前列不允许重复。
（4）每一格内的数字在当前小九宫内不允许重复。
其中第一个约束条件“每一格的数值范围仅限于1-9”将其作为后面试探/回溯操作的步进条件，则剩下的2-4条约束条件，将其细化成相应的约束函数。
⑴当前位置设置的数值是否和当前的小九宫中的已设置数值重复。
/// <summary>
/// 检查某元素在小九宫中是否有重复
/// </summary>
/// <param name="i">小九宫的行号</param>
/// <param name="j">小九宫的列号</param>
/// <param name="k">元素在小九宫内的行号</param>
/// <param name="l">元素在小九宫内的列号</param>
/// <param name="temp_arr">待比较4维数组本身</param>
/// <returns>是否重复,重复：true,不重复：false</returns>
private bool CheckInSmall(int i, int j, int k, int l,ref int[,,,] temp_arr)
{
bool isRepeat = false;
for (int k1 = 0; k1 < ROWS; k1++)
{
for (int l1 = 0; l1 < COLUMNS; l1++)
{
if (k == k1 && l == l1)//跳过自身
{
continue;
}
else
{
if (temp_arr[i, j, k, l] == temp_arr[i, j, k1, l1])
{
return true;
}
}
}
}
return isRepeat;
}
|
