[讨论]破解数独的算法

玄狼剑

貌似没有判断小宫格是否重复!

cheelumbill

首页的那个程序bug成堆，根本通不过编译，有些问题出得莫名其妙，没法修正。

Eastsun的程序貌似真有问题。

840300500
009000004
000800100
000010078
300050006
720040000
003002000
600000700
005009041

这是从您提供的网址上下的题，做了后有明显错误。

Eastsun

是么?我试了一下,这是运行结果,貌似没问题啊?





楼主的代码我没仔细看,感觉太繁琐了.

to 玄狼剑 :你说的"没有判断小宫格是否重复"是什么意思?应该不会有这种bug的,不过我现在代码都不知那里去了,没法去找是否有错误.

ps:这次百度之星复赛的第一题"杀人游戏"和约瑟夫环的问题有些相似,我居然做错了,郁闷!

玄狼剑

你一个都不输入，就可以看到你的bug了...

Eastsun

这就是一个都不输入的情况,有什么bug呢?

sun

eastsun, 你的结果中第1小格是847 / 589 / 976, 已分别有2个8,7,9这游戏是不可在同一小格上有相同的数字

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

Eastsun

原来是这样子啊,看来我把游戏规则搞错了,我以为只要每行每列不要出现相通数字就可以了...狂汗...过会再写个.

ps:sun也出现了,难得,呵呵






这是刚写的,规则是每行每列以及每一个小九宫中恰好把1~9出现一次

计算过程中可以按跳出强行跳出,此时会提示"No solution"

[此贴子已经被作者于2006-6-6 20:41:02编辑过]

玄狼剑

可以给出源代码吗？

玄狼剑

或者说一下算法也行

Eastsun

算法没什么好说的,就是深度搜索+剪枝.

wqx1

新的ＢＥＴＡ版本好象还有点问题

在ＮＣ３０００上运行开始下面会出现不规则黑色物体，输入数字后跳出，界面恢复正常

建议把数字输入后移动的延迟加快啊，太慢了．．．

Eastsun

呵呵,那是因为刚进入时没有调用ClearSreen清屏的缘故.

想用就将就着用吧,本来就没想把它做成一个完整的东西.

lufeng369

以下是引用Eastsun在2006-5-31 22:26:00的
@解法二，时间复杂度为O(n)
@Author  :Eastsun
@Version :1.0
@Date    :06.5.31
*/
int solve(int n,int m){
    int result,num;
    for(num =1;num<=n;num++) result=(result+m)%num;
    return result;
}
void main(){
    printf("%d",solve(100,99));
    getchar();
}[/code]

这段程序用来解约瑟夫环问题是错的。。第一result变量没有赋初值。。第二。。这段算法不知所云。。结果是错的。。

lufeng369

经测试Eestsun用数组解第一种约瑟夫环的算法也是错的。。

lufeng369

<FONT size=2>约瑟夫环问题：
N个人，围成一圈，从某一个人开始，沿一个方向每隔M个人，就踢出去一个人，最后剩下的那个人为胜利者。

不知道大家说的“约瑟夫”问题是不是就是这个“约瑟夫环”的问题。。？
如果是的话solve（100，99）的正确答案应该是21才对。。

用C解这个问题比较麻烦。。
用python解就很简单。。

1. 
   
2. 
   
3. def solve(num,intval):
   
4.     #自动身成列表,从0开始 到num-1
   
5.     people=range(num)
   
6.     del_people=intval
   
7.     while(len(people) > 1):
   
8.         del people[del_people]
   
9.         del_people = (del_people + intval) % len(people)
   
10.     return people[0]
    
11. print "the victor is %d"%solve(100,99)
    

复制代码

Eastsun

以下是引用lufeng369在2006-6-17 10:59:00的发言：[BR]


这段程序用来解约瑟夫环问题是错的。。第一result变量没有赋初值。。第二。。这段算法不知所云。。结果是错的。。

呵呵，

第一：在那个循环中，num＝1时，result ＝()%1=0，隐含赋值了。

第二：不知所云是因为你不理解算法的思想。

用python之所以看起来代码简单，因为它提供了一个链表而已，用C＋＋中的STL类库也可以达到同样的效果。

而且，楼上的算法固然容易看懂，也很自然，但效率确很不好。比如算n＝1000000，大概用你的算法就不能在很短的时间内给出结果了。

另外，我从没用过python，但del people[del_people]似乎应该改为del people[del_people－1]才对（纯属猜测，如果错了就错了，^_^）

Eastsun

以下是引用lufeng369在2006-6-17 11:48:00的发言：[BR]<FONT size=2>约瑟夫环问题：
N个人，围成一圈，从某一个人开始，沿一个方向每隔M个人，就踢出去一个人，最后剩下的那个人为胜利者。

不知道大家说的“约瑟夫”问题是不是就是这个“约瑟夫环”的问题。。？
如果是的话solve（100，99）的正确答案应该是21才对。。

用C解这个问题比较麻烦。。
用python解就很简单。。

1. 
   
2. 
   
3. def solve(num,intval):
   
4.     #自动身成列表,从0开始 到num-1
   
5.     people=range(num)
   
6.     del_people=intval
   
7.     while(len(people) > 1):
   
8.         del people[del_people]
   
9.         del_people = (del_people + intval) % len(people)
   
10.     return people[0]
    
11. print "the victor is %d"%solve(100,99)
    

复制代码

约瑟夫环问题：问题描述：n个人（编号0~(n-1))，从1开始报数，报到m的退出，剩下的人继续从1开始报数。求胜利者的编号。

又看了下，这段代码，似乎要改成

def solve(num,intval):
    #自动身成列表,从0开始 到num-1
    people=range(num)
    del_people=intval
    while(len(people) >1):
        del people[del_people-1]
        del_people = (del_people + intval-2) % len(people) +1
    return people[0]
print "the victor is %d"%solve(100,99)

lufeng369

原来是这样啊。。

我的问题描述和你的问题描述有偏差。。我是“每隔m个人踢人”就是把数到的第m＋1个人踢掉。而你是“把数到的第m个人踢掉”。。怪不得出来的结果不一样。。

Eastsun

呵呵，其实我的第一种算法和楼上的本质上是一样的，都是模拟算法。

lufeng369

但对于你的解法二。。我还是看不懂。。很难理解你到底是怎样思考出这种算法的。。