(2n+1)阶幻方

题目：

输出(2n+1)幻方的所有可能的排列

 

目前效率还很低。 5阶就要算好久。算法有些问题，成了枚举所有可能性了

 

my $size = 3;
my @pool = (1..$size*$size);
my @lines;
my @rows;


my $sum = $size*($size*$size +1)/2;

sub OutputSquare{
    for(@_){
        print "@{$_} \n";
    }
    print "\nxxxxxxxxxxxxxxxxxxxxxxxxxxx\n";
}

sub IsDuplicate{
    my ($reffset, $refeset) = @_;
    my @fset = @{$reffset};
    my @eset = @{$refeset};
    my $key = $eset[($size-1)/2];
    for(@fset){
        my @tmp = @{$_};
        if($tmp[($size -1)/2] eq $key){
            return 1;
        }
    }
    return 0;
}


sub BuildLine{
    my ($refline, $fresult,@pool) = @_;
    my @line = @{$refline};

    if(@line <$size){
        my $i = @line;
        for my $sv (@pool){
            my @linecopy = @line;
            $linecopy[$i] = $sv;
            BuildLine(\@linecopy, $fresult, grep {$_ ne $sv} @pool);
        }
    }
    else{
        if(IsValidRow(@{$refline})){
            push(@{$fresult}, $refline);
        }
    }
}

sub BuildSquare{
    my ($refrows, $fresult, @pool) =@_;
    my @rows = @{$refrows};

    if(@rows < $size){
        my $i = @rows;
        for my $sv( @pool){
            my @rowscopy = @rows;
            $rowscopy[$i] = $sv;
            @copypool = GetLeftRows(\@pool,\@rowscopy);
            BuildSquare(\@rowscopy, $fresult,@copypool);
        }
    }
    else{
        if(IsValidSquare(@$refrows)){
            push (@{$fresult} , $refrows);
        }
    }


}
sub IsValidSquare{
    my @rows = @_;
    my @sum;

    for $r (0..$size-1){
        my @row = @{$rows[$r]};
        for $c (0..$size-1){
            $sum[$c]+=$row[$c];
        }
        $sum[$size]+=$row[$r];
        $sum[$size+1]+=$row[$size - $r -1];
    }
#    print "checking: @sum \n";

    return 0 if( grep {$_ ne $sum} @sum);
    return 1;

}

sub IsValidRow{
    my @data = @_;
    my $tsum = 0;
    for(@data){
        $tsum += $_;
    }
    $tsum == $sum ? 1:0;
}

sub GetLeftRows{
    my ($refAllrow, $refrows) = @_;
    my @rows = @$refrows;
    my @allrow = @$refAllrow;
    my @tmppool = @pool;
    for my $row (@rows){
        for my $cell (@$row){
            @tmppool = grep {$_ ne $cell} @tmppool;
        }
    }
    my @result;
    for my $pr (@allrow){

        my %hash;
        foreach (@$pr, @tmppool){
            $hash{$_}++;
        }
        if((keys(%hash) == @tmppool)){
            push(@result,$pr);
        }

    }
    my $count = @result;
    return @result;
}

sub Square{
    my (@lineset) = @_;
    my @fs = ();
    my $index = 0;
    for my $l(@lineset){
        $index++;
        my @set = ($l);
        my @tmplineset = @lineset;
        BuildSquare(\@set, \@fs, GetLeftRows(\@tmplineset, \@set));
    }

    return @fs;
}

for my $i (@pool){
    my @r = ($i);
    BuildLine(\@r, \@lines, grep{$_ ne $i} @pool);
}

my $pos = @lines;

#sleep 20;
my @final = Square(@lines);
foreach(@final){

    OutputSquare(@{$_});
    IsValidSquare(@{$_});

}