2 zzbb2004 zzbb2004 于 2016.04.23 00:24 提问

最蠢数独穷举算法,就是不出结果,求解

用C++/C写了个数独暴力破解算法,运用递归来破解数独
搞了半天不知道错哪。。求前辈指教。。

PS:数独就是9×9=81个格子
要把9组1~9一共81个数字填入格子中
要求:
每一行不能有相同的数
每一列不能有相同的数
每一小宫(9个格子)不能有相同的数
图片说明

 #include <iostream>
using namespace std;
void Sudoku(int x,int y);    //放数
int Judge(int x,int y,int a);    //判断能否放数

int Array[9][9] = {    //数独
    {9,0,0,0,2,0,0,0,0},
    {1,0,0,0,0,6,0,4,0},
    {0,6,4,0,3,0,0,0,0},
    {6,9,7,0,8,0,0,0,0},
    {0,4,0,1,0,0,2,0,3},
    {3,0,0,0,5,0,0,0,8},
    {0,0,0,0,4,0,0,3,2},
    {0,7,0,3,1,0,0,0,0},
    {0,1,0,0,6,8,0,9,7}
};


int main(){
    Sudoku(0,0);    //从(0,0)开始放数

    for(int i=0;i<9;i++){    //打印
        for(int j=0;j<9;j++)
            cout<<Array[i][j]<<"  ";
        cout<<endl;
    }
    cout<<endl;

    return 0;
}

void Sudoku(int x,int y){
    if(Array[x][y]==0){    //如果该位没数表示可以放数
        int temp_A = 0;    //临时变量
        int temp_B = 0;
        for(int a=1;a<10;a++){    //从1到9循环放数
            if(Judge(x,y,a)==1){    //如果可以放数
                if(x<8){    //从行放数
                    Array[x][y]=a;    //就放数
                    if(Array[x+1][y]==0)    //下一个是不是可放数位
                        temp_A=1;    //是的话临时变量为1
                    else 
                        temp_A=0;    //不是则为0
                    Sudoku(x+1,y);    //去下一个位子放数
                    if(temp_A==1)    //递归回来以后,如果临时变量为1,即下一位原本是0
                        Array[x+1][y]=0;    //将下一位置0(还原)
                }
                if(x==8&&y<8){    //行满了去下一列,重复上述步骤
                    Array[x][y]=a;
                    if(Array[0][y+1]==0)
                        temp_B=1;
                    else
                        temp_B=0;
                    Sudoku(0,y+1);
                    if(temp_B==1)
                        Array[0][y+1]=0;
                }
            }
        }
    }
    if(Array[x][y]!=0){    //有数则直接去下一格放数
        if(x<8)
            Sudoku(x+1,y);
        if(x==8&&y<8)
            Sudoku(0,y+1);
    }
}

int Judge(int x,int y,int a){
    int row,len;
    row = x / 3;
    row = row * 3;
    len = y / 3;
    len = len * 3;
    for(int i=0;i<9;i++){
        if(a==Array[i][y])
            return 0;    //每列上有相同的则返回0说明不行
        if(a==Array[x][i])
            return 0;    //每行上有相同的则返回0说明不行
    }
    for(int i=row;i<row+3;i++)
        for(int j=len;j<len+3;j++)
            if(a==Array[i][j])
                return 0;    //每小宫里有相同的也返回0
    return 1;    //通过考研就返回1说明能放
}

3个回答

caozhy
caozhy   Ds   Rxr 2016.04.23 06:35

http://bbs.csdn.net/topics/390039859
这是我写的,用的是C#,不过你可以参考下

cxiaoln
cxiaoln   2016.04.23 13:36

void DFS(int curX, int curY) {
if (curY >= kArrSize) {
++curX;
curY = 0;
}

if (curX*kArrSize + curY >= kArrSize*kArrSize) {
    PrintData();
    return;
}

while (curX < kArrSize && curY < kArrSize && Array[curX][curY] > 0) {
    while (curY < kArrSize && Array[curX][curY] > 0)
        ++curY;
    if (curY >= kArrSize)
        curY = 0;
    else
        break;

    ++curX;
}

if (curX < kArrSize && curY < kArrSize) {

    for (int nCurLowerVal = 1; nCurLowerVal <= kArrSize; ++nCurLowerVal) {
        Array[curX][curY] = nCurLowerVal;
        if (JudgeCurRowAndColIsLegal(curX, curY))
            DFS(curX, curY + 1);
    }
    Array[curX][curY] = 0;
} else {
    DFS(curX, curY+1);
}

}

CSDNXIAON
CSDNXIAON   2016.04.23 00:32

数独求解算法
数独的求解算法
数独求解算法
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!