3X3数独

/**回溯法 
 * 生成数独矩阵 
 * From 编程之美1.15 
*/  
  
#include <stdio.h>  
#include <time.h>  
  
/*要生成的数独矩阵个数*/  
#define SUDOKU_NUM 1 
  
/** 
 * 函数is_digital_match 
 * 检测sudoku[i][j]上的值是否符合要求 
*/  
int is_digital_match(int sudoku[][9], int i, int j)  
{  
    int temp = sudoku[i][j];  
    int p, q;  
    int m, n;  
      
    for(p=0; p<9; p++)  
        if(p!=i && sudoku[p][j]==temp)  
            return 0;  
    for(p=0; p<9; p++)  
        if(p!=j && sudoku[i][p]==temp)  
            return 0;  
  
    p = i/3;  
    q = j/3;  
    for(m=p*3; m<p*3+3; m++)  
        for(n=q*3; n<q*3+3; n++)  
            if(m!=i && n!=j && sudoku[m][n]==temp)  
                return 0;  
      
    return 1;  
}  
  
/*输出数独矩阵*/  
void sudoku_print(int sudoku[][9])  
{  
    int i,j;  
    for(i=0; i<9; i++)  
    {  
        for(j=0; j<9; j++)  
            printf("%4d", sudoku[i][j]);  
        printf("\n");  
    }  
}  
  
int main(void)  
{  
    int sudoku[9][9] = {0};  
    int i, j, temp=0;  
    int k=0, num=0;  
  
    srand(time(0));  
    for(i=0; i<9; i++)  
        for(j=0; j<9; j++)  
            sudoku[i][j] = 0;  
    /*通过添加一些随机性，来每次生成不同的数独矩阵*/  
    /*添加更多随机性，则生成的矩阵将更随即*/  
    for(i=0; i<9; i++)  
    {  
        temp = rand() % 81;  
        sudoku[temp/9][temp%9] = i+1;  
    }  
    /*回溯法，构造数独矩阵*/  
    while(1)  
    {  
        i = k/9;  
        j = k%9;  
  
        while(1)  
        {  
            sudoku[i][j]++;  
            if(sudoku[i][j] == 10)  
            {  
                sudoku[i][j] = 0;  
                --k;  
                break;  
            }  
            else if(is_digital_match(sudoku, i, j) == 1)  
            {  
                ++k;  
                break;  
            }  
        }  
  
        if(k == 81)  
        {  
            printf("Proper sudoku matrix %d: \n", ++num);  
            sudoku_print(sudoku);  
            if(num >= SUDOKU_NUM)  
                return 0;  
  
            --k;  
        }  
    }  
      
    return 0;  
}