#!/usr/bin/perl

# http://perlmonks.org/?node_id=1207373

use strict;
use warnings;

my $start = <<END;
GRBBB
GRBBW
ORBBW
OOOWW
OOOOW
END

my $gap = $start =~ /\n/ && $-[0] - 1;
my $egap = $gap + 2;

my @queue = $start;
while( @queue )
  {
  local $_ = shift @queue;
  /#.*#/ and next;                      # same row
  /#(?:.{$gap}..)*.{$gap}.#/s and next; # same column
  /#(.{$gap,$egap}|)#/s and next;       # adjacent trees
  if( /[A-Z]/ ) # pick a color
    {
    push @queue, "$`#$'" =~ s/$&/\l$&/gr while /$&/g;
    }
  else
    {
    print "$start\nwin with\n\n$_";
    exit;
    }
  }
die "failed to find solution\n";