[讨论]破解数独的算法

cheelumbill

尽量使用hash重判，set很慢（set也是hash存储的），还有测试的CPU主频多少？

决大多数的数独题需要讨论枚举的情况都很少，是不是可以先建个引导函数，然后再搜索呢？

leesoft

我和一个朋友在去年已经编出LavaX版的解数独程序。我提出的思路，程序是他写的。

Eastsun

写了一个...基于栈的算法...




28楼有更新

[此贴子已经被作者于2006-6-5 15:53:31编辑过]

wqx1

可是拿到星星上速度就慢了!

10S?

P.S:建议增加强行跳出,都死机了...

Eastsun

WQX的CPU频率为10MHZ不到，电脑的CPU为1GHZ多。。。

相差不知多少。。。

加上强行跳出速度就更慢了。


这个程序只是用来说明一下算法的可行性，并没有想要用到wqx上去（我用NC3000测试了下，一分钟内可以做一些简单的题)

cheelumbill

这种问题，没有编不编得出来，只有编得好不好。

我又想到一个东西，n皇后上的Hash重判，好像很像啊。

栈是递归搜索的必然结果。

wqx1

楼上的指的是
N个人,每隔M次"删除"一个人,最后求最后剩余的人的位置吗?

请问如果处理?(我就这个不太会)

Eastsun

另外这个题目完全不需要用hash判重，那样只会降低程序的运行效率。

wqx1

那楼上有方法吗?

提供代码或程序?

cheelumbill

9楼，但是每添一个数就对整行整列标记不可使用也很费时间？两者这个问题差不多吧。

8楼，n皇后不是约瑟夫。

Eastsun

呵呵,谁说一定要用整数来标记呢^_^

对这个问题而言,可以用其它的方法.

wqx1

发现BUG

从报纸上找到个题

输入

出现结果不同

TRY AGAIN

死机,无反应长达10几分钟...

wqx1

11楼的

我说的问题可以解吗?

QQ:601041474

P.S:EASTSUN可以提供新版本吗?(修改的)

cheelumbill

约瑟夫应该和这个问题还是有距离的。

12楼能不能解释一下你的话？（尤其是什么叫“一定要用整数来标记”中的“整数”）

wqx1

有没有方法解释约瑟夫问题呢?

很感兴趣啊(P.S:我没说和这有关啊,只是说下)

Eastsun

以下是引用wqx1在2006-5-24 18:49:00的发言：[BR]发现BUG

从报纸上找到个题

输入

出现结果不同

TRY AGAIN

死机,无反应长达10几分钟...

是吗？你从新下载一次试试。

结果不同不一定说明不对啊，如果确实不对，把测试的数据发上来看看。

附：约瑟夫问题的两种算法

1. /**
   
2. @最简单的解法，用数组模拟，但效率低
   
3. @Author :Eastsun
   
4. @Version:1.0
   
5. @Date   :06.5.31
   
6. */
   
7. #define MAX 10000
   
8. char buf[MAX];
   
9. int solve(int n,int m){
   
10.     //注意，人的编号从0开始；如果是从1开始，返回值加1即可
    
11.     int count,num,index;
    
12.     if(n>MAX) return -1;
    
13.     count =n;
    
14.     index =0;
    
15.     num   =1;  //从1报数
    
16.     memset(buf,1,n);
    
17.     while(count>1){
    
18.         if(buf[index]){//有人
    
19.             if(num==m){//
    
20.                 buf[index] =0; //去掉该人
    
21.                 num =1;   
    
22.                 count--;
    
23.             }
    
24.             else num++;
    
25.         }
    
26.         if(index==n-1) index =0;
    
27.         else           index++;
    
28.     }
    
29.     for(index =0;buf[index]==0;index++);
    
30.     return index;
    
31. }
    
32. void main(){
    
33.     printf("%d",solve(100,99));
    
34.     getchar();
    
35. }

复制代码

1. /**
   
2. @解法二，时间复杂度为O(n)
   
3. @Author  :Eastsun
   
4. @Version :1.0
   
5. @Date    :06.5.31
   
6. */
   
7. int solve(int n,int m){
   
8.     int result,num;
   
9.     for(num =1;num<=n;num++) result=(result+m)%num;
   
10.     return result;
    
11. }
    
12. void main(){
    
13.     printf("%d",solve(100,99));
    
14.     getchar();
    
15. }

复制代码

wqx1

结果貌似也算对的,数独有多重结果啊

不过关于输入同一个数据,每次运行反应大不相同,这非常奇怪啊...

谢谢啦!

wqx1

那个

约瑟夫的代码是可以在LAVA上编译,可是输入呢?

要每隔M个人然后共N人呢?

在哪里呢?(输入就出现一个87)

Eastsun

以下是引用wqx1在2006-6-2 18:25:00的发言：[BR]
不过关于输入同一个数据,每次运行反应大不相同,这非常奇怪啊...

那个程序我中间修改过一次,一开始的有个小BUG,不知道你下的是那个.

ps:最好在电脑上的虚拟机上运行,除非你耐心足够好.

Eastsun

以下是引用wqx1在2006-6-2 18:33:00的发言：[BR]那个

约瑟夫的代码是可以在LAVA上编译,可是输入呢?

要每隔M个人然后共N人呢?

晕~,解约瑟夫问题的函数就是solve(int n,int m) (其中n就是总人数).

输入与输入你自己去写啊.
[em10]