Brute forcing Crazy Game Puzzles

In the 1980s, as a kid I loved my Crazy Turtles Puzzle ("Das verrückte Schildkrötenspiel"). For a number of variations, see here or here.

I had completely forgotten about those, but a few days ago, I saw a self-made reincarnation when staying at a friends' house:

I tried a few minutes to solve it, unsuccessfully (in case it is not clear: you are supposed to arrange the nine tiles in a square such that they form color matching arrows wherever they meet).

So I took the picture above with the plan to either try a bit more at home or write a program to solve it. Yesterday, I had about an hour and did the latter. I am a bit proud of the implementation I came up with and in particular the fact that I essentially came up with a correct program: It came up with the unique solution the first time I executed it. So, here I share it:

#!/usr/bin/perl

# 1 rot 8
# 2 gelb 7
# 3 gruen 6
# 4 blau 5

@karten = (7151, 6754, 4382, 2835, 5216, 2615, 2348, 8253, 4786);

foreach $karte(0..8) {
  $farbe[$karte] = [split //,$karten[$karte]];
}
&ausprobieren(0);

sub ausprobieren {
  my $pos = shift;

  foreach my $karte(0..8) {
    next if $benutzt[$karte];
    $benutzt[$karte] = 1;
    foreach my $dreh(0..3) {
      if ($pos % 3) {
 # Nicht linke Spalte
 $suche = 9 - $farbe[$gelegt[$pos - 1]]->[(1 - $drehung[$gelegt[$pos - 1]]) % 4];
 next if $farbe[$karte]->[(3 - $dreh) % 4] != $suche;
      }
      if ($pos >= 3) {
 # Nicht oberste Zeile
 $suche = 9 - $farbe[$gelegt[$pos - 3]]->[(2 - $drehung[$gelegt[$pos - 3]]) % 4];
 next if $farbe[$karte]->[(4 - $dreh) % 4] != $suche;
      }

      $benutzt[$karte] = 1;
      $gelegt[$pos] = $karte;
      $drehung[$karte] = $dreh;
      #print @gelegt[0..$pos]," ",@drehung[0..$pos]," ", 9 - $farbe[$gelegt[$pos - 1]]->[(1 - $drehung[$gelegt[$pos - 1]]) % 4],"\n";
      
      if ($pos == 8) {
 print "Fertig!\n";
 for $l(0..8) {
   print "$gelegt[$l] $drehung[$gelegt[$l]]\n";
 }
      } else {
 &ausprobieren($pos + 1);
      }
    }
    $benutzt[$karte] = 0;
  }
}

Sorry for variable names in German, but the idea should be clear. Regarding the implementation: red, yellow, green and blue backs of arrows get numbers 1,2,3,4 respectively and pointy sides of arrows 8,7,6,5 (so matching combinations sum to 9).

It implements depth first tree search where tile positions (numbered 0 to 8) are tried left to write top to bottom. So tile $n$ shares a vertical edge with tile $n-1$ unless it's number is 0 mod 3 (leftist column) and it shares a horizontal edge with tile $n-3$ unless $n$ is less than 3, which means it is in the first row.

It tries rotating tiles by 0 to 3 times 90 degrees clock-wise, so finding which arrow to match with a neighboring tile can also be computed with mod 4 arithmetic.