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

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-09-21 17:35 |显示全部楼层
本帖最后由 523066680 于 2017-09-21 17:58 编辑

回复 4# rubyish

你这个代码烧了我不少脑细胞啊,平时很少使用位操作,只能通过 print 看看端倪。
有些变量也是在探索原理后才明白含义

VERTI -> vertical       列数据
HORIS -> horizontal  行数据
BLOKE -> block        区块数据

$DAT 指空缺单元数组的最大下标,$LOST 表示越界
$DIT 表示空缺单元数组的起点,但是全拼猜不到。

函数 init 是初始化区块坐标对照表,以及对各种可能的类型以及可选数字建立数据表。
函数 play 其实也是初始化,读取数独游戏数据。explore 是递归解题。

优点:这种查表方案可以省去大量的数组遍历操作。

  1. #http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=4267389&page=1#pid24648966
  2. #!/usr/bin/perl
  3. # version 26, subversion 0 (v5.26.0)

  4. use 5.010;
  5. sub ERROR()  { 0b1111111110 }
  6. sub FINISH() { 0 }
  7. sub BEST()   { 1 }
  8. sub MIN()    { 10 }
  9. my ( @VERTI, @HORIS, @BLOKE, @MAYBE, @HOVER );
  10. my ( @GIMME, $DIT, $DAT, $LOST );

  11. my $sudo9 = [    # 0.536s
  12.     [ 0, 0, 0, 0, 0, 0, 8, 0, 0 ],
  13.     [ 0, 0, 2, 0, 7, 0, 0, 4, 0 ],
  14.     [ 0, 0, 0, 3, 0, 0, 6, 0, 1 ],
  15.     [ 6, 0, 0, 1, 0, 0, 0, 0, 5 ],
  16.     [ 0, 0, 9, 0, 4, 0, 0, 0, 0 ],
  17.     [ 0, 0, 0, 0, 5, 7, 0, 0, 0 ],
  18.     [ 0, 0, 7, 0, 0, 5, 0, 9, 0 ],
  19.     [ 3, 0, 0, 0, 0, 0, 1, 0, 8 ],
  20.     [ 0, 8, 0, 0, 0, 0, 0, 0, 0 ],
  21. ];

  22. init();
  23. play($sudo9);

  24. # ____________________SUB____________________
  25. sub init
  26. {
  27.     # i,j : 0,0 -> 8,8 对应3x3区块信息
  28.     for my $i ( 0 .. 8 )
  29.     {
  30.         my $i3 = 3 * int( $i / 3 );
  31.         for my $j ( 0 .. 8 )
  32.         {
  33.             $HOVER[$i][$j] = int( $j / 3 ) + $i3;
  34.         }
  35.     }

  36.     for ( my $n = 0 ; $n < ERROR ; $n += 2 )
  37.     {
  38.         printf "%010b : ", $n;
  39.         for my $i ( 1 .. 9 )
  40.         {
  41.             #如果预选数字和已有数字的"位"冲突,则略过;如果互补,则保留
  42.             next if ( $n & (1 << $i) );
  43.             printf "%d ", $i;
  44.             push @{ $MAYBE[$n] }, $i;
  45.         }
  46.         print "\n";
  47.     }
  48. }

  49. sub play
  50. {
  51.     my $sudo = shift;
  52.     @VERTI = @HORIS = @BLOKE = (0) x 9;
  53.     @GIMME = ();
  54.     $DIT   = 0;

  55.     for my $i ( 0 .. 8 )
  56.     {
  57.         for my $j ( 0 .. 8 )
  58.         {
  59.             my $k = $HOVER[$i][$j];

  60.             # 把空单元的坐标 [row, col, block] 堆入 @GIMME
  61.             if ( !$sudo->[$i][$j] ) {
  62.                 push @GIMME, [ $i, $j, $k ];
  63.                 next;
  64.             }

  65.             #如果非零,存储 9列/9行/9个区块的数据
  66.             $VERTI[$j] |= 1 << $sudo->[$i][$j];
  67.             $HORIS[$i] |= 1 << $sudo->[$i][$j];
  68.             $BLOKE[$k] |= 1 << $sudo->[$i][$j];
  69.         }
  70.     }

  71.     #VERTI HORIS BLOKE 用来存储行、列、区块的已有数字,并将数字转换为位置
  72.     #通过 $HORIS[$i] | $VERTI[$j] | $BLOKE[$k] 得到已有数字的组合模型

  73.     grep { printf "%010b ", $VERTI[$_] } (0..8); print "\n";
  74.     grep { printf "%010b ", $HORIS[$_] } (0..8); print "\n";
  75.     grep { printf "%010b ", $BLOKE[$_] } (0..8); print "\n";

  76.     $LOST = @GIMME + 1;
  77.     $DAT  = $#GIMME;

  78.     #求解
  79.     explore($sudo);
  80. }

  81. sub best
  82. {
  83.     my ( $min, $best, $posi ) = ( MIN, FINISH, $DAT );

  84.     #遍历空缺单元列表,从$DIT 到 $DAT,$DIT最初起点为 0
  85.     for my $that ( $DIT .. $DAT )
  86.     {
  87.         my ( $i, $j, $k ) = @{ $GIMME[$that] };
  88.         my $this = $HORIS[$i] | $VERTI[$j] | $BLOKE[$k];

  89.         return ERROR if $this == ERROR;

  90.         my $maybe = @{ $MAYBE[$this] };

  91.         if ( $maybe < $min )
  92.         {
  93.             $posi = $that;
  94.             $best = $this;
  95.             last if $maybe == BEST;
  96.             $min = $maybe;
  97.         }
  98.     }

  99.     #在空缺单元坐标数组中,调换 所选项和 $DIT 项 (下次不再选入)
  100.     @GIMME[ $DIT, $posi ] = @GIMME[ $posi, $DIT ];
  101.     $DIT++;
  102.     return $best;
  103. }

  104. sub explore
  105. {
  106.     my $sudo = shift;

  107.     #如果下标越界,提前结束
  108.     return if $DIT == $LOST;

  109.     #选择可选数字最少的单元索引
  110.     my $this = best();
  111.     return if $this == ERROR;

  112.     #空缺单元填充完时,best()函数没有执行循环,返回的 $best == FINISH,解题完成
  113.     echo($sudo) if $this == FINISH;

  114.     my ( $i, $j, $k ) = @{ $GIMME[ $DIT - 1 ] };

  115.     #对于每一个选项
  116.     for my $n ( @{ $MAYBE[$this] } )
  117.     {
  118.         my $that = 1 << $n;
  119.         $sudo->[$i][$j] = $n;
  120.         $HORIS[$i] |= $that;
  121.         $VERTI[$j] |= $that;
  122.         $BLOKE[$k] |= $that;
  123.         
  124.         explore($sudo);

  125.         #恢复数据
  126.         $HORIS[$i] ^= $that;
  127.         $VERTI[$j] ^= $that;
  128.         $BLOKE[$k] ^= $that;
  129.     }

  130.     #恢复数据
  131.     $sudo->[$i][$j] = 0;
  132.     $DIT--;
  133. }

  134. sub echo
  135. {
  136.     my ( $sudo, $i ) = @_;
  137.     for my $A (@$sudo) {
  138.         say '' if !( $i++ % 3 );
  139.         say " @$A[0..2]  @$A[3..5]  @$A[6..8]";
  140.     }
  141. }
复制代码

论坛徽章:
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-09-22 04:04 |显示全部楼层
回复 11# 523066680

Dancing Links tingshuo nashi zuikuaide.
Taifuzale xuebuhui ~~

Faxian rosetta you caiyong dancing links suanfa de javascript.
Yushi zuole 1 ge jiandan de xiaoceshi,
ceshile sudo9.

rosetta: javascript de bufen xiugai

  1. // [ SOME STRING ].forEach(reduceGrid);

  2. // Or of you want to create all the grids of a particular n-size.
  3. // I run out of stack space at n = 9
  4. //let n = 2;
  5. //let s = new Array(Math.pow(n, 4)).fill('.').join('');
  6. //reduceGrid(s);

  7. const sudo9 =
  8. "......8....2.7..4....3..6.16..1....5..9.4........57.....7..5.9.3.....1.8.8......."

  9. reduceGrid(sudo9);
复制代码


js: version 57

time js -b sudo.js

rosetta:
  1. +-------+-------+-------+
  2. | 5 9 3 | 4 1 6 | 8 2 7 |
  3. | 1 6 2 | 5 7 8 | 3 4 9 |
  4. | 7 4 8 | 3 2 9 | 6 5 1 |
  5. +-------+-------+-------+
  6. | 6 7 4 | 1 8 2 | 9 3 5 |
  7. | 8 5 9 | 6 4 3 | 7 1 2 |
  8. | 2 3 1 | 9 5 7 | 4 8 6 |
  9. +-------+-------+-------+
  10. | 4 1 7 | 8 6 5 | 2 9 3 |
  11. | 3 2 5 | 7 9 4 | 1 6 8 |
  12. | 9 8 6 | 2 3 1 | 5 7 4 |
  13. +-------+-------+-------+

  14. runtime = 602.870 ms

  15. real    0m0.750s
  16. user    0m0.748s
  17. sys    0m0.037s
复制代码



  1. 5 9 3  4 1 6  8 2 7
  2. 1 6 2  5 7 8  3 4 9
  3. 7 4 8  3 2 9  6 5 1

  4. 6 7 4  1 8 2  9 3 5
  5. 8 5 9  6 4 3  7 1 2
  6. 2 3 1  9 5 7  4 8 6

  7. 4 1 7  8 6 5  2 9 3
  8. 3 2 5  7 9 4  1 6 8
  9. 9 8 6  2 3 1  5 7 4
  10. runtime = 86.137 ms

  11. real    0m0.232s
  12. user    0m0.224s
  13. sys    0m0.033s
复制代码


sudo.js

  1. const ERROR = 1022;  // 0b1111111110
  2. const OK    = 0;
  3. const BEST  = 1;
  4. const MIN   = 10;
  5. const int   = Math.floor;

  6. let Verti = [];
  7. let Horiz = [];
  8. let Bloke = [];
  9. let Hover = [];
  10. let Maybe = [];
  11. let Gimme = [];
  12. let Dit;
  13. let Dat;

  14. let sudo3 = [
  15.     [8, 0, 0, 0, 0, 0, 0, 0, 0],
  16.     [0, 0, 3, 6, 0, 0, 0, 0, 0],
  17.     [0, 7, 0, 0, 9, 0, 2, 0, 0],
  18.     [0, 5, 0, 0, 0, 7, 0, 0, 0],
  19.     [0, 0, 0, 0, 4, 5, 7, 0, 0],
  20.     [0, 0, 0, 1, 0, 0, 0, 3, 0],
  21.     [0, 0, 1, 0, 0, 0, 0, 6, 8],
  22.     [0, 0, 8, 5, 0, 0, 0, 1, 0],
  23.     [0, 9, 0, 0, 0, 0, 4, 0, 0],
  24. ];

  25. let sudo9 = [
  26.     [0, 0, 0, 0, 0, 0, 8, 0, 0],
  27.     [0, 0, 2, 0, 7, 0, 0, 4, 0],
  28.     [0, 0, 0, 3, 0, 0, 6, 0, 1],
  29.     [6, 0, 0, 1, 0, 0, 0, 0, 5],
  30.     [0, 0, 9, 0, 4, 0, 0, 0, 0],
  31.     [0, 0, 0, 0, 5, 7, 0, 0, 0],
  32.     [0, 0, 7, 0, 0, 5, 0, 9, 0],
  33.     [3, 0, 0, 0, 0, 0, 1, 0, 8],
  34.     [0, 8, 0, 0, 0, 0, 0, 0, 0],
  35. ];


  36. init ();

  37. play (sudo9);


  38. /* ____________________SUB____________________ */

  39. function init (){
  40.     for (let i = 0; i < 9; i++) {
  41.         let i3 = 3 * int (i / 3);
  42.         Hover[i] = [];
  43.         for (let j = 0; j < 9; j++)
  44.             Hover[i][j] = int (j / 3) + i3;
  45.     }
  46.     for (let n = 0; n < ERROR; n += 2) {
  47.         Maybe[n] = [];
  48.         for (let i = 1; i <= 9; i++) {
  49.             if (n & 1 << i) continue;
  50.             Maybe[n].push (i);
  51.         }
  52.     }
  53. }

  54. function play (sudoku){
  55.     for (let i = 0; i < 9; i++)
  56.         Horiz[i] = Verti[i] = Bloke[i] = 0;

  57.     Gimme = [];
  58.     for (let i = 0; i < 9; i++) {
  59.         for (let j = 0; j < 9; j++) {
  60.             let k = Hover[i][j];
  61.             if (!sudoku[i][j]) {
  62.                 Gimme.push ([i, j, k]);
  63.                 continue;
  64.             }

  65.             Horiz[i] |= 1 << sudoku[i][j];
  66.             Verti[j] |= 1 << sudoku[i][j];
  67.             Bloke[k] |= 1 << sudoku[i][j];
  68.         }
  69.     }

  70.     Dat = Gimme.length;
  71.     Dit = 0;
  72.     // FOR  Gimme[Dit - 1] is undefined
  73.     Gimme.push ([0, 0, 0])
  74.     explore (sudoku);
  75. } /* play */

  76. function explore (sudoku) {
  77.     if (Dit > Dat) return;
  78.     let This = best ();

  79.     if (This == ERROR) return;
  80.     if (This == OK) echo (sudoku);

  81.     let maybe = Maybe[This];
  82.     let [h, v, b] = Gimme[Dit - 1];

  83.     for (let it = 0; it < maybe.length; it++) {
  84.         let n = 1 << maybe[it];
  85.         sudoku[h][v] = maybe[it];
  86.         Horiz[h] |= n;
  87.         Verti[v] |= n;
  88.         Bloke[b] |= n;
  89.         explore (sudoku);
  90.         Horiz[h] ^= n;
  91.         Verti[v] ^= n;
  92.         Bloke[b] ^= n;
  93.     }
  94.     sudoku[h][v] = 0;
  95.     Dit--;

  96. } /* explore */

  97. function best (){
  98.     let min  = MIN;
  99.     let best = OK;
  100.     let posi = Dit;

  101.     for (let it = Dit; it < Dat; it++) {
  102.         let [h, v, b] = Gimme[it];
  103.         let that = Horiz[h] | Verti[v] | Bloke[b];
  104.         if (that == ERROR) return ERROR;

  105.         let maybe = Maybe[that].length;
  106.         if (min > maybe) {
  107.             posi = it;
  108.             best = that;
  109.             if (maybe == BEST) break;
  110.             min = maybe;
  111.         }
  112.     }

  113.     let w = Gimme[posi];
  114.     Gimme[posi] = Gimme[Dit];
  115.     Gimme[Dit]  = w;
  116.     Dit++;
  117.     return best;
  118. } /* best */

  119. function echo (sudoku){
  120.     for (let i = 0; i < 9; i++) {
  121.         if (!(i % 3)) print ();
  122.         for (let j = 0; j < 9; j++) {
  123.             if (!(j % 3)) putstr (' ');
  124.             putstr (sudoku[i][j]), putstr (' ');
  125.         }
  126.         print ();
  127.     }
  128. }

复制代码



js zhenshi kuai,

perl    0m0.532s
js1.85    0m0.092s
C    0m0.010s

time js -m -b sudo.js
  1. 5 9 3  4 1 6  8 2 7
  2. 1 6 2  5 7 8  3 4 9
  3. 7 4 8  3 2 9  6 5 1

  4. 6 7 4  1 8 2  9 3 5
  5. 8 5 9  6 4 3  7 1 2
  6. 2 3 1  9 5 7  4 8 6

  7. 4 1 7  8 6 5  2 9 3
  8. 3 2 5  7 9 4  1 6 8
  9. 9 8 6  2 3 1  5 7 4
  10. runtime = 71.417 ms

  11. real    0m0.092s
  12. user    0m0.076s
  13. sys    0m0.013s
复制代码



jsshell dl here:
https://archive.mozilla.org/pub/ ... st-mozilla-central/
jsshell-XXXXXX.zip

论坛徽章:
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-09-22 08:52 |显示全部楼层
本帖最后由 523066680 于 2017-09-22 10:54 编辑

回复 12# rubyish

这个 Dancing Links JS 实现是挺快,我用 nodejs 运行的。但是有缺点,遇到以下题目会崩溃:
  1. sudoku_nd3.txt
  2. '7.56...19........89....8.....81.2.7...13..4.237...5.9.8.3..1.25...5....41........',
  3. '.....4...7.......2.....61.....2.......4...3..8..79.6....78....9.36........1......',
  4. '...3.1...49......638.......1.5..7.......9...8.........6...4...........5...3...71.',

  5. sudoku_nd4.txt
  6. '......3......2.1..1.84.9.....7....2..3.6...7...6.7...8....5846.2........9..1.....',
  7. '.....53..6.....5.8...1...2.45.8...1.3.....4.5..2.........2.18....7.3..6..2...4...',
  8. '....9..3...5..2.4.7.94....13.1....98.4.9........8..6..2...13..7..36...151....9...',
复制代码

如果测试 sudoku_nd2.txt 的题目,会有更多的崩溃,以及剩下的部分累计耗时超过100秒。


Dancing Links 求解精确覆盖问题有一个博文说的比较详细:

跳跃的舞者,舞蹈链(Dancing Links)算法——求解精确覆盖问题
http://www.cnblogs.com/grenet/p/3145800.html

算法实践——舞蹈链(Dancing Links)算法求解数独
http://www.cnblogs.com/grenet/p/3163550.html


我照着这个博文实现了 Perl 版本解精确覆盖问题的代码,用 hash 实现 left right up down 节点。
  1. =info
  2.     Perl - Dancing Links
  3.     523066680 2017-09
  4. =cut

  5. use IO::Handle;
  6. use Data::Dumper;
  7. use Time::HiRes qw/time/;
  8. STDOUT->autoflush(1);

  9. my $time_a = time();

  10. my $mat = [
  11.     [0,0,1,0,1,1,0],
  12.     [1,0,0,1,0,0,1],
  13.     [0,1,1,0,0,1,0],
  14.     [1,0,0,1,0,0,0],
  15.     [0,1,0,0,0,0,1],
  16.     [0,0,0,1,1,0,1]
  17. ];

  18. my $links;
  19. my $left;
  20. my $right;
  21. my $ubound = $#{$mat->[0]};
  22. my $len = $ubound+1;

  23. my $head;
  24. my $C = [];
  25. grep { $C->[$_] = {} } ( 0 .. $len );

  26. for my $col ( 0 .. $len )
  27. {
  28.     $left = $col == 0 ? $len : $col-1;
  29.     $right = $col == $len ? 0 : $col+1;
  30.     $C->[$col]{left} = $C->[$left];
  31.     $C->[$col]{right} = $C->[$right];
  32.     $C->[$col]{up} = $C->[$col];
  33.     $C->[$col]{down} = $C->[$col];
  34.     $C->[$col]{col} = $col; #temp
  35. }

  36. $head = $C->[0];

  37. my $E = [{}];  #$E->[0] 占位
  38. push_element( $E, \@{$mat->[0]}, 1 );
  39. grep { push_element( $E, \@{$mat->[$_]}, $_ + 1 ) } ( 1 .. $#$mat );

  40. print_links($head);

  41. my @result;
  42. dance($head, \@result, 0);
  43. print "Result: ", join(",", @result);

  44. printf "\n%.5fs\n", time()-$time_a;

  45. sub dance
  46. {
  47.     my ($head, $arr, $lv) = @_;

  48.     if ( $head->{right} == $head )
  49.     {
  50.         print join(",", @$arr);
  51.         return 1;
  52.     }

  53.     my $c = $head->{right};
  54.     my $r = $c->{down};
  55.     my $ele;

  56.     while ( $r != $c )
  57.     {
  58.         $ele = $r;

  59.         do {
  60.             remove_col( $ele->{col} );
  61.             $ele = $ele->{right};
  62.         }
  63.         until ( $ele == $r );

  64.         if ( dance($head, $arr, $lv+1) == 1)
  65.         {
  66.             $arr->[$lv] = $r->{row};
  67.             return 1;
  68.         }

  69.         do {
  70.             resume_col( $ele->{col} );
  71.             $ele = $ele->{right};
  72.         }
  73.         until ( $ele == $r );
  74.      
  75.         $r = $r->{down};
  76.     }
  77. }

  78. sub remove_col
  79. {
  80.     my ( $sel ) = @_;

  81.     $sel->{left}{right} = $sel->{right};
  82.     $sel->{right}{left} = $sel->{left};

  83.     my $vt = $sel->{down};
  84.     my $hz;

  85.     for ( ; $vt != $sel; $vt = $vt->{down})
  86.     {
  87.         $hz = $vt->{right};
  88.         for (  ; $hz != $vt; $hz = $hz->{right})
  89.         {
  90.             $hz->{up}{down} = $hz->{down};
  91.             $hz->{down}{up} = $hz->{up};
  92.         }
  93.     }
  94. }

  95. sub resume_col
  96. {
  97.     my ( $sel ) = @_;

  98.     $sel->{left}{right} = $sel;
  99.     $sel->{right}{left} = $sel;

  100.     my $vt = $sel->{up};
  101.     my $hz;

  102.     for ( ; $vt != $sel; $vt = $vt->{up})
  103.     {
  104.         $hz = $vt->{right};
  105.         for (  ; $hz != $vt; $hz = $hz->{right})
  106.         {
  107.             $hz->{up}{down} = $hz;
  108.             $hz->{down}{up} = $hz;
  109.         }
  110.     }
  111. }

  112. sub push_element
  113. {
  114.     my ($E, $ele, $row) = @_;

  115.     my $first = $#$E+1;
  116.     my $last;

  117.     for my $i ( 1 .. $len )
  118.     {
  119.         if ( $ele->[$i-1] == 1 )
  120.         {
  121.             push @$E,
  122.                 {
  123.                     val => $#$E+1,
  124.                     row => $row,
  125.                     col => $C->[$i],
  126.                     up  => $C->[$i]{up},
  127.                     down => $C->[$i]
  128.                 };

  129.             $C->[$i]{down} = $E->[$#$E] if ( $C->[$i]{down} == $C->[$i] );
  130.             $C->[$i]{up}{down} = $E->[$#$E];
  131.             $C->[$i]{up}   = $E->[$#$E];
  132.         }
  133.     }

  134.     $last = $#$E;
  135.     my ($left, $right);

  136.     for my $i ( $first .. $last )
  137.     {
  138.         $left = ($i == $first) ? $last : $i-1;
  139.         $right = ($i == $last) ? $first: $i+1;
  140.         $E->[$i]{left} = $E->[$left];
  141.         $E->[$i]{right} = $E->[$right];
  142.     }
  143. }


  144. sub print_links
  145. {
  146.     my $head = shift;
  147.     my $tmat = [];

  148.     grep { push @$tmat, [map { "   " } ( 0..$len )] } ( 0 .. $#$mat+1 );

  149.     my $vt;
  150.     my $hz;
  151.     my $c = $head->{right};

  152.     for ( ; $c != $head; $c = $c->{right} )
  153.     {
  154.         $tmat->[0][$c->{col}] = " C".$c->{col};

  155.         $vt = $c->{down};
  156.         for ( ; $vt != $c; $vt = $vt->{down} )
  157.         {
  158.             $tmat->[$vt->{row}][$c->{col}] = sprintf "%3d", $vt->{val};
  159.         }
  160.     }

  161.     for my $e ( @$tmat )
  162.     {
  163.         print join("", @$e),"\n";
  164.     }

  165.     print "\n";
  166. }
复制代码
  1.     C1 C2 C3 C4 C5 C6 C7
  2.            1     2  3   
  3.      4        5        6
  4.         7  8        9   
  5.     10       11         
  6.        12             13
  7.              14 15    16

  8. Result: 4,5,1
  9. 0.00014s
复制代码

但是在尝试改成解数独程序的时候,感觉效率很慢,完成一大半就暂停了计划,也许用编译型语言会快得多吧。

评分

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

查看全部评分

论坛徽章:
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-09-23 04:20 |显示全部楼层
回复 9# 523066680

判断 1-9 每个数字的全局分布情况(可能性)。
比如1可能分布的情况有6种,测试每一种,把9个1全部填入数独,然后继续测试其他数字的分布。
Buneng lijie? Keyi suoming?


改成解数独程序的时候
You Code ma? 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-09-23 22:32 |显示全部楼层
回复 14# rubyish

先说 Dancing Links 方案,我调试了一整天,终于把主要的问题解决。
js 版DLX方案遇到某些题型崩溃估计是相同的原因(js不熟,没细看):
一般为了优化速率,会实时统计列节点数量,从数量较少的列开始排查,在 Dance 函数递归回溯的过程中需要反复移除和恢复节点,
如果还原和统计的部分没写好,就会导致数据错乱,陷入冗余循环/无限递归。

另一个问题是内存,解决多组数独题时,需要清理上一组的所用引用数据。否则很快就爆内存。
由于这个十字交叉链表遍历起来还是麻烦,我单独建一个数组存储所有节点引用,然后统一清空。(现在1000道题后还是会涨到三十多MB。)

  1. =info
  2.     DLX 解数独方案,Perl 实现
  3.     523066680 2017-09

  4.     https://zhuanlan.zhihu.com/PerlExample
  5. =cut

  6. #use strict;
  7. use warnings;
  8. use IO::Handle;
  9. use File::Slurp;
  10. use Time::HiRes qw/time/;
  11. STDOUT->autoflush(1);

  12. my $file = "D:/sudoku_nd4.txt";
  13. my $gamedata = eval read_file( $file ) or die "$!";
  14. my @games = map { substr($gamedata->{$_}, 0, 81) } sort keys %$gamedata;

  15. my $index = 0;
  16. our $ele_id;
  17. our @nodes;

  18. grep { main( $games[$_], $_ ) } ( 0 .. $#games );

  19. sub main
  20. {
  21.     my ($game, $game_id) = @_;
  22.     my $C = [ map { {} } (0..324) ];
  23.     my $time_a  = time();
  24.     my $mat;
  25.     my $max_line;
  26.     my @answer;
  27.     my $res;

  28.     $mat = [[]];
  29.     $ele_id = 1;

  30.     #字符串转矩阵
  31.     str_to_mat( $game, $mat );

  32.     #初始化列首节点
  33.     init_head_col( $C, 324 );
  34.     create_matrix_nodes( $mat, $C, \$max_line );

  35.     $res = dance( $C->[0] , \@answer, 0);

  36.     #将数据依次填入数独
  37.     #index 0 的元素是固定项
  38.     shift @answer;
  39.     grep { $mat->[$_->{row}][$_->{col}] = $_->{val} } @answer;
  40.     print_mat($mat);

  41.     printf "Game index: %d, result: %d, time used: %.5f\n", $game_id, $res, time() - $time_a;

  42.     #清理内存
  43.     clean_matrix_nodes($C);
  44. }


  45. sub create_matrix_nodes
  46. {
  47.     my ($mat, $C, $main_row ) = @_;
  48.     my @elements;

  49.     $main_row = 1;
  50.     @elements = (0) x 324;

  51.     #已有的数字信息统一合并为一行
  52.     for my $r ( 0 .. 8 )
  53.     {
  54.         for my $c ( 0 .. 8 )
  55.         {
  56.             trans( $r, $c, $mat->[$r][$c], \@elements ) if ( $mat->[$r][$c] != 0 );
  57.         }
  58.     }

  59.     push_element( $C, \@elements, 324, $main_row, 0, 0, 0 );

  60.     my @possible;
  61.     for my $r ( 0 .. 8 )
  62.     {
  63.         for my $c ( 0 .. 8 )
  64.         {
  65.             if ( $mat->[$r][$c] == 0 )
  66.             {
  67.                 @possible = get_possible_num( $mat, $r, $c );
  68.                 die "Wrong" if ($#possible < 0);

  69.                 for my $e ( @possible )
  70.                 {
  71.                     $main_row++;
  72.                     @elements = (0) x 324;
  73.                     trans( $r, $c, $e, \@elements );
  74.                     push_element( $C, \@elements, 324, $main_row, $r, $c, $e );
  75.                 }
  76.             }
  77.         }
  78.     }
  79. }

  80. sub clean_matrix_nodes
  81. {
  82.     my ( $C ) = @_;
  83.     grep { %$_ = () } @nodes;
  84.     grep { %$_ = () } @$C;
  85.     [url=home.php?mod=space&uid=29550557]@Nodes[/url] = ();
  86.     @$C = ();
  87. }

  88. # ============================================================
  89. #                       Dancing Links
  90. # ============================================================

  91. sub dance
  92. {
  93.     my ($head, $answer, $lv) = @_;

  94.     return 1 if ( $head->{right} == $head );

  95.     my $c = $head->{right};
  96.     my $min = $c;

  97.     #get minimal column node
  98.     while ( $c != $head )
  99.     {
  100.         if ( $c->{count} < $min->{count} ) { $min = $c; }
  101.         $c = $c->{right};
  102.     }

  103.     $c = $min;
  104.     return 0 if ( $c->{count} <= 0 );

  105.     my $r = $c->{down};
  106.     my $ele;

  107.     my @count_array;
  108.     my $res = 0;

  109.     remove_col( $c );

  110.     while ( $r != $c )
  111.     {
  112.         $ele = $r->{right};

  113.         while ( $ele != $r )
  114.         {
  115.             remove_col( $ele->{top} );
  116.             $ele = $ele->{right}
  117.         }

  118.         $res = dance($head, $answer, $lv+1);
  119.         if ( $res == 1)
  120.         {
  121.             $answer->[$lv] = $r;
  122.             return 1;
  123.         }

  124.         $ele = $r->{left};
  125.         while ( $ele != $r )
  126.         {
  127.             resume_col( $ele->{top} );
  128.             $ele = $ele->{left}
  129.         }
  130.      
  131.         $r = $r->{down};
  132.     }

  133.     resume_col( $c );
  134.     return $res;
  135. }

  136. sub remove_col
  137. {
  138.     my ( $sel ) = @_;

  139.     $sel->{left}{right} = $sel->{right};
  140.     $sel->{right}{left} = $sel->{left};

  141.     my $vt = $sel->{down};
  142.     my $hz;

  143.     for ( ; $vt != $sel; $vt = $vt->{down} )
  144.     {
  145.         $hz = $vt->{right};
  146.         for (  ; $hz != $vt; $hz = $hz->{right})
  147.         {
  148.             $hz->{up}{down} = $hz->{down};
  149.             $hz->{down}{up} = $hz->{up};
  150.             $hz->{top}{count} --;
  151.         }
  152.         $hz->{top}{count} --;
  153.     }
  154. }

  155. sub resume_col
  156. {
  157.     my ( $sel ) = @_;

  158.     $sel->{left}{right} = $sel;
  159.     $sel->{right}{left} = $sel;

  160.     my $vt = $sel->{down};
  161.     my $hz;

  162.     for ( ; $vt != $sel; $vt = $vt->{down})
  163.     {
  164.         $hz = $vt->{right};
  165.         for (  ; $hz != $vt; $hz = $hz->{right})
  166.         {
  167.             $hz->{up}{down} = $hz;
  168.             $hz->{down}{up} = $hz;
  169.             $hz->{top}{count} ++;
  170.         }
  171.         $hz->{top}{count} ++;
  172.     }
  173. }

  174. sub print_nodes
  175. {
  176.     my ($head, $rows) = @_;
  177.     my $buff = [[]];
  178.     my $c = $head->{right};
  179.     my $ele;

  180.     grep { $buff->[$_] = [("    ") x 324] } ( 0 .. $rows+1 ); #加一行统计

  181.     for ( ; $c != $head; $c = $c->{right} )
  182.     {
  183.         $buff->[0][$c->{col}-1] = sprintf("%3d ", $c->{col} );
  184.         $buff->[1][$c->{col}-1] = sprintf("%3d ", $c->{count} );
  185.     }

  186.     $c = $head->{right};
  187.     for (; $c != $head; $c = $c->{right} )
  188.     {
  189.         $ele = $c->{down};
  190.         for ( ; $ele != $c; $ele = $ele->{down} )
  191.         {
  192.             $buff->[$ele->{row}+1][$ele->{col}-1] = sprintf("%3d ", $ele->{val} );
  193.         }
  194.     }

  195.     grep { print join("", @{$buff->[$_]} ),"\n"; } ( 0 .. $rows );
  196.     print "\n";
  197. }

  198. # ============================================================
  199. #                     Create Node Matrix
  200. # ============================================================

  201. sub init_head_col
  202. {
  203.     my ($C, $len) = @_;
  204.     my ($left, $right);

  205.     for my $col ( 0 .. $len )
  206.     {
  207.         $left = $col == 0 ? $len : $col-1;
  208.         $right = $col == $len ? 0 : $col+1;
  209.         $C->[$col]{val}  = 0;
  210.         $C->[$col]{row}  = 0;
  211.         $C->[$col]{col}  = $col;
  212.         $C->[$col]{count} = 0;
  213.         $C->[$col]{left}  = $C->[$left];
  214.         $C->[$col]{right} = $C->[$right];
  215.         $C->[$col]{up}    = $C->[$col];
  216.         $C->[$col]{down}  = $C->[$col];
  217.         $C->[$col]{top}   = $C->[$col];
  218.     }
  219. }

  220. sub push_element
  221. {
  222.     my ($C, $eles, $cols, $DL_row, $matr, $matc, $n ) = @_;

  223.     our $ele_id;
  224.     my $first;
  225.     my $ele;
  226.     my $ref;
  227.     my $prev = undef;
  228.     my $col;

  229.     for ( my $i = 0; $i < $cols; $i++ )
  230.     {
  231.         $col = $i+1;
  232.         if ( $eles->[$i] == 1 )
  233.         {
  234.             $ele = {
  235.                 val => $n,
  236.                 col => $matc,
  237.                 row => $matr,
  238.                 count => undef,
  239.                 left  => undef,
  240.                 right => undef,
  241.                 up    => $C->[$col]{up},
  242.                 down  => $C->[$col],
  243.                 top   => $C->[$col]
  244.             };

  245.             $nodes[ $ele_id-1 ] = $ele;
  246.             if ( $C->[$col]{down} == $C->[$col] )
  247.             {
  248.                 $C->[$col]{down} = $ele;
  249.             }

  250.             $C->[$col]{up}{down} = $ele;
  251.             $C->[$col]{up}       = $ele;
  252.             $C->[$col]{count}++;

  253.             if ( defined $prev )
  254.             {
  255.                 $prev->{right} = $ele;
  256.                 $ele->{left}   = $prev;
  257.             }
  258.             else
  259.             {
  260.                 $first = $ele;
  261.             }

  262.             $prev = $ele;
  263.             $ele_id ++;
  264.         }

  265.         $first->{left} = $ele;
  266.         $ele->{right}  = $first;
  267.     }
  268. }

  269. sub trans
  270. {
  271.     my ($r, $c, $n, $ref) = @_;
  272.     my $block;
  273.     my ($A, $B, $C, $D);

  274.     $block = int($r/3)*3 + int($c/3);

  275.     $A = $r * 9 + $c;
  276.     $B = $r * 9 + $n + 80;
  277.     $C = $c * 9 + $n + 161;
  278.     $D = $block * 9 + $n + 242;

  279.     $ref->[$A] = 1;
  280.     $ref->[$B] = 1;
  281.     $ref->[$C] = 1;
  282.     $ref->[$D] = 1;
  283. }

  284. # ============================================================
  285. #                           Sudoku
  286. # ============================================================
  287. SUDOKU:
  288. {
  289.     sub get_possible_num
  290.     {
  291.         my ($mat, $row, $col) = @_;
  292.         my @possible = (0,1,2,3,4,5,6,7,8,9);
  293.         my $blkr = int($row/3);
  294.         my $blkc = int($col/3);

  295.         my ($rr, $cc);
  296.         for my $n ( 0 .. 8 )
  297.         {
  298.             $rr = $blkr*3+int($n/3);
  299.             $cc = $blkc*3+ $n % 3;
  300.             $possible[ $mat->[$n][$col] ] = 0;
  301.             $possible[ $mat->[$row][$n] ] = 0;
  302.             $possible[ $mat->[$rr][$cc] ] = 0;
  303.         }

  304.         return grep { $_ } @possible;
  305.     }

  306.     sub str_to_mat
  307.     {
  308.         my ( $str, $mat ) = @_;
  309.         my $idx = 0;

  310.         for my $row ( 0 .. 8 )
  311.         {
  312.             for my $col ( 0 .. 8 )
  313.             {
  314.                 $mat->[$row][$col] = substr( $str, $idx++, 1 );
  315.             }
  316.         }
  317.     }

  318.     sub mat_to_str
  319.     {
  320.         my ( $mat ) = @_;
  321.         return join("", map { join("", @{$mat->[$_]} ) } (0..8));
  322.     }

  323.     sub print_mat
  324.     {
  325.         my ($mat) = @_;
  326.         grep { print join(",", @{$mat->[$_]} ),"\n" } ( 0..8 );
  327.     }
  328. }
复制代码

评分

参与人数 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-09-23 23:31 |显示全部楼层
本帖最后由 523066680 于 2017-09-23 23:44 编辑

上面的Perl 运行结果(不含print):
"sudoku_nd0.txt" 29.6s (并没有暴力跑法快)
"sudoku_nd1.txt" 88.0s
"sudoku_nd2.txt" 115.2s
"sudoku_nd3.txt" 78.0s
"sudoku_nd4.txt" 80.0s

同时也写了 C语言的版本,跑完四万多个17个提示数的数独题二十多秒 (i7 4790K),题目资源:
http://staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php

"sudoku_nd0.txt" 0.4s
"sudoku_nd1.txt" 1.1s
"sudoku_nd2.txt" 1.5s
"sudoku_nd3.txt" 1.0s
"sudoku_nd4.txt" 1.0s

以上数据不含 printf。

还是C语言好啊!

论坛徽章:
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-09-25 02:18 |显示全部楼层
3Q ~~ ganxie zhidao!
xuexile exact cover, hai xuebuhui dancing,
Ganjue?
wo de code jiushi exact cover?
zhishi xingshi butong? Nide kanfa?

论坛徽章:
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-09-25 02:24 |显示全部楼层
kandao zhege youyisi
Algorithm X in 30 lines!

http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

Solving Sudokus
http://www.cs.mcgill.ca/~aassaf9/python/sudoku.txt

python KBD ~~

论坛徽章:
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-09-25 08:36 |显示全部楼层
本帖最后由 523066680 于 2017-09-25 10:19 编辑

回复 17# rubyish

你的代码含有将数独问题转换成“位”操作的思想,把1-9数字不重复的特性转换为了位的特性,同时建立键值表,可以快速获得可选数字。

Dancing Links 算法解数独,也是先把单元特征转换成324位的"位"特征:
对于每一个单元,把行、列、宫(3x3区域)、数字值,转换为由 81*4 位0或1组成的特征数组。每个单元对应的特征数组只含4个1(请参考原文的转换规则

对于已知的单元,这些数组可以合并(如果数独题目本身成立的话~)到一行特征数组,因为他们的行、列、宫和数字都不冲突。
对于未知的单元,把每一个可选数,结合单元位置转成特征数组。假设一个单元可能是 6,7,9,则会产生3个特征数组。

然后把所有数组都存储在十字链表中,求出精确覆盖的项,即为满足数独4项特性的项:
81个单元填满,
9行中每行包含9种不同数字,
9列中每列包含9种不同数字,
9宫中每宫包含9种不同数字。

链表的好处就是假设某一行正确时,可以通过十字链关系删去大量冲突节点和对应行,对比剩下的行,达到高效率“剪枝”的效果。


论坛徽章:
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-09-25 09:11 |显示全部楼层
本帖最后由 523066680 于 2017-09-25 10:32 编辑

回复 18# rubyish

代码确实很短(操作过程是类似的),光是因为不用花括号就省了一坨,python 的各种数组和对象、lambda操作确实厉害。
相信perl的实现也可以很短,我的版本纯粹是为了先把功能堆出来,故而有些冗余且繁琐的地方。

python的强制缩进还是不习惯,也遇到过某个教学示例代码,既包含空格也包含tab,多层for和if镶嵌的话,如果缩进出了问题,要修复代码很凌乱。
第二语言准备转Ruby
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP