解数独的代码

xxandxx

不知道大家玩过数独没,这是我做的一个解数独得代码.
新建一个文本文档,名字叫 Sudo.txt
里面的内容如下(下面这个数字矩阵):
0 3 0 0 0 7 0 0 4
6 0 2 0 4 1 0 0 0
0 5 0 0 3 0 9 6 7
0 4 0 0 0 3 0 0 6
0 8 7 0 0 0 3 5 0
9 0 0 7 0 0 0 2 0
7 1 8 0 2 0 0 4 0
0 0 0 1 6 0 8 0 9
4 0 0 5 0 0 0 3 0
保存后就可以了,这个矩阵也可以自己改, 0表示未知值.
如果这个数独不止一个解,所有的解都会被打印出来.
下面就是具体代码了,希望大家玩得愉快,有什么问题的话就留个言吧!

1. 
   
2. #include <stdio.h>
   
3. #define debug(x) puts(x)
   
4. #define mask 0x1FF
   
5. #define besure(x) (!(x&(x-1)))
   
6. 
   
7. typedef struct sudo {
   
8.     int sudo_p[9][9];
   
9.     int sudo_set[3][9];
   
10.     int sudo_x, sudo_y;
    
11.     struct sudo *sudo_next;
    
12. } t_sudo;
    
13. 
    
14. void save(t_sudo **s, t_sudo *p)
    
15. {
    
16.     p->sudo_next = (*s);
    
17.     *s = p;
    
18. }
    
19. 
    
20. t_sudo *load(t_sudo **s)
    
21. {
    
22.     t_sudo *p = *s;
    
23.    
    
24.     if (!s || !(*s))
    
25.         return NULL;
    
26.     (*s) = p->sudo_next;
    
27.     return p;
    
28. }
    
29. 
    
30. int hex_to_int(int i)
    
31. {
    
32.     int j = 0;
    
33.    
    
34.     if (i == 0)
    
35.        return 0;
    
36.    
    
37.     if (besure(i)) {
    
38.         j = 1;
    
39.         while (!(i & 0x1)) {
    
40.               i >>= 1;
    
41.               j++;
    
42.         }
    
43.     }
    
44.     return j;
    
45. }
    
46. 
    
47. int Sudo_show (char *msg, t_sudo *s, FILE *fp)
    
48. {
    
49.     int i, j, count = 0;
    
50.    
    
51.     while (s) {
    
52.         count ++;
    
53.         if (msg) {
    
54.            fputs(msg, fp);
    
55.            fputs("\n", fp);
    
56.         }
    
57.         
    
58.         for (i = 0; i < 9; ++i) {
    
59.             for (j = 0; j < 9; ++j)
    
60.                 fprintf(fp, "%d ", hex_to_int(s->sudo_p[i][j]));
    
61.             fputs("\n", fp);
    
62.         }
    
63.         s = s->sudo_next;
    
64.     }
    
65.     return count;
    
66. }
    
67. 
    
68. int Sudo_init(char const* filename, t_sudo *s)
    
69. {
    
70.     FILE *fp;
    
71.     int i, j, t;
    
72.    
    
73.     memset(s, 0, sizeof(t_sudo));
    
74.     fp = fopen(filename, "r");
    
75.     if (!fp) {
    
76.         fprintf(stderr, "File open error!\n");
    
77.         return -1;
    
78.     }
    
79.    
    
80.     for (i = 0; i < 9; ++i) {
    
81.         for (j = 0; j < 9; ++j) {
    
82.             if (fscanf(fp, "%d", &t) != 1) {
    
83.                 fprintf(stderr, "Scan error in line %d row %d\n", i, j);
    
84.                 return -1;
    
85.             }
    
86.             if (t == 0)
    
87.                 s->sudo_p[i][j] = mask;
    
88.             else
    
89.                 s->sudo_p[i][j] = 1 << (t-1);
    
90.         }
    
91.     }
    
92.    
    
93.     fclose(fp);
    
94.     Sudo_show("Sudo Init Complete!", s, stdout);
    
95.     return 0;
    
96. }
    
97. 
    
98. int sudo_check(t_sudo *s, int *x, int *y)
    
99. {
    
100.     int i, j, k, tmp;
     
101.    
     
102.     for (i = 0, tmp = 0; i < 9; ++i) {
     
103.         for (j = 0; j < 9; ++j) {
     
104.             if (!besure(s->sudo_p[i][j])) {
     
105.                 *x = i;
     
106.                 *y = j;
     
107.                 return 1;                                
     
108.             }
     
109.             tmp |= s->sudo_p[i][j];
     
110.         }
     
111.         
     
112.         if (tmp != mask)
     
113.             return 2;
     
114.     }
     
115.    
     
116.     for (k = 0; k < 9; ++k) {
     
117.         for (i = (k/3)*3, tmp = 0; i < (k/3)*3+3; ++i)
     
118.             for (j = (k%3)*3; j < (k%3)*3+3; ++j)
     
119.                 tmp |= s->sudo_p[i][j];
     
120.             
     
121.         if (tmp != mask)
     
122.             return 2;
     
123.     }
     
124.         
     
125.     return 0;
     
126. }
     
127. 
     
128. #define zerolowbit(x) (x & (x-1))
     
129. #define lowbit(x) ((x & (x-1)) ^ x)
     
130. 
     
131. #define CLOSE(s, i, j) if (besure(s->sudo_p[i][j])) { \
     
132.                             s->sudo_set[0][i] &= ~s->sudo_p[i][j];    \
     
133.                             s->sudo_set[1][j] &= ~s->sudo_p[i][j];    \
     
134.                             s->sudo_set[2][(i/3)*3+j/3] &= ~s->sudo_p[i][j]; \
     
135.                         }
     
136. 
     
137. #define CLOSESTACK(s, i, j)  if (!besure(s->sudo_p[i][j])) { \
     
138.                                 s->sudo_p[i][j] &= s->sudo_set[0][i]; \
     
139.                                 s->sudo_p[i][j] &= s->sudo_set[1][j]; \
     
140.                                 s->sudo_p[i][j] &= s->sudo_set[2][(i/3)*3+j/3]; \
     
141.                                 if (s->sudo_p[i][j] == 0) {\
     
142.                                     sp = 0; \
     
143.                                     goto load; \
     
144.                                 } \
     
145.                                 if (besure(s->sudo_p[i][j])) { \
     
146.                                     s->sudo_set[0][i] &= ~s->sudo_p[i][j];    \
     
147.                                     s->sudo_set[1][j] &= ~s->sudo_p[i][j];    \
     
148.                                     s->sudo_set[2][(i/3)*3+j/3] &= ~s->sudo_p[i][j]; \
     
149.                                     stack[sp++] = i; \
     
150.                                     stack[sp++] = j; \
     
151.                                 } \
     
152.                             }
     
153. 
     
154. int Sudo(t_sudo *s)
     
155. {
     
156.     int i, j, x, y, ret, k = 0;
     
157.     int stack[182];
     
158.     int sp = 0;
     
159.     t_sudo *t, *head = NULL, *res=NULL;
     
160.    
     
161.     t = malloc(sizeof(t_sudo));
     
162.     *t = *s;
     
163.     s = t;
     
164.         
     
165.     for (i = 0; i < 3; ++i)
     
166.         for (j = 0; j < 9; ++j)
     
167.             s->sudo_set[i][j] = mask;
     
168.    
     
169.     for (i = 0; i < 9; ++i) {
     
170.         for (j = 0; j < 9; ++j) {
     
171.             CLOSE(s, i, j)
     
172.         }
     
173.     }
     
174.    
     
175.     for (i = 0; i < 9; ++i) {
     
176.         for (j = 0; j < 9; ++j) {
     
177.             CLOSESTACK(s, i, j);
     
178.         }
     
179.     }
     
180.    
     
181.     while (1) {
     
182.         while (sp != 0) {
     
183.               y = stack[--sp];
     
184.               x = stack[--sp];
     
185.               for (i = 0; i < 9; ++i) {
     
186.                   CLOSESTACK(s, i, y);
     
187.                   CLOSESTACK(s, x, i);
     
188.               }
     
189.               for (i = (x/3)*3; i < (x/3)*3+3; ++i)
     
190.                   for (j = (y/3)*3; j < (y/3)*3+3; ++j)
     
191.                       CLOSESTACK(s, i, j);
     
192.         }
     
193.         
     
194.         ret = sudo_check(s, &i, &j);
     
195.         if (ret == 0) {
     
196.            s->sudo_next = res;
     
197.            res = s;
     
198.            goto notfreeload;
     
199.         } else if (ret == 2) {
     
200.            goto load;
     
201.         }
     
202.         t = malloc(sizeof(t_sudo));
     
203.         *t = *s;
     
204.         t->sudo_x = i;
     
205.         t->sudo_y = j;
     
206.         t->sudo_p[i][j] = zerolowbit(t->sudo_p[i][j]) ;      
     
207.         save(&head, t);
     
208.         s->sudo_p[i][j] = lowbit(s->sudo_p[i][j]) ;
     
209.         CLOSE(s, i, j);
     
210.         stack[sp++] = i;
     
211.         stack[sp++] = j;
     
212.         continue;
     
213.         load:
     
214.             free(s);
     
215.         notfreeload:
     
216.             s = load(&head);
     
217.             if (!s) {
     
218.                 break;
     
219.             }
     
220.             CLOSE(s, s->sudo_x, s->sudo_y);
     
221.     }
     
222.    
     
223.     k = Sudo_show("-----------------", res, stdout);
     
224.     printf("-----------------\n%d result(s) Found!\n", k);
     
225.    
     
226.     while(res) {
     
227.         s = res->sudo_next;
     
228.         free(res);
     
229.         res = s;
     
230.     }
     
231. }
     
232. 
     
233. int main()
     
234. {
     
235.     t_sudo p;
     
236.    
     
237.     Sudo_init("Sudo.txt" , &p);
     
238.     Sudo(&p);
     
239.    
     
240.     system("pause");
     
241.     return 0;
     
242. }
     
243. 
     

复制代码

[ 本帖最后由 xxandxx 于 2007-5-29 09:56 编辑 ]

emacsnw

Amazing! 算法实现很精简，代码风格也很赞，这个要顶。

emacsnw

刚玩了一会儿，好像存在一些bug，当数独难度比较大的时候容易出现问题，例如下面的一个数独：
1 0 0 0 0 2 3 0 0
4 0 0 0 5 3 0 0 0
0 0 0 6 7 8 0 0 0
0 7 0 0 9 0 0 5 0
0 8 0 0 0 0 0 4 0
0 5 0 0 3 0 0 2 0
0 0 0 7 2 1 0 0 0
0 0 0 5 8 0 0 0 6
0 0 9 3 0 0 0 0 7

它存在唯一解：
1 6 8 9 4 2 3 7 5
4 2 7 1 5 3 9 6 8
3 9 5 6 7 8 4 1 2
2 7 1 4 9 6 8 5 3
6 8 3 2 1 5 7 4 9
9 5 4 8 3 7 6 2 1
8 3 6 7 2 1 5 9 4
7 4 2 5 8 9 1 3 6
5 1 9 3 6 4 2 8 7

这个程序找到了此解，但是还找出了另外1254个错误的解，例如
1 6 8 9 4 2 3 8 8
4 9 8 1 5 3 9 9 9
9 9 5 6 7 8 9 9 9
3 7 4 8 9 6 8 5 8
9 8 6 2 1 5 9 4 9
9 5 6 8 3 7 9 2 9
8 4 8 7 2 1 9 9 9
7 4 7 5 8 9 4 3 6
8 2 9 3 6 4 8 8 7

xxandxx

谢谢 emacsnw指出这个问题
我在sudo_check中作的弱检测，因此一些不正确的解也被当作了正确解。
现在把sudo_check中的检测作了强化，可以正确解出 emacsnw那个比较难的数独了。