Fun little thing to write a solver for :)

#!/usr/bin/perl

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

use strict; # solver
use warnings;

$_ = <<END; # game 21
abbcc 
addde 
affge 
 hRgii
 hRjj 
      
END

my %seen;
my @queue = [$_];

while( @queue )
  {
  my @prev = shift(@queue)->@*;
  local $_ = $prev[-1];
  $seen{$_}++ and next;
  if( /^.*R/ )
    {
    my $moves = @prev - 1;
    my $count = 0;
    print "WINNER in $moves moves\n\n",
      map "\n        " . $count++ . "\n$_", @prev;
    exit;
    }
  while( / ((\w)\2+)/g ) { push @queue, [ @prev, "$`$1 $'" ]; }
  while( /((\w)\2+) /g ) { push @queue, [ @prev, "$` $1$'" ]; }
  $_ = transpose($_);
  while( / ((\w)\2+)/g ) { push @queue, [ @prev, transpose("$`$1 $'") 
+]; }
  while( /((\w)\2+) /g ) { push @queue, [ @prev, transpose("$` $1$'") 
+]; }
  }
print "Unsolvable\n";

sub transpose
  {
  local $_ = shift;
  my $answer = '';
  $answer .= "\n" while s/^./ $answer .= $&; ''/gem;
  return $answer;
  }
[download]