[Bielefeld-pm] Sudoku lösen in D

taulmarill at xgn.de taulmarill at xgn.de
Mi Apr 15 04:23:50 PDT 2009


Hallo,

hatte nach dem letzten Treffen ganz vergessen, dass ich ja noch was
schreiben wollte. Also, ich bin Momentan dabei, mir D anzuschauen und habe
mir zum lernen vorgenommen, mein Sudoku-Löseprogramm von Perl nach D zu
übersetzen. Hier erst mal die Perlversion:

----<sudoku.pl begin>----
my $fieldstring = $ARGV[0];
if ( ! $fieldstring or $fieldstring !~ /^[\d.]{81}$/ ) {
    die 'Fehlerhaftes Feld!';
}

my @block = (
    [ 1, 2 ], [ 0, 2 ], [ 0, 1 ],
    [ 4, 5 ], [ 3, 5 ], [ 3, 4 ],
    [ 7, 8 ], [ 6, 8 ], [ 6, 7 ],
);
my @fieldr = map{ [ split //, $_ ] } $fieldstring =~ /(.{9})/g;
print join(' ',@$_) . "\n" for @fieldr;
my @fieldc = map{ my $x = $_; [ map{ $fieldr[$_]->[$x] } 0 .. 8 ] } 0 .. 8;
my @empty = map{ @$_ } sort{ @$a <=> @$b } map{
    my $y = $_;
    [ map{ [ $_, $y ] }grep{ $fieldr[$y]->[$_] eq '.' } 0..8 ]
} 0..8;
my %candidates;
brute_force( @empty );

sub brute_force {
    unless ( @_ ) { print_solved(); return; }
    my( $x, $y ) = @{ shift() };
    @candidates{
        1,2,3,4,5,6,7,8,9,
        @{ $fieldr[$y] },
        @{ $fieldc[$x] },
        @{ $fieldr[$block[$y]->[0]] }[@{ $block[$x] }],
        @{ $fieldr[$block[$y]->[1]] }[@{ $block[$x] }],
    } = (1,1,1,1,1,1,1,1,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0,);
    for ( grep{ $candidates{$_} } keys %candidates ) {
        $fieldc[$x]->[$y] = $fieldr[$y]->[$x] = $_;
        brute_force( @_ );
    }
    $fieldc[$x]->[$y] = $fieldr[$y]->[$x] = '.';
}

sub print_solved {
    print "\n";
    print join( ' ', @$_ ) . "\n" for @fieldr;
    print "\n";
}
----<sudoku.pl end>----

Zur Erinnerung: das Script erwartet als erstes Argument ein Sudoku in Form
eine 81 Zeichen langen Strings. Zum testen nehme ich bei mir folgendes:

...........9.6.3...7.3.4.9...72.86...4.....7...21.65...1.9.5.4...8.2.7...........

Mit meiner D-Version bin ich zwar noch nicht fertig (vermisse doch einigen
Komfort von Perl) aber hier ist was ich bis jetzt habe:

----<sudoku.d begin>----
import std.stdio;

void main( char[][] args ) {
    if ( (args.length != 2) || (args[1].length != 81) ) {
        writefln( "Fehlerhaftes Feld!" );
        return 0;
    }
    int[][] block = [
        [ 1, 2 ], [ 0, 2 ], [ 0, 1 ],
        [ 4, 5 ], [ 3, 5 ], [ 3, 4 ],
        [ 7, 8 ], [ 6, 8 ], [ 6, 7 ],
    ];
    char[9][9] fieldr, fieldc;
    int[2][] empty;
    for (int x = 0; x <= 8; x++ ) {
        fieldr[x][0..9] = args[1][x*9..x*9+9];
        for (int y = 0; y <= 8; y++) {
            fieldc[y][x] = fieldr[x][y];
            if ( fieldr[x][y] == '.' ) {
                empty ~= [x,y];
            }
        }
    }
    print_field( fieldr );
}

void print_field ( char[9][9] field ) {
    foreach ( row; field ) {
        foreach ( square; row ) {
            writef( "%s ", square );
        }
        writefln();
    }
}
----<sudoku.d end>----

Zur Zeit frage ich mich ein bisschen, wie ich das Array empty möglicht
einfach sortieren kann. So was wie Perls sort habe ich nicht finden
können.


Gruß,
Jürgen



Mehr Informationen über die Mailingliste Bielefeld-pm