#!/usr/bin/perl -w

use strict;
use Time::HiRes 'time';

# Wenn kein Argument uebergeben wurde.
unless (@ARGV)
{
    print "USAGE: ", $0=~m{.*/(.*)}, " sudokofile\n";
    exit;
}

# Array das dass Sudoku Enthaelt.
our @su;

# Werte aus Datei in das Array @su kopieren
my ($x, $y) = qw/0 0/;
while (<>)
{
    next if /^\s*$/;
    $su[$x++][$y] = $1 while m/\G\s*(\S+)/gc;
    $x=0;
    $y++;
}

# Ruft die Rekursive Funktion auf, die das Sudoku loest
my $start = time();
my $end;
&try_num(0,0);
print "F&�r dieses Sudoku gibt es keine L&�sung.\n";



# Loese Sudoku
sub try_num
{
    my ($x, $y) = @_;

    # Wenn x == 9 dann naechste Zeile, erste Spalte
    if ( $x >= 9 )
    {
        $x=0;
        $y++;
        # Wenn Zeile 9 erreicht (es gibt nur 8) dann wurde Sudoku bearbeitet.
        if ( $y >= 9 )
        {
            &ausgabe;
            $end = time();
            printf "Die Zeit betrug %.4f Sekunden\n", $end - $start;
            exit;
        }
    }

    # Solange weiter gehen bis zum naechsten '-' Zeichen.
    until ( $su[$x][$y] eq '-' )
    {
        $x++;
        if ( $x >= 9 )
        {
            $x=0;
            $y++;
            if ( $y >= 9 )
            {
                &ausgabe;
                exit;
            }
        }
    }

    # Probiere an dieser Stelle die Werte 1..9 und prufe ob die Zahl gueltig ist.
    for my $w (1..9)
    {
        $su[$x][$y] = $w;
        if ( check_num($x, $y) )
        {
            try_num(++$x, $y);
            --$x;
        }
        else
        {
            next;
        }
    }
    $su[$x][$y] = '-';
    return 0;
}



# Ausgabe des Sudoku
sub ausgabe
{
    for my $y (0..8)
    {
        for my $x (0..8)
        {
            print $su[$x][$y], " ";
            print " " unless ($x+1) % 3;
        }
        print "\n";
        print "\n" unless ($y+1) % 3;
    }
}


# Zeile, Spalte, Block der uebergebenen Position Ueberprufen
sub check_num
{
    my ($x, $y) = @_;
    my %h = ();

    # Zeile ueberprufen
    for my $w ( 0..8 )
    {
        next      if  $su[$w][$y] eq '-';
        return 0  if  exists $h{$su[$w][$y]};

        $h{$su[$w][$y]} = 1;
    }
    %h = ();

    # Spalte ueberpruefen
    for my $w ( @{$su[$x]} )
    {
        next      if  $w eq '-';
        return 0  if  exists $h{$w};

        $h{$w} = 1;
    }
    %h = ();

    # Block ueberpruefen
    my (@bx, @by);
    @bx = $x<3 ? qw/0 1 2/ : $x<6 ? qw/3 4 5/ : qw/6 7 8/;
    @by = $y<3 ? qw/0 1 2/ : $y<6 ? qw/3 4 5/ : qw/6 7 8/;

    for my $x (@bx)
    {
        for my $y (@by)
        {
            next      if  $su[$x][$y] eq '-';
            return 0  if  exists $h{$su[$x][$y]};

            $h{$su[$x][$y]} = 1;
        }
    }
    %h = ();

    # Wert ist Okay.
    return 1;
}