2018.1.16，我看到一道题，它的名字叫做“数独”，问题要求如下：
整个是一个9X9的大宫格，其中又被划分成9个3X3的小宫格。要求在每个小格中放入1-9中的某个数字。要求是：每行、每列、每个小宫格中数字不能重复。
我不知道它应该怎么解，但我知道我可以用回溯法去解决它。于是我打开了两年前算法设计与分析课上的PPT，试图去解决这个问题。以下则是解决这个问题时候的思考和收获：
什么是回溯法？
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
它能干什么？
回溯法有“通解法”之称
回溯法可以系统地搜索一个问题的所有解或任一解.
回溯法是一个既带系统性又带跳跃性的搜索算法.
回溯法是解决较为复杂枚举题的一种常用算法.
怎样去实现它？
用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含一个解。
确定了解空间树后，回溯法从根结点出发，以深度优先方式搜索整个解空间。
用回溯法搜索解答树时，要采用一定策略进行“剪枝”，避免无效搜索，来提高效率。
“剪枝”策略：
（1）用约束函数剪去不满足条件的子树；
（2）用限界函数剪去得不到最优解的子树。
递归回溯框架
void backtrack( int t )
{ if (t>n) Output(x);
else
for(i=f(n,t); i<=g(n,t); ++i)
{ x[t]=h(i);
if(Constrain(t)&&Bound(t) ) backtrack(t+1); }
}
解题思路：
1.初始化一个二维数组，用来存储全部9X9表格数独数据
2.初始化一个一维数组，用来存储所有空位坐标
3.对于每一个空位，填入1-9范围内的随意数，看是否可行：如果可行，把该数填入空位（numMap[x][y]=i），继续搜索下一位，直到step==stalen(当前空位已经是最后空位)时输出解；否则，说明填入该数导致无解，该数及后面填入的数应该全部废弃，numMap[x][y]=0表示全部置空，重新试填其他得数。
trynum(x,y,i)代表是否可以在（x,y）处填入数字i，如果当前行或当前列或当前小九宫里面存在该数字，表示不可行，否则可行。
以上过程其实是一个搜索解的过程。每一个空位都有1-9共九个数值方案，但是根据数独的规则，有些方案是明显不可行的的，我们可以通过该规则进行剪枝操作，即为if (trynum(x,y,i))。
网友评论