moved files to higher directory after split to new repositoryHEADtrunk

1 files changed, 173 insertions, 0 deletions

diff --git a/096.pl b/096.pl
new file mode 100644
index 0000000..2658358
--- /dev/null
+++ b/096.pl
@@ -0,0 +1,173 @@
+#!/usr/bin//perl
+
+use strict;
+use warnings;
+use List::Util qw(any);
+
+sub remove_numbers {
+    my $numbers = shift;
+    my $to_rem = shift;
+
+    foreach my $n (keys %$to_rem) {
+        delete $numbers->{$n};
+    }
+}
+
+sub numbers_in_row {
+    my $field = shift;
+    my $row = shift;
+    my $numbers = {};
+
+    for(my $i=0; $i<9; $i++) {
+        my $number = $field->[9*$row + $i];
+        $numbers->{$number} = 1 if $number;
+    }
+
+    return $numbers;
+}
+
+sub numbers_in_col {
+    my $field = shift;
+    my $col = shift;
+    my $numbers = {};
+
+    for(my $i=0; $i<9; $i++) {
+        my $number = $field->[9*$i + $col];
+        $numbers->{$number} = 1 if $number;
+    }
+
+    return $numbers;
+}
+
+sub numbers_in_block {
+    my $field = shift;
+    my $block = shift;
+    my $numbers = {};
+
+    my $blk_row = int($block / 3);
+    my $blk_col = $block % 3;
+
+    for(my $row=0; $row<3; $row++) {
+        for (my $col=0; $col<3; $col++) {
+            my $number = $field->[9*(3*$blk_row + $row) + (3*$blk_col + $col)];
+            $numbers->{$number} = 1 if $number;
+        }
+    }
+
+    return $numbers;
+}
+
+sub collect_numbers {
+    my $field = shift;
+
+    my $row_n = [];
+    my $col_n = [];
+    my $blk_n = [];
+
+    for(my $i=0; $i<9; $i++) {
+        $row_n->[$i] = numbers_in_row($field, $i);
+    }
+    for(my $i=0; $i<9; $i++) {
+        $col_n->[$i] = numbers_in_col($field, $i);
+    }
+    for(my $i=0; $i<9; $i++) {
+        $blk_n->[$i] = numbers_in_block($field, $i);
+    }
+
+    return ($row_n, $col_n, $blk_n);
+}
+
+sub print_field {
+    my $field = shift || return;
+
+    for(my $i=0; $i<9; $i++) {
+        for(my $j=0; $j<9; $j++) {
+            print $field->[9*$i + $j] . " ";
+        }
+        print "\n";
+    }
+    print "\n";
+}
+
+sub find_candidates {
+    my $field = shift;
+    my ($row_n, $col_n, $blk_n) = collect_numbers($field);
+
+restart:
+    my $candidates = {};
+    for(my $row=0; $row<9; $row++) {
+        for(my $col=0; $col<9; $col++) {
+            next if $field->[9*$row + $col];
+
+            my $blk = 3*int($row / 3) + int($col / 3);
+            my %numbers = map { $_ => 1 } 1..9;
+            remove_numbers(\%numbers, $row_n->[$row]);
+            remove_numbers(\%numbers, $col_n->[$col]);
+            remove_numbers(\%numbers, $blk_n->[$blk]);
+
+            if (scalar keys %numbers == 1) {
+                # there is only one possibility -> restart search with updated field
+                my $n = (keys %numbers)[0];
+                $field->[9*$row + $col] = $n;
+                $row_n->[$row]->{$n} = 1;
+                $col_n->[$col]->{$n} = 1;
+                $blk_n->[$blk]->{$n} = 1;
+                goto restart;
+            } elsif (scalar keys %numbers > 1) {
+                $candidates->{9*$row + $col} = [ sort keys %numbers ];
+            } else {
+                # no candidate possible on this position
+                return;
+            }
+        }
+    }
+    return $candidates;
+}
+
+sub solve {
+    my @field = @_;
+
+    my $candidates = find_candidates(\@field) || return;
+
+    if (scalar keys %$candidates == 0) {
+        return \@field;
+    }
+
+    my @field_copy = @field;
+
+    # iterate remaining positions with multiple possibilities
+    foreach my $pos (sort { scalar @{$candidates->{$a}} <=> scalar @{$candidates->{$b}} } keys %$candidates) {
+        @field = @field_copy;
+        foreach my $cand (@{$candidates->{$pos}}) {
+            @field[$pos] = $cand;
+            my $solved_field = solve(@field);
+            return $solved_field if $solved_field;
+        }
+        return;
+    }
+}
+
+sub main {
+    my $content;
+    open FILE, "<096.txt" or die "Can't open file: $!\n";
+    while(<FILE>) {
+        $content .= $_;
+    }
+    close FILE;
+
+    my @sudokus = split('\n?Grid [0-9]+\n', $content);
+    shift @sudokus;     # remove empty first element
+
+    my $sum = 0;
+
+    foreach my $sudoku (@sudokus) {
+        my @field = split("\n?", $sudoku);
+        my $solution = solve(@field);
+        $sum += 100*$solution->[0] + 10*$solution->[1] + 1*$solution->[2] . "\n";
+    }
+
+    print $sum . "\n";
+}
+
+main();
+