忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
楼主: 523066680

[Perl]解数独题 [复制链接]

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-10-11 12:38 |显示全部楼层
本帖最后由 523066680 于 2017-10-11 19:12 编辑

回复 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秒


评分

参与人数 1信誉积分 +10 收起 理由
rubyish + 10 3Q~~

查看全部评分

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-10-14 00:47 |显示全部楼层
回复 21# 523066680

test xia meiyou dance de sudu shi ruhe??
  1. # include <stdio.h>

  2. # define ERROR 0b1111111110
  3. # define OK    0
  4. # define BEST  1

  5. typedef char kar;
  6. typedef int Sdk[][9];
  7. typedef struct { int v, h, b; } Ijk;

  8. void explore (Sdk);
  9. void echo (Sdk);
  10. void play (Sdk);
  11. void init (void);
  12. int best ();

  13. int Verti[9];
  14. int Horiz[9];
  15. int Bloke[9];
  16. int Hover[9][9];
  17. kar Maybe[1024][10];
  18. Ijk Dit[81];
  19. int Head;
  20. int Tail;
  21. int Lost;
  22. int main (){

  23.     Sdk sudo1 = {
  24.         { 0, 0, 0, 0, 0, 0, 0, 9, 0 },
  25.         { 1, 9, 0, 4, 7, 0, 6, 0, 8 },
  26.         { 0, 5, 2, 8, 1, 9, 4, 0, 7 },
  27.         { 2, 0, 0, 0, 4, 8, 0, 0, 0 },
  28.         { 0, 0, 9, 0, 0, 0, 5, 0, 0 },
  29.         { 0, 0, 0, 7, 5, 0, 0, 0, 9 },
  30.         { 9, 0, 7, 3, 6, 4, 1, 8, 0 },
  31.         { 5, 0, 6, 0, 8, 1, 0, 7, 4 },
  32.         { 0, 8, 0, 0, 0, 0, 0, 0, 0 },
  33.     };


  34.     init ();
  35.    
  36.     //for (int i = 0; i < 10000; i++)
  37.     play (sudo1);
  38.     // play (sudo3);
  39.     // play (sudo2);
  40.     // play (sudo1);

  41. } /* main */

  42. void init (){
  43.     for (int i = 0; i < 9; i++) {
  44.         int i3 = 3 * (i / 3);
  45.         for (int j = 0; j < 9; j++)
  46.             Hover[i][j] = j / 3 + i3;
  47.     }
  48.     for (int n = 0; n < ERROR; n += 2) {
  49.         int len = 0;
  50.         for (int i = 1; i <= 9; i++) {
  51.             if (n & 1 << i) continue;
  52.             Maybe[n][1 + len++] = i;
  53.         }
  54.         Maybe[n][0] = len;
  55.     }
  56. }

  57. void play (Sdk sudo){
  58.     for (int i = 0; i < 9; i++)
  59.         Horiz[i] = Verti[i] = Bloke[i] = 0;

  60.     Head = 0;

  61.     for (int i = 0; i < 9; i++) {
  62.         for (int j = 0; j < 9; j++) {
  63.             int k = Hover[i][j];
  64.             if (!sudo[i][j]) {
  65.                 Dit[Head++] = (Ijk) {j, i, k };
  66.                 continue;
  67.             }

  68.             Horiz[i] |= 1 << sudo[i][j];
  69.             Verti[j] |= 1 << sudo[i][j];
  70.             Bloke[k] |= 1 << sudo[i][j];
  71.         }
  72.     }

  73.     Tail = Head;
  74.     Lost = Tail + 1;
  75.     Head = 0;

  76.     explore (sudo);
  77.     puts (" ___________________");
  78. } /* play */

  79. void explore (Sdk sudo) {
  80.     if (Head == Lost) return;
  81.     int this = best ();
  82.     if (this == ERROR) return;
  83.     if (this == OK) echo (sudo);

  84.     kar *maybe = &Maybe[this][OK];
  85.     Ijk *w     = &Dit[Head - 1];

  86.     for (int it = 1; it <= maybe[OK]; it++) {
  87.         int n = 1 << maybe[it];
  88.         sudo[w->h][w->v] = maybe[it];
  89.         Horiz[w->h] |= n;
  90.         Verti[w->v] |= n;
  91.         Bloke[w->b] |= n;
  92.         explore (sudo);
  93.         Horiz[w->h] ^= n;
  94.         Verti[w->v] ^= n;
  95.         Bloke[w->b] ^= n;
  96.     }
  97.     sudo[w->h][w->v] = 0;
  98.     Head--;
  99. } /* explore */

  100. int best (){
  101.     int min    = 10;
  102.     int best   = OK;
  103.     int posisi = Head;

  104.     for (int head = Head; head < Tail; head++) {
  105.         Ijk *w   = &Dit[head];
  106.         int this = Verti[w->v] | Horiz[w->h] | Bloke[w->b];
  107.         if (this == ERROR) return ERROR;
  108.         int maybe = Maybe[this][OK];

  109.         if (min > maybe) {
  110.             posisi = head, best = this;
  111.             if (maybe == BEST) break;
  112.             min = maybe;
  113.         }
  114.     }

  115.     Ijk dat = Dit[posisi];
  116.     Dit[posisi] = Dit[Head];
  117.     Dit[Head++] = dat;
  118.     return best;
  119. } /* best */

  120. void echo (Sdk sudo){
  121.     for (int i = 0; i < 9; i++) {
  122.         if (!(i % 3)) puts ("");

  123.         for (int j = 0; j < 9; j++) {
  124.             if (!(j % 3)) printf (" ");
  125.             printf ("%d ", sudo[i][j]);
  126.         }
  127.         puts ("");
  128.     }
  129. }
复制代码


论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-10-14 00:47 |显示全部楼层
本帖最后由 rubyish 于 2017-10-13 20:51 编辑

d  e  l  ~  ~

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-10-14 15:11 |显示全部楼层
本帖最后由 523066680 于 2017-10-15 08:42 编辑

回复 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. # include <stdio.h>
  7. # include <stdlib.h>
  8. # include <string.h>
  9. # include <time.h>

  10. # define ERROR 0b1111111110
  11. # define OK    0
  12. # define BEST  1

  13. typedef char kar;
  14. typedef int Sdk[9][9];
  15. typedef struct { int v, h, b; } Ijk;

  16. struct game {
  17.     int id;
  18.     char s[100];
  19.     struct game *next;
  20. };

  21. void str_to_mat( char *s, Sdk sudo );
  22. void load_games( struct game * games, char *filename  );
  23. void explore (Sdk);
  24. void echo (Sdk);
  25. void play (Sdk);
  26. void init (void);
  27. int best ();

  28. int Verti[9];
  29. int Horiz[9];
  30. int Bloke[9];
  31. int Hover[9][9];
  32. kar Maybe[1024][10];
  33. Ijk Dit[81];
  34. int Head;
  35. int Tail;
  36. int Lost;

  37. int main (int argc, char *argv[])
  38. {
  39.     int time_a;
  40.     Sdk sudo;
  41.     struct game *gamenode = (struct game *)malloc( sizeof(struct game) );
  42.     load_games( gamenode, "../../Puzzles/sudoku_nd3.txt" );

  43.     //备用数据初始化
  44.     init ();

  45.     while ( gamenode->next != NULL )
  46.     {
  47.         time_a = clock();
  48.         str_to_mat( gamenode->s, sudo );
  49.         play (sudo);

  50.         // fprintf(stderr, "Game ID: %d, Time used: %.3f\n", gamenode->id,
  51.         //     (float)(clock()-time_a)/(float)CLOCKS_PER_SEC );
  52.         gamenode = gamenode->next;
  53.         //break;
  54.     }

  55.     fprintf(stderr, "Time used: %.3f\n", (float)clock() / (float)CLOCKS_PER_SEC );
  56.     return 0;
  57. } /* main */

  58. void init ()
  59. {
  60.     for (int i = 0; i < 9; i++)
  61.     {
  62.         int i3 = 3 * (i / 3);
  63.         for (int j = 0; j < 9; j++)
  64.             Hover[i][j] = j / 3 + i3;
  65.     }

  66.     for (int n = 0; n < ERROR; n += 2)
  67.     {
  68.         int len = 0;
  69.         for (int i = 1; i <= 9; i++)
  70.         {
  71.             if (n & 1 << i) continue;
  72.             Maybe[n][1 + len++] = i;
  73.         }
  74.         Maybe[n][0] = len;
  75.     }
  76. }

  77. void play (Sdk sudo)
  78. {
  79.     static int i, j, k;
  80.     for (i = 0; i < 9; i++)
  81.         Horiz[i] = Verti[i] = Bloke[i] = 0;

  82.     Head = 0;
  83.     for (i = 0; i < 9; i++)
  84.     {
  85.         for (j = 0; j < 9; j++)
  86.         {
  87.             k = Hover[i][j];
  88.             if (!sudo[i][j])
  89.             {
  90.                 Dit[Head++] = (Ijk) {j, i, k };
  91.                 continue;
  92.             }

  93.             Horiz[i] |= 1 << sudo[i][j];
  94.             Verti[j] |= 1 << sudo[i][j];
  95.             Bloke[k] |= 1 << sudo[i][j];
  96.         }
  97.     }

  98.     Tail = Head;
  99.     Lost = Tail + 1;
  100.     Head = 0;

  101.     explore (sudo);
  102.     puts (" ___________________");
  103. } /* play */

  104. void explore (Sdk sudo)
  105. {
  106.     if (Head == Lost) return;
  107.     int this = best ();
  108.     if (this == ERROR) return;
  109.     if (this == OK) echo (sudo);

  110.     kar *maybe = &Maybe[this][OK];
  111.     Ijk *w     = &Dit[Head - 1];

  112.     for (int it = 1; it <= maybe[OK]; it++)
  113.     {
  114.         int n = 1 << maybe[it];
  115.         sudo[w->h][w->v] = maybe[it];
  116.         Horiz[w->h] |= n;
  117.         Verti[w->v] |= n;
  118.         Bloke[w->b] |= n;
  119.         explore (sudo);
  120.         Horiz[w->h] ^= n;
  121.         Verti[w->v] ^= n;
  122.         Bloke[w->b] ^= n;
  123.     }
  124.     sudo[w->h][w->v] = 0;
  125.     Head--;
  126. } /* explore */

  127. int best ()
  128. {
  129.     int min    = 10;
  130.     int best   = OK;
  131.     int posisi = Head;

  132.     for (int head = Head; head < Tail; head++)
  133.     {
  134.         Ijk *w   = &Dit[head];
  135.         int this = Verti[w->v] | Horiz[w->h] | Bloke[w->b];
  136.         if (this == ERROR) return ERROR;
  137.         int maybe = Maybe[this][OK];

  138.         if (min > maybe) {
  139.             posisi = head, best = this;
  140.             if (maybe == BEST) break;
  141.             min = maybe;
  142.         }
  143.     }

  144.     Ijk dat = Dit[posisi];
  145.     Dit[posisi] = Dit[Head];
  146.     Dit[Head++] = dat;
  147.     return best;
  148. } /* best */

  149. void echo (Sdk sudo)
  150. {
  151.     for (int i = 0; i < 9; i++)
  152.     {
  153.         if (!(i % 3)) puts ("");
  154.         for (int j = 0; j < 9; j++)
  155.         {
  156.             if (!(j % 3)) printf (" ");
  157.             printf ("%d ", sudo[i][j]);
  158.         }
  159.         puts ("");
  160.     }
  161. }

  162. void load_games( struct game * node, char *filename  )
  163. {
  164.     FILE *fp;
  165.     fp = fopen( filename, "r" );

  166.     int id = 1;
  167.     while ( ! feof( fp ) )
  168.     {
  169.         fgets( node->s, 100, fp );
  170.         //如果读取到空行或者残缺行,提前break,下一节点为 NULL
  171.         if ( (int)strlen(node->s) < 81 ) break;
  172.         node->id = id++;
  173.         node->next = (struct game *) malloc( sizeof(struct game) );
  174.         node = node->next;
  175.     }
  176.     node->next = NULL;
  177. }

  178. void str_to_mat( char *s, Sdk sudo )
  179. {
  180.     static int i, r, c;
  181.     static int delta = '0' - 0;
  182.     for (i = 0; i < 81; i++ )  //r,c from 0,0 to 8,8
  183.     {
  184.         r = (int)(i/9);
  185.         c = (int)(i%9);
  186.         sudo[r][c] = s[i] - delta;  //char to integer
  187.     }
  188. }
复制代码

解题效率(不含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 参数后速度相当快。

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-10-14 15:22 |显示全部楼层
本帖最后由 523066680 于 2017-10-14 15:26 编辑

耗时较长的题目行号(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 7 2  6 3 8  4 1 9
  5. 9 6 3  4 5 1  8 2 7
  6. 8 1 4  9 7 2  6 5 3

  7. 6 3 8  2 9 7  5 4 1
  8. 1 4 9  8 6 5  7 3 2
  9. 7 2 5  3 1 4  9 6 8
  10. ___________________
  11. Game ID: 44227, Time used: 0.452
复制代码

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-10-15 21:04 |显示全部楼层
本帖最后由 rubyish 于 2017-10-15 18:21 编辑

回复 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.     for (int head = Head; head < Tail; head++) {
  7.         Ijk *w   = &Dit[head];
  8.         int this = Verti[w->v] | Horiz[w->h] | Bloke[w->b];
  9.         if (this == ERROR) return ERROR;
  10.         int maybe = Maybe[this][OK];

  11.         int that  = Verti[w->v] & Horiz[w->h] & Bloke[w->b];
  12.         int magic = Maybe[that][OK];

  13.         if (min > maybe) {
  14.             posisi = head, best = this,Magic = magic;
  15.             if (maybe == BEST) break;
  16.             min = maybe;
  17.         } else if (min == maybe && Magic < magic) {
  18.             posisi = head, best = this, Magic = magic;
  19.         }
  20.     }

  21.     Ijk dat = Dit[posisi];
  22.     Dit[posisi] = Dit[Head];
  23.     Dit[Head++] = dat;
  24.     return best;
  25. } /* best */
复制代码


论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-10-15 22:46 |显示全部楼层
本帖最后由 523066680 于 2017-10-16 09:06 编辑

回复 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

评分

参与人数 1信誉积分 +10 收起 理由
rubyish + 10 赞一个! 3Q ~~

查看全部评分

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-10-16 16:13 |显示全部楼层
本帖最后由 523066680 于 2017-10-17 14:49 编辑

回复 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 秒

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-10-16 22:39 |显示全部楼层
本帖最后由 523066680 于 2017-10-17 15:37 编辑

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

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

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

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

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-10-18 01:05 |显示全部楼层
回复 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. int cmp (const void *a, const void *b){
  3.     return *(int *)a - *(int *)b;
  4. }

  5. # define CHERRY { A, A, A, A, A, A, A, A, A }
  6. # define A      { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, }

  7. void fill (Sdk sudo){
  8.     int I[][10] = CHERRY;
  9.     int J[][10] = CHERRY;
  10.     int K[][10] = CHERRY;

  11.     for (int h = Head; h < Tail; h++) {
  12.         Ijk *w   = &Dit[h];
  13.         int this = Verti[w->v] | Horiz[w->h] | Bloke[w->b];
  14.         kar *may = Maybe[this];
  15.         for (int i = 1; i <= may[OK]; i++) {
  16.             int val = may[i];
  17.             I[w->h][val] = I[w->h][val] == -1 ? h : -2;
  18.             J[w->v][val] = J[w->v][val] == -1 ? h : -2;
  19.             K[w->b][val] = K[w->b][val] == -1 ? h : -2;
  20.         }
  21.     }

  22.     Fill ijk[] = { I, J, K };
  23.     int posi[Tail - Head];
  24.     int go = 0;

  25.     for (int i = 0; i < 3; i++) {
  26.         for (int j = 0; j < 9; j++) {
  27.             for (int n = 1; n <= 9; n++) {
  28.                 int this = ijk[i][j][n];
  29.                 if (this < 0) continue;
  30.                 Ijk *x = &Dit[this];
  31.                 if (sudo[x->h][x->v]) continue;
  32.                 sudo[x->h][x->v] = n;
  33.                 Horiz[x->h]     |= 1 << n;
  34.                 Verti[x->v]     |= 1 << n;
  35.                 Bloke[x->b]     |= 1 << n;
  36.                 posi[go++]       = this;
  37.             }
  38.         }
  39.     }

  40.     if (!go) return;

  41.     // SORT INDEX, IMPORTANT!!
  42.     qsort (posi, go, sizeof(int), cmp);
  43.     for (int i = 0; i < go; i++)
  44.         Dit[posi[i]] = Dit[Head++];

  45.     fill (sudo);

  46. } /* fill */
复制代码


评分

参与人数 1信誉积分 +10 收起 理由
523066680 + 10 i7CPU Sudoku17: 2.5s

查看全部评分

您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP