RDW #6 - Raetsel der Woche Nummer 6
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


 Regeln:  * Bitte nicht vor Ablauf der ersten 72 Stunden ( = drei Tage ) nach
 ~~~~~~~    Veroeffentlichung Hinweise (Spoiler) oder Loesungen veroeffent-
            lichen!

          * Wenn diese Zeit abgelaufen ist, werde ich einen Thread mit passen-
            dem Titel erstellen, in dem die Loesungen gepostet werden und dis-
            kutiert werden koennen.

          * Die Loesungen sollten nicht nur gepostet, sondern auch an mich ge-
            mailt werden, damit ich sie testen, "bewerten"  und zusammenfassen
            kann. Die Adrese dafuer lautet:

            crian <---AT---> perl <---MINUS---> community <---DOT---> de

            Im Betreff sollte 'RDW' und die Nummer des Raetsels stehen. Hilf-
            reich waere neben dem Quellcode der Username im Forum sowie Perl-
            und OS-Version, falls Du diese kennst.

          * Verstaendnisfragen duerfen in diesem Thread gestellt werden, aber
            Tipps und (Teil-) Loesungen sind hier unerwuenscht.

          * Ich werde die eingeschickten Programme im Netz zur Verfuegung
            stellen, so dass gerade lange Quellcodes nicht (komplett)
            gepostet werden muessen.

          * Zur Verwendung von Modulen: Ich moechte diese nicht generell aus-
            schliessen, aber wenn quasi die komplette Aufgabe durch die Ver-
            wendung eines Moduls ersetzt werden kann, ist dies vielleicht nicht
            der Sinn der Aufgabe gewesen.



 Aufgabe: Ausgehend von der Loesung zu Raetsel RDW #4 (welches die folgende
 ~~~~~~~~ Aufgabenstellung hatte:

                                    -----

          Gegeben sei ein rechteckiges Spielfeld F mit n x m Feldern.
           
          Desweiteren gibt es eine Menge S mit Steinen auf diesem Spielfeld.
          Jeder dieser Steine ist rechteckig und belegt p x q Felder (die
          Steine koennen verschieden gross sein).

          Die Steine duerfen sich auf dem Feld nicht ueberlappen. (Das heisst
          jedes Feld von F darf von hoechstens einem Stein aus S belegt sein.)

          Schaffe eine interne Darstellung von F und S und Funktionen (oder
          Methoden), um den Stein S_i in eine der vier Himmelsrichtungen auf
          dem Spielfeld zu verschieben.

          Ist es nicht moeglich, den gegebenen Stein in die gegebene Richtung
          zu verschieben, so soll dies dem Aufrufer auf irgend eine Weise mit-
          geteilt werden.

                                    -----

          ) soll eine Moeglichkeit geschaffen werden, zu gegebenen Ausgangs-
          stellungen und Zielvorgaben Loesungen zu finden. Dabei sollte nach
          Moeglichkeit eine Loesung mit der kleinsten Anzahl an Zuegen gefun-
          den werden.

          Beispiel:

             +---+---+---+        Der Stein "1" soll aus dem Feld unten
           2 | 1 | 0 | 2 |        rechts aus dem Spielfeld herausgescho-
             +---+---+---+        ben werden, d.h., dass er auf dem Feld
           1 | 0 | 3 | 0 |        unten rechts landen soll.
             +---+---+---+        Eine minimale Loesung ist:
           0 | 4 | 0 | 0 | ->         3-l, 1-r, 1-u, 1-u, 1-r
             +---+---+---+        Dann steht der Stein vor dem Ausgang
               0   1   2          und kann herausgezogen werden.
         
         Die Zielvorgaben werden in Form von Koordinaten für einen bestimmten
         Stein (im Beispiel Stein 1) angeben, hier etwa
             (0,2) == 1
         (Stein 1 auf Zeile Null, Spalte Zwei)

         Ev. laesst sich diese Zielvorgabe elegant als Funktionsreferenz mit-
         geben, aber da kann sich jeder selbst etwas ausdenken.


         Wenn das Programm die Loesung gefunden hat, sollte es sie in der oben
         angegebenen Form (d.h. jeder Zug besteht aus X-Y, wobei X die
         Steinnummer angibt und Y die Richtung, in der dieser Stein einen
         Schritt weit bewegt wird, mit Y ist Element der Menge {r, l, o, u})
         ausgeben und optional auch Schritt fuer Schritt darstellen.


         Bei den bisherigen Betrachtungen wurde davon ausgegangen, dass sich
         jeder Stein prinzipiell in alle vier Himmelsrichtungen bewegen
         laesst. Eine Variante des Spiels waere es, wenn nichtquadratische
         Steine nur in Richtung ihrer laengsten Ausdehnung verschoben werden
         duerfen. (Es gibt solche Spielvarianten, da gilt es, ein bestimmtes
         Auto aus einem Gewirr anderer Autos zu befreien, dafuer waere diese
         Variante notwendig.)

         Die Unterstuetzung dieser Spielvariante sehe ich als optional an.

#
# Test 1
#

columns = 5
rows    = 3

stone 1 = (0, 0), (0, 1)
stone 2 = (1, 0), (1, 1)
stone 3 = (1, 2), (0, 2)
stone 4 = (2, 2), (2, 1)

goal = 1, (2, 3), (2, 4)

# Koordinaten beginnen links unten mit 0,0
# Die erste Koordinate ist die Zeile, die
# zweite die Spalte.

+---+---+---+---+---+
| 0 | 4 | 4 | 0 | 0 | ->
+---+---+---+---+---+
| 2 | 2 | 3 | 0 | 0 |
+---+---+---+---+---+
| 1 | 1 | 3 | 0 | 0 |
+---+---+---+---+---+

#
# Test 1
#

columns = 5
rows    = 3

stone 1 = (0, 0), (0, 1)
stone 2 = (1, 0), (1, 1)
stone 3 = (1, 2), (0, 2)
stone 4 = (2, 2), (2, 1)

goal = 1, (2, 3), (2, 4)

# Koordinaten beginnen links unten mit 0,0
# Die erste Koordinate ist die Zeile, die
# zweite die Spalte.
#
#   +---+---+---+---+---+
# 2 | 4 | 4 | 0 | 0 | 0 | ->
#   +---+---+---+---+---+
# 1 | 2 | 2 | 3 | 0 | 0 |
#   +---+---+---+---+---+
# 0 | 1 | 1 | 3 | 0 | 0 |
#   +---+---+---+---+---+
#     0   1   2   3   4
#
# Eine minimale Loesung ist 4-l, 3-u, 1-r, 1-r, 1-r, 1-u, 1-u

#
# Test 1
#

columns = 3
rows    = 3

stone 1 = (2, 0)
stone 2 = (2, 2)
stone 3 = (1, 1)
stone 4 = (0, 0)

goal = 1, (0, 2)

# Koordinaten beginnen links unten mit 0,0
# Die erste Koordinate ist die Zeile, die
# zweite die Spalte.
#
#            +---+---+---+        Der Stein "1" soll aus dem Feld unten
#          2 | 1 | 0 | 2 |        rechts aus dem Spielfeld herausgescho-
#            +---+---+---+        ben werden, d.h., dass er auf dem Feld
#          1 | 0 | 3 | 0 |        unten rechts landen soll.
#            +---+---+---+        Eine minimale Loesung ist:
#          0 | 4 | 0 | 0 | ->         3-l, 1-r, 1-u, 1-u, 1-r
#            +---+---+---+        Dann steht der Stein vor dem Ausgang
#              0   1   2          und kann herausgezogen werden.

#
# Test 1
#

columns = 5
rows    = 5

stone 1 = (2, 0), (2, 1)
stone 2 = (2, 2), (3, 2)
stone 3 = (4, 1), (4, 2)
stone 4 = (0, 2), (1, 2)
stone 5 = (3, 3), (4, 3)
stone 6 = (1, 3), (2, 3)
stone 7 = (0, 3), (0, 4)

goal = 1, (2, 3), (2, 4)

type = car

# Koordinaten beginnen links unten mit 0,0
# Die erste Koordinate ist die Zeile, die
# zweite die Spalte.
#
#   +---+---+---+---+---+
# 4 | 0 | 3 | 3 | 5 | 0 |
#   +---+---+---+---+---+
# 3 | 0 | 0 | 2 | 5 | 0 |
#   +---+---+---+---+---+
# 2 | 1 | 1 | 2 | 6 | 0 | ->
#   +---+---+---+---+---+
# 1 | 0 | 0 | 4 | 6 | 0 |
#   +---+---+---+---+---+
# 0 | 0 | 0 | 4 | 7 | 7 |
#   +---+---+---+---+---+
#     0   1   2   3   4
#
# Eine minimale Loesung ist
#     3-l, 2-u, 4-u, 7-l, 7-l, 7-l, 4-d, 6-d, 1-r, 1-r, 1-r