- //#include "sudoku.h"
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- #include <time.h>
- int sdk[9][9];
- static void GenRandom(int line[])
- {
- int i,j;
- for (i = 0; i < 9; i++)
- {
- line[i] = 0;
- }
- srand((unsigned)time(NULL));
- line[0]=rand()%(8-0+1)+1;
- for (i = 1; i < 9; )
- {
- line[i]=rand()%(8-0+1)+1;
- for (j = 0; j < i; j++)
- if(line[i] == line[j])
- break;
- if(j == i)
- i++;
- }
- }
- static void ListSDK()
- {
- int i,j;
- for (i = 0; i < 9; i++)
- {
- if (i == 6||i == 3)
- {
- printf("-----------------\\n");
- }
- for (j = 0; j < 9; j++)
- {
- printf("%d", sdk[i][j]);
- if (j == 2||j == 5)
- {
- printf("|");
- }
- else
- {
- printf(" ");
- }
- }
- printf("\\n");
- }
- }
- static int Initial_state( int i , int j ) //搜索第( i , j )位置处可以存储的数字,找到解则返回1,否则返回0
- {
- int k,m,n,p,q;
- if( i >= 9 || j >= 9 )
- return 1;
- for( k = 1 ; k <= 9 ; k++ )
- {
- int can = 1; // can 变量用于记录数字k能否放在 ( i , j ) 处
- for( m = 0 ; m < i ; ++m )
- if( sdk[m][j] == k ) // 检查同一列是否出现过数字k
- {
- can = 0 ;
- break ;
- }
- if ( can )
- for( n = 0 ; n < j ; ++n )
- if( sdk[i][n] == k ) // 检查同一行是否出现过数字k
- {
- can = 0 ;
- break;
- }
- if( can )
- {
- int up1 = ( i/3 ) * 3 + 3 ; // (i,j)方格所在的3×3小方格i坐标的上限
- int up2 = ( j/3 ) *3 + 3; // (i,j)方格所在的3×3小方格在j坐标的上限
- for( p = up1-3 ; p < up1 ; ++p ) /* 检查在3×3的小方格中是否出现了同一个数字 */
- {
- if( can == 0 ) /* 跳出外层循环 */
- break ;
- for( q = up2-3 ; q < up2 ; ++q )
- if( sdk[p][q] == k )
- {
- can = 0 ;
- break ;
- }
- }
- }
- if( can )
- {
- sdk[i][j] = k ;
- if( j < 8 )
- {
- if( Initial_state( i , j +1 ) ) /* 到同一行的下一位置开始搜索 */
- return 1 ;
- }
- else
- {
- if( i < 8 )
- {
- if( Initial_state( i + 1 , 0 ) ) /* 到下一行的第一个空格开始搜索 */
- return 1 ;
- }
- else
- return 1 ; /* i >= 9 && j >= 9 , 搜索结束 */
- }
- sdk[i][j] = 0 ; /* 关键这一步:找不到解就要回复原状,否则会对下面的搜索造成影响 */
- }
- }
- return 0 ; /* 1到9都尝试过都不行,则返回递归的上一步 */
- }
- static void InitSDK()
- {
- int i,j;
- for (i = 0; i < 9; i++)
- for (j = 0; j < 9; j++) sdk[i][j] = 0;
- //第1行随即数产生
- GenRandom(sdk[0]);
- //从第2行第1个位置开始检索
- Initial_state(1, 0);
- ListSDK();
- }
- static void InputSDK()
- {
- int i,j;
- char input[9+1];
- printf("输入9行数独数组,未知的位置用0表示:\\n");
- for (i = 0; i < 9; i++)
- {
- memset(input, 0x00, sizeof(input));
- printf("第%d行:",i+1);
- scanf("%s", input);
- for (j = 0; j < 9; j ++)
- {
- if (input[j] > '0' && input[j] <= '9')
- {
- sdk[i][j] = input[j] - '0';
- }
- else
- { //非数字和0统认为是未知位置
- sdk[i][j] = 0;
- }
- }
- }
- printf("输入的数独数组为:\\n");
- ListSDK();
- }
- static int Parse_state( int i , int j ) //搜索第( i , j )位置处可以存储的数字,找到解则返回1,否则返回0
- {
- if (sdk[i][j] != 0)
- {
- if( j < 8 )
- {
- if( Parse_state( i , j +1 ) ) /* 到同一行的下一位置开始搜索 */
- return 1 ;
- }
- else
- {
- if( i < 8 )
- {
- if( Parse_state( i + 1 , 0 ) ) /* 到下一行的第一个空格开始搜索 */
- return 1 ;
- }
- else
- return 1 ; /* i >= 9 && j >= 9 , 搜索结束 */
- }
- return 0;
- }
- int k,m,n,p,q;
- if( i >= 9 || j >= 9 )
- return 1;
- for( k = 1 ; k <= 9 ; k++ )
- {
- int can = 1; // can 变量用于记录数字k能否放在 ( i , j ) 处
- for( m = 0 ; m < 9 ; ++m )
- if( sdk[m][j] == k ) // 检查同一列是否出现过数字k
- {
- can = 0 ;
- break ;
- }
- if ( can )
- for( n = 0 ; n < 9 ; ++n )
- if( sdk[i][n] == k ) // 检查同一行是否出现过数字k
- {
- can = 0 ;
- break;
- }
- if( can )
- {
- int up1 = ( i/3 ) * 3 + 3 ; // (i,j)方格所在的3×3小方格i坐标的上限
- int up2 = ( j/3 ) *3 + 3; // (i,j)方格所在的3×3小方格在j坐标的上限
- for( p = up1-3 ; p < up1 ; ++p ) /* 检查在3×3的小方格中是否出现了同一个数字 */
- {
- if( can == 0 ) /* 跳出外层循环 */
- break ;
- for( q = up2-3 ; q < up2 ; ++q )
- if( sdk[p][q] == k )
- {
- can = 0 ;
- break ;
- }
- }
- }
- if( can )
- {
- sdk[i][j] = k ;
- if( j < 8 )
- {
- if( Parse_state( i , j +1 ) ) /* 到同一行的下一位置开始搜索 */
- return 1 ;
- }
- else
- {
- if( i < 8 )
- {
- if( Parse_state( i + 1 , 0 ) ) /* 到下一行的第一个空格开始搜索 */
- return 1 ;
- }
- else
- return 1 ; /* i >= 9 && j >= 9 , 搜索结束 */
- }
- sdk[i][j] = 0 ; /* 关键这一步:找不到解就要回复原状,否则会对下面的搜索造成影响 */
- }
- }
- return 0 ; /* 1到9都尝试过都不行,则返回递归的上一步 */
- }
- static void ParseSDK()
- {
- Parse_state(0, 0);
- printf("解析后的数独数组为:\\n");
- ListSDK();
- }
- int main(int argc, char *argv[])
- {
- if (argc != 2)
- {
- fprintf(stderr, "usage:sudoku init|parse\\n");
- return 1;
- }
- if (strcmp(argv[1], "init") == 0)
- {
- InitSDK();
- }
- if (strcmp(argv[1], "parse") == 0)
- {
- InputSDK();
- ParseSDK();
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/291120137602.html
来源: http://www.codesnippet.cn/detail/291120137602.html