[已解决]关于 sfqxx 数独算法的证明

tommyyu

zhangjinxuan 发表于 2023-7-22 15:31
是这样的，这是挖洞法生成题目，因此，需要一个完整的数独作为参考，然后“挖洞”，这样“挖”出来的数独 ...

我感觉他的算法效率保证不了，唯一性也保证不了

tommyyu

zhangjinxuan 发表于 2023-7-22 15:32
这就得不到保证了，就像你在 这篇帖子 的回复一样，充满了随机性，可能跑的很慢，也可能一下子就跑出来了 ...

你的运气不好，我一下子就运行出来了（反正也证明不了）

sfqxx

tommyyu 发表于 2023-7-22 15:32
我感觉他的算法效率保证不了，唯一性也保证不了

6

那你hack一下？没有证据是不行的

陈尚涵

zhangjinxuan 发表于 2023-7-22 15:31
是这样的，这是挖洞法生成题目，因此，需要一个完整的数独作为参考，然后“挖洞”，这样“挖”出来的数独 ...

我有个想法啊，是不是可以限制生成？比如说这一行有1，就不生成1？当然这生成的顺序还没想好

歌者文明清理员

陈尚涵 发表于 2023-7-22 15:35
我有个想法啊，是不是可以限制生成？比如说这一行有1，就不生成1？当然这生成的顺序还没想好

tommyyu

sfqxx 发表于 2023-7-22 15:34
6

那你hack一下？没有证据是不行的

通过你的描述，你的算法是有很小的可能性出现不稳定，我认为这种不稳定性在理论上存在，但是在大部分时间都表现不出来。我们需要的是一个稳定的、有最低效率保证的算法

陈尚涵

tommyyu 发表于 2023-7-22 15:32
我感觉他的算法效率保证不了，唯一性也保证不了

唯一性应该能保证吧？

tommyyu

陈尚涵 发表于 2023-7-22 15:36
唯一性应该能保证吧？

根据他的描述，我认为会在一定的情况下（运气差的时候）保证不了

陶远航

isdkz 发表于 2023-7-22 15:14
我的脚本竟然看懂了你的帖子内容没有回复

啊？你怎么做到的？
我认为是你的prompt里面有“有外部链接导致无法回答的问题，请输出False”等内容

zhangjinxuan

陈尚涵 发表于 2023-7-22 15:35
我有个想法啊，是不是可以限制生成？比如说这一行有1，就不生成1？当然这生成的顺序还没想好

就是这样的啊？

但是如果填着填着，如果这个空放不了任何数字怎么办？

isdkz

陶远航 发表于 2023-7-22 15:37
啊？你怎么做到的？
我认为是你的prompt里面有“有外部链接导致无法回答的问题，请输出False”等内容

说实话我自己也不知道，可能就只是个bug

zhangjinxuan

tommyyu 发表于 2023-7-22 15:28
那如何证明不挖 45 以上空就一定有唯一解？？？
万一刚好把后半段（后面四行）挖走了，那能保证有唯一 ...

你别说，我跑了 5 组数据都是唯一的

陶远航

isdkz 发表于 2023-7-22 15:38
说实话我自己也不知道，可能就只是个bug

啊？这个应该不会吧...

tommyyu

zhangjinxuan 发表于 2023-7-22 15:37
就是这样的啊？

但是如果填着填着，如果这个空放不了任何数字怎么办？

感觉他的几个问题：
1. 证明不了不用 dfs 也能生成数独
2. 证明不了他自己算法的效率稳定性
3. 证明不了他算法生成数独的唯一性

tommyyu

zhangjinxuan 发表于 2023-7-22 15:38
你别说，我跑了 5 组数据都是唯一的

但是我们要证明啊

陈尚涵

zhangjinxuan 发表于 2023-7-22 15:37
就是这样的啊？

但是如果填着填着，如果这个空放不了任何数字怎么办？

确实，可能会出现这种情况
那是不是可以围绕一个点生成几个面？这样是不是能避免？

tommyyu

陈尚涵 发表于 2023-7-22 15:40
确实，可能会出现这种情况
那是不是可以围绕一个点生成几个面？这样是不是能避免？

dfs 是个好东西

zhangjinxuan

tommyyu 发表于 2023-7-22 15:39
感觉他的几个问题：
1. 证明不了不用 dfs 也能生成数独
2. 证明不了他自己算法的效率稳定性

本质上都是要用 dfs，迭代也可以，或许 sfqxx 写的可能是迭代版的 dfs，但是我觉得这样实现很复杂。

是的，这个是证明不了的，因为 sfqxx 他说自己看如果重复了就重新生成，如果一直这样卡，就不行了。

唯一性这个是有点难，我宽限可以不用唯一的，但是他非要钻这个唯一，所以没有办法，只能让大伙评评理了。

zhangjinxuan

tommyyu 发表于 2023-7-22 15:39
但是我们要证明啊

啊对啊，所以这个问题，诶？

“大脑飞速运转中”

zhangjinxuan

hack数据驾到！！！

所有人给我站一边，因为zhangjinxuan我找到hack数据

立正，立正！

因为hack数据他要出现！

把程序WA掉就是帅~

数据帅呆了！

从头帅到脚趾尖

听说程序已经高上天

我就hack了一个又一个！

太牛了！

hack程序从来不用愁！

嘿样样不缺我就有数据！

数据!!!!

噢无法无天神马都是云烟~

噢让程序WA是我的特权~

噢我最大在这里我就是天~

程序管不着我因为我数据~

我数据!

我数据就是很强！！！！

Yeah！

数独（0表示没有数字）：

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

复制代码

存在以下两个解：

1. 6 2 9 3 1 5 8 7 4
   
2. 4 1 7 6 9 8 5 3 2
   
3. 3 5 8 7 4 2 9 1 6
   
4. 9 3 6 8 2 7 1 4 5
   
5. 2 4 1 5 3 9 6 8 7
   
6. 7 8 5 4 6 1 2 9 3
   
7. 5 6 3 1 8 4 7 2 9
   
8. 8 9 4 2 7 6 3 5 1
   
9. 1 7 2 9 5 3 4 6 8
   
10. 
    
11. 
    
12. 6 4 9 3 1 5 8 7 2
    
13. 2 1 7 6 9 8 5 3 4
    
14. 3 5 8 7 4 2 9 1 6
    
15. 9 3 6 8 2 7 1 4 5
    
16. 4 2 1 5 3 9 6 8 7
    
17. 7 8 5 4 6 1 2 9 3
    
18. 5 6 3 1 8 4 7 2 9
    
19. 8 9 4 2 7 6 3 5 1
    
20. 1 7 2 9 5 3 4 6 8

复制代码