Lösung des Hundepuzzles

Es mag bei den nur neun Karten des Hundepuzzles auf den ersten Blick erstaunen, doch tatsächlich gibt es mehr als 95,1 Milliarden Möglichkeiten, um die Karten im 3×3-Quadrat auszulegen.¹ Allerdings unterscheidet sich jede dieser Konfigurationen von drei anderen allein durch Drehung des ganzen Ergebnisses, sodass man auch von „nur“ 23,8 Milliarden unterschiedlichen Konfigurationen sprechen kann.

Zwar muss ein Mensch, der „das verflixte Hunde-Spiel“ zu lösen versucht, bei weitem nicht stumpf alle 23,8 Milliarden Möglichkeiten durchprobieren. Dennoch liegt mir der Ansatz des langwierigen Probierens mit viel Geduld in so einem Fall wenig. Ich besitze auch nicht das Glück, von meinem Gehirn nach Anschauen der Karten des Puzzles die fertige Lösung ins Bewusstsein geschickt zu bekommen.

Namen für die Hündinnen, von links nach rechts: **Eclipse**, **Trinity**, **Muffins** und **Bipolar**.

Ich entschloss mich, das Problem auf dem Programmierweg anzugehen – der PHP-Quelltext meiner rekursiven Lösung findet sich unten. Die Karten nummerierte ich durch, gab den Hündinnen Namen und übertrug so die Pappbilder in die virtuelle Welt. Im Programm wird dieser Kartenvorrat anfangs im Feld $queue gehalten.

Die Karten werden dann von $queue entnommen und von links nach rechts und Zeile für Zeile in allen möglichen Varianten ausgelegt (ins Feld $board übertragen) und rotiert, solange sie mit den zuvor ausgelegten Karten zusammenpassen. Konnten alle Karten aus $queue passend in $board abgelegt werden, wird das Ergebnis als Lösung ausgegeben.

Quelltext

<!doctype html>
<meta charset='UTF-8'>
<meta content='Martin Janecke' name='author'>
<title>recursive dog puzzle solution</title>
<?php

// This piece of software may be shared and remixed under the terms of
// the Creative Commons Attribution 3.0 license.
// See http://creativecommons.org/licenses/by/3.0/ for more information.

// define dog names

    define ('ECLIPSE', 1); // the black dog
    define ('TRINITY', 2); // the tricolored dog
    define ('MUFFINS', 3); // the black-and-brown dog
    define ('BIPOLAR', 4); // the black-and-white dog

// define a card class

    class card {

        // the card's north, east, south and west edge
        public $N, $E, $S, $W;
        // the card's identifier
        public $identifier;
        // the number (0 to 3) of clockwise 90° rotations of the card
        public $orientation;
        
        public function __construct ($identifier, $N, $E, $S, $W) {
            $this->identifier = $identifier;
            $this->N = $N;
            $this->E = $E;
            $this->S = $S;
            $this->W = $W;
            $this->orientation = 0;
        } // public function __construct
        
        // rotates the card 90° clockwise once 
        public function rotate () {
            $this->orientation = ($this->orientation + 1) & 3;
            $W = $this->W;
            $this->W = $this->S;
            $this->S = $this->E;
            $this->E = $this->N;
            $this->N = $W;
        } // public function rotate

    } // class card

// define the cards by the dogs they show; clockwise: face, -tail, -tail, face

    $queue = array (
        new card (0, ECLIPSE, -TRINITY, -BIPOLAR, TRINITY),    
        new card (1, MUFFINS, -BIPOLAR, -TRINITY, TRINITY),
        new card (2, ECLIPSE, -MUFFINS, -BIPOLAR, TRINITY),
        new card (3, ECLIPSE, -BIPOLAR, -ECLIPSE, MUFFINS),
        new card (4, BIPOLAR, -MUFFINS, -ECLIPSE, TRINITY),
        new card (5, TRINITY, -ECLIPSE, -BIPOLAR, MUFFINS),
        new card (6, TRINITY, -BIPOLAR, -TRINITY, MUFFINS),
        new card (7, BIPOLAR, -TRINITY, -ECLIPSE, MUFFINS),
        new card (8, BIPOLAR, -MUFFINS, -ECLIPSE, MUFFINS)
    ); // $queue

// initialize the board array which shall be filled with cards from the queue,
// order TL TC TR CL CC CR BL BC BR where T=top C=center B=bottom L=left R=right

    $board = array ();

// function check returns whether the n^th card on the board matches with
// the other cards previously put on the board

    function check ($board, $n) {
        $vertical   = $n > 2? $board[$n - 3]->S + $board[$n]->N == 0: TRUE;
        $horizontal = $n % 3? $board[$n - 1]->E + $board[$n]->W == 0: TRUE;
        return $vertical and $horizontal;
    } // function check

// function show prints a board configuration, i.e. the cards' positions and
// orientations

    function show ($board) {
        $output = "\ncards | turns\n";
        for ($i = 0; $i < 3; ++$i):
            $orientation = '';
            $identifiers = '';
            for ($j = 0; $j < 3; ++$j):
                $orientation .= ' ' . $board[3 * $i + $j]->orientation;
                $identifiers .= $board[3 * $i + $j]->identifier . ' ';
            endfor;
            $output .= $identifiers . '|' . $orientation . "\n";
        endfor;
        print '<pre>' . $output . '</pre>';
    } // function show

// function play checks all card configurations on the board recursively

    function play ($board, $queue) {
        $count = count ($board);
        // check for every card from the queue …
        for ($q = count ($queue); $q > 0; --$q):
            array_push ($board, array_shift ($queue));
            // … and for all their possible orientations …
            for ($k = 4; $k > 0; --$k):
                // … whether they fit on the board as next card …
                if (check ($board, $count)):
                    // … until no card is left in the queue & show the solution
                    if (empty ($queue)):
                        show ($board);
                    else:
                        play ($board, $queue);
                    endif;
                endif;
                $board[$count]->rotate ();
            endfor;
            array_push ($queue, array_pop ($board));
        endfor;
    } // function play

// kick-off

    play ($board, $queue);

// end

Ergebnis

So sieht es aus: das Programm in Aktion. Eine Lösung besteht jeweils aus 3 mal 3 Zahlen, welche die Karten (cards) im Quadrat anhand ihrer Nummern platzieren, und weiteren 3 mal 3 Zahlen, die angeben, wie oft die Karten an den jeweiligen Positionen gegenüber ihrer Ausgangsstellung mit Hundegesichtern links und oben im Uhrzeigersinn um 90° gedreht werden (turns) müssen.

Es finden sich acht Lösungen, wobei jeweils vier der Lösungen sich nur dadurch unterscheiden, dass das ganze Ergebnis rotiert wurde. Unter den gut 23,8 Milliarden verschiedenen Möglichkeiten, die Karten zueinander auszurichten, gibt es also nur zwei individuelle Lösungen des Puzzles.

9! × 4⁹ = 95126814720. Legt man die erste Karte aus, kann man sich für eine von neun Karten entscheiden; legt man die zweite Karte aus, kann man sich noch zwischen acht Karten entscheiden; legt man die dritte Karte aus, fällt die Wahl zwischen sieben Karten, und so weiter. Daraus ergeben sich 9! = 362880 Möglichkeiten. Hinzu kommt, dass jede der neun Karten in vier verschiedene Stellungen gedreht werden kann, was für jede der möglichen Kartenreihenfolgen noch einmal 4⁹ = 262144 mögliche Ausrichtungen bringt.