平時喜歡玩數獨游戲，昨日突發想用程序自動求解。思路是回溯法，不斷試探。
程序代碼如下：
1 #include<stdio.h>
2
3 /*
4 {0,0,4,6,0,2,0,9,1},
5 {2,1,0,9,8,4,0,5,6},
6 {9,0,0,0,7,1,4,2,0},
7 {1,2,5,0,6,0,3,4,7},
8 {4,7,6,0,0,0,9,8,5},
9 {8,3,9,0,4,0,1,6,2},
10 {0,9,1,2,5,0,0,0,4},
11 {5,8,0,4,1,6,0,3,9},
12 {6,4,0,3,0,7,5,0,0}};
13 */
14
15 int data[9][9] = {
16 {0,7,0,2,6,0,9,0,0},
17 {3,0,0,0,0,8,0,0,7},
18 {0,9,0,0,5,7,0,0,0},
19 {5,0,0,0,0,0,0,7,0},
20 {0,4,7,3,1,2,8,5,0},
21 {0,8,0,0,0,0,0,0,1},
22 {0,0,0,8,2,0,0,4,0},
23 {7,0,0,6,0,0,0,0,2},
24 {0,0,4,0,3,9,0,8,0}};
25
26 void input()
27 {
28 int i,j;
29 for(i = 0;i < 9;i++)
30 for(j = 0;j < 9;j++)
31 scanf("%d",&data[i][j]);
32 }
33
34 void output()
35 {
36 int i,j;
37 for(i = 0;i < 9;i++)
38 {
39 for(j = 0;j < 9;j++)
40 printf("%d ",data[i][j]);
41 printf("\n");
42 }
43 printf("\n");
44 }
45
46 /*檢查num是否可放置在3*3區域是否有沖突*/
47 int CheckSquare(int line,int col,int num)
48 {
49 int i = (line / 3) * 3;
50 int j = (col / 3) * 3;
51 int m,n;
52 for(m = i;m < i + 3;m++)
53 for(n = j;n < j + 3;n++)
54 if((data[m][n] == num) && !(m == line && n == col))
55 return 0;
56 return 1;
57 }
58
59 /*檢查行沖突*/
60 int CheckLine(int line,int col,int num)
61 {
62 int i = 9;
63 while(i--)
64 if((data[line][i] == num) && (i != col))
65 return 0;
66 return 1;
67 }
68
69 /*檢查列沖突*/
70 int CheckColumn(int line,int col,int num)
71 {
72 int i = 9;
73 while(i--)
74 if((data[i][col] == num) && (i != line))
75 return 0;
76 return 1;
77 }
78
79 /*檢查i行j列是否可放置num*/
80 int Check(int i,int j,int num)
81 {
82 return CheckSquare(i,j,num) && CheckLine(i,j,num) && CheckColumn(i,j,num);
83 }
84
85 /*檢查是否完成*/
86 int IsDone()
87 {
88 int i,j;
89 for(i = 0;i < 9;i++)
90 for(j = 0;j < 9;j++)
91 if(!Check(i,j,data[i][j]) || (data[i][j] == 0))
92 return 0;
93 return 1;
94 }
95
96 void Calc()
97 {
98 int i,j,x;
99 if(IsDone())
100 {
101 output();
102 return;
103 }
104 for(i = 0;i < 9;i++)
105 {
106 for(j = 0;j < 9;j++)
107 {
108 if(data[i][j] == 0)
109 {
110 for(x = 1; x <= 9;x++)
111 {
112 if(Check(i,j,x))
113 {
114 data[i][j] = x;
115 Calc();
116 }
117 }
118 if(x == 10)
119 {
120 data[i][j] = 0;
121 return ;
122 }
123 }
124 }
125 }
126 }
127
128 int main()
129 {
130 // input();
131 Calc();
132 output();
133
134 return 0;
135 }
上述程序中，數字0表示該位置為空，待填入數字。
摘自 泡泡騰
