#!/usr/bin/perl

use strict;
use warnings;

my @letters=('A'..'Z');
for my $n(2..15){
  print "$n\n";
  my $a=2*$n;
  for my $x(2..sqrt $a){
    (my $y=$a/$x)=~/\./ and next;
    my %grid;
    my $max=$letters[$n-1];
    fill(\%grid,$x,$y,'A',$max);
  }
}

sub fill{
  my($grid,$X,$Y,$letter,$max)=@_;
  CHECK_X: for my $x(1..$X-1){
    my($holes_l,$holes_r);
    for my $y(1..$Y){
      my $l=$grid->{$x,$y};
      my $r=$grid->{$x+1,$y};
      if($l && $r){
        next CHECK_X if $l eq $r;
      }
      $holes_l+=!$l;
      $holes_r+=!$r;
    }
    return if !$holes_l || !$holes_r;
  }
  CHECK_Y: for my $y(1..$Y-1){
    my($holes_l,$holes_r);
    for my $x(1..$X){
      my $l=$grid->{$x,$y};
      my $r=$grid->{$x,$y+1};
      if($l && $r){
        next CHECK_Y if $l eq $r;
      }
      $holes_l+=!$l;
      $holes_r+=!$r;
    }
    return if !$holes_l || !$holes_r;
  }
      
  if($letter gt $max){
    print "Solution:\n";
    display($grid,$X,$Y);
    return;
  }
  ++(my $next=$letter);

  for my $x(1..$X){
    for my $y(1..$Y){
      next if $grid->{$x,$y};
      local $grid->{$x,$y}=$letter;
      if($x<$X && !$grid->{$x+1,$y}){
        local $grid->{$x+1,$y}=$letter;
	fill($grid,$X,$Y,$next,$max);
      }
      if($y<$Y && !$grid->{$x,$y+1}){
        local $grid->{$x,$y+1}=$letter;
	fill($grid,$X,$Y,$next,$max);
      }
      return;
    }
  }
}

sub display{
  my($grid,$X,$Y)=@_;

  for my $x(1..$X){
    print "   ";
    for my $y(1..$Y){
      print $grid->{$x,$y} || '-';
    }
    print "\n";
  }
  print "\n";
}