数独的perl实现

Question:

有一个大方格，将其划分成3*3的9个中方格，将每个中方格划分成3*3的9个小方格(希望我表述明白了),也就是说，现在这个大方格里就有9*9个小方格了，初始的时候，这81个小方格里某一些被随机填上了1-9种任一个数字，另一些则空白，写一个程序，将空白的小方格填上数字(1-9任一数字)，要求大方格的每一行跟每一列不得有重复的数字，同时每一个中方格内不得有重复数字.

作为面试题如果要写出来没bug挺不容易。我写的过于啰嗦。

Answer:

要点：

1有点动态规划的意思。每个坐标都会有3种限制。1.行不重复 2列不重复 3块不重复。给定一个部分完成的方格，我们可以推算出指定坐标元素的可选值

2.递归进行。填入一个元素，然后坐标移到下一个。此时待填入的位置所有可能的选择可以根据1的描述给出，然后选一个填入。如此递归进行，每次移动坐标。如果到某位置是可选列表里没有元素，说明之前排列错误，直接放弃。如果到(8,8)点，填完，说明成功，直接退出。

 

my @pool = (1..9);

#There should be no duplicate element in line
sub RowRestrict{
    my $x = shift;
    my $y = shift;
    my @tm = @_;
    my @tpool;
    for(my $i = 0; $i < $x; $i++){
        push(@tpool, $tm[$y][$i]) if(defined($tm[$y][$i]));
    }
    return @tpool;
}

#there should be no duplicate elemment in column
sub ColumnRestrict{
    my $x = shift;
    my $y = shift;
    my @tm = @_;
    my @tpool;
    for(my $i = 0; $i< $y; $i++){
        push (@tpool, $tm[$i][$x]);
    }
    return @tpool;
}


#there should be no duplicate element in block
sub BlockRestrict{
    my $x = shift;
    my $y = shift;
    my @tm = @_;
    my @tpool;

    my $sx = (int($x/3))*3;
    my $sy = (int($y/3))*3;
    for my $ty ($sy..$sy+2){
        for my $tx ($sx..$sx+2){
            push(@tpool, $tm[$ty][$tx]) if(defined $tm[$ty][$tx]);
        }
    }
    return @tpool;
}

#generate next element position
sub Next{
    my ($x, $y) = @_;
    if($x<8){
        $x++;
    }
    else{
        $x = 0;
        $y ++;
    }
    return $x, $y;
}

#get possible choice of ($x, $y)
sub GetValidNum{
    my ($x, $y, @mtr) = @_;
    my @tpool;
    my @r = (RowRestrict($x,$y,@mtr),ColumnRestrict($x, $y, @mtr), BlockRestrict($x, $y, @mtr));
    for(@pool){
        if($_ ~~ @r){
            next;
        }
        else{
            push(@tpool, $_);
        }
    }
    return @tpool;
}

#output the result
sub Output{
    my @mtr = @_;
    for my $tx (0..8){
        for my $ty (0..8){
            print $mtr[$tx][$ty]."--";
        }
        print "\n";
    }
}

sub f{

    my ($x, $y, @mtr) = @_;
    if($x !=8 or $y != 8){
        ($x, $y) = Next($x, $y);

        my @tpool = GetValidNum($x, $y, @mtr);
        if(@tpool == 0){
            return;
        }
        for(@tpool){
            $mtr[$y][$x] = $_;
            f($x, $y, @mtr);
        }
    }
    else{
        print "Find !!\n";
        push(@allresult, \@mtr);
        Output(@mtr);
        #exit when found an anwser, if you want to get all anwser, remove it
        exit;

    }
}

my @metr;
#assign 0 to the (0,0). you can assign another value to it.
$metr[0][0] = 0;
f(0,0,@metr);