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

论坛徽章:: 7

12楼 [报告]

发表于 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

// [ SOME STRING ].forEach(reduceGrid);
// Or of you want to create all the grids of a particular n-size.
// I run out of stack space at n = 9
//let n = 2;
//let s = new Array(Math.pow(n, 4)).fill('.').join('');
//reduceGrid(s);
const sudo9 =
"......8....2.7..4....3..6.16..1....5..9.4........57.....7..5.9.3.....1.8.8......."
reduceGrid(sudo9);

复制代码

js: version 57

time js -b sudo.js

rosetta:

+-------+-------+-------+
| 5 9 3 | 4 1 6 | 8 2 7 |
| 1 6 2 | 5 7 8 | 3 4 9 |
| 7 4 8 | 3 2 9 | 6 5 1 |
+-------+-------+-------+
| 6 7 4 | 1 8 2 | 9 3 5 |
| 8 5 9 | 6 4 3 | 7 1 2 |
| 2 3 1 | 9 5 7 | 4 8 6 |
+-------+-------+-------+
| 4 1 7 | 8 6 5 | 2 9 3 |
| 3 2 5 | 7 9 4 | 1 6 8 |
| 9 8 6 | 2 3 1 | 5 7 4 |
+-------+-------+-------+
runtime = 602.870 ms
real 0m0.750s
user 0m0.748s
sys 0m0.037s

复制代码

5 9 3 4 1 6 8 2 7
1 6 2 5 7 8 3 4 9
7 4 8 3 2 9 6 5 1
6 7 4 1 8 2 9 3 5
8 5 9 6 4 3 7 1 2
2 3 1 9 5 7 4 8 6
4 1 7 8 6 5 2 9 3
3 2 5 7 9 4 1 6 8
9 8 6 2 3 1 5 7 4
runtime = 86.137 ms
real 0m0.232s
user 0m0.224s
sys 0m0.033s

复制代码

sudo.js

const ERROR = 1022; // 0b1111111110
const OK = 0;
const BEST = 1;
const MIN = 10;
const int = Math.floor;
let Verti = [];
let Horiz = [];
let Bloke = [];
let Hover = [];
let Maybe = [];
let Gimme = [];
let Dit;
let Dat;
let sudo3 = [
[8, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 6, 0, 0, 0, 0, 0],
[0, 7, 0, 0, 9, 0, 2, 0, 0],
[0, 5, 0, 0, 0, 7, 0, 0, 0],
[0, 0, 0, 0, 4, 5, 7, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 3, 0],
[0, 0, 1, 0, 0, 0, 0, 6, 8],
[0, 0, 8, 5, 0, 0, 0, 1, 0],
[0, 9, 0, 0, 0, 0, 4, 0, 0],
];
let sudo9 = [
[0, 0, 0, 0, 0, 0, 8, 0, 0],
[0, 0, 2, 0, 7, 0, 0, 4, 0],
[0, 0, 0, 3, 0, 0, 6, 0, 1],
[6, 0, 0, 1, 0, 0, 0, 0, 5],
[0, 0, 9, 0, 4, 0, 0, 0, 0],
[0, 0, 0, 0, 5, 7, 0, 0, 0],
[0, 0, 7, 0, 0, 5, 0, 9, 0],
[3, 0, 0, 0, 0, 0, 1, 0, 8],
[0, 8, 0, 0, 0, 0, 0, 0, 0],
];
init ();
play (sudo9);
/* ____________________SUB____________________ */
function init (){
for (let i = 0; i < 9; i++) {
let i3 = 3 * int (i / 3);
Hover[i] = [];
for (let j = 0; j < 9; j++)
Hover[i][j] = int (j / 3) + i3;
}
for (let n = 0; n < ERROR; n += 2) {
Maybe[n] = [];
for (let i = 1; i <= 9; i++) {
if (n & 1 << i) continue;
Maybe[n].push (i);
}
}
}
function play (sudoku){
for (let i = 0; i < 9; i++)
Horiz[i] = Verti[i] = Bloke[i] = 0;
Gimme = [];
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
let k = Hover[i][j];
if (!sudoku[i][j]) {
Gimme.push ([i, j, k]);
continue;
}
Horiz[i] |= 1 << sudoku[i][j];
Verti[j] |= 1 << sudoku[i][j];
Bloke[k] |= 1 << sudoku[i][j];
}
}
Dat = Gimme.length;
Dit = 0;
// FOR Gimme[Dit - 1] is undefined
Gimme.push ([0, 0, 0])
explore (sudoku);
} /* play */
function explore (sudoku) {
if (Dit > Dat) return;
let This = best ();
if (This == ERROR) return;
if (This == OK) echo (sudoku);
let maybe = Maybe[This];
let [h, v, b] = Gimme[Dit - 1];
for (let it = 0; it < maybe.length; it++) {
let n = 1 << maybe[it];
sudoku[h][v] = maybe[it];
Horiz[h] |= n;
Verti[v] |= n;
Bloke[b] |= n;
explore (sudoku);
Horiz[h] ^= n;
Verti[v] ^= n;
Bloke[b] ^= n;
}
sudoku[h][v] = 0;
Dit--;
} /* explore */
function best (){
let min = MIN;
let best = OK;
let posi = Dit;
for (let it = Dit; it < Dat; it++) {
let [h, v, b] = Gimme[it];
let that = Horiz[h] | Verti[v] | Bloke[b];
if (that == ERROR) return ERROR;
let maybe = Maybe[that].length;
if (min > maybe) {
posi = it;
best = that;
if (maybe == BEST) break;
min = maybe;
}
}
let w = Gimme[posi];
Gimme[posi] = Gimme[Dit];
Gimme[Dit] = w;
Dit++;
return best;
} /* best */
function echo (sudoku){
for (let i = 0; i < 9; i++) {
if (!(i % 3)) print ();
for (let j = 0; j < 9; j++) {
if (!(j % 3)) putstr (' ');
putstr (sudoku[i][j]), putstr (' ');
}
print ();
}
}

复制代码

js zhenshi kuai,

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

time js -m -b sudo.js

5 9 3 4 1 6 8 2 7
1 6 2 5 7 8 3 4 9
7 4 8 3 2 9 6 5 1
6 7 4 1 8 2 9 3 5
8 5 9 6 4 3 7 1 2
2 3 1 9 5 7 4 8 6
4 1 7 8 6 5 2 9 3
3 2 5 7 9 4 1 6 8
9 8 6 2 3 1 5 7 4
runtime = 71.417 ms
real 0m0.092s
user 0m0.076s
sys 0m0.013s

复制代码

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

论坛徽章:: 12

13楼 [报告]

发表于 2017-09-22 08:52 |只看该作者

本帖最后由 523066680 于 2017-09-22 10:54 编辑

回复 12# rubyish

这个 Dancing Links JS 实现是挺快，我用 nodejs 运行的。但是有缺点，遇到以下题目会崩溃：

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...',

复制代码

如果测试 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 节点。

=info
Perl - Dancing Links
523066680 2017-09
=cut
use IO::Handle;
use Data::Dumper;
use Time::HiRes qw/time/;
STDOUT->autoflush(1);
my $time_a = time();
my $mat = [
[0,0,1,0,1,1,0],
[1,0,0,1,0,0,1],
[0,1,1,0,0,1,0],
[1,0,0,1,0,0,0],
[0,1,0,0,0,0,1],
[0,0,0,1,1,0,1]
];
my $links;
my $left;
my $right;
my $ubound = $#{$mat->[0]};
my $len = $ubound+1;
my $head;
my $C = [];
grep { $C->[$_] = {} } ( 0 .. $len );
for my $col ( 0 .. $len )
{
$left = $col == 0 ? $len : $col-1;
$right = $col == $len ? 0 : $col+1;
$C->[$col]{left} = $C->[$left];
$C->[$col]{right} = $C->[$right];
$C->[$col]{up} = $C->[$col];
$C->[$col]{down} = $C->[$col];
$C->[$col]{col} = $col; #temp
}
$head = $C->[0];
my $E = [{}]; #$E->[0] 占位
push_element( $E, \@{$mat->[0]}, 1 );
grep { push_element( $E, \@{$mat->[$_]}, $_ + 1 ) } ( 1 .. $#$mat );
print_links($head);
my @result;
dance($head, \@result, 0);
print "Result: ", join(",", @result);
printf "\n%.5fs\n", time()-$time_a;
sub dance
{
my ($head, $arr, $lv) = @_;
if ( $head->{right} == $head )
{
print join(",", @$arr);
return 1;
}
my $c = $head->{right};
my $r = $c->{down};
my $ele;
while ( $r != $c )
{
$ele = $r;
do {
remove_col( $ele->{col} );
$ele = $ele->{right};
}
until ( $ele == $r );
if ( dance($head, $arr, $lv+1) == 1)
{
$arr->[$lv] = $r->{row};
return 1;
}
do {
resume_col( $ele->{col} );
$ele = $ele->{right};
}
until ( $ele == $r );
$r = $r->{down};
}
}
sub remove_col
{
my ( $sel ) = @_;
$sel->{left}{right} = $sel->{right};
$sel->{right}{left} = $sel->{left};
my $vt = $sel->{down};
my $hz;
for ( ; $vt != $sel; $vt = $vt->{down})
{
$hz = $vt->{right};
for ( ; $hz != $vt; $hz = $hz->{right})
{
$hz->{up}{down} = $hz->{down};
$hz->{down}{up} = $hz->{up};
}
}
}
sub resume_col
{
my ( $sel ) = @_;
$sel->{left}{right} = $sel;
$sel->{right}{left} = $sel;
my $vt = $sel->{up};
my $hz;
for ( ; $vt != $sel; $vt = $vt->{up})
{
$hz = $vt->{right};
for ( ; $hz != $vt; $hz = $hz->{right})
{
$hz->{up}{down} = $hz;
$hz->{down}{up} = $hz;
}
}
}
sub push_element
{
my ($E, $ele, $row) = @_;
my $first = $#$E+1;
my $last;
for my $i ( 1 .. $len )
{
if ( $ele->[$i-1] == 1 )
{
push @$E,
{
val => $#$E+1,
row => $row,
col => $C->[$i],
up => $C->[$i]{up},
down => $C->[$i]
};
$C->[$i]{down} = $E->[$#$E] if ( $C->[$i]{down} == $C->[$i] );
$C->[$i]{up}{down} = $E->[$#$E];
$C->[$i]{up} = $E->[$#$E];
}
}
$last = $#$E;
my ($left, $right);
for my $i ( $first .. $last )
{
$left = ($i == $first) ? $last : $i-1;
$right = ($i == $last) ? $first: $i+1;
$E->[$i]{left} = $E->[$left];
$E->[$i]{right} = $E->[$right];
}
}
sub print_links
{
my $head = shift;
my $tmat = [];
grep { push @$tmat, [map { " " } ( 0..$len )] } ( 0 .. $#$mat+1 );
my $vt;
my $hz;
my $c = $head->{right};
for ( ; $c != $head; $c = $c->{right} )
{
$tmat->[0][$c->{col}] = " C".$c->{col};
$vt = $c->{down};
for ( ; $vt != $c; $vt = $vt->{down} )
{
$tmat->[$vt->{row}][$c->{col}] = sprintf "%3d", $vt->{val};
}
}
for my $e ( @$tmat )
{
print join("", @$e),"\n";
}
print "\n";
}

复制代码

C1 C2 C3 C4 C5 C6 C7
1 2 3
4 5 6
7 8 9
10 11
12 13
14 15 16
Result: 4,5,1
0.00014s

复制代码

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

评分

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

查看全部评分

论坛徽章:: 7

14楼 [报告]

发表于 2017-09-23 04:20 |只看该作者

回复 9# 523066680

判断 1-9 每个数字的全局分布情况（可能性）。
比如1可能分布的情况有6种，测试每一种，把9个1全部填入数独，然后继续测试其他数字的分布。

Buneng lijie? Keyi suoming?

改成解数独程序的时候

You Code ma? 3Q ~~

论坛徽章:: 12

15楼 [报告]

发表于 2017-09-23 22:32 |只看该作者

回复 14# rubyish

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

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

=info
DLX 解数独方案，Perl 实现
523066680 2017-09
https://zhuanlan.zhihu.com/PerlExample
=cut
#use strict;
use warnings;
use IO::Handle;
use File::Slurp;
use Time::HiRes qw/time/;
STDOUT->autoflush(1);
my $file = "D:/sudoku_nd4.txt";
my $gamedata = eval read_file( $file ) or die "$!";
my @games = map { substr($gamedata->{$_}, 0, 81) } sort keys %$gamedata;
my $index = 0;
our $ele_id;
our @nodes;
grep { main( $games[$_], $_ ) } ( 0 .. $#games );
sub main
{
my ($game, $game_id) = @_;
my $C = [ map { {} } (0..324) ];
my $time_a = time();
my $mat;
my $max_line;
my @answer;
my $res;
$mat = [[]];
$ele_id = 1;
#字符串转矩阵
str_to_mat( $game, $mat );
#初始化列首节点
init_head_col( $C, 324 );
create_matrix_nodes( $mat, $C, \$max_line );
$res = dance( $C->[0] , \@answer, 0);
#将数据依次填入数独
#index 0 的元素是固定项
shift @answer;
grep { $mat->[$_->{row}][$_->{col}] = $_->{val} } @answer;
print_mat($mat);
printf "Game index: %d, result: %d, time used: %.5f\n", $game_id, $res, time() - $time_a;
#清理内存
clean_matrix_nodes($C);
}
sub create_matrix_nodes
{
my ($mat, $C, $main_row ) = @_;
my @elements;
$main_row = 1;
@elements = (0) x 324;
#已有的数字信息统一合并为一行
for my $r ( 0 .. 8 )
{
for my $c ( 0 .. 8 )
{
trans( $r, $c, $mat->[$r][$c], \@elements ) if ( $mat->[$r][$c] != 0 );
}
}
push_element( $C, \@elements, 324, $main_row, 0, 0, 0 );
my @possible;
for my $r ( 0 .. 8 )
{
for my $c ( 0 .. 8 )
{
if ( $mat->[$r][$c] == 0 )
{
@possible = get_possible_num( $mat, $r, $c );
die "Wrong" if ($#possible < 0);
for my $e ( @possible )
{
$main_row++;
@elements = (0) x 324;
trans( $r, $c, $e, \@elements );
push_element( $C, \@elements, 324, $main_row, $r, $c, $e );
}
}
}
}
}
sub clean_matrix_nodes
{
my ( $C ) = @_;
grep { %$_ = () } @nodes;
grep { %$_ = () } @$C;
[url=home.php?mod=space&uid=29550557]@Nodes[/url] = ();
@$C = ();
}
# ============================================================
# Dancing Links
# ============================================================
sub dance
{
my ($head, $answer, $lv) = @_;
return 1 if ( $head->{right} == $head );
my $c = $head->{right};
my $min = $c;
#get minimal column node
while ( $c != $head )
{
if ( $c->{count} < $min->{count} ) { $min = $c; }
$c = $c->{right};
}
$c = $min;
return 0 if ( $c->{count} <= 0 );
my $r = $c->{down};
my $ele;
my @count_array;
my $res = 0;
remove_col( $c );
while ( $r != $c )
{
$ele = $r->{right};
while ( $ele != $r )
{
remove_col( $ele->{top} );
$ele = $ele->{right}
}
$res = dance($head, $answer, $lv+1);
if ( $res == 1)
{
$answer->[$lv] = $r;
return 1;
}
$ele = $r->{left};
while ( $ele != $r )
{
resume_col( $ele->{top} );
$ele = $ele->{left}
}
$r = $r->{down};
}
resume_col( $c );
return $res;
}
sub remove_col
{
my ( $sel ) = @_;
$sel->{left}{right} = $sel->{right};
$sel->{right}{left} = $sel->{left};
my $vt = $sel->{down};
my $hz;
for ( ; $vt != $sel; $vt = $vt->{down} )
{
$hz = $vt->{right};
for ( ; $hz != $vt; $hz = $hz->{right})
{
$hz->{up}{down} = $hz->{down};
$hz->{down}{up} = $hz->{up};
$hz->{top}{count} --;
}
$hz->{top}{count} --;
}
}
sub resume_col
{
my ( $sel ) = @_;
$sel->{left}{right} = $sel;
$sel->{right}{left} = $sel;
my $vt = $sel->{down};
my $hz;
for ( ; $vt != $sel; $vt = $vt->{down})
{
$hz = $vt->{right};
for ( ; $hz != $vt; $hz = $hz->{right})
{
$hz->{up}{down} = $hz;
$hz->{down}{up} = $hz;
$hz->{top}{count} ++;
}
$hz->{top}{count} ++;
}
}
sub print_nodes
{
my ($head, $rows) = @_;
my $buff = [[]];
my $c = $head->{right};
my $ele;
grep { $buff->[$_] = [(" ") x 324] } ( 0 .. $rows+1 ); #加一行统计
for ( ; $c != $head; $c = $c->{right} )
{
$buff->[0][$c->{col}-1] = sprintf("%3d ", $c->{col} );
$buff->[1][$c->{col}-1] = sprintf("%3d ", $c->{count} );
}
$c = $head->{right};
for (; $c != $head; $c = $c->{right} )
{
$ele = $c->{down};
for ( ; $ele != $c; $ele = $ele->{down} )
{
$buff->[$ele->{row}+1][$ele->{col}-1] = sprintf("%3d ", $ele->{val} );
}
}
grep { print join("", @{$buff->[$_]} ),"\n"; } ( 0 .. $rows );
print "\n";
}
# ============================================================
# Create Node Matrix
# ============================================================
sub init_head_col
{
my ($C, $len) = @_;
my ($left, $right);
for my $col ( 0 .. $len )
{
$left = $col == 0 ? $len : $col-1;
$right = $col == $len ? 0 : $col+1;
$C->[$col]{val} = 0;
$C->[$col]{row} = 0;
$C->[$col]{col} = $col;
$C->[$col]{count} = 0;
$C->[$col]{left} = $C->[$left];
$C->[$col]{right} = $C->[$right];
$C->[$col]{up} = $C->[$col];
$C->[$col]{down} = $C->[$col];
$C->[$col]{top} = $C->[$col];
}
}
sub push_element
{
my ($C, $eles, $cols, $DL_row, $matr, $matc, $n ) = @_;
our $ele_id;
my $first;
my $ele;
my $ref;
my $prev = undef;
my $col;
for ( my $i = 0; $i < $cols; $i++ )
{
$col = $i+1;
if ( $eles->[$i] == 1 )
{
$ele = {
val => $n,
col => $matc,
row => $matr,
count => undef,
left => undef,
right => undef,
up => $C->[$col]{up},
down => $C->[$col],
top => $C->[$col]
};
$nodes[ $ele_id-1 ] = $ele;
if ( $C->[$col]{down} == $C->[$col] )
{
$C->[$col]{down} = $ele;
}
$C->[$col]{up}{down} = $ele;
$C->[$col]{up} = $ele;
$C->[$col]{count}++;
if ( defined $prev )
{
$prev->{right} = $ele;
$ele->{left} = $prev;
}
else
{
$first = $ele;
}
$prev = $ele;
$ele_id ++;
}
$first->{left} = $ele;
$ele->{right} = $first;
}
}
sub trans
{
my ($r, $c, $n, $ref) = @_;
my $block;
my ($A, $B, $C, $D);
$block = int($r/3)*3 + int($c/3);
$A = $r * 9 + $c;
$B = $r * 9 + $n + 80;
$C = $c * 9 + $n + 161;
$D = $block * 9 + $n + 242;
$ref->[$A] = 1;
$ref->[$B] = 1;
$ref->[$C] = 1;
$ref->[$D] = 1;
}
# ============================================================
# Sudoku
# ============================================================
SUDOKU:
{
sub get_possible_num
{
my ($mat, $row, $col) = @_;
my @possible = (0,1,2,3,4,5,6,7,8,9);
my $blkr = int($row/3);
my $blkc = int($col/3);
my ($rr, $cc);
for my $n ( 0 .. 8 )
{
$rr = $blkr*3+int($n/3);
$cc = $blkc*3+ $n % 3;
$possible[ $mat->[$n][$col] ] = 0;
$possible[ $mat->[$row][$n] ] = 0;
$possible[ $mat->[$rr][$cc] ] = 0;
}
return grep { $_ } @possible;
}
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 );
}
}

复制代码

评分

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

查看全部评分

论坛徽章:: 12

16楼 [报告]

发表于 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

17楼 [报告]

发表于 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

18楼 [报告]

发表于 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 ~~

论坛徽章:: 12

19楼 [报告]

发表于 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种不同数字。

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