#!/usr/bin/perl

# https://perlmonks.org/?node_id=1233341

use strict;
use warnings;

local $_ = do { local $/; <DATA> };
my $original = $_;
s/.\K  //g;                       # tweaks to make it easier to work with
my $width = /\n/ && $-[0];
s/.+/sprintf "%-${width}s", $&/ge;
my @squares;
my $g = qr/..{$width}/s;
my $letter = 'A';

while( /x| / )
  {
  my $pos = $-[0];
  my $found = $&;
  my ($x, $y) = ( $pos % ($width + 1), int $pos / ($width + 1) );
  for my $size ( reverse 1 .. $width - 1 )
    {
    my $sm1 = $size - 1;
    pos($_) = $pos;
    if( /\G(?=$found {$sm1})(?:$g(?= {$size})){$sm1}/ ) # try magic
      {
      push @squares, [ $x, $y, $size, $letter ];
      for my $n ( 1 .. $size )
        {
        substr $_, $pos, $size, $letter x $size;
        $pos += $width + 1;
        }
      $letter++;
      length $letter > 1 and chop $letter;
      last;
      }
    }
  }
use Data::Dump 'dd'; dd \@squares;
print $original;
print s/./$&  /gr =~ s/  $//gmr;

__DATA__
0  1  2  3  4  5  6  7  8  9  0  1  2
1
2                             x
3                    x
4        x
5  x
6              x
7                       x  x
8        x
9        x                 x
0        x
1     x                  x
2