[挑战]解数独程序与数独题目生成
[i=s] 本帖最后由 523066680 于 2017-9-24 16:14 编辑 [/i]以下是从某网站提取的5种难度的数独游戏（难度从1-5，循着网站是可以找到答案的）：
001000008800010532750024090005302060670500004010780900098053406426179803537460219
503092000700000008006007310020600000065000730007043500000706102070000800400009000
700306000000000050060000018000081000000000000900000200000200900050400000080000007
030000001200806000000005000000000000000000650043070000600002080090000000000010003
010000200300800000000504000800090000000070120500000000000000000020130000400000005
写程序对这五个数独题目求解，并计算解每道题的时间消耗。
编程语言：不限
------------------------------------------ 2017-09-18补充 ------------------------------------------
如果解决上面五道题耗时不超过1秒，可以尝试批量解题库中的题，并统计时间消耗。
题库下载：[url]http://523066680.ys168.com/[/url]
Perl/数独/数独题库200801-201709_含答案.zip
题库按键值对存储，key 是时间戳，value 中前81个字符是题目，后81个字符是唯一答案。
nd0 - nd4 表示不同的难度。 [i=s] 本帖最后由 523066680 于 2017-9-14 16:57 编辑 [/i]
脚本，每填入一个数字，重新判断并缩小范围，第四道数独花了五百多秒 ……
[img]http://bbs.bathome.net/images/smilies/default/sweat.gif[/img][code]
2,6,1,9,3,5,7,4,8
8,4,9,6,1,7,5,3,2
7,5,3,8,2,4,6,9,1
9,8,5,3,4,2,1,6,7
6,7,2,5,9,1,3,8,4
3,1,4,7,8,6,9,2,5
1,9,8,2,5,3,4,7,6
4,2,6,1,7,9,8,5,3
5,3,7,4,6,8,2,1,9
Game level: 1, time used: 0.000s
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
Game level: 4, time used: 537.594s[/code]--------------- 2017-09-14 蜜汁 Trick ----------------[code]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
[Finished in 2.2s][/code] 这个用暴力解肯定慢啦...这是我解数独的基本思路，除了第一步，其他的都是嵌套循环的步骤
1、生成草稿表
2、检查纵、横、九宫格内唯一数，填写并从相关单元格的草稿中去除该数
3、根据草稿，排除某九宫格中唯一行或者唯一列对其他行列的影响
4、根据数独“只有唯一解”的规则排除平行对称基本型
5、setlocal，寻找连锁反应最多的点进行暴力解（以只有两种可能性的点为佳） [i=s] 本帖最后由 523066680 于 2017-9-14 17:44 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=203030&ptid=45402]3#[/url] [i]CrLf[/i] [/b]
也不是完全的暴力跑，前三项规则已经应用了，后两项还没有试过。题目的前两道数独秒出结果，第四道耗时很长。 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脚本,选择下一个可用时,是随机抽取一个,
所以运算时间不固定,有运气成分在里面.
[attach]10862[/attach]
不过,level 5运行10次也在1分钟内,level 4运行了3次,长的达26分钟?
level你是不是写反了.
另外,有个数独的小flash程序,做的挺好的,简单,而且各个格子4个角还可以临时设置候选值.
[attach]10861[/attach] 居然是按字符串存储和处理的,如果用int估计会变快吧. :L [i=s] 本帖最后由 523066680 于 2017-9-15 09:53 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=203060&ptid=45402]5#[/url] [i]slore[/i] [/b]
题库在这个网站抓的 [url=http://link.zhihu.com/?target=http%3A//www.cn.sudokupuzzle.org]免费的在线数独[/url]
[url=http://bbs.bathome.net/thread-45401-1-1.html]http://bbs.bathome.net/thread-45401-1-1.html[/url]
[url=http://523066680.ys168.com/]http://523066680.ys168.com/[/url]
Perl/数独/数独题库200801-201709_含答案.zip
难度分为 入门，初级，中级，高级，骨灰级。1楼的题来自每个等级的第一道题目。这个等级划分我也觉得有点问题……
初级的比如：[url=http://www.cn.sudokupuzzle.org/printable.php?nd=1&y=2008&m=1&d=06]数独 - 2008年1月6日 - 初级[/url]
000600500001007000004000000050002000060000800000001007080900000000500001007000004
比同等级的其他题目明显数字要少，可选数字可能性更多。 Rosettacode 有一段 Perl 代码非常简短，不过这段代码因为简短而牺牲了性能，有很多冗余的循环。
[url]http://rosettacode.org/wiki/Sudoku#Perl[/url] [i=s] 本帖最后由 523066680 于 2017-9-16 10:13 编辑 [/i]
初始版本[code]=info
解数独 初版
523066680 2017-09
=cut
use IO::Handle;
use Time::HiRes qw/time/;
STDOUT->autoflush(1);
my @games =
qw/
001000008800010532750024090005302060670500004010780900098053406426179803537460219
503092000700000008006007310020600000065000730007043500000706102070000800400009000
700306000000000050060000018000081000000000000900000200000200900050400000080000007
030000001200806000000005000000000000000000650043070000600002080090000000000010003
010000200300800000000504000800090000000070120500000000000000000020130000400000005
/;
our @unsolve;
our $block = []; #区块引用
my $mat = [[]];
my $level = 0;
my $time_a;
#创建区块引用，以便于操作
make_block_refs( $block, $mat );
while ( $level <= $#games )
{
#字符串转矩阵
str_to_mat( $games[$level] , $mat );
$time_a = time();
#设置 @unsolve 数组，存储空缺元素的坐标
set_unsolve_array($mat);
solve($mat, 0);
print_mat($mat);
printf "Game level: %d, time used: %.3fs\n\n", $level+1, time() - $time_a;
$level++;
}
sub solve
{
my ($mat, $prev, $lv) = @_;
my @possible;
my ($row, $col);
my $current;
for my $i ( $prev .. $#unsolve )
{
($row, $col) = @{$unsolve[$i]};
if ( $mat->[$row][$col] == 0 )
{
$current = $i;
@possible = get_possible_num( $mat, $row, $col );
last;
}
}
if ( not defined $current ) { return 1 }
else
{
return 0 if ( $#possible < 0 )
}
my $res = 0;
for my $p ( @possible )
{
$mat->[ $row ][ $col ] = $p;
$res = solve($mat, $current+1, $lv+1);
last if ($res == 1);
}
#使对应单元恢复为0 否则影响递归判断
$mat->[$row][$col] = 0 if ($res == 0) ;
return $res;
}
sub get_possible_num
{
our ($block, %hash);
my ($mat, $row, $col) = @_;
my %possible = (1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9);
#排除元素
for my $n ( 0 .. 8 )
{
delete $possible{ $mat->[$n][$col] };
delete $possible{ $mat->[$row][$n] };
delete $possible{ ${$block->[$row/3][$col/3][$n]} };
}
return sort keys %possible;
}
sub get_possible_num_2
{
our ($block, %hash);
my ($mat, $row, $col) = @_;
my @possible = (0,1,2,3,4,5,6,7,8,9);
#区块坐标
my $blockrow = int($row/3);
my $blockcol = int($col/3);
#排除元素
for my $n ( 0 .. 9 )
{
$possible[ $mat->[$n][$col] ] = 0;
$possible[ $mat->[$row][$n] ] = 0;
$possible[ ${$block->[$blockrow][$blockcol][$n]} ] = 0;
}
return grep { $_ } @possible;
}
sub set_unsolve_array
{
our ( @unsolve );
my ($mat) = @_;
@unsolve = ();
for my $row ( 0..8 )
{
for my $col ( 0..8 )
{
if ( $mat->[$row][$col] == 0 )
{
push @unsolve, [ $row, $col, [get_possible_num( $mat, $row, $col )] ];
}
}
}
#根据可选数字的数量由少到多排序
#@unsolve = sort { $#{$a->[2]} <=> $#{$b->[2]} } @unsolve;
}
sub make_block_refs
{
my ($block, $mat) = @_;
#将数独的九个宫对应的引用分组保存
for my $r ( 0..2 )
{
for my $c ( 0..2 )
{
for my $rr ( $r*3 .. $r*3+2 )
{
for my $cc ( $c*3 .. $c*3+2 )
{
push @{ $block->[$r][$c] }, \$mat->[$rr][$cc];
}
}
}
}
}
sub str_to_mat
{
my ( $str, $mat ) = @_;
my $idx = 0;
for my $row ( 0 .. 8 )
{
for my $col ( 0 .. 8 )
{
$mat->[$row][$col] = substr( $str, $idx++, 1 );
}
}
}
sub print_mat
{
my ($mat) = @_;
grep { print join(",", @{$mat->[$_]} ),"\n" } ( 0..8 );
}
[/code]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 [i=s] 本帖最后由 523066680 于 2017-9-18 16:27 编辑 [/i]
最近换了个方案，遇到难度高的题目时比原来的方案快得多（但还是没有Rubyish @Chinaunix 的代码快）
给定一个题目，判断 1-9 每个数字的全局分布情况（可能性）。
比如1可能分布的情况有6种，测试每一种，把9个1全部填入数独，然后继续测试其他数字的分布。
题目
[quote]140968000000000900600057300000000007300000840000196500070000405406010030000000000[/quote]
数字1的可能分布情况
[quote][color=b00000]1[/color]4096800000000[color=b00000]1[/color]9006000573[color=b00000]1[/color]00[color=b00000]1[/color]000000730000084[color=b00000]1[/color]000[color=b00000]1[/color]9650007[color=b00000]1[/color]0004054060[color=b00000]1[/color]0030000000[color=b00000]1[/color]00
[color=b00000]1[/color]4096800000000[color=b00000]1[/color]9006000573[color=b00000]1[/color]0000000[color=b00000]1[/color]073[color=b00000]1[/color]0000840000[color=b00000]1[/color]9650007[color=b00000]1[/color]0004054060[color=b00000]1[/color]003000000000[color=b00000]1[/color]
[color=b00000]1[/color]4096800000000[color=b00000]1[/color]90060005730[color=b00000]1[/color]000000[color=b00000]1[/color]073[color=b00000]1[/color]0000840000[color=b00000]1[/color]9650007[color=b00000]1[/color]0004054060[color=b00000]1[/color]00300000000[color=b00000]1[/color]0
[color=b00000]1[/color]4096800000000[color=b00000]1[/color]90060005730[color=b00000]1[/color]000000[color=b00000]1[/color]073[color=b00000]1[/color]0000840000[color=b00000]1[/color]965000700004[color=b00000]1[/color]54060[color=b00000]1[/color]003000[color=b00000]1[/color]000000
[color=b00000]1[/color]4096800000000[color=b00000]1[/color]90060005730[color=b00000]1[/color]000000[color=b00000]1[/color]0730[color=b00000]1[/color]000840000[color=b00000]1[/color]965000700004[color=b00000]1[/color]54060[color=b00000]1[/color]00300[color=b00000]1[/color]0000000
[color=b00000]1[/color]4096800000000[color=b00000]1[/color]90060005730[color=b00000]1[/color]0000000[color=b00000]1[/color]73[color=b00000]1[/color]0000840000[color=b00000]1[/color]9650007[color=b00000]1[/color]0004054060[color=b00000]1[/color]0030000000[color=b00000]1[/color]00
[/quote]
完整代码：[code]=info
方案 - 遍历数字分布情况
523066680 2017-09
=cut
use File::Slurp;
use IO::Handle;
STDOUT->autoflush(1);
# my $gamedata = eval read_file("../sudoku_nd1.txt");
# grep { push @games, $gamedata->{$_} } sort keys %$gamedata;
@games =
qw/
001000008800010532750024090005302060670500004010780900098053406426179803537460219
503092000700000008006007310020600000065000730007043500000706102070000800400009000
700306000000000050060000018000081000000000000900000200000200900050400000080000007
030000001200806000000005000000000000000000650043070000600002080090000000000010003
010000200300800000000504000800090000000070120500000000000000000020130000400000005
/;
our @order;
our $answer_mat = [[]];
my $mat;
my $res;
my $allcase;
my $answer_str;
#坐标对应区块位置的表
our @blk = map { int($_ / 3) } ( 0..8 );
while ( $index <= $#games )
{
$mat = [[]];
$time_a = time();
str_to_mat( $games[$index] , $mat );
$allcase = [ map { [] } (0..9) ];
grep { possible_mat($mat, $_, $allcase->[$_], 0) } (1..9);
@order = sort { $#{$allcase->[$a]} <=> $#{$allcase->[$b]} } ( 0 .. 9 );
$res = recursive( $mat, 1 ); #起点为1，下标 0占位
if ($res == 1)
{
print_mat_inline( $answer_mat );
}
else { die "false\n" }
printf "Game index: %d, time used: %.3fs\n\n", $index, time() - $time_a;
$index++;
}
sub recursive
{
our (@order, $answer_mat);
my ( $mat, $lv ) = @_;
my @case;
if ( $lv > 9 )
{
$answer_mat = $mat;
return 1;
}
$target = $order[$lv];
possible_mat($mat, $target, \@case, 0);
my $t_mat = [[]];
my $res = 0;
for my $s ( @case )
{
str_to_mat( $s, $t_mat );
$res = recursive( $t_mat, $lv+1 );
last if ($res == 1);
}
return $res;
}
sub possible_mat
{
my ( $mat, $target, $aref, $lv ) = @_;
# level means row
my $str;
if ($lv == 9)
{
$count++;
push @$aref, mat_to_str($mat);
return 1;
}
my @cols = get_possible_column( $mat, $lv, $target );
my $res = 0;
my $ever;
for my $c ( @cols )
{
$ever = $mat->[$lv][$c];
$mat->[$lv][$c] = $target;
$res = possible_mat( $mat, $target, $aref, $lv+1 );
$mat->[$lv][$c] = $ever;
}
return $res;
}
sub get_possible_column
{
our @blk;
my ( $mat, $row, $target ) = @_;
my @cols = ( 0..8 );
for my $c ( 0..8 )
{
#如果当前行已经存在这个数字，则直接返回这个数字的位置。
if ( $mat->[$row][$c] == $target )
{
return ( $c );
}
elsif ( $mat->[$row][$c] != 0 )
{
$cols[$c] = -1;
}
for my $r ( 0..8 )
{
if ( $mat->[$r][$c] == $target )
{
$cols[$c] = -1;
if ( $blk[$r] == $blk[$row] )
{
$cols[ $blk[$c] * 3 + 0] = -1;
$cols[ $blk[$c] * 3 + 1] = -1;
$cols[ $blk[$c] * 3 + 2] = -1;
}
}
}
}
return grep { $_ != -1 } @cols;
}
sub str_to_mat
{
my ( $str, $mat ) = @_;
my $idx = 0;
for my $row ( 0 .. 8 )
{
for my $col ( 0 .. 8 )
{
$mat->[$row][$col] = substr( $str, $idx++, 1 );
}
}
}
sub mat_to_str
{
my ( $mat ) = @_;
return join("", map { join("", @{$mat->[$_]} ) } (0..8));
}
sub print_mat
{
my ($mat) = @_;
grep { print join(",", @{$mat->[$_]} ),"\n" } ( 0..8 );
}
sub print_mat_inline
{
my ($mat) = @_;
grep { print join("", @{$mat->[$_]} ),"" } ( 0..8 );
print "\n";
}
[/code][quote]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[/quote]
跑完 sudoku_nd0.txt 三千多道题需要十多秒，跑完 sudoku_nd4.txt 大约六百秒。
CU Rubyish 的代码，跑完 nd0 零点几秒，nd4 一百多秒 旋转90度，180度等，开4个进程并行跑，应该会某个路线快些，只用把初始数据按规律变换即可。
再有，4个线程的某单元格的候选项目共享，更快得出唯一解。
再有，改变搜索前进方向，上面旋转数独盘，左右，上下，4个方向同时了，还有顺时旋转前进，逆时针方向，先斜线，先小格等方向，可以开更多线程。 [b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=203138&ptid=45402]11#[/url] [i]slore[/i] [/b]
线程的方案留到最后，单线程仍然有更快的算法，快到解 sudoku_nd4.txt 所有题只要十多秒。 [b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=203162&ptid=45402]12#[/url] [i]523066680[/i] [/b]
单纯考虑算法的话，肯定有更优的，但是 多线程对于现在大内存，多核CPU才是更好的利用，而且很多问题都可以采用这个方法来提高。
至于探索路径，不一定非要0～81这个顺序，可以把每个格子的候选项，从小到大排列，按这个数据填，有大概率先填入正确的数据，可以减少尝试次数吧。那天有时间了ruby写下试试。 [i=s] 本帖最后由 slore 于 2017-9-20 13:03 编辑 [/i]
[code]class Soduku
def initialize(str)
@matrix = 9.times.map{[0]*9}
str.reverse! <-只加了一句，LEVEL4立马难度变低了
nums = str.split('').map(&:to_i)
...
end
[/code][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] [quote]至于探索路径，不一定非要0～81这个顺序，可以把每个格子的候选项，从小到大排列，按这个数据填，有大概率先填入正确的数据，可以减少尝试次数吧。[/quote]
错了，如果按候选项探索的话，比如, [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秒之间 :)[code]
#魔法CODE
str.reserse!
v = ans.sample
[/code][code] sort_seq = []
while
sort_seq.push @solve_seq[min_seq]
x = @solve_seq[min_seq][0]
y = @solve_seq[min_seq][1]
z = ((x / 3) * 3) + (y / 3)
@solve_seq.delete_at(min_seq)
break if @solve_seq.size == 0
min = 10
min_seq = -1
@solve_seq.each_with_index do |seq, i|
zz = ((seq[0] / 3) * 3) + (seq[1] / 3)
if seq[0] == x || seq[1] == y || zz == z
seq[2] -= 1
if seq[2] < min
min = seq[2]
min_seq = i
end
end
end
end
p sort_seq
@solve_seq = sort_seq[/code] [i=s] 本帖最后由 523066680 于 2017-9-20 20:34 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=203181&ptid=45402]15#[/url] [i]slore[/i] [/b]
对于回溯法，有一个优化很有效果。示意图（注意除了中间有个独立的候选数字2，右上角还有个框选的数字8）：
[img]http://imgout.ph.126.net/57740103/D6BBB3F6CFD6D2BBB4CEB5C4.jpg[/img]
程序给定的单元候选数字中，大多单元格有多个可选数字，但是可以进一步排除。例如：
如果累计一行中的所有候选数，某个数字只出现一次，那么这个数字就是必选数字。同样，一列、一宫(3x3 block)的区域内也是如此。
我为程序增加了一个while 循环，反复筛选并填充唯一的数字，直到再也没有，然后才开始递归解题。
[quote]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[/quote] [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=203183&ptid=45402]16#[/url] [i]523066680[/i] [/b]
VBS当时写代码,就有这个逻辑.先CreatePlan里面有presolvecount,然后才SolvePanes递归的. 我来了,等下用我之前的生成类试试 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=203278&ptid=45402]18#[/url] [i]bbaa[/i] [/b]
随机法真的 身败名裂[code]Allowed memory size of 134217728 bytes exhausted (tried to allocate 40 bytes)[/code] [i=s] 本帖最后由 523066680 于 2017-9-24 16:09 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=203280&ptid=45402]19#[/url] [i]bbaa[/i] [/b]
对于题目和结果判断，你先用现成的题库弄上网站跑跑看？我前面发的题库分为5种难度等级，你可以随机抽取。
这些题只有一种答案，也都在文件里了，检验方便。（虽然这样提供了作弊条件，可以直接POST现有答案，不过也就是试试效果） 闲时再弄弄, JS 还有些冗余的变量及逻辑
保存为 htm 文件, 浏览器 F12 控制台看运行[code]<script>
var cntEmptyCell = 9 * 9;
var schPath = [];
var P = [[], [], [], [], [], [], [], [], []];
// i 行 j 列
for (let i = 0; i < 9; i++)
for (let j = 0; j < 9; j++) {
P[i][j] = {fill: 0, maybe: 0x1FF, choose: 9, block: (Math.floor(i / 3) * 3 + Math.floor(j / 3))};
}
var problems = [
'001000008800010532750024090005302060670500004010780900098053406426179803537460219',
'503092000700000008006007310020600000065000730007043500000706102070000800400009000',
'700306000000000050060000018000081000000000000900000200000200900050400000080000007',
'030000001200806000000005000000000000000000650043070000600002080090000000000010003',
'010000200300800000000504000800090000000070120500000000000000000020130000400000005',
'510000700076089000004000805400100007000030000090706010000460201047000300005000084'
];
var problem;
problem = problems[3];
const LOOPCNT_CTRL = 50000;
var LOOPCNT_OUTPUT_BEGIN = LOOPCNT_CTRL - 50;
var a_p = Array.from(problem);
var minchoose = 10, i_minchoose = 0, j_minchoose = 0;
// 题面初始化
for (let i = 0; i < 9; i++)
for (let j = 0; j < 9; j++)
if (a_p[i * 9 + j] - 0 != 0) {
P[i][j].maybe = P[i][j].fill = 1 << (a_p[i * 9 + j] - 1);
P[i][j].choose = 1;
cntEmptyCell -= 1;
for (let u = 0; u < 9; u++)
if ((u != i) && (P[u][j].fill == 0)) {
if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
P[u][j].choose -= 1;
if (P[u][j].choose < minchoose) {
minchoose = P[u][j].choose;
i_minchoose = u;
j_minchoose = j;
}
P[u][j].maybe &= ~(P[i][j].fill);
}
}
for (let v = 0; v < 9; v++) {
if ((v != j) && (P[i][v].fill == 0)) {
if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
P[i][v].choose -= 1;
if (P[i][v].choose < minchoose) {
minchoose = P[i][v].choose;
i_minchoose = i;
j_minchoose = v;
}
P[i][v].maybe &= ~(P[i][j].fill);
}
}
}
g = P[i][j].block;
// 3X3 块的左上角坐标
r = Math.floor(g / 3) * 3;
c = g % 3 * 3;
for (let u = 0; u < 3; u++)
for (let v = 0; v < 3; v++) {
if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {
if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
P[r + u][c + v].choose -= 1;
if (P[r + u][c + v].choose < minchoose) {
minchoose = P[r + u][c + v].choose;
i_minchoose = r + u;
j_minchoose = c + v;
}
P[r + u][c + v].maybe &= ~(P[i][j].fill);
}
}
}
// console.log('F=' + a_p[i * 9 + j] + ', i=' + i + ', j=' + j + ', g=' + P[i][j].block + '\n');
}
console.log('题面初始化后\n');
console.log('cntEmptyCell=' + cntEmptyCell + '\n');
print_fill_intuitive();
// 初始化尝试填数
let try_num;
try_num = 1 << 8;
while ((try_num != 0) && ((P[i_minchoose][j_minchoose].maybe & try_num) == 0)) {
try_num >>= 1;
}
if (try_num == 0) {
throw 'error problem\n';
}
let maybe;
let fail_flag = false;
let success = false;
let loopcnt = 0;
// 节点状态:
// NEW_POS: 填数未失败,新位置填第一个试数
// NEXT_TRY: 失败换填下一个试数
// UNDO_POS: 所有试数失败撤消填数
let state_code = 'NEW_POS';
do {
loopcnt++;
if (fail_flag) {
// 撤消所有 SET_MAYBE
while (schPath[0].type == 'SET_MAYBE') {
P[schPath[0].row][schPath[0].col].maybe = schPath[0].oldMaybe;
P[schPath[0].row][schPath[0].col].choose += 1;
schPath.shift();
}
// 撤消 FILL_POS
// 若 try_num 不是最后一个可试数,
// try_num 取下一个可试数, fail_flag 设为 false
if (schPath[0].type == 'FILL_POS') {
i = schPath[0].row;
j = schPath[0].col;
P[i][j].fill = schPath[0].oldFill;
P[i][j].choose = schPath[0].oldChoose;
P[i][j].maybe = schPath[0].oldMaybe;
if (schPath[0].oldFill == 0)
cntEmptyCell += 1;
// 下一个可试的数
try_num = schPath[0].fillValue >> 1;
schPath.shift();
// 试探是否还有下一个可试填数
while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {
try_num >>= 1;
}
if (try_num != 0) {
fail_flag = false;
state_code = 'NEXT_TRY';
} else {
fail_flag = true;
state_code = 'UNDO_POS';
}
}
} else {
if (state_code == 'NEW_POS') {
if (cntEmptyCell == 0) {
// 成功, 输出结果并退出
console.log('\n\n' + 'SUCCESS! @ ' + 'loopcnt = ' + loopcnt + '\n\n' + 'problem and answer:\n\n' + PA_STR());
print_fill_intuitive();
// print_state();
success = true;
break;
}
minchoose = 10; // 准备搜索下一轮的最少选择位置
i = i_minchoose;
j = j_minchoose;
// 初始化 try_num
try_num = 1 << 8;
while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {
try_num >>= 1;
}
} else if (state_code == 'NEXT_TRY') {
}
if (try_num == 0) {
throw 'BUG: try_num == 0';
} else {
// TRYFILL
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});
if (P[i][j].fill == 0)
cntEmptyCell -= 1;
P[i][j].choose = 1;
P[i][j].maybe = try_num;
P[i][j].fill = try_num;
for (let u = 0; !fail_flag && (u < 9); u++)
if ((u != i) && (P[u][j].fill == 0)) {
if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
// 搜索栈压栈
schPath.unshift({type: 'SET_MAYBE', row: u, col: j, oldMaybe: P[u][j].maybe});
P[u][j].choose -= 1;
if (P[u][j].choose < minchoose) {
minchoose = P[u][j].choose;
i_minchoose = u;
j_minchoose = j;
}
maybe = P[u][j].maybe &= ~(P[i][j].fill);
if (maybe == 0) {
fail_flag = true;
break;
}
}
}
for (let v = 0; !fail_flag && (v < 9); v++) {
if ((v != j) && (P[i][v].fill == 0)) {
if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
// 搜索栈压栈
schPath.unshift({type: 'SET_MAYBE', row: i, col: v, oldMaybe: P[i][v].maybe});
P[i][v].choose -= 1;
if (P[i][v].choose < minchoose) {
minchoose = P[i][v].choose;
i_minchoose = i;
j_minchoose = v;
}
maybe = P[i][v].maybe &= ~(P[i][j].fill);
if (maybe == 0) {
fail_flag = true;
break;
}
}
}
}
if (!fail_flag) {
g = P[i][j].block;
// 3X3 块的左上角坐标
r = Math.floor(g / 3) * 3;
c = g % 3 * 3;
for (let u = 0; !fail_flag && (u < 3); u++)
for (let v = 0; !fail_flag && (v < 3); v++) {
if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {
if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
// 搜索栈压栈
schPath.unshift({type: 'SET_MAYBE', row: r + u, col: c + v, oldMaybe: P[r + u][c + v].maybe});
P[r + u][c + v].choose -= 1;
if (P[r + u][c + v].choose < minchoose) {
minchoose = P[r + u][c + v].choose;
i_minchoose = r + u;
j_minchoose = c + v;
}
maybe = P[r + u][c + v].maybe &= ~(P[i][j].fill);
if (maybe == 0) {
fail_flag = true;
break;
}
}
}
}
}
for (let u = 0; u < 9; u++)
for (let v = 0; v < 9; v++) {
if (!(u == i && v == j) && P[u][v].fill == 0) {
if (P[u][v].choose < minchoose) {
minchoose = P[u][v].choose;
i_minchoose = u;
j_minchoose = v;
}
}
}
if (COUNT_EmptyCell() != cntEmptyCell) {
throw 'BUG: COUNT_EmptyCell = ' + COUNT_EmptyCell();
}
}
if (fail_flag) {
state_code = 'NEXT_TRY';
} else {
state_code = 'NEW_POS';
}
}
} while ((true || (loopcnt < LOOPCNT_CTRL)) && (schPath.length > 0 || (!fail_flag && state_code == 'NEXT_TRY' && try_num != 0)));
function print_choose_num() {
console.log('\n\n\n' + 'print_choose_num:' + '\n\n');
for (let i = 0; i < 9; i++) {
let line = i + ': ';
for (let j = 0; j < 9; j++) {
line += ((P[i][j].fill != 0) ? '+' : P[i][j].choose) + ' ';
}
console.log(line);
}
}
function print_maybe_bin() {
console.log('\n\n\n' + 'print_maybe_bin:' + '\n\n');
for (let i = 0; i < 9; i++) {
let line = i + ': ';
for (let j = 0; j < 9; j++) {
line += ('000000000' + P[i][j].maybe.toString(2)).slice(-9).replace(/0/g, '_') + ' ';
}
console.log(line);
}
}
function print_block_num() {
for (let i = 0; i < 9; i++) {
let line = i + ': ';
for (let j = 0; j < 9; j++) {
line += ', ' + P[i][j].block;
}
console.log(line);
}
}
function print_fill_bin() {
console.log('\n\n\n' + 'print_fill_bin:' + '\n\n');
for (let i = 0; i < 9; i++) {
let line = i + ': ';
for (let j = 0; j < 9; j++) {
line += ('000000000' + P[i][j].fill.toString(2)).slice(-9).replace(/0/g, '_') + ' ';
}
console.log(line);
}
}
function print_fill_intuitive() {
console.log('\n\n\n' + 'print_fill_intuitive:' + '\n\n');
for (let i = 0; i < 9; i++) {
let line = i + ': ';
for (let j = 0; j < 9; j++) {
line += get_fill_intuitive(P[i][j].fill) + ' ';
}
console.log(line);
}
}
function COUNT_EmptyCell() {
let sum = 0;
for (let i = 0; i < 9; i++)
for (let j = 0; j < 9; j++)
if (P[i][j].fill == 0)
sum++;
return sum;
}
function get_fill_intuitive(y) {
if (y == 0) {
return '_'
} else
return (Math.round(Math.log(y) / Math.log(2)) + 1);
}
function print_state() {
console.log('\n\n\n' + 'BEGIN print_state:' + '\n\n');
print_fill_intuitive();
print_fill_bin();
print_choose_num();
print_maybe_bin();
console.log('\n\n\n' + 'END print_state.' + '\n\n');
console.log('\n\n\n' + 'loopcnt = ' + loopcnt);
}
function print_choose_state() {
console.log('\n\n\n' + 'BEGIN print_choose_state:' + '\n\n');
print_choose_num();
print_maybe_bin();
console.log('\n\n\n' + 'END print_choose_state.' + '\n\n');
console.log('\n\n\n' + 'loopcnt = ' + loopcnt);
}
function PA_STR() {
let t = problem;
for (let i = 0; i < 9; i++)
for (let j = 0; j < 9; j++)
t += get_fill_intuitive(P[i][j].fill);
return t;
}
/*
搜索算法
数组存储
P 二维数组 9 行 X 9 列,
元素为对象 引用方式: P[行号,列号]
{
fill: 填数 -- 0 为未填,否则为已填的数值,
maybe: 可选数的完全可能 -- 以2进制位表达,右至左数第1位表示可选1,第2位表示可选2,...第9位表示可选9, 当此属性值为0x1FF表示1~9全部可选,
当有任意一个位置的 maybe 为 0 时, 说明最后试填的数失败, 必须撤回
choose: 可选数的数目 -- 也就是 maybe 的所有二进制位上 '1' 的总数,
block: 区块号 -- 值范围[0..8]
};
cntEmptyCell -- 未填数单元格计数
解成功判断: if (cntEmptyCell == 0) 成功, 输出结果并退出
最大关联位置 -- 以当前线索简单判断最少可能选择的位置
节点状态:
NEW_POS: 填数未失败,新位置填第一个试数
NEXT_TRY: 失败换填下一个试数
UNDO_POS: 所有试数失败撤消填数
初始化题面并找出最大关联位置
节点状态 = NEW_POS
试填失败标志: fail_flag = false
:loop
if (fail_flag == true) {
撤消搜索栈顶的所有 SET_MAYBE 操作并 弹栈搜索栈
撤消 FILL_POS 操作 弹栈搜索栈
如果 当前 处理位置还有可试填的其他数值可能(同时设置好下一个试填数值),
fail_flag = false;
节点状态 = 'NEXT_TRY';
否则
fail_flag = true;
节点状态 = 'UNDO_POS';
} else {
if (节点状态 == 'NEW_POS') {
检测解出是否成功(成功则输出并退出程序)
操作位置设为最大关联位置
找出操作位置上第一个可选数值(0x100 --> 0x1 的次序)
}
执行 FILL_POS 操作 并 压栈搜索栈, 将同行同列同区块的 maybe 值作相应处理 并 压栈搜索栈, 找出所有未填数单元格中的 最大关联位置
处理 maybe 值时 如果 发现无解 (任意一个位置的 maybe == 0), 则 设置失败标志 fail_flag = true
}
当 搜索栈未空 或 (fail_flag 为假 且 节点状态 == 'NEXT_TRY' 且 存在可试填数)
goto :loop
搜索栈结构:
结点: {type: FILL_POS 或 SET_MAYBE, row:行坐标, col:列坐标, oldMaybe: Maybe原值, fillValue}
type 为 FILL_POS 时, 有 fillValue 值
fillValue 可能的值: 从 2 ** 8 (256) 0X100 开始 依次 >> 1 位, 直到 1, 不包括 0
*/
</script>
[/code]
RE: [挑战]解数独程序与数独题目生成 —— Dancing Links 算法
[i=s] 本帖最后由 523066680 于 2017-10-10 14:25 编辑 [/i]Rosettacode 上面有一段js的示例，代码较长不粘贴了
[url=http://rosettacode.org/wiki/Sudoku#JavaScript]http://rosettacode.org/wiki/Sudoku#JavaScript[/url]
效率是很高，但是实现细节有问题，某些题型会崩溃[code]sudoku_nd3.txt
//'7.56...19........89....8.....81.2.7...13..4.237...5.9.8.3..1.25...5....41........',
//'.....4...7.......2.....61.....2.......4...3..8..79.6....78....9.36........1......',
//'...3.1...49......638.......1.5..7.......9...8.........6...4...........5...3...71.',
sudoku_nd4.txt
//'......3......2.1..1.84.9.....7....2..3.6...7...6.7...8....5846.2........9..1.....',
//'.....53..6.....5.8...1...2.45.8...1.3.....4.5..2.........2.18....7.3..6..2...4...',
//'....9..3...5..2.4.7.94....13.1....98.4.9........8..6..2...13..7..36...151....9...',
[/code]开始我以为是 js 限制递归层数太少，用Perl和C分别实现后发现主要还是和实现有关，递归回溯过程的数据处理写对了就不会有崩溃的情况。
顺便贴一些相关的：
Python 版DLX实现
[url=http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html]http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html[/url][code]#!/usr/bin/env python3
# http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
# Author: Ali Assaf <ali.assaf.mail@gmail.com>
# Copyright: (C) 2010 Ali Assaf
# License: GNU General Public License <http://www.gnu.org/licenses/>
from itertools import product
def solve_sudoku(size, grid):
R, C = size
N = R * C
X = ([("rc", rc) for rc in product(range(N), range(N))] +
[("rn", rn) for rn in product(range(N), range(1, N + 1))] +
[("cn", cn) for cn in product(range(N), range(1, N + 1))] +
[("bn", bn) for bn in product(range(N), range(1, N + 1))])
Y = dict()
for r, c, n in product(range(N), range(N), range(1, N + 1)):
b = (r // R) * R + (c // C) # Box number
Y[(r, c, n)] = [
("rc", (r, c)),
("rn", (r, n)),
("cn", (c, n)),
("bn", (b, n))]
X, Y = exact_cover(X, Y)
for i, row in enumerate(grid):
for j, n in enumerate(row):
if n:
select(X, Y, (i, j, n))
for solution in solve(X, Y, []):
for (r, c, n) in solution:
grid[r][c] = n
yield grid
def exact_cover(X, Y):
X = {j: set() for j in X}
for i, row in Y.items():
for j in row:
X[j].add(i)
return X, Y
def solve(X, Y, solution):
if not X:
yield list(solution)
else:
c = min(X, key=lambda c: len(X[c]))
for r in list(X[c]):
solution.append(r)
cols = select(X, Y, r)
for s in solve(X, Y, solution):
yield s
deselect(X, Y, r, cols)
solution.pop()
def select(X, Y, r):
cols = []
for j in Y[r]:
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].remove(i)
cols.append(X.pop(j))
return cols
def deselect(X, Y, r, cols):
for j in reversed(Y[r]):
X[j] = cols.pop()
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].add(i)
grid = [
[0,0,0,4,0,2,0,0,0],
[0,0,0,0,0,5,0,0,3],
[1,0,0,0,7,0,0,9,6],
[6,0,0,0,3,0,0,0,0],
[0,0,0,0,0,0,2,0,0],
[0,0,4,0,0,0,7,0,0],
[0,0,0,0,9,0,0,0,0],
[0,0,0,0,0,0,0,0,1],
[0,0,5,7,0,4,0,0,0]]
for solution in solve_sudoku((3, 3), grid):
print(*solution, sep='\n')[/code][url=http://www.cnblogs.com/grenet/p/3145800.html]跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题[/url]
[url=http://www.cnblogs.com/grenet/p/3163550.html]算法实践——舞蹈链（Dancing Links）算法求解数独[/url]
17提示数的题库资源
[url=http://staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php]四万多道17提示数的数独题[/url]
用C链表实现的DLX算法，加-O2编译优化，i7 CPU，printf不计入，解这四万多题只要3-6秒。
（参考[url=http://www.cnblogs.com/grenet/p/3163550.html]算法实践——舞蹈链（Dancing Links）算法求解数独[/url] 最后一个评论，这个人用C重新实现，也是3秒。） [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=203747&ptid=45402]22#[/url] [i]523066680[/i] [/b]
太牛叉了，4万道6秒。 [i=s] 本帖最后由 523066680 于 2017-10-17 11:00 编辑 [/i]
正在学着用 github，代码已提交
[url]https://github.com/vicyang/Sudoku/tree/master/Solver/DancingLinks[/url]
ChinaUnix 的rubyish把他的方案也写成了C版本，我在上面套了 fill_one_possible_num 函数 后，解sudoku17.txt 也是6秒，
在 i7 cpu 主机上面，3秒
[img]http://bbs.bathome.net/images/smilies/coolmonkey/02.gif[/img]
[url=https://github.com/vicyang/Sudoku/blob/RubyishOPT_02/Others/Rubyish/solve_multiGame.c]Rubyish/solve_multiGame.c[/url] [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=203764&ptid=45402]24#[/url] [i]523066680[/i] [/b]
不错，代码整理的很整齐。方便今后他人研究分析。 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=203747&ptid=45402]22#[/url] [i]523066680[/i] [/b]
那个算法666，看来把人脑的算法套用给电脑，的确不合适
页:
[1]