hallo.
ich brauche mal kurz hilfe.
ich hab folgende aufgabe:

Beim Aufräumen haben Sie im Keller ein Puzzle gefunden. Die 9 Teile sollen so zu einem Quadrat zusammengefügt werden, dass an jeder Kante ein durchgehender Pfeil und ggf. eine komplette geometrische Figur entsteht. Nach etwas Probieren haben Sie immerhin 8 Teile passend zusammengefƒugt, nur das Teil mit der Nummer 7 passt nicht in die verbleibende Ecke.
Schreiben Sie ein Programm, dass alle möglichen Lösungen des Puzzles ausgibt (geben Sie für die 3 Reihen jeweils an, welche Teile dort verwendet und ob diese um 90, 180 oder 270 Grad gedreht wurden).

Bild dazu:
http://home.arcor.de/mario.neichel/puzzel.JPG

Wie gehe ich das am besten an?
Kann ich eine generische Liste auf ein Array tun? (hab sowas im Raum schweben hören) und wenn ja wie?

würde mich auf antwort freuen.
loki

[edit=sakura] - hilfe - aus dem Titel geworfen, die brauchen wir alle Mfg, sakura[/edit]

Nur als Stichwort: man könnte Backtracking verwenden, umdas Problem zu lösen.

MfG
Binärbaum
//Edit: ach ja: willkommen in der DP!

Hi.

Ich empfehle ein 2-dimensionales Array für das aufbewahren der Puzzleteile. Sowas in dieser Richtung:

markieren

Delphi-Quellcode:

type
  TPuzzle = array[1..3, 1..3] of TPuzzleteil; // 9 Puzzleteile
  TPuzzleteil = array[1..4] of TPfeil; // 4 Richtungen
  TPfeil = (pfPfeilSpitze, pfPfeilRest, pfQuadratSpitze, {...});

Nur müßtest du da jetzt noch für jedes Puzzleteil die Nr und die aktuelle Drehung einbauen. Schließlich muß das später mit angegeben werden

danke für so vielen schnelle antworten.
an backtracking habe ich auch schon gedacht, doch das hat im worst case exponentielle Laufzeit. das ist verdammt viel. und wenn ich mir das so ansehe, kann das verdammt lange dauern. hm .. viell bleibt mir auch nix anderes übrig?

ne mögliche darstellung habe ich auch schon. aber aber immer für vorschläge offen.

zusammenfalten · markieren

Delphi-Quellcode:

package Puzzle is
  
    type Orientation_Type is ( North, East, South, West ); -- 0, 90, 180, 270
    type Match_Neighbour_Type is ( Yes, No, Not_Applicable );
  
    type Element_Type is
    record
       Orientation : Orientation_Type;
       Arrow_Direction : Oreintation_Type;
       Match_Left_Neighbour : Match_Neighbour_Type;
       Match_Right_Neighbour : Match_Neighbour_Type;
       Match_Upper_Neighbour : Match_Neighbour_Type;
       Match_Lower_Neighbour : Match_Neighbour_Type;
    end record;
  
    type Board_Type is array ( 1..3, 1..3 ) of Element_Type;
   
 end Puzzle;

freu mich auf weitere antworten

loki

Hi.

Zitat von loki:

zusammenfalten · markieren

Delphi-Quellcode:

package Puzzle is
  
    type Orientation_Type is ( North, East, South, West ); -- 0, 90, 180, 270
    type Match_Neighbour_Type is ( Yes, No, Not_Applicable );
  
    type Element_Type is
    record
       Orientation : Orientation_Type;
       Arrow_Direction : Oreintation_Type;
       Match_Left_Neighbour : Match_Neighbour_Type;
       Match_Right_Neighbour : Match_Neighbour_Type;
       Match_Upper_Neighbour : Match_Neighbour_Type;
       Match_Lower_Neighbour : Match_Neighbour_Type;
    end record;
  
    type Board_Type is array ( 1..3, 1..3 ) of Element_Type;
   
 end Puzzle;

Ein Feld kann mehrere Pfeile haben und die 4 Match_..._Neighbour kann man zusammenfassen, also

markieren

Delphi-Quellcode:

Arrow_Directions : array (1..4) of Orientation_Type;
Match_Neighbour : array (1..4) of Match_Neighbour_Type;

Zitat von Waldteufel:

markieren

Delphi-Quellcode:

Arrow_Directions : array (1..4) of Orientation_Type;
Match_Neighbour : array (1..4) of Match_Neighbour_Type;

Bei Arrays verwendet man aber immer eckige Klammern [ und ]

MfG
Binärbaum

Hi.

Zitat von Binärbaum:

Bei Arrays verwendet man aber immer eckige Klammern [ und ]

Das war doch gar nicht Pascal...

[edit] Das war ADA... [/edit]

@waldteufel
danke für die idee, doch ich fürchte um die übersichtlichkeit. und wenn die aufgabe kontrolliert wird und der typ lange braucht um durch zu blicken, wird der mir punkte abziehen

@binärbaum
das mit den klammern ist ok, pseudo code reicht mir auch.
und in ada sind es auch normale klammern, und in pascal weis ich das gar nicht mehr, hab schon ewig nicht mehr pascaliert *g* und wozu gibt es fehlermeldungen?


@all
wie würdet ihr den grund algorith. angehen?

loki

Hi.

Zitat von loki:

@all: wie würdet ihr den grund algorith. angehen?

Verschachtelte For-Schleifen

markieren

Delphi-Quellcode:

for i := 1 to 3 do
  for j := 1 to 3 do
    for k := 1 to 4 do
    begin
      Teile[i, j].Rotieren(k);
      Teile[i, j].Ausgeben;
    end;

oder Rekursion

zusammenfalten · markieren

Delphi-Quellcode:

procedure MachDas(i : integer);
begin
  if (i <> 9) then
  begin
    Rotieren;
    MachDas(i + 1);
    Rotieren;
    MachDas(i + 1);
    Rotieren;
    MachDas(i + 1);
    Rotieren;
    MachDas(i + 1);
  end;
end;