娱乐 每 日 算 法 挑 战 【第16期】

[Mr.K 018]

第16期到了！

出题人偷偷地告诉各位，这个题之所以放在这里，是因为它没有看上去那么难哦……

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

第16期 数独终局

各位应该都了解数独。数独的目标是从指定的状态出发，设法解出一个合理的数独终局——即数独棋盘的九行、九列和九个九宫格中，1-9这九个数字都恰出现一次。今天的任务并非给数独求解，而是从空的数独棋盘开始，“从无到有”地生成出数独终局。

并且，我们要生成出许多数独终局，左上角的数字还要求一样。

输入

只有一组测试用例。一行两个整数a和n，分别表示数独终局左上角的数字，和要求给出的数独终局数量。保证1<=a<=9, 1<=n<=2,000,000。

输出

输出所有的数独终局，两个数独终局间空一行。数独终局的形式如下：

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

不要输出到标准输出流中。请输出到文件result.txt。

时间限制

用C或C++编制的程序，时间限制分为三级：

easy：无时间限制
normal：120秒
hard：30秒
extreme：20秒（仅Windows）

想要挑战extreme难度？试试Windows的文件映射相关API，或者换用固态硬盘没错，氪金使人变强

------

虽然有四个模式，但是本题有意思的点都在easy模式和normal模式之间，剩下两个难度都是解决“如何科学地和硬盘打交道”这样的无聊的编程小问题。因此，只考虑算法的话，挑战normal模式就可以了。

各位加油！

[yhz012]

感觉好像是动态规划问题？

 

说起来左上角数字是多少其实无所谓？毕竟对于数独来说，我只需要把123456789映射到abcdefghi上就完了。确定左上角只是确定其中一个数字的映射就完了？

四月 28, 2020，由yhz012修改

[Mr.K 018]

15 分钟前, yhz012 说道:

感觉好像是动态规划问题？

 

说起来左上角数字是多少其实无所谓？毕竟对于数独来说，我只需要把123456789映射到abcdefghi上就完了。确定左上角只是确定其中一个数字的映射就完了？

不是的哟（笑

[yhz012]

30 分钟前, Mr.K 018 说道:

不是的哟（笑

首次题目类型判断失误，完了我这回怕是要彻底回到最暴力的思路开始跑了……

[Mr.K 018]

1 分钟前, yhz012 说道:

首次题目类型判断失误，完了我这回怕是要彻底回到最暴力的思路开始跑了……

这个题跟别的题不一样，这个题更像猜谜（笑

给个提示：注意到这个两百万的数据大小是远远小于可以构造出的全部数独终局数量的，所以说可以找一些有特定规律的……

[yhz012]

2 小时前, Mr.K 018 说道:

这个题跟别的题不一样，这个题更像猜谜（笑

给个提示：注意到这个两百万的数据大小是远远小于可以构造出的全部数独终局数量的，所以说可以找一些有特定规律的……

我大概理解你说的意思了

实际上可以拓展我上面提到的引理，把123456789映射到abcdefghi上就完了

在确定了左上角的情况下，实际上我们还剩下8个数字到字母的映射，总计有8! = 40 320种不同的映射方法。

 

换句话说，我可以用abcdefghi来写数独，称作 “原型”，然后把原型经过映射得到实际的数独，每一个原型可以映射出4万种不同的数独

换句话说我只要有50个原型就已经可以带走了

而50个原型存到内存里并没有难度

 

所以接下来的问题就是我需要编出来这50个了

 

↓问题是我现在还没编出来50个不同的“原型”啊

当然暴力点的做法是直接抄一些现成的数独答案，把里面的数字替换成abcd，看和之前的是否有相同的结构，反正肯定能抄出来50个吧……大概…………

不过我在想有没有更结构化的生成原型的方式

四月 28, 2020，由yhz012修改

[Mr.K 018]

3 小时前, yhz012 说道:

我大概理解你说的意思了

实际上可以拓展我上面提到的引理，把123456789映射到abcdefghi上就完了

在确定了左上角的情况下，实际上我们还剩下8个数字到字母的映射，总计有8! = 40 320种不同的映射方法。

 

换句话说，我可以用abcdefghi来写数独，称作 “原型”，然后把原型经过映射得到实际的数独，每一个原型可以映射出4万种不同的数独

换句话说我只要有50个原型就已经可以带走了

而50个原型存到内存里并没有难度

 

所以接下来的问题就是我需要编出来这50个了

 

↓问题是我现在还没编出来50个不同的“原型”啊

当然暴力点的做法是直接抄一些现成的数独答案，把里面的数字替换成abcd，看和之前的是否有相同的结构，反正肯定能抄出来50个吧……大概…………

不过我在想有没有更结构化的生成原型的方式

少侠，你已经接近答案了✓

[yhz012]

1 小时前, Mr.K 018 说道:

少侠，你已经接近答案了✓

反正最坏情况是我去抄50个数独的原型嘛，这个肯定不难，但是我觉得这个算机械降神的玩法

找原型这个事情我觉得应该是需要一些额外的引理的，当然暴搜+剪枝肯定能做就是了，第一行安排上abcdefghi不变，然后开始搜第二行，第三行这样

但是这样做不有趣（

[Mr.K 018]

16 分钟前, yhz012 说道:

反正最坏情况是我去抄50个数独的原型嘛，这个肯定不难，但是我觉得这个算机械降神的玩法

找原型这个事情我觉得应该是需要一些额外的引理的，当然暴搜+剪枝肯定能做就是了，第一行安排上abcdefghi不变，然后开始搜第二行，第三行这样

但是这样做不有趣（

不会的不会的，不会那么机械无趣的

在思考要不要给第二个提示，不过这个提示给出来跟直接告诉题解也没区别了（

[Mr.K 018]

5 小时前, 莫得姓名 说道:

日常魔鬼，你上辈子一定是困扰大家的三角函数和圆锥曲线

真的有那么魔鬼的嘛？（笑

而且三角函数还好吧，我这里难题都是解析几何和导数……

[inuisanaa]

不对劲啊...F之后应该是10怎么会是16

[Mr.K 018]

11 小时前, inuisanaa 说道:

不对劲啊...F之后应该是10怎么会是16

十进制和十六进制之间反复横跳√