首页 > C++ > (怀旧向)第二弹:数独全解程序

(怀旧向)第二弹:数独全解程序

2012年7月25日 发表评论 阅读评论

要把这代码贴上来我都略显不好意思了。也是大一暑假时候写的吧,一直觉得递归是个很神奇的东西,任何用了递归的代码都会变得很艺术,嗯,记得大一第一次被编程这种东西震惊到的时候就是看网上一个全排列的C++代码,显然是递归,当时对递归还没有太大的概念,所以一步一步跟着那个代码走了很深,最后觉得,编程真是一门艺术啊!!(难道我喜欢上编程就是那段代码害的??)

不过现在看看这段数独全解的代码,还真是。。唉。。都说了是怀旧向了,就不能乱改了,现在不知脑子被门挤了的话是绝对不会变量用a来表示的,也不会在主函数里面写一大坨,你看看shudu那个函数里面那个销魂的花括号,哈哈哈,现在能笑,说明我成长了~

#include <iostream.h>
#include <stdlib.h>
bool checkhang(int a[9][9],int hang,int num)
{
    for(int i=0;i<9;i++)
    {
        if(a[hang][i]==num)
            return false;
    }
    return true;
}

bool finish(int a[9][9])
{
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
            if(a[i][j]==0)
                return false;
            return true;
}

bool checklie(int a[9][9],int lie,int num)
{
    for(int i=0;i<9;i++)
    {
        if(a[i][lie]==num) return false;
    }
    return true;
}

int kuaishu(int i,int j)
{
    return int(i/3)*3+int(j/3);
}

bool checkkuai(int a[9][9],int hang,int lie,int num)
{
    int kuai=kuaishu(hang,lie);
    int hangbegin=int(kuai/3)*3;
    int liebegin=(kuai%3)*3;
    for(int i=hangbegin;i<hangbegin+3;i++)
        for(int j=liebegin;j<liebegin+3;j++)
            if(a[i][j]==num) return false;
            return true;
}

bool check(int a[9][9],int hang,int lie,int num)
{
    if(checkhang(a,hang,num)&&checklie(a,lie,num)&&checkkuai(a,hang,lie,num))
        return true;
    else return false;
}

void show(int a[9][9])
{
    for(int i=0;i<9;i++)
    {for(int j=0;j<9;j++)
    {cout<<a[i][j]<<" ";
    if(j==2||j==5) cout<<" ";
    }
    cout<<endl;
    if(i==2||i==5) cout<<endl;
    }
}

void shudu(int a[9][9])
{
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
            if(a[i][j]==0)
            {
                for(int l=1;l<=9;l++)
                    if(check(a,i,j,l))
                    {
                        a[i][j]=l;
                        if(finish(a))
                        {
                            show(a);
                            cout<<endl<<endl;
                        }
                        else shudu(a);
                        a[i][j]=0;
                    }
                    if(l==10)
                        goto loop;

            }
loop:;

}
void main()
{
/*int a[9][9]=
{8,0,0,0,0,0,0,0,0,
0,0,6,0,9,0,0,0,0,
2,4,7,5,0,1,0,0,0,
4,5,0,1,0,0,0,0,0,
0,0,8,4,0,7,9,0,0,
0,0,0,0,0,8,0,3,1,
0,0,0,6,0,2,1,5,8,
0,0,0,0,4,0,2,0,0,
0,0,0,0,0,0,0,0,0};
*/
    int a[9][9]={0};
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        {
            int d;
            show(a);
            cout<<"\n第"<<i+1<<"行,第"<<j+1<<"列:";
            cin>>d;
            if((!check(a,i,j,d))&&(d!=0))
                j--;
            else a[i][j]=d;
            cout<<endl;
            system("cls");
        }

        int change=0;
        while(!change)
        {
            change=1;
            for(int i=0;i<9;i++)
            {
                for(int j=0;j<9;j++)
                    if(a[i][j]==0)
                    {
                        int counter=0;
                        for(int l=1;l<=9;l++)
                            if(check(a,i,j,l))
                            {
                                a[i][j]=l;
                                counter++;
                                if(counter>1)
                                    a[i][j]=0;
                            }
                            if(counter==1)
                                change=0;
                    }
            }
        }
        cout<<"result:"<<endl;
        if(finish(a))
            show(a);
        else
            shudu(a);
        cout<<endl;
        system("pause");
}

【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

分类: C++ 标签:
  1. 2015年11月19日19:54 | #1

    checklie
    查谎

验证码:3 + 4 = ?

友情提示:留言可以使用大部分html标签和属性;

添加代码示例:[code lang="cpp"]your code...[/code]

添加公式请用Latex代码,前后分别添加两个$$