Zauberquadrat ermitteln

[kwhk]

Hallo Klaus,
vielen Dank für Deinen Code, er funktioniert !

NextCombi ändert die Belegung des Arrays, dabei entstehen doppelte Ziffern dafür fehlen welche.

CheckCombi prüft, ob von NxtCombi zulässige Belegungen erzeugt wurden, wen ja, dann result=TRUE.

CheckMagic prüft, ob die Bedingungen für das Zauberquadrat erfüllt sind.

Wenn Du mir noch ein paar Hinweise zu CheckCombi geben könntest, den dort benutzten Code habe ich bisher noch nie benutzt oder gesehen.

Delphi-Quellcode:

const
    Size=3;
    Numbers=Size*Size;
    RowSum=(1+Numbers)*Numbers div 2 div Size;
var
    Combi:Array[0..Numbers-1] of Byte;
    Square:Array[0..Size-1,0..Size-1] of Byte absolute Combi;

FUNCTION CheckCombi:Boolean;
var I:Integer; Entries:Set of 1..Numbers;
begin
    Entries:=[];
    for I:=High(Combi) downto 0 do Include(Entries,Combi[I]);
    Result:=Entries=[1..Numbers];
end;

Die Anweisung Include(Entries,Combi[I]); fügt offenbar die Zahl Combi[I] in Entries ein.
Mit Entries=[1..Numbers] wird geprüft, ob tatsächlich nur die Ziffern z.B. 1..9 in Combi enthalten sind.
Gibt es doppelte oder fehlende Ziffern, ist das Ergebnis FALSE.

@Schokohase,
Deine Version werde ich prüfen, wenn sie schneller ist, dann wäre das ein Vorteil.

Noch eine Anmerkung
Die Permutation ist ein Teil der Kombinatorik
https://www.mathebibel.de/kombinatorik
https://www.mathebibel.de/permutation-ohne-wiederholung

Danke für Euere Hinweise

[kwhk]

@Schokohase

Delphi-Quellcode:

//   TArray.Permute<Integer>( [1, 2, 3, 4, 5, 6, 7, 8, 9],
   TArray.Permute<Integer>( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16],

]
Ich habe diese Anweisung geändert, um ein 4x4 Quadrat zu berechnen.
Da bleibt das Programm hängen.
Was mache ich falsch ?

[Schokohase]

Bei 9 Zahlen haben wir 9! = 362.880 Permutationen.
Bei 16 Zahlen haben wir 16! = 20.922.789.888.000 Permutationen.

Das sind mal eben so 57.657.600 mal mehr Permutationen als bei 9 Zahlen.
Davon ausgehend, dass wir für diese 9 Zahlen ungefähr eine viertel Sekunde zum Berechnen brauchen, würde ich das Ergebnis in frühestens 166,8 Tagen erwarten.

Was du falsch machst: Du bist zu ungeduldig.

[Amateurprofi]

@kwhk:

Zu CheckCombi:

Delphi-Quellcode:

const
     Size=3;
     Numbers=Size*Size;
     RowSum=(1+Numbers)*Numbers div 2 div Size;
var
     Combi:Array[0..Numbers-1] of Byte;
     Square:Array[0..Size-1,0..Size-1] of Byte absolute Combi;

FUNCTION CheckCombi:Boolean;
var I:Integer; Entries:Set of 1..Numbers;
begin
     Entries:=[];
     for I:=High(Combi) downto 0 do Include(Entries,Combi[I]);
     Result:=Entries=[1..Numbers];
end;

Das in der Prozedur deklarierte "Entries" ist ein Set, das die Elemente 1 bis Numbers enthalten kann.
Wenn du einem Set ein Element mehrfach hinzufügst, ist es im Set trotzdem nur einmal enthalten.
Erste Zeile:
"Entries" wird = [] gesetzt, das Set enthält dann nichts.
Zweite Zeile:
Alle Werte aus "Combi" werden zu "Entries" hinzugefügt.
Dritte Zeile:
Prüft, ob "Entries" = [1,2,3, ...,Numbers] ist, anders ausgedrückt ob "Entries" alle Werte von 1 bis Numbers enthält.
Wenn das der Fall ist, sind in "Combi" die Werte von 1 bis Numbers, die Combi (korrekterweise die Permutation, wie Schokohase anmerkte) ist dann wirklich eine Permutatation der Werte 1..Numbers.
Sorry, bin nicht so gut im Erklären.

[kwhk]

Hallo Klaus,
es ist eine gute Erklärung.
Wahrscheinlich werden die einzelnen Elemente eines SETs auch noch sortiert.
Ansonsten wäre [1,2,3] <> [1,3,2], obwohl beide Sets die gleichen Elemente enthalten.

Man könnte das Programm beenden, wenn die erste Lösung gefunden wird, da die anderen Lösungen ja nur Spiegelungen sind, die man viel schneller anders ermitteln könnte, falls man das will.
Eigentlich wollte ich ja nur EINE Lösung, das kann ich aber ins Programm einbauen, dann geht es evtl. auch bei 4x4 und größer schneller.

[Schokohase]

Das wage ich zu bezweifeln. Bei 4x4 und größer wirst du ein anderes Verfahren benötigen als das mit den Permutationen.

Backtracking wie man bei Sudoku verwendet wäre z.B. eine Möglichkeit um wesentlich schneller ans Ziel zu gelangen

[KodeZwerg]

Im Anhang noch etwas aus meinem Fundus, die original Webseite existiert nicht mehr.
Dieses Demo ist für 3x3 ausgelegt, auch Graphiken dazu werden eingeblendet.

Ich hoffe es ist ne Berreicherung für diesen Thread,

viel Spass damit.

Ps: Der Anhang ist der Source only release, mit D2010 und Tokyo ließ es sich problemlos kompilieren, habe aber nicht auf Warnungen (falls vorhanden) geachtet, nur obs funktioniert.