我们在做数独题的时候会大概看一遍整个9×9矩阵,选择一个周围数字比较多的点来,周围的数字越多,这个点上可排除的数字就越多,可能的情况是最少的。
我们就按照人的思路来,先遍历9×9矩阵,选择一个缺少的数字的数量最少的点,当做最优点,“猜”这个点上的数字。
定义一个选点函数:
result=vvnum;
首先需要确定这个这个点上缺少哪些数字,然后对这个点上可能的数字进行一个一个的试。我们首先想到的用一个固定的1-9数组,每当存在一个数字我们就从这个数组中删去这个数字,这个数组上需要的操作只有删除。如果删除数字时可以不用检查数组中是否包含这个数字,操作会方便很多。最后决定选择set作为容器,可以简单且快速的的进行删除
两个函数:
至此主要矛盾已解决,上述代码将递归求解数独矩阵。
我们不能寄希望于用户提供的数字是完美的,相反,用户提供的数字常常可能伴着错误,比如直接在同一行里输入了两个1。如果带着这些错误运行,程序不卡死也会陷入巨大数量的循环中,几乎会对没有提供的数字集合进行一个遍历。假设用户提供了20个数字,其中有一行有两个1,那么程序会对剩下的71个点,每个点有n种(1< n< 9)可能,程序会进行n^71次计算,,最后返回一个0表示失败。这是一个不可能完成的任务。
所以我们需要提前检查错误,发现错误直接返回,不进入递归中。
cout<<"数独非法!在某行中有重复数字!"<<endl;
cout<<"数独非法!在某列中有重复数字!"<<endl;
cout<<"数独非法!在某3×3矩阵中有重复数字!"<<endl;
