Board logo

标题: [挑战]解数独程序与数独题目生成 [打印本页]

作者: 523066680    时间: 2017-9-12 20:39     标题: [挑战]解数独程序与数独题目生成

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

以下是从某网站提取的5种难度的数独游戏(难度从1-5,循着网站是可以找到答案的):
001000008800010532750024090005302060670500004010780900098053406426179803537460219
503092000700000008006007310020600000065000730007043500000706102070000800400009000
700306000000000050060000018000081000000000000900000200000200900050400000080000007
030000001200806000000005000000000000000000650043070000600002080090000000000010003
010000200300800000000504000800090000000070120500000000000000000020130000400000005

写程序对这五个数独题目求解,并计算解每道题的时间消耗。
编程语言:不限

------------------------------------------ 2017-09-18补充 ------------------------------------------
如果解决上面五道题耗时不超过1秒,可以尝试批量解题库中的题,并统计时间消耗。

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

题库按键值对存储,key 是时间戳,value 中前81个字符是题目,后81个字符是唯一答案。
nd0 - nd4 表示不同的难度。
作者: 523066680    时间: 2017-9-13 11:24

本帖最后由 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]
复制代码

作者: CrLf    时间: 2017-9-13 23:52

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

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

回复 3# CrLf

    也不是完全的暴力跑,前三项规则已经应用了,后两项还没有试过。题目的前两道数独秒出结果,第四道耗时很长。
作者: slore    时间: 2017-9-14 21:44

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
作者: slore    时间: 2017-9-14 21:52

居然是按字符串存储和处理的,如果用int估计会变快吧.  
作者: 523066680    时间: 2017-9-15 09:27

本帖最后由 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
比同等级的其他题目明显数字要少,可选数字可能性更多。
作者: 523066680    时间: 2017-9-15 10:09

Rosettacode 有一段 Perl 代码非常简短,不过这段代码因为简短而牺牲了性能,有很多冗余的循环。
http://rosettacode.org/wiki/Sudoku#Perl
作者: 523066680    时间: 2017-9-16 09:32

本帖最后由 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
作者: 523066680    时间: 2017-9-18 16:13

本帖最后由 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 一百多秒
作者: slore    时间: 2017-9-19 07:59

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

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

再有,改变搜索前进方向,上面旋转数独盘,左右,上下,4个方向同时了,还有顺时旋转前进,逆时针方向,先斜线,先小格等方向,可以开更多线程。
作者: 523066680    时间: 2017-9-20 00:13

回复 11# slore

    线程的方案留到最后,单线程仍然有更快的算法,快到解 sudoku_nd4.txt 所有题只要十多秒。
作者: slore    时间: 2017-9-20 10:02

回复 12# 523066680


单纯考虑算法的话,肯定有更优的,但是 多线程对于现在大内存,多核CPU才是更好的利用,而且很多问题都可以采用这个方法来提高。
至于探索路径,不一定非要0~81这个顺序,可以把每个格子的候选项,从小到大排列,按这个数据填,有大概率先填入正确的数据,可以减少尝试次数吧。那天有时间了ruby写下试试。
作者: slore    时间: 2017-9-20 13:02

本帖最后由 slore 于 2017-9-20 13:03 编辑
  1. class Soduku
  2.   def initialize(str)
  3.     @matrix = 9.times.map{[0]*9}
  4.     str.reverse!       <-只加了一句,LEVEL4立马难度变低了
  5.     nums = str.split('').map(&:to_i)
  6.     ...
  7.   end
复制代码
[3, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 9, 0]
[0, 8, 0, 2, 0, 0, 0, 0, 6]
[0, 0, 0, 0, 7, 0, 3, 4, 0]
[0, 5, 6, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 5, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 0, 8, 0, 0, 2]
[1, 0, 0, 0, 0, 0, 0, 3, 0]
5.069903 秒
[3, 6, 9, 4, 1, 5, 2, 8, 7]
[2, 4, 1, 8, 6, 7, 5, 9, 3]
[5, 8, 7, 2, 9, 3, 4, 1, 6]
[8, 1, 2, 9, 7, 6, 3, 4, 5]
[9, 5, 6, 3, 8, 4, 7, 2, 1]
[4, 7, 3, 1, 5, 2, 8, 6, 9]
[6, 3, 8, 5, 2, 1, 9, 7, 4]
[7, 9, 4, 6, 3, 8, 1, 5, 2]
[1, 2, 5, 7, 4, 9, 6, 3, 8]
作者: slore    时间: 2017-9-20 16:09

至于探索路径,不一定非要0~81这个顺序,可以把每个格子的候选项,从小到大排列,按这个数据填,有大概率先填入正确的数据,可以减少尝试次数吧。


错了,如果按候选项探索的话,比如, [0,0]点可以用5和4,[8,8]可以用1,3,
都是最小的2个候选,但是填写0,0,在填8,8,变成了散点,如果50%概率选错了的话,
其他格子,无效探索反而变得多了,填写的多,但是排除无效值的情报却少了。

探索改成下面这样。

先选择出有最少候选项的位置,然后对它相同X,Y和Z区域的 格子 权值-1。
(假设最小的这个格子我们填入了一个数字,被影响的其他格子,候选项-1)
然后,被影响的格子里面,权值最低的(候选项-1后,最小的),
是我们接下来优先探索的,同理,整理出,每次填入一个单元格,
受其影响的,候选项最少的格的探索路径。这样填入数据之间有关联,
如果填入了错误值,可以更早地回溯。

VBS代码移植为ruby脚本的,只在处理前,修改这1处,从几百秒到稳定10秒LEVEL4的结果输出,
很大的改善方案。

ans = candidate(x, y)
return false if ans.size <= 0

v = ans[0]  #取出候选的第一个
ans.delete v
@matrix[x][y] = v

改成, v = ans.sample #候选中随机抽1个,LEVEL4的结果,2秒~18秒之间
  1. #魔法CODE
  2. str.reserse!
  3. v = ans.sample
复制代码
  1.     sort_seq = []
  2.     while
  3.       sort_seq.push @solve_seq[min_seq]
  4.       x = @solve_seq[min_seq][0]
  5.       y = @solve_seq[min_seq][1]
  6.       z = ((x / 3) * 3) + (y / 3)
  7.       @solve_seq.delete_at(min_seq)
  8.       break if @solve_seq.size == 0
  9.       min = 10
  10.       min_seq = -1
  11.       @solve_seq.each_with_index do |seq, i|
  12.         zz = ((seq[0] / 3) * 3) + (seq[1] / 3)
  13.         if seq[0] == x || seq[1] == y || zz == z
  14.           seq[2] -= 1
  15.           if seq[2] < min
  16.             min = seq[2]
  17.             min_seq = i
  18.           end
  19.         end
  20.       end
  21.     end
  22.     p sort_seq
  23.     @solve_seq = sort_seq
复制代码

作者: 523066680    时间: 2017-9-20 16:36

本帖最后由 523066680 于 2017-9-20 20:34 编辑

回复 15# slore

对于回溯法,有一个优化很有效果。示意图(注意除了中间有个独立的候选数字2,右上角还有个框选的数字8):


程序给定的单元候选数字中,大多单元格有多个可选数字,但是可以进一步排除。例如:
如果累计一行中的所有候选数,某个数字只出现一次,那么这个数字就是必选数字。同样,一列、一宫(3x3 block)的区域内也是如此。

我为程序增加了一个while 循环,反复筛选并填充唯一的数字,直到再也没有,然后才开始递归解题。

Sudoku:
3,0,0,0,1,0,0,0,0
0,0,0,0,0,0,0,9,0
0,8,0,2,0,0,0,0,6
0,0,0,0,7,0,3,4,0
0,5,6,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,5,0,0,0,0,0
0,0,0,6,0,8,0,0,2
1,0,0,0,0,0,0,3,0

Fill only one possible cells
R:1 C:8 Fill:3
R:3 C:5 Fill:6
R:3 C:8 Fill:5
R:6 C:5 Fill:1
R:0 C:1 Fill:6
R:1 C:4 Fill:6
R:6 C:0 Fill:6
R:8 C:6 Fill:6
R:5 C:7 Fill:6
R:8 C:2 Fill:5
R:8 C:8 Fill:8
R:6 C:2 Fill:8
R:6 C:7 Fill:7

Result:
3,6,0,0,1,0,0,0,0
0,0,0,0,6,0,0,9,3
0,8,0,2,0,0,0,0,6
0,0,0,0,7,6,3,4,5
0,5,6,0,0,0,0,0,0
0,0,0,0,0,0,0,6,0
6,0,8,5,0,1,0,7,0
0,0,0,6,0,8,0,0,2
1,0,5,0,0,0,6,3,8

Solve:
3,6,9,4,1,5,2,8,7
2,4,1,8,6,7,5,9,3
5,8,7,2,9,3,4,1,6
8,1,2,9,7,6,3,4,5
9,5,6,3,8,4,7,2,1
4,7,3,1,5,2,8,6,9
6,3,8,5,2,1,9,7,4
7,9,4,6,3,8,1,5,2
1,2,5,7,4,9,6,3,8
time used: 0.211s

作者: slore    时间: 2017-9-20 20:21

回复 16# 523066680

VBS当时写代码,就有这个逻辑.先CreatePlan里面有presolvecount,然后才SolvePanes递归的.
作者: bbaa    时间: 2017-9-23 19:56

我来了,等下用我之前的生成类试试
作者: bbaa    时间: 2017-9-23 21:18

回复 18# bbaa


    随机法真的 身败名裂
  1. Allowed memory size of 134217728 bytes exhausted (tried to allocate 40 bytes)
复制代码

作者: 523066680    时间: 2017-9-24 15:49

本帖最后由 523066680 于 2017-9-24 16:09 编辑

回复 19# bbaa

      对于题目和结果判断,你先用现成的题库弄上网站跑跑看?我前面发的题库分为5种难度等级,你可以随机抽取。
这些题只有一种答案,也都在文件里了,检验方便。(虽然这样提供了作弊条件,可以直接POST现有答案,不过也就是试试效果)
作者: search_Sudoku    时间: 2017-10-2 02:02

闲时再弄弄, JS 还有些冗余的变量及逻辑
保存为 htm 文件, 浏览器 F12 控制台看运行
  1. <script>
  2.     var cntEmptyCell = 9 * 9;
  3.     var schPath = [];
  4.     var P = [[], [], [], [], [], [], [], [], []];
  5.     // i 行 j 列
  6.     for (let i = 0; i < 9; i++)
  7.         for (let j = 0; j < 9; j++) {
  8.             P[i][j] = {fill: 0, maybe: 0x1FF, choose: 9, block: (Math.floor(i / 3) * 3 + Math.floor(j / 3))};
  9.         }
  10.     var problems = [
  11.         '001000008800010532750024090005302060670500004010780900098053406426179803537460219',
  12.         '503092000700000008006007310020600000065000730007043500000706102070000800400009000',
  13.         '700306000000000050060000018000081000000000000900000200000200900050400000080000007',
  14.         '030000001200806000000005000000000000000000650043070000600002080090000000000010003',
  15.         '010000200300800000000504000800090000000070120500000000000000000020130000400000005',
  16.         '510000700076089000004000805400100007000030000090706010000460201047000300005000084'
  17.     ];
  18.     var problem;
  19.     problem = problems[3];
  20.     const LOOPCNT_CTRL = 50000;
  21.     var LOOPCNT_OUTPUT_BEGIN = LOOPCNT_CTRL - 50;
  22.     var a_p = Array.from(problem);
  23.     var minchoose = 10, i_minchoose = 0, j_minchoose = 0;
  24.     // 题面初始化
  25.     for (let i = 0; i < 9; i++)
  26.         for (let j = 0; j < 9; j++)
  27.             if (a_p[i * 9 + j] - 0 != 0) {
  28.                 P[i][j].maybe = P[i][j].fill = 1 << (a_p[i * 9 + j] - 1);
  29.                 P[i][j].choose = 1;
  30.                 cntEmptyCell -= 1;
  31.                 for (let u = 0; u < 9; u++)
  32.                     if ((u != i) && (P[u][j].fill == 0)) {
  33.                         if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
  34.                             P[u][j].choose -= 1;
  35.                             if (P[u][j].choose < minchoose) {
  36.                                 minchoose = P[u][j].choose;
  37.                                 i_minchoose = u;
  38.                                 j_minchoose = j;
  39.                             }
  40.                             P[u][j].maybe &= ~(P[i][j].fill);
  41.                         }
  42.                     }
  43.                 for (let v = 0; v < 9; v++) {
  44.                     if ((v != j) && (P[i][v].fill == 0)) {
  45.                         if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
  46.                             P[i][v].choose -= 1;
  47.                             if (P[i][v].choose < minchoose) {
  48.                                 minchoose = P[i][v].choose;
  49.                                 i_minchoose = i;
  50.                                 j_minchoose = v;
  51.                             }
  52.                             P[i][v].maybe &= ~(P[i][j].fill);
  53.                         }
  54.                     }
  55.                 }
  56.                 g = P[i][j].block;
  57.                 // 3X3 块的左上角坐标
  58.                 r = Math.floor(g / 3) * 3;
  59.                 c = g % 3 * 3;
  60.                 for (let u = 0; u < 3; u++)
  61.                     for (let v = 0; v < 3; v++) {
  62.                         if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {
  63.                             if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
  64.                                 P[r + u][c + v].choose -= 1;
  65.                                 if (P[r + u][c + v].choose < minchoose) {
  66.                                     minchoose = P[r + u][c + v].choose;
  67.                                     i_minchoose = r + u;
  68.                                     j_minchoose = c + v;
  69.                                 }
  70.                                 P[r + u][c + v].maybe &= ~(P[i][j].fill);
  71.                             }
  72.                         }
  73.                     }
  74.                 // console.log('F=' + a_p[i * 9 + j] + ', i=' + i + ', j=' + j + ', g=' + P[i][j].block + '\n');
  75.             }
  76.     console.log('题面初始化后\n');
  77.     console.log('cntEmptyCell=' + cntEmptyCell + '\n');
  78.     print_fill_intuitive();
  79.     // 初始化尝试填数
  80.     let try_num;
  81.     try_num = 1 << 8;
  82.     while ((try_num != 0) && ((P[i_minchoose][j_minchoose].maybe & try_num) == 0)) {
  83.         try_num >>= 1;
  84.     }
  85.     if (try_num == 0) {
  86.         throw 'error problem\n';
  87.     }
  88.     let maybe;
  89.     let fail_flag = false;
  90.     let success = false;
  91.     let loopcnt = 0;
  92.     // 节点状态:
  93.     // NEW_POS: 填数未失败,新位置填第一个试数
  94.     // NEXT_TRY: 失败换填下一个试数
  95.     // UNDO_POS: 所有试数失败撤消填数
  96.     let state_code = 'NEW_POS';
  97.     do {
  98.         loopcnt++;
  99.         if (fail_flag) {
  100.             // 撤消所有 SET_MAYBE
  101.             while (schPath[0].type == 'SET_MAYBE') {
  102.                 P[schPath[0].row][schPath[0].col].maybe = schPath[0].oldMaybe;
  103.                 P[schPath[0].row][schPath[0].col].choose += 1;
  104.                 schPath.shift();
  105.             }
  106.             // 撤消 FILL_POS
  107.             // 若 try_num 不是最后一个可试数,
  108.             // try_num 取下一个可试数, fail_flag 设为 false
  109.             if (schPath[0].type == 'FILL_POS') {
  110.                 i = schPath[0].row;
  111.                 j = schPath[0].col;
  112.                 P[i][j].fill = schPath[0].oldFill;
  113.                 P[i][j].choose = schPath[0].oldChoose;
  114.                 P[i][j].maybe = schPath[0].oldMaybe;
  115.                 if (schPath[0].oldFill == 0)
  116.                     cntEmptyCell += 1;
  117.                 // 下一个可试的数
  118.                 try_num = schPath[0].fillValue >> 1;
  119.                 schPath.shift();
  120.                 // 试探是否还有下一个可试填数
  121.                 while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {
  122.                     try_num >>= 1;
  123.                 }
  124.                 if (try_num != 0) {
  125.                     fail_flag = false;
  126.                     state_code = 'NEXT_TRY';
  127.                 } else {
  128.                     fail_flag = true;
  129.                     state_code = 'UNDO_POS';
  130.                 }
  131.             }
  132.         } else {
  133.             if (state_code == 'NEW_POS') {
  134.                 if (cntEmptyCell == 0) {
  135.                     // 成功, 输出结果并退出
  136.                     console.log('\n\n' + 'SUCCESS! @ ' + 'loopcnt = ' + loopcnt + '\n\n' + 'problem and answer:\n\n' + PA_STR());
  137.                     print_fill_intuitive();
  138.                     // print_state();
  139.                     success = true;
  140.                     break;
  141.                 }
  142.                 minchoose = 10; // 准备搜索下一轮的最少选择位置
  143.                 i = i_minchoose;
  144.                 j = j_minchoose;
  145.                 // 初始化 try_num
  146.                 try_num = 1 << 8;
  147.                 while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {
  148.                     try_num >>= 1;
  149.                 }
  150.             } else if (state_code == 'NEXT_TRY') {
  151.             }
  152.             if (try_num == 0) {
  153.                 throw 'BUG: try_num == 0';
  154.             } else {
  155.                 // TRYFILL
  156.                 schPath.unshift({type: 'FILL_POS', oldFill: P[i][j].fill, row: i, col: j, fillValue: try_num, fillValue_fact: get_fill_intuitive(try_num), oldChoose: P[i][j].choose, oldMaybe: P[i][j].maybe});
  157.                 if (P[i][j].fill == 0)
  158.                     cntEmptyCell -= 1;
  159.                 P[i][j].choose = 1;
  160.                 P[i][j].maybe = try_num;
  161.                 P[i][j].fill = try_num;
  162.                 for (let u = 0; !fail_flag && (u < 9); u++)
  163.                     if ((u != i) && (P[u][j].fill == 0)) {
  164.                         if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
  165.                             // 搜索栈压栈
  166.                             schPath.unshift({type: 'SET_MAYBE', row: u, col: j, oldMaybe: P[u][j].maybe});
  167.                             P[u][j].choose -= 1;
  168.                             if (P[u][j].choose < minchoose) {
  169.                                 minchoose = P[u][j].choose;
  170.                                 i_minchoose = u;
  171.                                 j_minchoose = j;
  172.                             }
  173.                             maybe = P[u][j].maybe &= ~(P[i][j].fill);
  174.                             if (maybe == 0) {
  175.                                 fail_flag = true;
  176.                                 break;
  177.                             }
  178.                         }
  179.                     }
  180.                 for (let v = 0; !fail_flag && (v < 9); v++) {
  181.                     if ((v != j) && (P[i][v].fill == 0)) {
  182.                         if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
  183.                             // 搜索栈压栈
  184.                             schPath.unshift({type: 'SET_MAYBE', row: i, col: v, oldMaybe: P[i][v].maybe});
  185.                             P[i][v].choose -= 1;
  186.                             if (P[i][v].choose < minchoose) {
  187.                                 minchoose = P[i][v].choose;
  188.                                 i_minchoose = i;
  189.                                 j_minchoose = v;
  190.                             }
  191.                             maybe = P[i][v].maybe &= ~(P[i][j].fill);
  192.                             if (maybe == 0) {
  193.                                 fail_flag = true;
  194.                                 break;
  195.                             }
  196.                         }
  197.                     }
  198.                 }
  199.                 if (!fail_flag) {
  200.                     g = P[i][j].block;
  201.                     // 3X3 块的左上角坐标
  202.                     r = Math.floor(g / 3) * 3;
  203.                     c = g % 3 * 3;
  204.                     for (let u = 0; !fail_flag && (u < 3); u++)
  205.                         for (let v = 0; !fail_flag && (v < 3); v++) {
  206.                             if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {
  207.                                 if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
  208.                                     // 搜索栈压栈
  209.                                     schPath.unshift({type: 'SET_MAYBE', row: r + u, col: c + v, oldMaybe: P[r + u][c + v].maybe});
  210.                                     P[r + u][c + v].choose -= 1;
  211.                                     if (P[r + u][c + v].choose < minchoose) {
  212.                                         minchoose = P[r + u][c + v].choose;
  213.                                         i_minchoose = r + u;
  214.                                         j_minchoose = c + v;
  215.                                     }
  216.                                     maybe = P[r + u][c + v].maybe &= ~(P[i][j].fill);
  217.                                     if (maybe == 0) {
  218.                                         fail_flag = true;
  219.                                         break;
  220.                                     }
  221.                                 }
  222.                             }
  223.                         }
  224.                 }
  225.                 for (let u = 0; u < 9; u++)
  226.                     for (let v = 0; v < 9; v++) {
  227.                         if (!(u == i && v == j) && P[u][v].fill == 0) {
  228.                             if (P[u][v].choose < minchoose) {
  229.                                 minchoose = P[u][v].choose;
  230.                                 i_minchoose = u;
  231.                                 j_minchoose = v;
  232.                             }
  233.                         }
  234.                     }
  235.                 if (COUNT_EmptyCell() != cntEmptyCell) {
  236.                     throw 'BUG: COUNT_EmptyCell = ' + COUNT_EmptyCell();
  237.                 }
  238.             }
  239.             if (fail_flag) {
  240.                 state_code = 'NEXT_TRY';
  241.             } else {
  242.                 state_code = 'NEW_POS';
  243.             }
  244.         }
  245.     } while ((true || (loopcnt < LOOPCNT_CTRL)) && (schPath.length > 0 || (!fail_flag && state_code == 'NEXT_TRY' && try_num != 0)));
  246.     function print_choose_num() {
  247.         console.log('\n\n\n' + 'print_choose_num:' + '\n\n');
  248.         for (let i = 0; i < 9; i++) {
  249.             let line = i + ': ';
  250.             for (let j = 0; j < 9; j++) {
  251.                 line += ((P[i][j].fill != 0) ? '+' : P[i][j].choose) + ' ';
  252.             }
  253.             console.log(line);
  254.         }
  255.     }
  256.     function print_maybe_bin() {
  257.         console.log('\n\n\n' + 'print_maybe_bin:' + '\n\n');
  258.         for (let i = 0; i < 9; i++) {
  259.             let line = i + ': ';
  260.             for (let j = 0; j < 9; j++) {
  261.                 line += ('000000000' + P[i][j].maybe.toString(2)).slice(-9).replace(/0/g, '_') + ' ';
  262.             }
  263.             console.log(line);
  264.         }
  265.     }
  266.     function print_block_num() {
  267.         for (let i = 0; i < 9; i++) {
  268.             let line = i + ': ';
  269.             for (let j = 0; j < 9; j++) {
  270.                 line += ', ' + P[i][j].block;
  271.             }
  272.             console.log(line);
  273.         }
  274.     }
  275.     function print_fill_bin() {
  276.         console.log('\n\n\n' + 'print_fill_bin:' + '\n\n');
  277.         for (let i = 0; i < 9; i++) {
  278.             let line = i + ': ';
  279.             for (let j = 0; j < 9; j++) {
  280.                 line += ('000000000' + P[i][j].fill.toString(2)).slice(-9).replace(/0/g, '_') + ' ';
  281.             }
  282.             console.log(line);
  283.         }
  284.     }
  285.     function print_fill_intuitive() {
  286.         console.log('\n\n\n' + 'print_fill_intuitive:' + '\n\n');
  287.         for (let i = 0; i < 9; i++) {
  288.             let line = i + ': ';
  289.             for (let j = 0; j < 9; j++) {
  290.                 line += get_fill_intuitive(P[i][j].fill) + ' ';
  291.             }
  292.             console.log(line);
  293.         }
  294.     }
  295.     function COUNT_EmptyCell() {
  296.         let sum = 0;
  297.         for (let i = 0; i < 9; i++)
  298.             for (let j = 0; j < 9; j++)
  299.                 if (P[i][j].fill == 0)
  300.                     sum++;
  301.         return sum;
  302.     }
  303.     function get_fill_intuitive(y) {
  304.         if (y == 0) {
  305.             return '_'
  306.         } else
  307.             return (Math.round(Math.log(y) / Math.log(2)) + 1);
  308.     }
  309.     function print_state() {
  310.         console.log('\n\n\n' + 'BEGIN print_state:' + '\n\n');
  311.         print_fill_intuitive();
  312.         print_fill_bin();
  313.         print_choose_num();
  314.         print_maybe_bin();
  315.         console.log('\n\n\n' + 'END print_state.' + '\n\n');
  316.         console.log('\n\n\n' + 'loopcnt = ' + loopcnt);
  317.     }
  318.     function print_choose_state() {
  319.         console.log('\n\n\n' + 'BEGIN print_choose_state:' + '\n\n');
  320.         print_choose_num();
  321.         print_maybe_bin();
  322.         console.log('\n\n\n' + 'END print_choose_state.' + '\n\n');
  323.         console.log('\n\n\n' + 'loopcnt = ' + loopcnt);
  324.     }
  325.     function PA_STR() {
  326.         let t = problem;
  327.         for (let i = 0; i < 9; i++)
  328.             for (let j = 0; j < 9; j++)
  329.                 t += get_fill_intuitive(P[i][j].fill);
  330.         return t;
  331.     }
  332. /*
  333. 搜索算法
  334. 数组存储
  335. P 二维数组 9 行 X 9 列,
  336.     元素为对象 引用方式: P[行号,列号]
  337.         {
  338.             fill:   填数 -- 0 为未填,否则为已填的数值,
  339.             maybe:  可选数的完全可能 -- 以2进制位表达,右至左数第1位表示可选1,第2位表示可选2,...第9位表示可选9, 当此属性值为0x1FF表示1~9全部可选,
  340.                     当有任意一个位置的 maybe 为 0 时, 说明最后试填的数失败, 必须撤回
  341.             choose: 可选数的数目 -- 也就是 maybe 的所有二进制位上 '1' 的总数,
  342.             block:  区块号 -- 值范围[0..8]
  343.          };
  344. cntEmptyCell -- 未填数单元格计数
  345. 解成功判断: if (cntEmptyCell == 0) 成功, 输出结果并退出
  346. 最大关联位置 -- 以当前线索简单判断最少可能选择的位置
  347. 节点状态:
  348. NEW_POS: 填数未失败,新位置填第一个试数
  349. NEXT_TRY: 失败换填下一个试数
  350. UNDO_POS: 所有试数失败撤消填数
  351. 初始化题面并找出最大关联位置
  352. 节点状态 = NEW_POS
  353. 试填失败标志: fail_flag = false
  354. :loop
  355. if (fail_flag == true) {
  356.     撤消搜索栈顶的所有 SET_MAYBE 操作并 弹栈搜索栈
  357.     撤消 FILL_POS 操作 弹栈搜索栈
  358.     如果 当前 处理位置还有可试填的其他数值可能(同时设置好下一个试填数值),
  359.         fail_flag = false;
  360.         节点状态 = 'NEXT_TRY';
  361.     否则
  362.         fail_flag = true;
  363.         节点状态 = 'UNDO_POS';
  364. } else {
  365.     if (节点状态 == 'NEW_POS') {
  366.         检测解出是否成功(成功则输出并退出程序)
  367.         操作位置设为最大关联位置
  368.         找出操作位置上第一个可选数值(0x100 --> 0x1 的次序)
  369.     }
  370.     执行 FILL_POS 操作 并 压栈搜索栈, 将同行同列同区块的 maybe 值作相应处理 并 压栈搜索栈, 找出所有未填数单元格中的 最大关联位置
  371.     处理 maybe 值时 如果 发现无解 (任意一个位置的 maybe == 0), 则 设置失败标志 fail_flag = true
  372. }
  373. 当 搜索栈未空 或 (fail_flag 为假 且 节点状态 == 'NEXT_TRY' 且 存在可试填数)
  374.     goto :loop
  375. 搜索栈结构:
  376. 结点: {type: FILL_POS 或 SET_MAYBE, row:行坐标, col:列坐标, oldMaybe: Maybe原值, fillValue}
  377. type 为 FILL_POS 时, 有 fillValue 值
  378. fillValue 可能的值: 从 2 ** 8 (256) 0X100 开始 依次 >> 1 位, 直到 1, 不包括 0
  379. */
  380. </script>
复制代码

作者: 523066680    时间: 2017-10-10 11:55     标题: RE: [挑战]解数独程序与数独题目生成 —— Dancing Links 算法

本帖最后由 523066680 于 2017-10-10 14:25 编辑

Rosettacode 上面有一段js的示例,代码较长不粘贴了
http://rosettacode.org/wiki/Sudoku#JavaScript
效率是很高,但是实现细节有问题,某些题型会崩溃
  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...',
复制代码
开始我以为是 js 限制递归层数太少,用Perl和C分别实现后发现主要还是和实现有关,递归回溯过程的数据处理写对了就不会有崩溃的情况。

顺便贴一些相关的:
Python 版DLX实现
http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
  1. #!/usr/bin/env python3
  2. # http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
  3. # Author: Ali Assaf <ali.assaf.mail@gmail.com>
  4. # Copyright: (C) 2010 Ali Assaf
  5. # License: GNU General Public License <http://www.gnu.org/licenses/>
  6. from itertools import product
  7. def solve_sudoku(size, grid):
  8.     R, C = size
  9.     N = R * C
  10.     X = ([("rc", rc) for rc in product(range(N), range(N))] +
  11.          [("rn", rn) for rn in product(range(N), range(1, N + 1))] +
  12.          [("cn", cn) for cn in product(range(N), range(1, N + 1))] +
  13.          [("bn", bn) for bn in product(range(N), range(1, N + 1))])
  14.     Y = dict()
  15.     for r, c, n in product(range(N), range(N), range(1, N + 1)):
  16.         b = (r // R) * R + (c // C) # Box number
  17.         Y[(r, c, n)] = [
  18.             ("rc", (r, c)),
  19.             ("rn", (r, n)),
  20.             ("cn", (c, n)),
  21.             ("bn", (b, n))]
  22.     X, Y = exact_cover(X, Y)
  23.     for i, row in enumerate(grid):
  24.         for j, n in enumerate(row):
  25.             if n:
  26.                 select(X, Y, (i, j, n))
  27.     for solution in solve(X, Y, []):
  28.         for (r, c, n) in solution:
  29.             grid[r][c] = n
  30.         yield grid
  31. def exact_cover(X, Y):
  32.     X = {j: set() for j in X}
  33.     for i, row in Y.items():
  34.         for j in row:
  35.             X[j].add(i)
  36.     return X, Y
  37. def solve(X, Y, solution):
  38.     if not X:
  39.         yield list(solution)
  40.     else:
  41.         c = min(X, key=lambda c: len(X[c]))
  42.         for r in list(X[c]):
  43.             solution.append(r)
  44.             cols = select(X, Y, r)
  45.             for s in solve(X, Y, solution):
  46.                 yield s
  47.             deselect(X, Y, r, cols)
  48.             solution.pop()
  49. def select(X, Y, r):
  50.     cols = []
  51.     for j in Y[r]:
  52.         for i in X[j]:
  53.             for k in Y[i]:
  54.                 if k != j:
  55.                     X[k].remove(i)
  56.         cols.append(X.pop(j))
  57.     return cols
  58. def deselect(X, Y, r, cols):
  59.     for j in reversed(Y[r]):
  60.         X[j] = cols.pop()
  61.         for i in X[j]:
  62.             for k in Y[i]:
  63.                 if k != j:
  64.                     X[k].add(i)
  65. grid = [
  66.     [0,0,0,4,0,2,0,0,0],
  67.     [0,0,0,0,0,5,0,0,3],
  68.     [1,0,0,0,7,0,0,9,6],
  69.     [6,0,0,0,3,0,0,0,0],
  70.     [0,0,0,0,0,0,2,0,0],
  71.     [0,0,4,0,0,0,7,0,0],
  72.     [0,0,0,0,9,0,0,0,0],
  73.     [0,0,0,0,0,0,0,0,1],
  74.     [0,0,5,7,0,4,0,0,0]]
  75. for solution in solve_sudoku((3, 3), grid):
  76.     print(*solution, sep='\n')
复制代码
跳跃的舞者,舞蹈链(Dancing Links)算法——求解精确覆盖问题
算法实践——舞蹈链(Dancing Links)算法求解数独

17提示数的题库资源
四万多道17提示数的数独题
用C链表实现的DLX算法,加-O2编译优化,i7 CPU,printf不计入,解这四万多题只要3-6秒。
(参考算法实践——舞蹈链(Dancing Links)算法求解数独 最后一个评论,这个人用C重新实现,也是3秒。)
作者: happy886rr    时间: 2017-10-10 14:06

回复 22# 523066680
太牛叉了,4万道6秒。
作者: 523066680    时间: 2017-10-11 12:14

本帖最后由 523066680 于 2017-10-17 11:00 编辑

正在学着用 github,代码已提交
https://github.com/vicyang/Sudoku/tree/master/Solver/DancingLinks

ChinaUnix 的rubyish把他的方案也写成了C版本,我在上面套了 fill_one_possible_num 函数 后,解sudoku17.txt 也是6秒,
在 i7 cpu 主机上面,3秒


Rubyish/solve_multiGame.c
作者: happy886rr    时间: 2017-10-11 12:49

回复 24# 523066680
不错,代码整理的很整齐。方便今后他人研究分析。
作者: CrLf    时间: 2017-10-11 13:39

回复 22# 523066680


    那个算法666,看来把人脑的算法套用给电脑,的确不合适




欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2