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

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.

## 1 comment:

Nice! I did a very similar exercise in Java some years ago... https://github.com/jugglingcats/naturepuzzle. The bulk of the code is in Runner.java.

Post a Comment