[Perl]解数独题

523066680

回复 18# rubyish

Dancing Links 解数独 C语言实现，代码共享到了github：
https://github.com/vicyang/Sudoku/tree/master/Solver/DancingLinks

借用了你的位操作的方案，效率进一步提升(fill_one_possible_num 函数写的很难看 )

效率：
i7 CPU，gcc 编译带 -O2 参数，解 sudoku17.txt 四万九千多道题，3秒，不含printf
sudoku_nd0.txt 0.05s
解 nd1-nd4 所有题均不到1秒

rubyish

回复 21# 523066680

test xia meiyou dance de sudu shi ruhe??

1. # include <stdio.h>
   
2. 
   
3. # define ERROR 0b1111111110
   
4. # define OK    0
   
5. # define BEST  1
   
6. 
   
7. typedef char kar;
   
8. typedef int Sdk[][9];
   
9. typedef struct { int v, h, b; } Ijk;
   
10. 
    
11. void explore (Sdk);
    
12. void echo (Sdk);
    
13. void play (Sdk);
    
14. void init (void);
    
15. int best ();
    
16. 
    
17. int Verti[9];
    
18. int Horiz[9];
    
19. int Bloke[9];
    
20. int Hover[9][9];
    
21. kar Maybe[1024][10];
    
22. Ijk Dit[81];
    
23. int Head;
    
24. int Tail;
    
25. int Lost;
    
26. int main (){
    
27. 
    
28.     Sdk sudo1 = {
    
29.         { 0, 0, 0, 0, 0, 0, 0, 9, 0 },
    
30.         { 1, 9, 0, 4, 7, 0, 6, 0, 8 },
    
31.         { 0, 5, 2, 8, 1, 9, 4, 0, 7 },
    
32.         { 2, 0, 0, 0, 4, 8, 0, 0, 0 },
    
33.         { 0, 0, 9, 0, 0, 0, 5, 0, 0 },
    
34.         { 0, 0, 0, 7, 5, 0, 0, 0, 9 },
    
35.         { 9, 0, 7, 3, 6, 4, 1, 8, 0 },
    
36.         { 5, 0, 6, 0, 8, 1, 0, 7, 4 },
    
37.         { 0, 8, 0, 0, 0, 0, 0, 0, 0 },
    
38.     };
    
39. 
    
40. 
    
41.     init ();
    
42.    
    
43.     //for (int i = 0; i < 10000; i++)
    
44.     play (sudo1);
    
45.     // play (sudo3);
    
46.     // play (sudo2);
    
47.     // play (sudo1);
    
48. 
    
49. } /* main */
    
50. 
    
51. void init (){
    
52.     for (int i = 0; i < 9; i++) {
    
53.         int i3 = 3 * (i / 3);
    
54.         for (int j = 0; j < 9; j++)
    
55.             Hover[i][j] = j / 3 + i3;
    
56.     }
    
57.     for (int n = 0; n < ERROR; n += 2) {
    
58.         int len = 0;
    
59.         for (int i = 1; i <= 9; i++) {
    
60.             if (n & 1 << i) continue;
    
61.             Maybe[n][1 + len++] = i;
    
62.         }
    
63.         Maybe[n][0] = len;
    
64.     }
    
65. }
    
66. 
    
67. void play (Sdk sudo){
    
68.     for (int i = 0; i < 9; i++)
    
69.         Horiz[i] = Verti[i] = Bloke[i] = 0;
    
70. 
    
71.     Head = 0;
    
72. 
    
73.     for (int i = 0; i < 9; i++) {
    
74.         for (int j = 0; j < 9; j++) {
    
75.             int k = Hover[i][j];
    
76.             if (!sudo[i][j]) {
    
77.                 Dit[Head++] = (Ijk) {j, i, k };
    
78.                 continue;
    
79.             }
    
80. 
    
81.             Horiz[i] |= 1 << sudo[i][j];
    
82.             Verti[j] |= 1 << sudo[i][j];
    
83.             Bloke[k] |= 1 << sudo[i][j];
    
84.         }
    
85.     }
    
86. 
    
87.     Tail = Head;
    
88.     Lost = Tail + 1;
    
89.     Head = 0;
    
90. 
    
91.     explore (sudo);
    
92.     puts (" ___________________");
    
93. } /* play */
    
94. 
    
95. void explore (Sdk sudo) {
    
96.     if (Head == Lost) return;
    
97.     int this = best ();
    
98.     if (this == ERROR) return;
    
99.     if (this == OK) echo (sudo);
    
100. 
     
101.     kar *maybe = &Maybe[this][OK];
     
102.     Ijk *w     = &Dit[Head - 1];
     
103. 
     
104.     for (int it = 1; it <= maybe[OK]; it++) {
     
105.         int n = 1 << maybe[it];
     
106.         sudo[w->h][w->v] = maybe[it];
     
107.         Horiz[w->h] |= n;
     
108.         Verti[w->v] |= n;
     
109.         Bloke[w->b] |= n;
     
110.         explore (sudo);
     
111.         Horiz[w->h] ^= n;
     
112.         Verti[w->v] ^= n;
     
113.         Bloke[w->b] ^= n;
     
114.     }
     
115.     sudo[w->h][w->v] = 0;
     
116.     Head--;
     
117. } /* explore */
     
118. 
     
119. int best (){
     
120.     int min    = 10;
     
121.     int best   = OK;
     
122.     int posisi = Head;
     
123. 
     
124.     for (int head = Head; head < Tail; head++) {
     
125.         Ijk *w   = &Dit[head];
     
126.         int this = Verti[w->v] | Horiz[w->h] | Bloke[w->b];
     
127.         if (this == ERROR) return ERROR;
     
128.         int maybe = Maybe[this][OK];
     
129. 
     
130.         if (min > maybe) {
     
131.             posisi = head, best = this;
     
132.             if (maybe == BEST) break;
     
133.             min = maybe;
     
134.         }
     
135.     }
     
136. 
     
137.     Ijk dat = Dit[posisi];
     
138.     Dit[posisi] = Dit[Head];
     
139.     Dit[Head++] = dat;
     
140.     return best;
     
141. } /* best */
     
142. 
     
143. void echo (Sdk sudo){
     
144.     for (int i = 0; i < 9; i++) {
     
145.         if (!(i % 3)) puts ("");
     
146. 
     
147.         for (int j = 0; j < 9; j++) {
     
148.             if (!(j % 3)) printf (" ");
     
149.             printf ("%d ", sudo[i][j]);
     
150.         }
     
151.         puts ("");
     
152.     }
     
153. }
     

复制代码

rubyish

d  e  l  ~  ~

523066680

回复 23# rubyish

做了一些改动，用于批量读取题目

https://github.com/vicyang/Sudoku/tree/master/Others/Rubyish

1. /*
   
2.     作者：Rubyish
   
3.     日期: 2017-10
   
4.     http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=4267389&page=3&authorid=25822983
   
5. */
   
6. 
   
7. # include <stdio.h>
   
8. # include <stdlib.h>
   
9. # include <string.h>
   
10. # include <time.h>
    
11. 
    
12. # define ERROR 0b1111111110
    
13. # define OK    0
    
14. # define BEST  1
    
15. 
    
16. typedef char kar;
    
17. typedef int Sdk[9][9];
    
18. typedef struct { int v, h, b; } Ijk;
    
19. 
    
20. struct game {
    
21.     int id;
    
22.     char s[100];
    
23.     struct game *next;
    
24. };
    
25. 
    
26. void str_to_mat( char *s, Sdk sudo );
    
27. void load_games( struct game * games, char *filename  );
    
28. void explore (Sdk);
    
29. void echo (Sdk);
    
30. void play (Sdk);
    
31. void init (void);
    
32. int best ();
    
33. 
    
34. int Verti[9];
    
35. int Horiz[9];
    
36. int Bloke[9];
    
37. int Hover[9][9];
    
38. kar Maybe[1024][10];
    
39. Ijk Dit[81];
    
40. int Head;
    
41. int Tail;
    
42. int Lost;
    
43. 
    
44. int main (int argc, char *argv[])
    
45. {
    
46.     int time_a;
    
47.     Sdk sudo;
    
48.     struct game *gamenode = (struct game *)malloc( sizeof(struct game) );
    
49.     load_games( gamenode, "../../Puzzles/sudoku_nd3.txt" );
    
50. 
    
51.     //备用数据初始化
    
52.     init ();
    
53. 
    
54.     while ( gamenode->next != NULL )
    
55.     {
    
56.         time_a = clock();
    
57.         str_to_mat( gamenode->s, sudo );
    
58.         play (sudo);
    
59. 
    
60.         // fprintf(stderr, "Game ID: %d, Time used: %.3f\n", gamenode->id,
    
61.         //     (float)(clock()-time_a)/(float)CLOCKS_PER_SEC );
    
62.         gamenode = gamenode->next;
    
63.         //break;
    
64.     }
    
65. 
    
66.     fprintf(stderr, "Time used: %.3f\n", (float)clock() / (float)CLOCKS_PER_SEC );
    
67.     return 0;
    
68. } /* main */
    
69. 
    
70. void init ()
    
71. {
    
72.     for (int i = 0; i < 9; i++)
    
73.     {
    
74.         int i3 = 3 * (i / 3);
    
75.         for (int j = 0; j < 9; j++)
    
76.             Hover[i][j] = j / 3 + i3;
    
77.     }
    
78. 
    
79.     for (int n = 0; n < ERROR; n += 2)
    
80.     {
    
81.         int len = 0;
    
82.         for (int i = 1; i <= 9; i++)
    
83.         {
    
84.             if (n & 1 << i) continue;
    
85.             Maybe[n][1 + len++] = i;
    
86.         }
    
87.         Maybe[n][0] = len;
    
88.     }
    
89. }
    
90. 
    
91. void play (Sdk sudo)
    
92. {
    
93.     static int i, j, k;
    
94.     for (i = 0; i < 9; i++)
    
95.         Horiz[i] = Verti[i] = Bloke[i] = 0;
    
96. 
    
97.     Head = 0;
    
98.     for (i = 0; i < 9; i++)
    
99.     {
    
100.         for (j = 0; j < 9; j++)
     
101.         {
     
102.             k = Hover[i][j];
     
103.             if (!sudo[i][j])
     
104.             {
     
105.                 Dit[Head++] = (Ijk) {j, i, k };
     
106.                 continue;
     
107.             }
     
108. 
     
109.             Horiz[i] |= 1 << sudo[i][j];
     
110.             Verti[j] |= 1 << sudo[i][j];
     
111.             Bloke[k] |= 1 << sudo[i][j];
     
112.         }
     
113.     }
     
114. 
     
115.     Tail = Head;
     
116.     Lost = Tail + 1;
     
117.     Head = 0;
     
118. 
     
119.     explore (sudo);
     
120.     puts (" ___________________");
     
121. } /* play */
     
122. 
     
123. void explore (Sdk sudo)
     
124. {
     
125.     if (Head == Lost) return;
     
126.     int this = best ();
     
127.     if (this == ERROR) return;
     
128.     if (this == OK) echo (sudo);
     
129. 
     
130.     kar *maybe = &Maybe[this][OK];
     
131.     Ijk *w     = &Dit[Head - 1];
     
132. 
     
133.     for (int it = 1; it <= maybe[OK]; it++)
     
134.     {
     
135.         int n = 1 << maybe[it];
     
136.         sudo[w->h][w->v] = maybe[it];
     
137.         Horiz[w->h] |= n;
     
138.         Verti[w->v] |= n;
     
139.         Bloke[w->b] |= n;
     
140.         explore (sudo);
     
141.         Horiz[w->h] ^= n;
     
142.         Verti[w->v] ^= n;
     
143.         Bloke[w->b] ^= n;
     
144.     }
     
145.     sudo[w->h][w->v] = 0;
     
146.     Head--;
     
147. } /* explore */
     
148. 
     
149. int best ()
     
150. {
     
151.     int min    = 10;
     
152.     int best   = OK;
     
153.     int posisi = Head;
     
154. 
     
155.     for (int head = Head; head < Tail; head++)
     
156.     {
     
157.         Ijk *w   = &Dit[head];
     
158.         int this = Verti[w->v] | Horiz[w->h] | Bloke[w->b];
     
159.         if (this == ERROR) return ERROR;
     
160.         int maybe = Maybe[this][OK];
     
161. 
     
162.         if (min > maybe) {
     
163.             posisi = head, best = this;
     
164.             if (maybe == BEST) break;
     
165.             min = maybe;
     
166.         }
     
167.     }
     
168. 
     
169.     Ijk dat = Dit[posisi];
     
170.     Dit[posisi] = Dit[Head];
     
171.     Dit[Head++] = dat;
     
172.     return best;
     
173. } /* best */
     
174. 
     
175. void echo (Sdk sudo)
     
176. {
     
177.     for (int i = 0; i < 9; i++)
     
178.     {
     
179.         if (!(i % 3)) puts ("");
     
180.         for (int j = 0; j < 9; j++)
     
181.         {
     
182.             if (!(j % 3)) printf (" ");
     
183.             printf ("%d ", sudo[i][j]);
     
184.         }
     
185.         puts ("");
     
186.     }
     
187. }
     
188. 
     
189. void load_games( struct game * node, char *filename  )
     
190. {
     
191.     FILE *fp;
     
192.     fp = fopen( filename, "r" );
     
193. 
     
194.     int id = 1;
     
195.     while ( ! feof( fp ) )
     
196.     {
     
197.         fgets( node->s, 100, fp );
     
198.         //如果读取到空行或者残缺行，提前break，下一节点为 NULL
     
199.         if ( (int)strlen(node->s) < 81 ) break;
     
200.         node->id = id++;
     
201.         node->next = (struct game *) malloc( sizeof(struct game) );
     
202.         node = node->next;
     
203.     }
     
204.     node->next = NULL;
     
205. }
     
206. 
     
207. void str_to_mat( char *s, Sdk sudo )
     
208. {
     
209.     static int i, r, c;
     
210.     static int delta = '0' - 0;
     
211.     for (i = 0; i < 81; i++ )  //r,c from 0,0 to 8,8
     
212.     {
     
213.         r = (int)(i/9);
     
214.         c = (int)(i%9);
     
215.         sudo[r][c] = s[i] - delta;  //char to integer
     
216.     }
     
217. }

复制代码

解题效率（不含printf）
CPU: E5700 3.00GHz
sudoku_nd3.txt - Time used: 4.040
sudoku_nd0.txt - Time used: 0.093
sudoku17.txt - Time used: 210.477

CPU: i7-4790K 4.00GHz
sudoku_nd3.txt - Time used: 1.934
sudoku_nd0.txt - Time used: 0.031
sudoku17.txt - Time used: 96.127

CPU: i7-4790K 4.00GHz/gcc -O2
sudoku_nd3.txt - Time used: 0.820
sudoku_nd0.txt - Time used: 0.038
sudoku17.txt - Time used: 49.668

加了-O2 参数后速度相当快。

523066680

耗时较长的题目行号（sudoku17.txt）

1. 35458 -> 0.202
   
2. 44702 -> 0.202
   
3. 46685 -> 0.218
   
4. 46824 -> 0.218
   
5. 47738 -> 0.218
   
6. 42983 -> 0.219
   
7. 27713 -> 0.234
   
8. 44379 -> 0.250
   
9. 46920 -> 0.265
   
10. 40907 -> 0.281
    
11. 2113 -> 0.296
    
12. 47587 -> 0.296
    
13. 12489 -> 0.297
    
14. 48725 -> 0.343
    
15. 13667 -> 0.374
    
16. 44227 -> 0.468

复制代码

44227: 200500080001020000000000000070008000003000020000070600600200001040000700000300000

1. 2 9 7  5 4 3  1 8 6
   
2. 4 8 1  7 2 6  3 9 5
   
3. 3 5 6  1 8 9  2 7 4
   
4. 
   
5. 5 7 2  6 3 8  4 1 9
   
6. 9 6 3  4 5 1  8 2 7
   
7. 8 1 4  9 7 2  6 5 3
   
8. 
   
9. 6 3 8  2 9 7  5 4 1
   
10. 1 4 9  8 6 5  7 3 2
    
11. 7 2 5  3 1 4  9 6 8
    
12. ___________________
    
13. Game ID: 44227, Time used: 0.452

复制代码

rubyish

回复 25# 523066680

bijiaole zhege sudoku17.txt:
dance       3s, lines 600
no dance    49.668, lines 300

code de shuliang zhiyou 2 bei,
dan sudu jingran gaoda 16.5 bei.
dance guoran mingbuxuchuan!

3Q~~ floor25, very good de fenxi!!
zhendui 44227 you yige small OPT, sudu dayue tishenle 8 ~ 10 bei.

1. my $slow_44227 = [
   
2.     [ 2, 0, 0, 5, 0, 0, 0, 8, 0 ],
   
3.     [ 0, 0, 1, 0, 2, 0, 0, 0, 0 ],
   
4.     [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
   
5.     [ 0, 7, 0, 0, 0, 8, 0, 0, 0 ],
   
6.     [ 0, 0, 3, 0, 0, 0, 0, 2, 0 ],
   
7.     [ 0, 0, 0, 0, 7, 0, 6, 0, 0 ],
   
8.     [ 6, 0, 0, 2, 0, 0, 0, 0, 1 ],
   
9.     [ 0, 4, 0, 0, 0, 0, 7, 0, 0 ],
   
10.     [ 0, 0, 0, 3, 0, 0, 0, 0, 0 ],
    
11. ];

复制代码

perl: old 1m58.981s, new 0m7.008s
gcc[-Ofast]:  old 0m0.673s, new 0m0.082s


sudoku_nd0.txt, sudoku_nd1.txt hui bijiao man
sudoku_nd3.txt, sudoku_nd4.txt sudu ying you dafudude tishen?


new sub best:

1. int best (){
   
2.     int min    = 10;
   
3.     int Magic  = 10;
   
4.     int best   = OK;
   
5.     int posisi = Head;
   
6. 
   
7.     for (int head = Head; head < Tail; head++) {
   
8.         Ijk *w   = &Dit[head];
   
9.         int this = Verti[w->v] | Horiz[w->h] | Bloke[w->b];
   
10.         if (this == ERROR) return ERROR;
    
11.         int maybe = Maybe[this][OK];
    
12. 
    
13.         int that  = Verti[w->v] & Horiz[w->h] & Bloke[w->b];
    
14.         int magic = Maybe[that][OK];
    
15. 
    
16.         if (min > maybe) {
    
17.             posisi = head, best = this,Magic = magic;
    
18.             if (maybe == BEST) break;
    
19.             min = maybe;
    
20.         } else if (min == maybe && Magic < magic) {
    
21.             posisi = head, best = this, Magic = magic;
    
22.         }
    
23.     }
    
24. 
    
25.     Ijk dat = Dit[posisi];
    
26.     Dit[posisi] = Dit[Head];
    
27.     Dit[Head++] = dat;
    
28.     return best;
    
29. } /* best */
    

复制代码

523066680

回复 26# rubyish

你在什么地区？今天回复的时间和往常不太一样。

还有一些优化方案：
对于可能性唯一的数字，比如下图中第五行第五列的数字2，是唯一的，先填入。
然后找出隐含的唯一数字，比如第一行最后一个格，对于该[行]来说有1237 1379 1239 ... 189，8在所有可能数中只出现1次，所以这个8是必填的。
针对每个空缺单元的行列、区块做一次这个判断，填入必填项（循环这个过程，直到没有必填项）。
我的代码中 fill_one_possible_num 函数就是处理这个的，写的很粗糙。


200500080001020000000000000070008000003000020000070600600200001040000700000300000
第一回合：
R:3 C:2 Fill:2
R:4 C:1 Fill:6
R:4 C:8 Fill:7
R:5 C:5 Fill:2
R:7 C:8 Fill:2
R:8 C:1 Fill:2
第二回合：
R:2 C:6 Fill:2
R:3 C:4 Fill:3
R:5 C:1 Fill:1
第三回合：
R:3 C:3 Fill:6

填入10个数字之后变成：
200500080001020000000000200072638000063000027010072600600200001040000702020300000
2,0,0,5,0,0,0,8,0
0,0,1,0,2,0,0,0,0
0,0,0,0,0,0,2,0,0
0,7,2,6,3,8,0,0,0
0,6,3,0,0,0,0,2,7
0,1,0,0,7,2,6,0,0
6,0,0,2,0,0,0,0,1
0,4,0,0,0,0,7,0,2
0,2,0,3,0,0,0,0,0

i7 CPU:
效率区别, gcc不带-O参数编译
填入唯一数之前：0.218s
填入唯一数之后：0.015s

523066680

回复 26# rubyish

有个奇怪的问题，修改后的best函数，遇到nd3的以下两道题的时候，第二道产生了不同的多个结果
第二题位于nd3的2583行，和下面第一个题目配合才会触发问题（神奇不神奇）。
题：
000005002801000000030000000002080000104070030700003048209000700000000054000019300
000000009040006200806007004900605000000290003008000500200000600400070908007060050

输出：
967835412821947563435261897392684175184572639756193248249356781613728954578419326
532814769741936285896527314973685421654291873128743596219358647465172938387469152
532652769741936285896527314973615842654298173128743596219584637465371928387269451
532752769741936285896527314973615842654298173128743596219584637465371928387269451
532952769741936285896527314973615842654298173128743596219584637465371928387269451
（后面三行是无效解）

解决方法：
if (this == OK) echo (sudo);
改为
if (this == OK) {echo (sudo); return; }

速度会变慢，改一下explore函数的return机制即可提速。

另外我把 fill_one_possible_number 改到了你的代码中，效率不输给 Dancing Links 方案
[github]RubyishOPT_02
[github]RubyishOPT_03

solve_multiGame.c
CPU: E5700 3.00GHz, gcc -O2
sudoku17.txt - Time used: 6.215

在i7 CPU上面 3.110 秒

523066680

@rubyish
你的代码如果要改成求多解，要怎么改？
比如 123456789456789123789123456312645978000000000000000000000000000000000000000000000
遍历生成所有可能的终盘。

2017-10-17
改好了，枚举63万种终盘，耗时7秒（同一台电脑上 Dancing Links 方案枚举需要10秒）

相关代码放到了以下分支
Rubyish_multi_answer

调整：在 explore 函数参数中添加 int lv 表示层次，取代全局变量 Head
这个 lv 随着递归层深入而递增(+1)，传递给 best(int begin)，作为Dit数组取值范围的起点。
这样确保在递归过程中 begin 是和递归层同步的。

rubyish

回复 28# 523066680

3Q ~~
sudo44227 + sub fill
[tcc] jiasule 32 bei ~~

1. old:    0m1.843s
   
2. best2:  0m0.142s
   
3. best3:  0m0.122s
   
4. fill:   0m0.057s

复制代码

sub fill:

1. typedef int (*Fill)[10];
   
2. 
   
3. int cmp (const void *a, const void *b){
   
4.     return *(int *)a - *(int *)b;
   
5. }
   
6. 
   
7. # define CHERRY { A, A, A, A, A, A, A, A, A }
   
8. # define A      { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, }
   
9. 
   
10. void fill (Sdk sudo){
    
11.     int I[][10] = CHERRY;
    
12.     int J[][10] = CHERRY;
    
13.     int K[][10] = CHERRY;
    
14. 
    
15.     for (int h = Head; h < Tail; h++) {
    
16.         Ijk *w   = &Dit[h];
    
17.         int this = Verti[w->v] | Horiz[w->h] | Bloke[w->b];
    
18.         kar *may = Maybe[this];
    
19.         for (int i = 1; i <= may[OK]; i++) {
    
20.             int val = may[i];
    
21.             I[w->h][val] = I[w->h][val] == -1 ? h : -2;
    
22.             J[w->v][val] = J[w->v][val] == -1 ? h : -2;
    
23.             K[w->b][val] = K[w->b][val] == -1 ? h : -2;
    
24.         }
    
25.     }
    
26. 
    
27.     Fill ijk[] = { I, J, K };
    
28.     int posi[Tail - Head];
    
29.     int go = 0;
    
30. 
    
31.     for (int i = 0; i < 3; i++) {
    
32.         for (int j = 0; j < 9; j++) {
    
33.             for (int n = 1; n <= 9; n++) {
    
34.                 int this = ijk[i][j][n];
    
35.                 if (this < 0) continue;
    
36.                 Ijk *x = &Dit[this];
    
37.                 if (sudo[x->h][x->v]) continue;
    
38.                 sudo[x->h][x->v] = n;
    
39.                 Horiz[x->h]     |= 1 << n;
    
40.                 Verti[x->v]     |= 1 << n;
    
41.                 Bloke[x->b]     |= 1 << n;
    
42.                 posi[go++]       = this;
    
43.             }
    
44.         }
    
45.     }
    
46. 
    
47.     if (!go) return;
    
48. 
    
49.     // SORT INDEX, IMPORTANT!!
    
50.     qsort (posi, go, sizeof(int), cmp);
    
51.     for (int i = 0; i < go; i++)
    
52.         Dit[posi[i]] = Dit[Head++];
    
53. 
    
54.     fill (sudo);
    
55. 
    
56. } /* fill */
    

复制代码