本帖最后由 523066680 于 2017-09-11 22:02 编辑
回复 48# sunzhiguolu
生成数独,内容完全随机,来一个? 解数独也准备开搞
- =info
- 523066680
- 2017-09
- =cut
- use IO::Handle;
- STDOUT->autoflush(1);
- my $main = 0;
- my $bad = 0;
- AGAIN:
- our %hash;
- grep { $hash{$_} = 1 } (1..9);
- @nums = (1..9);
- our $mat =
- [
- #[ 1,2,3,4,5,6,7,8,9 ],
- [map { splice @nums, int(rand($#nums+1)), 1 } (1..9)],
- [],[],[],[],[],[],[],[]
- ];
- my $nextline;
- for my $line ( 1 .. 8 )
- {
- $nextline = undef;
- func( $line, 0, \$nextline );
- if ( not defined $nextline )
- {
- $bad++;
- print "not ok\n";
- }
- $mat->[$line] = [ split("", $nextline) ];
- }
- for my $idx ( 0..$#$mat )
- {
- printf "%s\n", join(",", @{$mat->[$idx]} );
- }
- print "\n";
- goto AGAIN if ($main++ < 1000);
- printf "bad: %d\n", $bad;
- sub func
- {
- our @all;
- our $mat;
- our %hash;
- my ( $curr, $lv, $ref ) = @_;
- if ($lv > 8)
- {
- #如果当前行是第五行或者第八行,预判下一行是否无解
- if ( $curr == 4 or $curr == 7)
- {
- if ( try_next_line( $curr ) == 0 )
- {
- return 0;
- }
- else
- {
- $ref = join("", @{$mat->[$curr]});
- return 1;
- }
- }
- else
- {
- $ref = join("", @{$mat->[$curr]});
- return 1;
- }
- }
- my @out;
- my %dupl;
- if ( $curr % 3 == 1 ) # 1 2 4 5 7 8
- {
- if ( $lv < 3 ) { @out = @{$mat->[$curr-1]}[0..2]; }
- elsif ( $lv < 6 ) { @out = @{$mat->[$curr-1]}[3..5]; }
- else { @out = @{$mat->[$curr-1]}[6..8]; }
- }
- elsif ( $curr % 3 == 2 )
- {
- if ( $lv < 3 ) { @out = (@{$mat->[$curr-1]}[0..2], @{$mat->[$curr-2]}[0..2]) }
- elsif ( $lv < 6 ) { @out = (@{$mat->[$curr-1]}[3..5], @{$mat->[$curr-2]}[3..5]) }
- else { @out = (@{$mat->[$curr-1]}[6..8], @{$mat->[$curr-2]}[6..8]) }
- }
- if ($curr >= 3)
- {
- push @out, map { $mat->[$_][$lv] } ( 0 .. 3*int($curr/3) - 1 );
- }
-
- push @out, @{$mat->[$curr]}[ 0 .. $lv-1 ];
- %dupl = %hash;
- grep { delete $dupl{$_} } @out;
- my $res = 0;
- for my $e ( keys %dupl )
- {
- $mat->[$curr][$lv] = $e;
- $res = func($curr, $lv+1, $ref);
- last if ($res == 1);
- }
- return $res;
- }
- sub try_next_line
- {
- my ($row) = shift;
- my $nextline = undef;
- func( $row+1, 0, \$nextline );
- if ( not defined $nextline )
- {
- return 0;
- }
- else
- {
- return 1;
- }
- }
复制代码- 1,5,8,2,3,9,6,4,7
- 2,7,3,1,6,4,8,5,9
- 4,6,9,5,8,7,2,3,1
- 3,2,7,6,1,5,4,9,8
- 9,4,1,8,7,3,5,6,2
- 5,8,6,9,4,2,7,1,3
- 6,9,5,3,2,8,1,7,4
- 7,1,2,4,9,6,3,8,5
- 8,3,4,7,5,1,9,2,6
- 6,7,4,8,2,1,9,3,5
- 9,3,8,5,4,7,6,1,2
- 1,2,5,3,6,9,7,4,8
- 3,6,1,7,9,5,2,8,4
- 4,5,7,1,8,2,3,6,9
- 2,8,9,4,3,6,1,5,7
- 7,4,2,6,1,8,5,9,3
- 5,1,3,9,7,4,8,2,6
- 8,9,6,2,5,3,4,7,1
- 4,1,5,3,7,8,9,6,2
- 7,9,6,5,4,2,1,3,8
- 3,8,2,9,1,6,4,5,7
- 9,2,3,8,5,4,6,7,1
- 6,5,4,7,9,1,8,2,3
- 1,7,8,6,2,3,5,9,4
- 2,3,1,4,6,9,7,8,5
- 8,6,7,1,3,5,2,4,9
- 5,4,9,2,8,7,3,1,6
- 4,5,9,6,8,7,2,1,3
- 6,2,7,4,1,3,9,5,8
- 1,3,8,2,9,5,4,6,7
- 3,7,2,1,5,4,8,9,6
- 9,6,4,7,2,8,1,3,5
- 5,8,1,3,6,9,7,4,2
- 2,1,3,8,4,6,5,7,9
- 7,4,5,9,3,2,6,8,1
- 8,9,6,5,7,1,3,2,4
- 9,6,5,7,4,8,1,3,2
- 1,2,4,5,3,9,8,6,7
- 3,7,8,2,6,1,9,5,4
- 2,4,6,9,1,3,5,7,8
- 7,1,9,6,8,5,4,2,3
- 8,5,3,4,2,7,6,1,9
- 5,8,2,1,7,4,3,9,6
- 4,9,7,3,5,6,2,8,1
- 6,3,1,8,9,2,7,4,5
- 5,1,8,2,9,7,3,6,4
- 2,7,6,4,5,3,9,1,8
- 9,3,4,6,1,8,5,2,7
- 4,8,9,1,2,6,7,5,3
- 1,6,3,9,7,5,8,4,2
- 7,2,5,3,8,4,6,9,1
- 8,5,1,7,4,9,2,3,6
- 3,4,7,5,6,2,1,8,9
- 6,9,2,8,3,1,4,7,5
- 3,2,7,1,9,8,6,4,5
- 5,4,1,2,7,6,9,8,3
- 6,8,9,4,3,5,7,2,1
- 1,5,2,8,4,7,3,9,6
- 4,9,8,6,1,3,2,5,7
- 7,3,6,9,5,2,8,1,4
- 8,6,4,3,2,1,5,7,9
- 2,1,5,7,6,9,4,3,8
- 9,7,3,5,8,4,1,6,2
- 1,4,7,9,5,2,6,8,3
- 2,9,5,6,3,8,1,7,4
- 3,6,8,4,1,7,2,5,9
- 8,2,4,3,6,9,5,1,7
- 6,3,1,2,7,5,4,9,8
- 5,7,9,1,8,4,3,2,6
- 4,1,2,7,9,3,8,6,5
- 9,5,3,8,2,6,7,4,1
- 7,8,6,5,4,1,9,3,2
- 1,8,2,4,9,7,5,3,6
- 6,4,9,2,3,5,7,8,1
- 3,7,5,1,6,8,2,9,4
- 9,6,3,7,1,4,8,5,2
- 4,5,1,8,2,9,3,6,7
- 7,2,8,3,5,6,1,4,9
- 8,1,6,5,4,2,9,7,3
- 5,3,4,9,7,1,6,2,8
- 2,9,7,6,8,3,4,1,5
- 5,8,7,1,9,6,2,4,3
- 1,3,4,2,7,5,8,9,6
- 9,6,2,8,3,4,1,5,7
- 3,1,6,4,5,2,9,7,8
- 2,9,8,7,1,3,4,6,5
- 7,4,5,6,8,9,3,1,2
- 8,5,9,3,4,7,6,2,1
- 4,2,1,5,6,8,7,3,9
- 6,7,3,9,2,1,5,8,4
复制代码
|