| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1110 人关注过本帖, 1 人收藏
标题:【分享】解独数程序 刚研究出来的^_^
只看楼主 加入收藏
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
结帖率:94.44%
收藏(1)
已结贴  问题点数:100 回复次数:10 
【分享】解独数程序 刚研究出来的^_^
什么叫数独就不多少了 不知道的自己百度吧;
输入要求空的地方以0代替就行^_^


#include<cstdio>
#include<cstring>
using namespace std;

const int MAX=800*800;
int l[MAX],r[MAX],u[MAX],d[MAX];
int s[MAX],col[MAX],row[MAX];
int mp[10][10],head[10][10][10];

void insert_node(int cnt, int c){
    s[c]++;
    col[cnt] = c;
    u[d[c]]=cnt;
    d[cnt] = d[c];
    u[cnt] =c;
    d[c] = cnt;
}

void remove(int c){
    l[r[c]] = l[c];
    r[l[c]] = r[c];
    for(int i=d[c]; i!=c; i=d[i])
        for(int j=r[i]; j!=i; j=r[j]){
            u[d[j]] = u[j];
            d[u[j]] = d[j];
            --s[col[j]];
        }
}

void Resume(int c){
    l[r[c]] = r[l[c]] = c;
    for(int i= u[c]; i!=c; i=u[i]){
        for(int j=l[i]; j!=i; j=l[j]){
            u[d[j]]=j;
            d[u[j]]=j;
            ++s[col[j]];
        }
    }
}
bool DFS(int k){
    if(k > 81 ) return true;
    int min=MAX,c;
    for(int i=r[0]; i!=0; i=r[i]){
        if( !s[i] ) return false;
        if(s[i] < min ){
            min = s[i];
            c=i;
        }
    }
    remove(c);
    for(int i=d[c]; i!=c; i=d[i]){
        mp[row[i]/100][(row[i]/10)%10] = row[i]%10;
        for(int j=r[i]; j!=i; j=r[j])
            remove(col[j]);
        if( DFS(k+1) ) return true;
        for(int j=l[i]; j!=i; j=l[j])
            Resume(col[j]);
    }
    Resume(c);
    return false;
}
int main(){
    while(true){
         for(int i=1; i<=9; ++i){
            for(int j=1; j<=9; ++j)
                scanf("%d",&mp[i][j]);
         }
        int sum=(9+9+9)*9+9*9;
        for(int i=0; i<=sum; ++i){
            s[i]=0;
            l[i]=i-1;
            r[i]=i+1;
            u[i]=d[i]=i;
        }
        l[0]=sum;
        r[sum]=0;
        int cnt=sum;
        for(int i=1; i<=9; ++i){
            for(int j=1; j<=9; ++j){
                for(int k=1; k<=9; ++k){
                    for(int u=1; u<=4; ++u){
                        l[cnt+u]=cnt+u-1;
                        r[cnt+u]=cnt+u+1;
                        row[cnt+u] = i*100+j*10+k;
                    }
                    l[cnt+1] = cnt+4;
                    r[cnt+4] = cnt+1;

                    insert_node(cnt+1,(i-1)*9+j);
                    insert_node(cnt+2,81+(i-1)*9+k);
                    insert_node(cnt+3,81*2+(j-1)*9+k);
                    insert_node(cnt+4,81*3+(((i-1)/3)*3+(j-1)/3)*9+k);
                    head[i][j][k] = cnt+1;
                    cnt+=4;
                }
            }
        }
        int k=0;
        for(int i=1; i<=9; ++i)
            for(int j=1; j<=9; ++j){
                if(mp[i][j]){
                    ++k;
                    remove(col[head[i][j][mp[i][j]]]);
                    for(int w=r[head[i][j][mp[i][j]]]; w!=head[i][j][mp[i][j]]; w=r[w])
                        remove(col[w]);

                }
            }
       if( DFS(k+1) ){
           puts("解为:");
            for(int i=1; i<=9; ++i){
                for(int j=1; j<=9; ++j)
                    printf("%d ",mp[i][j]);
                puts("");
            }
            puts("");
       }else{
            puts("无解");
       }

    }
    return 0;
}

[ 本帖最后由 草狼 于 2011-8-26 17:32 编辑 ]
搜索更多相关主题的帖子: using 百度吧 include 数独 
2011-08-26 14:35
voidx
Rank: 12Rank: 12Rank: 12
来 自:邯郸
等 级:火箭侠
帖 子:1250
专家分:3538
注 册:2011-4-7
收藏
得分:14 
难道是数独?
2011-08-26 16:42
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:14 
SudokuWin.rar (14.9 KB)
很久以前有段时间很痴迷于数独游戏,也写过数独的求解程序,不过是用C#写的。各位电脑支持.net(2.0以上)的话可以试试拙作。




     

重剑无锋,大巧不工
2011-08-26 17:12
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 2楼 voidx
数独
2011-08-26 17:31
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:14 
如果不能判断出是否多解,那就还不够

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2011-08-26 17:33
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:14 
请御姐提供思路

                                         
===========深入<----------------->浅出============
2011-08-26 18:22
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 5楼 御坂美琴
所有解只要在DFS找到一个解的时候不要马上跳出就可以了,
不过这样复杂度很高,不知道又什么好的算法不,求思路;

笨办法代码:

#include<cstdio>
#include<cstring>
using namespace std;

const int MAX=800*800;
int l[MAX],r[MAX],u[MAX],d[MAX];
int s[MAX],col[MAX],row[MAX];
int mp[10][10],head[10][10][10];
int flag;
void insert_node(int cnt, int c){
    s[c]++;
    col[cnt] = c;
    u[d[c]]=cnt;
    d[cnt] = d[c];
    u[cnt] =c;
    d[c] = cnt;
}

void remove(int c){
    l[r[c]] = l[c];
    r[l[c]] = r[c];
    for(int i=d[c]; i!=c; i=d[i])
        for(int j=r[i]; j!=i; j=r[j]){
            u[d[j]] = u[j];
            d[u[j]] = d[j];
            --s[col[j]];
        }
}

void Resume(int c){
    l[r[c]] = r[l[c]] = c;
    for(int i= u[c]; i!=c; i=u[i]){
        for(int j=l[i]; j!=i; j=l[j]){
            u[d[j]]=j;
            d[u[j]]=j;
            ++s[col[j]];
        }
    }
}
void DFS(int k){
    if(k > 81 ){
        printf("第%d解为:\n",++flag);
        for(int i=1; i<=9; ++i){
            for(int j=1; j<=9; ++j)
                printf("%d ",mp[i][j]);
            puts("");
        }
        puts("");
         return;
    }
    int min=MAX,c;
    for(int i=r[0]; i!=0; i=r[i]){
        if( !s[i] ){
             return;
        }
        if(s[i] < min ){
            min = s[i];
            c=i;
        }
    }
    remove(c);
    for(int i=d[c]; i!=c; i=d[i]){
        mp[row[i]/100][(row[i]/10)%10] = row[i]%10;
        for(int j=r[i]; j!=i; j=r[j])
            remove(col[j]);
        DFS(k+1);
        for(int j=l[i]; j!=i; j=l[j])
            Resume(col[j]);
    }
    Resume(c);
}
int main(){
    while(true){
         for(int i=1; i<=9; ++i){
            for(int j=1; j<=9; ++j)
                scanf("%d",&mp[i][j]);
         }
        int sum=(9+9+9)*9+9*9;
        for(int i=0; i<=sum; ++i){
            s[i]=0;
            l[i]=i-1;
            r[i]=i+1;
            u[i]=d[i]=i;
        }
        l[0]=sum;
        r[sum]=0;
        int cnt=sum;
        for(int i=1; i<=9; ++i){
            for(int j=1; j<=9; ++j){
                for(int k=1; k<=9; ++k){
                    for(int u=1; u<=4; ++u){
                        l[cnt+u]=cnt+u-1;
                        r[cnt+u]=cnt+u+1;
                        row[cnt+u] = i*100+j*10+k;
                    }
                    l[cnt+1] = cnt+4;
                    r[cnt+4] = cnt+1;

                    insert_node(cnt+1,(i-1)*9+j);
                    insert_node(cnt+2,81+(i-1)*9+k);
                    insert_node(cnt+3,81*2+(j-1)*9+k);
                    insert_node(cnt+4,81*3+(((i-1)/3)*3+(j-1)/3)*9+k);
                    head[i][j][k] = cnt+1;
                    cnt+=4;
                }
            }
        }
        int k=0;
        for(int i=1; i<=9; ++i)
            for(int j=1; j<=9; ++j){
                if(mp[i][j]){
                    ++k;
                    remove(col[head[i][j][mp[i][j]]]);
                    for(int w=r[head[i][j][mp[i][j]]]; w!=head[i][j][mp[i][j]]; w=r[w])
                        remove(col[w]);

                }
            }
        flag=0;
        DFS(k+1);
        if(!flag){
            puts("无解");
        }
    }
    return 0;
}
2011-08-26 19:11
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:14 
回复 7楼 草狼
dancing links

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2011-08-26 19:16
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 8楼 卧龙孔明
我的就是啊,这几天再学这个,然后就写了下
2011-08-26 19:17
小偌
Rank: 4
来 自:成都
等 级:业余侠客
帖 子:170
专家分:241
注 册:2011-8-15
收藏
得分:14 
厉害~~

不是很好么..比起关在笼子里的可怜小鸟..我成为乌鸦已足矣
2011-08-26 21:14
快速回复:【分享】解独数程序 刚研究出来的^_^
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031735 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved