|
⑷试探/回溯步进调整。
步进就是当本位置设置的值符合约束函数的约束，需要进入到下一个位置的条件设定，或者本位置的所有可能都已经遍历未发现符合条件的解，需要回溯到上一个位置，此时调整数组位置就称之为步进。本程序的步进调整按照4维数组的维数从后向前依次调整的方式进行调整，也就是按照每个小九宫中的每个元素从列到行依次步进，每个小九宫在大九宫中也按照此原则依次步进。
/// <summary>
/// 调整回溯值
/// </summary>
/// <param name="i">原始i</param>
/// <param name="j">原始j</param>
/// <param name="k">原始k</param>
/// <param name="l">原始l</param>
/// <param name="addition">l的步进值，正为后移，负为回溯</param>
private void ResetIJKL(ref int i, ref int j, ref int k, ref int l, int addition)
{
int i1 = i;
int j1 = j;
int k1 = k;
int l1 = l;
int l2 = l1 + addition;
while (true)
{
if (l2 >= COLUMNS) //l到达尾部
{
l2 = 0;
k1++;
}
else
if(l2<0) //l到达头部
{
l2 = COLUMNS - 1;
k1--;
}
…
在步进中会遇到几个问题，第一是数组越界，如果步进（含试探步进和回溯）到下一个位置恰好超出了大小九宫的行、列尽头，则按照上述代码的方式依次调整位置。
…
if (i1 >= ROWS||i1<0) //i到达头部或者尾部 结束
{
i = i1;
j = j1;
k = k1;
l = l2;
return;
}
在步进中，遇到的第二个问题就是步进到整个数组的开头或者尽头。此时将不再步进，返回原值。
if (bk_sd[i1, j1, k1, l2] == true) //如果回溯的上一个位置为不可移动的固定位，则继续步进
l2 += addition;
else
break;
}
…
}
在步进中会遇到第三个问题是步进到的下一个位置恰好是初始设置，该位置的值不能改变，因此步进将跳过该位置，步进到该位置前或者后一个位置去。
⑸回溯法获得数独问题的一个解。
/// <summary>
/// 获得数独的一个解
/// </summary>
/// <returns></returns>
public int ComputeShudo()
{
///回溯法步骤计数，当初始状态的所有可能全部遍历
///则该问题无解
int step = 0;
int i = 0;
int j = 0;
int k = 0;
int l = 0;
bool IsInSmall = false;//当前元素的值是否存在于小九宫中
bool IsInRow = false;//当前元素的值是否存在于行中
bool IsInColumn = false;//当前元素的值是否存在于列中
while ((step >= 0 && process_sd[i, j, k, l] <= MAX_NUM) && (i < ROWS && j < COLUMNS && k < ROWS && l < COLUMNS))
//回溯循环结束的条件（无解条件）：1，数组越界；2，当前位置的值超出0-9的范围；3，回溯步骤归零（回溯到开始状态）
{
if (bk_sd[i, j, k, l])//当前格为固定格
{
ResetIJKL(ref i, ref j, ref k, ref l,1);
}
else//当前格为非固定格
{
while (process_sd[i, j, k, l]++ <= MAX_NUM)//当 当前元素的值和其他已知的值都不冲突时，设置值，否则当前元素的值+1继续测试
{
IsInSmall = CheckInSmall(i, j, k, l, ref process_sd);
if (IsInSmall)
continue;
IsInRow = CheckInRow(i, j, k, l, false, ref process_sd);
if (IsInRow)
continue;
IsInColumn = CheckInColumn(i, j, k, l, false, ref process_sd);
if (IsInColumn)
continue;
break;
}
if (process_sd[i, j, k, l] <= MAX_NUM)//当前位置所安置的数值位于0-9之间时，准备下一轮试探
{
if (step == 80 - init_count)//当所置的数值的个数达到了规定的个数，则回溯算法结束，获得一个解
{
break;
}
step++;
ResetIJKL(ref i, ref j, ref k, ref l,1);
}
else //当前位置所安置的数值超过0-9的范围外时，准备下一轮回溯
{
process_sd[i, j, k, l] = 0;
step--;
ResetIJKL(ref i, ref j, ref k, ref l, -1);
}
}
if (i >= ROWS)
{
break;
}
}
return step;
}
⑹回溯法获得数独问题的一个解。
如前所述，用回溯法获得的解并非该问题的全部解，为了获得该问题的全部解。在获得一个解的方法基础上，对部分代码进行适当调整从而得到全解方法。
引入一个ArrayList型的对象all_shudo用来存放每一个获得的数独解。
/// <summary>
/// 数独所有解的集合
/// </summary>
private ArrayList all_shudo=new ArrayList ();
同时修改单解方法中的以下部分。
if (step == 80 - init_count)//当所置的数值的个数达到了规定的个数，则获得一个解，将该解置入解集中，同时打印该解，同时在该解的基础上开始回溯，以求得下一个解
{
all_shudo.Add(process_sd.Clone());
ResetIJKL(ref i, ref j, ref k, ref l, -1);
step--;
continue;
}
当获得一个解以后，将这个解存入all_shudo中，同时进行回溯步进，通过改变上一个位置的值进行试探，从而达到回溯到下一个可能解的目的。
四、结论
回溯法通过约束条件的筛选，在所有解中筛除掉不可能的解，从而获得问题的一个或者全部解。通过运用回溯法可以获得数独的一个解或者全部解。
|
