use warnings; use strict;
#use Data::Dump::Streamer;

our $N = int($ARGV[0]) || 5;

sub zip { 
    my($v,$x,$y,@z) = @_; @$x == @$y or die "length error in zip"; 
    [map { &$v($$x[$_], $$y[$_], @z) } 0 .. @$x-1];
}

sub show {
    my($a) = @_;
    "[" . join(",", map { "[" . join(",", @$_) . "]" } @$a) . "]\n";
}
sub show1 {
    my($p) = @_;
    my @o = (" " . "."x$N . "\n") x $N;
    for my $i (0 .. @$p-1) {
        my $c = $$p[$i];
        substr($o[$$c[0]], 1 + $$c[1], 1) = chr(ord("A") + $i);
    }
    print @o;
}

sub add {
    my($m, $p) = @_;
    zip sub { 
        my($m1, $p1) = @_; zip sub { my($m2, $p2) = @_; $m2 + $p2 }, $
+m1, $p1 
    }, $m, $p;
}
sub check {
    my($p) = @_;
    my %h;
    for my $c (@$p) {
        0 <= $_ && $_ < $N or return for @$c;
        $h{join(",",@$c)}++ and return;
    }
    1;
}
sub kick {
    my($m, $p) = @_;
    while (1) {
        my $q = add($m, $p);
        check($q) or last;
        $p = $q;
    }
    $p;
}
my $state0 = [[0,0],[0,$N-1],[$N-1,$N-1]];
my @move = 
    map { my $m = $_;
        map { my @t = map { [0,0] } 0 .. 2; $t[$_] = $m; [@t] } 0 .. 2
    } [0,1],[1,0],[0,-1],[-1,0];
sub kickall {
    my($p) = @_;
    map { kick $_, $p } @move;
}
sub goal {
    my($p) = @_;
    grep { 
        int(($N-1)/2) <= $$_[0] && $$_[0] <= int($N/2) && int(($N-1)/2
+) <= $$_[1] && $$_[1] <= int($N/2)
    } @$p;
}

my @poss = [$state0, undef, 0];
my %found = (show($state0), 1);
SEARCH: {
for (my $k = 0; $k < @poss; $k++) {
    my($state, $_prev, $depth) = @{$poss[$k]};
    for my $next (kickall $state) {
        $found{show($next)}++ and next;
        #print "(" . (1 + $depth) . " " . (0+@poss) . ") " . show $nex
+t;
        push @poss, [$next, $k, 1 + $depth];
        if (0 == @poss % 2000) { warn "(" . (1 + $depth) . " " . (0+@p
+oss) . ")\n"; }
        goal($next) and last SEARCH;
    }
}
print "no solution found for N = $N (number of states is " . (0+@poss)
+ . ", max depth is " . ${$poss[-1]}[2] . ").\n\n";
exit 1;
}

print "solution for N = $N:\n";
my $k = @poss - 1;
while (defined($k)) {
    my($state, $prev, $depth) = @{$poss[$k]};
    print $depth . " " . $k . ":\n";
    show1 $state;
    $k = $prev;
}
print "\n";

__END__
[download]