| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1110 人关注过本帖, 1 人收藏
标题:【分享】解独数程序 刚研究出来的^_^
取消只看楼主 加入收藏
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
结帖率:94.44%
收藏(1)
已结贴  问题点数:100 回复次数:3 
【分享】解独数程序 刚研究出来的^_^
什么叫数独就不多少了 不知道的自己百度吧;
输入要求空的地方以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
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 2楼 voidx
数独
2011-08-26 17:31
草狼
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
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 8楼 卧龙孔明
我的就是啊,这几天再学这个,然后就写了下
2011-08-26 19:17
快速回复:【分享】解独数程序 刚研究出来的^_^
数据加载中...
 
   



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

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