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

5 3 -  - 7 -  - - -
6 - -  1 9 5  - - -
- 9 8  - - -  - 6 -

8 - -  - 6 -  - - 3
4 - -  8 - 3  - - 1
7 - -  - 2 -  - - 6

- 6 -  - - -  2 8 -
- - -  4 1 -  - - 5
- - -  - - -  - 7 -

5 3 4  6 7 8  9 1 2
6 7 2  1 9 5  3 4 8
1 9 8  3 4 2  5 6 7

8 5 9  7 6 1  4 2 3
4 2 6  8 5 3  7 9 1
7 1 3  9 2 4  8 5 6

9 6 1  5 3 7  2 8 4
2 8 7  4 1 9  6 3 5
3 4 5  2 8 6  1 7 9

Die Zeit betrug 1.5638 Sekunden