Here's one that lets the regex engine find the largest square all by itself :)

#!/usr/bin/perl

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

use strict;
use warnings;

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

while( s/x| / / )
  {
  my $pos = $-[0];
  pos($_) = $pos;
  /\G( +)(??{ ('.{' . ($width + 1 - length $1) . "}$1") x ~-length $1}
+)/s
    or die "tricky regex failed - oops";
  my $size = $& =~ tr/\n// + 1;
  for my $n ( 1 .. $size )
    {
    substr $_, $pos, $size, ('A' .. 'Z')[@squares % 26] x $size;
    $pos += $width + 1;
    }
  push @squares, [ $pos % ($width + 1), int $pos / ($width + 1), $size
+ ];
  }

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
[download]

EDIT: removed leftover unneeded instructions.

Fun little problem (if I understand it correctly)

#!/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 w
+ith
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
[download]

Outputs:

[
  [1, 1, 3, "A"],
  [4, 1, 3, "B"],
  [7, 1, 2, "C"],
  [9, 1, 1, "D"],
  [10, 1, 1, "E"],
  [11, 1, 2, "F"],
  [9, 2, 1, "G"],
  [10, 2, 1, "H"],
  [7, 3, 4, "I"],
  [11, 3, 2, "J"],
  [1, 4, 1, "K"],
  [2, 4, 1, "L"],
  [3, 4, 2, "M"],
  [5, 4, 2, "N"],
  [1, 5, 2, "O"],
  [11, 5, 2, "P"],
  [3, 6, 2, "Q"],
  [5, 6, 2, "R"],
  [1, 7, 2, "S"],
  [7, 7, 1, "T"],
  [8, 7, 1, "U"],
  [9, 7, 2, "V"],
  [11, 7, 2, "W"],
  [3, 8, 1, "X"],
  [4, 8, 5, "Y"],
  [1, 9, 2, "Z"],
  [3, 9, 1, "A"],
  [9, 9, 2, "B"],
  [11, 9, 2, "C"],
  [3, 10, 1, "D"],
  [1, 11, 1, "E"],
  [2, 11, 2, "F"],
  [9, 11, 2, "G"],
  [11, 11, 2, "H"],
  [1, 12, 1, "I"],
]
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
0  1  2  3  4  5  6  7  8  9  0  1  2
1  A  A  A  B  B  B  C  C  D  E  F  F
2  A  A  A  B  B  B  C  C  G  H  F  F
3  A  A  A  B  B  B  I  I  I  I  J  J
4  K  L  M  M  N  N  I  I  I  I  J  J
5  O  O  M  M  N  N  I  I  I  I  P  P
6  O  O  Q  Q  R  R  I  I  I  I  P  P
7  S  S  Q  Q  R  R  T  U  V  V  W  W
8  S  S  X  Y  Y  Y  Y  Y  V  V  W  W
9  Z  Z  A  Y  Y  Y  Y  Y  B  B  C  C
0  Z  Z  D  Y  Y  Y  Y  Y  B  B  C  C
1  E  F  F  Y  Y  Y  Y  Y  G  G  H  H
2  I  F  F  Y  Y  Y  Y  Y  G  G  H  H
[download]

So what are the rules allowing squares to cover one (or more) x?

update

OK I misread that line 12 is empty, so a square is either empty or has an x in the upper left corner.

You are filling max squares first left to right and then up to down.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}

My guess was "only one x and it must be at the upper left corner".

Another version:

use strict;
use warnings;
my $grid = join('', <DATA>);
$grid =~ s/\n//g;
my $n = sqrt(length $grid);
my @sqs;
while( $grid =~ /(.*?)[.x]/ ) {
  my $sq = ('A'..'Z')[scalar(@sqs)%26];
  my $pos = length $1;
  substr( $grid, $pos, 1 ) = '.';
  my $i = 1;
  my $x = $pos%$n;
  my $y = int $pos/$n;
  $i++ while $x+$i < $n and $y+$i < $n and join( '', map { substr($gri
+d,$_*$n+$x,$i+1) } $y..$y+$i ) eq '.' x (($i+1)*($i+1));
  substr($grid,$_*$n+$x,$i) = $sq x $i for $y..$y+$i-1;
  push @sqs, [ $x+1, $y+1, $i, $sq ];
  $sq++;
}
print substr($grid,$n*$_,$n)."\n" for 0..$n-1;
print "@$_\n" for @sqs;
__DATA__
............
.........x..
......x.....
..x.........
x...........
....x.......
.......xx...
..x.........
..x.....x...
..x.........
.x.....x....
............
[download]

No!

Given space (x,y) and a bunch of points (x_i,y_j) starting from (1,1) partition the space into squared such that each square starts from (1,1) or (x_i,y_j) filling the space to (x_i+,y_j+1) (in ither words filling the space between it) and no square overlaps with any other. Example: if the (x_i,y_j) is at (3,4) than the area between (1,1) and (3,4) can be filled with square o=(1,1,3):

0  1  2  3   
1  o  o  o
2  o  o  o   
3  o  o  o   
4        x
[download]

and a=(1,4,1) b=(2,4,1) x = (3,4,1)

0  1  2  3   
1  o  o  o
2  o  o  o   
3  o  o  o   
4  a  b  x
[download]

so the result is :

(1,1,3)
(1,4,1)
(2,4,1)
(3,4,1)
[download]

and of course this repeats for all other points in the initial chart (marked with "X") until the entire area (12,12) is filled

You want to fill the gaps between your x points with disjoint squares?

> I need to know how many of these squares are in the space and all their coordinates (tuples). 

You are implying there is only one solution, that's wrong because you exclude overlaps.

Maybe you have an "optimal" solution in mind, but you didn't tell us the criteria.

Like

• smallest number of covering squares or
• always starting from the left upper corner going right then down

otherwise the solution is trivial, just take all "squares" with length 1.

Give us your solution for your OP maybe we can guess what you really want.

Smells like an XY problem to me.

Rectangles instead of squares would be much easier.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}

Example: if the (x_i,y_j) is at (3,4) than the area between (1,1) and (3,4) can be filled with square o=(1,1,3):

Why? You're saying s is the lenght of the square starting at 1,1. With length 3 the resulting corner would be 4,4. Not 3,4. Or in other words, there can't be a square between (1,1) and (3,4) since a squares' sides are of equal length.
(3,4) - (1,1) = (2,3) #NotASquare


holli

You can lead your users to water, but alas, you cannot drown them.

https://en.m.wikipedia.org/wiki/Polygon_covering

> the square covering problem is linear for hole-free polygons but NP-hard for general polygons

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}