#!/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();