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

[yhz012]

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

 

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

四月 28, 2020，由yhz012修改

[yhz012]

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

不是的哟（笑

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

[yhz012]

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

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

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

我大概理解你说的意思了

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

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

 

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

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

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

 

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

 

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

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

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

四月 28, 2020，由yhz012修改

[yhz012]

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

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

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

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

但是这样做不有趣（