娱乐 每日算法挑战·第16期题解

[Mr.K 018]

召唤 @yhz012

这个题我觉得就是那种很狗的题。

做之前：？？？这也能做？

做之后：？？？就这？

解这个题需要对数独终局的两条引理：

引理1. 任意给定数独的第一行，可以构造出至少一个合法的数独终局。（实际上某一行即可，这里为了简便，就说是第一行）

怎么构造呢？可以像这样构造：

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

可以看出，这么构造过之后每一行、每一列、每一个九宫格之内1-9都恰好出现了一次。

这样的话，由于左上角的值不能变，剩下八个数能产生8!=40,320种排列。到这里还不够两百万，为了达到我们二百万终局的目标，我们还需要引理2.

引理2. 任给一个合理的数独终局，重新排列这个终局的前三行，所得终局仍然相同；对中间三行和后三行也成立。

举个例子：把上例中的第4行和第6行交换，得到的数独终局仍然合法；或者说，把7，8，9行重新排列成9，8，7行，得到的新数独终局仍然成立。

由于第一行有限制，它只好继续呆在第一行，因此前三行有2种排法；中间三行和后三行没什么限制，分别可以产生6种排法。

这样的话，任给一个数独终局，我们能构造出2*6*6=72个数独终局（包括给的那个终局）。

 

并用引理1和引理2，我们就能用这样的很简单的操作构造出多达72*40,320=2,903,040种不同的数独终局！

事实上，中间三行和后三行是可以整体交换的，这样可以构造出的数独终局数量还能再加倍。不过我们只要两百万种，不这么交换也够用了。

 

这样，我们就给出了能过掉normal的算法。当然，这个算法稍微做一点优化（主要是磁盘IO方面的），也是可以过掉hard和extreme难度的。实际上如果这个算法都过不掉的话，很难想象还有什么算法能过掉了，毕竟这道题输出量是非常大的……

算法大意如下：

1. 首先构造出初始的第一行：从1排到9，然后把需要在左上角的那个数换过去。

2. 对第一行剩下8个数进行全排列，对每一个排列进行下述操作：

2.1 按照引理1提供的方法填满其余的格子；

2.2 按照引理2排列各行，输出之，直到输出数量够为止。

 

最后再说一下怎么就优化吧。这一部分其实不是算法本身关注的重点，不过还是简单说一下。

首先按照上面算法直接写，用C++的输入输出库的话，可以搞定normal难度，但是hard难度是跑不通的。

第一步优化：扔掉所有C++输入输出方法，改用C语言的输出函数。这比C++的同样方法快得多。（所以说这里的优化都是一些无聊的小细节）

第二步优化：不要每输出一个数字就调用一次C语言输出函数，而是每输出一次数独调用一次。这样可以大幅减少函数调用的次数。（无聊细节+1）到此可以过掉hard难度。

第三步优化：其实交换两行的时候，不用整个一起交换的。可以记录一个“行索引表”，对行的交换只在索引表上进行。这需要对算法进行一些修改。

第四步优化：连C语言的输入输出函数都扔掉，而是直接用Windows的API。Windows的文件映射功能可以让程序可以像访问内存一样访问文件，进一步提高了磁盘的利用效率。这样，extreme难度也可以过掉了。

相比算法本身来说，这个优化过程就显得平凡很多了。而且在OJ平台上也没有Windows API可以调用不是么（笑

[Mr.K 018]

9 小时前, yhz012 说道:

我怎么就想不到交换三行内呢

学到了学到了

 

前两步优化能想到，第三步优化会做不过未必想得到，第四步优化我是真的不会

关于第四步优化，可以参考MSDN上的介绍：

https://docs.microsoft.com/en-us/windows/win32/memory/creating-a-file-mapping-object

真的就是字面意义上的，像访问数组一样访问文件内容……

[Mr.K 018]

2 分钟前, yhz012 说道:

感谢，学到了全新的技巧，之前是真的不知道有这种功能

我刚才看了下，好像Linux也有做这事的API，貌似是mmap