问题描述

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

用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说明能放
}

解决方案

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

解决方案二：

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);
}

}

解决方案三：

数独求解算法
数独的求解算法
数独求解算法