数独求解

#include <stdio.h>

#define false    (0)
#define true     (1)

int sudoku[9][9]={
    {0, 7, 1, 0, 5, 9, 0, 0, 4},
    {2, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 4, 0, 7, 0, 0, 6, 0, 0},
    {0, 0, 0, 5, 1, 0, 9, 4, 0},
    {0, 6, 8, 0, 0, 0, 1, 5, 0},
    {0, 5, 9, 0, 8, 4, 0, 0, 0},
    {0, 0, 2, 0, 0, 5, 0, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 3},
    {3, 0, 0, 4, 9, 0, 5, 2, 0},
};
  
// 判断填在空白位置的数字在行、列上是否符合要求
int Judge1(int x, int y, int n)
{
    int i;
    
    for(i = 0;i < 9;i++)
    {
        //判断 列
        if((sudoku[i][y]==n) && (i!=x))
            return false;
        //判断 行
        if((sudoku[x][i]==n) && (i!=y))
            return false;
    }
    
    return true;
}
  
// 判断填在空白位置的数字在九宫格之内是否符合要求
int Judge2(int x, int y, int n)
{
    int xx,yy,i,j;
    
    xx = x / 3;
    yy = y / 3;
    for(i = xx*3; i < xx*3+3; i++)
    {
        for(j = yy*3; j< yy*3+3; j++)
        {
            if(sudoku[i][j] == n)
            {
                if(i == x && j == y)
                    continue;
                else
                    return false;
            }
        }
    }
    return true;
}
  
// 填充空白数组，m为9*9方格中的序号（左到右，上到下），从0号开始
int Fill(int m)
{
    int n,x,y;
    
    x = m / 9; // 行号
    y = m % 9; // 列号
    
    if (m >= 81) // 递归边界，如果能填充到最后一个空格，则必然正确
        return true;
        
    if (sudoku[x][y]==0)
    {
        for(n = 1; n <= 9; n++)
        {
            sudoku[x][y] = n; // 从1到9尝试填入数据
            
            if(Judge1(x, y, n) && Judge2(x, y, n))
            {
                // 如果当前填入的数据符合要求，则尝试填充下一个空格
                if(Fill(m+1))
                    return true;
            }
            sudoku[x][y]=0;
        }
    }
    else
    {
        return Fill(m+1);
    }
    
    return false;
}

void show_sudoku(int sudoku[9][9])
{
    int i, j, k;
    
    for(i = 0; i < 12; i++)
        printf("__");
    printf("
");
    
    for(i = 0; i < 9; i++)
    {
        for(j = 0; j < 9; j++)
        {
            printf("%d ", sudoku[i][j]);    
            if((j+1)%3 == 0)
                printf("| ");
        }    
        printf("
");
        
        if((i+1)%3 == 0)
        {
            for(k=0;k<12;k++)
                printf("__");
            printf("
");
        }
    }    
}

int main(void)
{
    //printf("输入初始数独数据，空白用0代替
");
    printf("初始数独数据:
");
    show_sudoku(sudoku);
    
    printf("
求解得数独数据:
");

    if(Fill(0) == true) // 填充数独的空白位置完毕
    {
        show_sudoku(sudoku);
    }
    else
    {
        printf("该数独无解，请检查原始数独是否有误
");
    }
    
    return 0;
}

【以上代码参考整理自：链接】