[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖
回复 11# slore

    线程的方案留到最后,单线程仍然有更快的算法,快到解 sudoku_nd4.txt 所有题只要十多秒。

TOP

旋转90度,180度等,开4个进程并行跑,应该会某个路线快些,只用把初始数据按规律变换即可。

再有,4个线程的某单元格的候选项目共享,更快得出唯一解。

再有,改变搜索前进方向,上面旋转数独盘,左右,上下,4个方向同时了,还有顺时旋转前进,逆时针方向,先斜线,先小格等方向,可以开更多线程。

TOP

本帖最后由 523066680 于 2017-9-18 16:27 编辑

最近换了个方案,遇到难度高的题目时比原来的方案快得多(但还是没有Rubyish @Chinaunix 的代码快)

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

题目
140968000000000900600057300000000007300000840000196500070000405406010030000000000

数字1的可能分布情况
140968000000001900600057310010000007300000841000196500071000405406010030000000100
140968000000001900600057310000000107310000840000196500071000405406010030000000001
140968000000001900600057301000000107310000840000196500071000405406010030000000010
140968000000001900600057301000000107310000840000196500070000415406010030001000000
140968000000001900600057301000000107301000840000196500070000415406010030010000000
140968000000001900600057301000000017310000840000196500071000405406010030000000100

完整代码:
  1. =info
  2.     方案 - 遍历数字分布情况
  3.     523066680 2017-09
  4. =cut
  5. use File::Slurp;
  6. use IO::Handle;
  7. STDOUT->autoflush(1);
  8. # my $gamedata = eval read_file("../sudoku_nd1.txt");
  9. # grep { push @games, $gamedata->{$_} } sort keys %$gamedata;
  10. @games =
  11. qw/
  12.     001000008800010532750024090005302060670500004010780900098053406426179803537460219
  13.     503092000700000008006007310020600000065000730007043500000706102070000800400009000
  14.     700306000000000050060000018000081000000000000900000200000200900050400000080000007
  15.     030000001200806000000005000000000000000000650043070000600002080090000000000010003
  16.     010000200300800000000504000800090000000070120500000000000000000020130000400000005
  17. /;
  18. our @order;
  19. our $answer_mat = [[]];
  20. my $mat;
  21. my $res;
  22. my $allcase;
  23. my $answer_str;
  24. #坐标对应区块位置的表
  25. our @blk = map { int($_ / 3) } ( 0..8 );
  26. while ( $index <= $#games )
  27. {
  28.     $mat = [[]];
  29.     $time_a = time();
  30.     str_to_mat( $games[$index] , $mat );
  31.     $allcase = [ map { [] } (0..9) ];
  32.     grep { possible_mat($mat, $_, $allcase->[$_], 0) } (1..9);
  33.     @order = sort { $#{$allcase->[$a]} <=> $#{$allcase->[$b]} } ( 0 .. 9 );
  34.     $res = recursive( $mat, 1 ); #起点为1,下标 0占位
  35.     if ($res == 1)
  36.     {
  37.         print_mat_inline( $answer_mat );
  38.     }
  39.     else { die "false\n" }
  40.     printf "Game index: %d, time used: %.3fs\n\n", $index, time() - $time_a;
  41.     $index++;
  42. }
  43. sub recursive
  44. {
  45.     our (@order, $answer_mat);
  46.    
  47.     my ( $mat, $lv ) = @_;
  48.     my @case;
  49.     if ( $lv > 9 )
  50.     {
  51.         $answer_mat = $mat;
  52.         return 1;
  53.     }
  54.     $target = $order[$lv];
  55.     possible_mat($mat, $target, \@case, 0);
  56.     my $t_mat = [[]];
  57.     my $res = 0;
  58.     for my $s ( @case )
  59.     {
  60.         str_to_mat( $s, $t_mat );
  61.         $res = recursive( $t_mat, $lv+1 );
  62.         last if ($res == 1);
  63.     }
  64.     return $res;
  65. }
  66. sub possible_mat
  67. {
  68.     my ( $mat, $target, $aref, $lv ) = @_;
  69.     # level means row
  70.     my $str;
  71.     if ($lv == 9)
  72.     {
  73.         $count++;
  74.         push @$aref, mat_to_str($mat);
  75.         return 1;
  76.     }
  77.     my @cols = get_possible_column( $mat, $lv, $target );
  78.     my $res = 0;
  79.     my $ever;
  80.     for my $c ( @cols )
  81.     {
  82.         $ever = $mat->[$lv][$c];
  83.         $mat->[$lv][$c] = $target;
  84.         $res = possible_mat( $mat, $target, $aref, $lv+1 );
  85.         $mat->[$lv][$c] = $ever;
  86.     }
  87.     return $res;
  88. }
  89. sub get_possible_column
  90. {
  91.     our @blk;
  92.     my ( $mat, $row, $target ) = @_;
  93.     my @cols = ( 0..8 );
  94.     for my $c ( 0..8 )
  95.     {
  96.         #如果当前行已经存在这个数字,则直接返回这个数字的位置。
  97.         if ( $mat->[$row][$c] == $target )
  98.         {
  99.             return ( $c );
  100.         }
  101.         elsif ( $mat->[$row][$c] != 0 )
  102.         {
  103.             $cols[$c] = -1;
  104.         }
  105.         for my $r ( 0..8 )
  106.         {
  107.             if ( $mat->[$r][$c] == $target )
  108.             {
  109.                 $cols[$c] = -1;
  110.                 if ( $blk[$r] == $blk[$row] )
  111.                 {
  112.                     $cols[ $blk[$c] * 3 + 0] = -1;
  113.                     $cols[ $blk[$c] * 3 + 1] = -1;
  114.                     $cols[ $blk[$c] * 3 + 2] = -1;
  115.                 }
  116.             }
  117.         }
  118.     }
  119.     return grep { $_ != -1 } @cols;
  120. }
  121. sub str_to_mat
  122. {
  123.     my ( $str, $mat ) = @_;
  124.     my $idx = 0;
  125.     for my $row ( 0 .. 8 )
  126.     {
  127.         for my $col ( 0 .. 8 )
  128.         {
  129.             $mat->[$row][$col] = substr( $str, $idx++, 1 );
  130.         }
  131.     }
  132. }
  133. sub mat_to_str
  134. {
  135.     my ( $mat ) = @_;
  136.     return join("", map { join("", @{$mat->[$_]} ) } (0..8));
  137. }
  138. sub print_mat
  139. {
  140.     my ($mat) = @_;
  141.     grep { print join(",", @{$mat->[$_]} ),"\n" } ( 0..8 );
  142. }
  143. sub print_mat_inline
  144. {
  145.     my ($mat) = @_;
  146.     grep { print join("", @{$mat->[$_]} ),"" } ( 0..8 );
  147.     print "\n";
  148. }
复制代码
261935748849617532753824691985342167672591384314786925198253476426179853537468219
Game index: 0, time used: 0.000s

513892467749361258286457319324675981165928734897143526958736142672514893431289675
Game index: 1, time used: 0.000s

718356492492817653563924718624781539835692174971543286147238965356479821289165347
Game index: 2, time used: 0.000s

836947521251836497479125836968251374127483659543679218614392785395768142782514963
Game index: 3, time used: 0.000s

718963254354827961296514873872391546943675128561248739187456392625139487439782615
Game index: 4, time used: 1.000s


跑完 sudoku_nd0.txt 三千多道题需要十多秒,跑完 sudoku_nd4.txt 大约六百秒。
CU Rubyish 的代码,跑完 nd0 零点几秒,nd4 一百多秒

TOP

本帖最后由 523066680 于 2017-9-16 10:13 编辑

初始版本
  1. =info
  2.     解数独 初版
  3.     523066680 2017-09
  4. =cut
  5. use IO::Handle;
  6. use Time::HiRes qw/time/;
  7. STDOUT->autoflush(1);
  8. my @games =
  9. qw/
  10.     001000008800010532750024090005302060670500004010780900098053406426179803537460219
  11.     503092000700000008006007310020600000065000730007043500000706102070000800400009000
  12.     700306000000000050060000018000081000000000000900000200000200900050400000080000007
  13.     030000001200806000000005000000000000000000650043070000600002080090000000000010003
  14.     010000200300800000000504000800090000000070120500000000000000000020130000400000005
  15. /;
  16. our @unsolve;
  17. our $block = [];  #区块引用
  18. my $mat = [[]];
  19. my $level = 0;
  20. my $time_a;
  21. #创建区块引用,以便于操作
  22. make_block_refs( $block, $mat );
  23. while ( $level <= $#games )
  24. {
  25.     #字符串转矩阵
  26.     str_to_mat( $games[$level] , $mat );
  27.     $time_a = time();
  28.     #设置 @unsolve 数组,存储空缺元素的坐标
  29.     set_unsolve_array($mat);
  30.     solve($mat, 0);
  31.    
  32.     print_mat($mat);
  33.     printf "Game level: %d, time used: %.3fs\n\n", $level+1, time() - $time_a;
  34.     $level++;
  35. }
  36. sub solve
  37. {
  38.     my ($mat, $prev, $lv) = @_;
  39.     my @possible;
  40.     my ($row, $col);
  41.     my $current;
  42.     for my $i ( $prev .. $#unsolve )
  43.     {
  44.         ($row, $col) = @{$unsolve[$i]};
  45.         if ( $mat->[$row][$col] == 0 )
  46.         {
  47.             $current = $i;
  48.             @possible = get_possible_num( $mat, $row, $col );
  49.             last;
  50.         }
  51.     }
  52.     if ( not defined $current ) { return 1 }
  53.     else
  54.     {   
  55.         return 0 if ( $#possible < 0 )
  56.     }
  57.     my $res = 0;
  58.     for my $p ( @possible )
  59.     {
  60.         $mat->[ $row ][ $col ] = $p;
  61.         $res = solve($mat, $current+1, $lv+1);
  62.         last if ($res == 1);
  63.     }
  64.     #使对应单元恢复为0 否则影响递归判断
  65.     $mat->[$row][$col] = 0 if ($res == 0) ;
  66.     return $res;
  67. }
  68. sub get_possible_num
  69. {
  70.     our ($block, %hash);
  71.     my ($mat, $row, $col) = @_;
  72.     my %possible = (1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9);
  73.     #排除元素
  74.     for my $n ( 0 .. 8 )
  75.     {
  76.         delete $possible{ $mat->[$n][$col] };
  77.         delete $possible{ $mat->[$row][$n] };
  78.         delete $possible{ ${$block->[$row/3][$col/3][$n]} };
  79.     }
  80.     return sort keys %possible;
  81. }
  82. sub get_possible_num_2
  83. {
  84.     our ($block, %hash);
  85.     my ($mat, $row, $col) = @_;
  86.     my @possible = (0,1,2,3,4,5,6,7,8,9);
  87.     #区块坐标
  88.     my $blockrow = int($row/3);
  89.     my $blockcol = int($col/3);
  90.     #排除元素
  91.     for my $n ( 0 .. 9 )
  92.     {
  93.         $possible[ $mat->[$n][$col] ] = 0;
  94.         $possible[ $mat->[$row][$n] ] = 0;
  95.         $possible[ ${$block->[$blockrow][$blockcol][$n]} ] = 0;
  96.     }
  97.     return grep { $_ } @possible;
  98. }
  99. sub set_unsolve_array
  100. {
  101.     our ( @unsolve );
  102.     my ($mat) = @_;
  103.     @unsolve = ();
  104.     for my $row ( 0..8 )
  105.     {
  106.         for my $col ( 0..8 )
  107.         {
  108.             if ( $mat->[$row][$col] == 0 )
  109.             {
  110.                 push @unsolve, [ $row, $col, [get_possible_num( $mat, $row, $col )] ];
  111.             }
  112.         }
  113.     }
  114.     #根据可选数字的数量由少到多排序
  115.     #@unsolve = sort { $#{$a->[2]} <=> $#{$b->[2]} } @unsolve;
  116. }
  117. sub make_block_refs
  118. {
  119.     my ($block, $mat) = @_;
  120.     #将数独的九个宫对应的引用分组保存
  121.     for my $r ( 0..2 )
  122.     {
  123.         for my $c ( 0..2 )
  124.         {
  125.             for my $rr ( $r*3 .. $r*3+2 )
  126.             {
  127.                 for my $cc ( $c*3 .. $c*3+2 )
  128.                 {
  129.                     push @{ $block->[$r][$c] }, \$mat->[$rr][$cc];
  130.                 }
  131.             }
  132.         }
  133.     }
  134. }
  135. sub str_to_mat
  136. {
  137.     my ( $str, $mat ) = @_;
  138.     my $idx = 0;
  139.     for my $row ( 0 .. 8 )
  140.     {
  141.         for my $col ( 0 .. 8 )
  142.         {
  143.             $mat->[$row][$col] = substr( $str, $idx++, 1 );
  144.         }
  145.     }
  146. }
  147. sub print_mat
  148. {
  149.     my ($mat) = @_;
  150.     grep { print join(",", @{$mat->[$_]} ),"\n" } ( 0..8 );
  151. }
复制代码
Game level: 1, time used: 0.001s
Game level: 2, time used: 0.002s
Game level: 3, time used: 11.373s
Game level: 4, time used: 432.737s
Game level: 5, time used: 24.571s

结果相当难看,有空试试 Dancing Links

TOP

Rosettacode 有一段 Perl 代码非常简短,不过这段代码因为简短而牺牲了性能,有很多冗余的循环。
http://rosettacode.org/wiki/Sudoku#Perl
1

评分人数

TOP

本帖最后由 523066680 于 2017-9-15 09:53 编辑

回复 5# slore

题库在这个网站抓的 免费的在线数独
http://bbs.bathome.net/thread-45401-1-1.html

http://523066680.ys168.com/
Perl/数独/数独题库200801-201709_含答案.zip

难度分为 入门,初级,中级,高级,骨灰级。1楼的题来自每个等级的第一道题目。这个等级划分我也觉得有点问题……  
初级的比如:数独 - 2008年1月6日 - 初级
000600500001007000004000000050002000060000800000001007080900000000500001007000004
比同等级的其他题目明显数字要少,可选数字可能性更多。

TOP

居然是按字符串存储和处理的,如果用int估计会变快吧.  

TOP

level 3:3,7,9,6,8,8,26 秒

level 5:52,17,85,64,57,34,82,51,14,35 秒


level 4:503,1402,690 秒

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

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

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


找到了9年前用回溯法解数独的VBS脚本,选择下一个可用时,是随机抽取一个,
所以运算时间不固定,有运气成分在里面.
链接: https://pan.baidu.com/s/1EGOqaIQyPy5yZd0unXLMuA?pwd=sycn

不过,level 5运行10次也在1分钟内,level 4运行了3次,长的达26分钟?
level你是不是写反了.

另外,有个数独的小flash程序,做的挺好的,简单,而且各个格子4个角还可以临时设置候选值.

链接: https://pan.baidu.com/s/1GYg2RMSW7X-1mQQqcw1RHg?pwd=8sjh
1

评分人数

TOP

本帖最后由 523066680 于 2017-9-14 17:44 编辑

回复 3# CrLf

    也不是完全的暴力跑,前三项规则已经应用了,后两项还没有试过。题目的前两道数独秒出结果,第四道耗时很长。

TOP

这个用暴力解肯定慢啦...这是我解数独的基本思路,除了第一步,其他的都是嵌套循环的步骤
1、生成草稿表
2、检查纵、横、九宫格内唯一数,填写并从相关单元格的草稿中去除该数
3、根据草稿,排除某九宫格中唯一行或者唯一列对其他行列的影响
4、根据数独“只有唯一解”的规则排除平行对称基本型
5、setlocal,寻找连锁反应最多的点进行暴力解(以只有两种可能性的点为佳)

TOP

本帖最后由 523066680 于 2017-9-14 16:57 编辑

脚本,每填入一个数字,重新判断并缩小范围,第四道数独花了五百多秒 ……
  1. 2,6,1,9,3,5,7,4,8
  2. 8,4,9,6,1,7,5,3,2
  3. 7,5,3,8,2,4,6,9,1
  4. 9,8,5,3,4,2,1,6,7
  5. 6,7,2,5,9,1,3,8,4
  6. 3,1,4,7,8,6,9,2,5
  7. 1,9,8,2,5,3,4,7,6
  8. 4,2,6,1,7,9,8,5,3
  9. 5,3,7,4,6,8,2,1,9
  10. Game level: 1, time used: 0.000s
  11. 8,3,6,9,4,7,5,2,1
  12. 2,5,1,8,3,6,4,9,7
  13. 4,7,9,1,2,5,8,3,6
  14. 9,6,8,2,5,1,3,7,4
  15. 1,2,7,4,8,3,6,5,9
  16. 5,4,3,6,7,9,2,1,8
  17. 6,1,4,3,9,2,7,8,5
  18. 3,9,5,7,6,8,1,4,2
  19. 7,8,2,5,1,4,9,6,3
  20. Game level: 4, time used: 537.594s
复制代码
--------------- 2017-09-14 蜜汁 Trick ----------------
  1. 8,3,6,9,4,7,5,2,1
  2. 2,5,1,8,3,6,4,9,7
  3. 4,7,9,1,2,5,8,3,6
  4. 9,6,8,2,5,1,3,7,4
  5. 1,2,7,4,8,3,6,5,9
  6. 5,4,3,6,7,9,2,1,8
  7. 6,1,4,3,9,2,7,8,5
  8. 3,9,5,7,6,8,1,4,2
  9. 7,8,2,5,1,4,9,6,3
  10. [Finished in 2.2s]
复制代码

TOP

返回列表