Autor Beitrag
pzktupel
Hält's aus hier
Beiträge: 127
Erhaltene Danke: 28



BeitragVerfasst: Do 06.12.18 22:39 
Ein interessanter Aspekt. Ich löste zwar die Gleichung mit dem PC, aber schriftlich konnte ich nicht zu Ende lösen,aber folgendes:
114x^2+1=y^2 -> 114x^2=y^2-1-> 114x^2=(y-1)(y+1)

Da 114=19*6 ist, muss 19 Teiler zum Bsp. von (y+1) sein.
Alle Zahlen , die infrage kämen sind: 18+19n. Man findet bei n=53 die 1025.
Warum aber ausgerechnet x=96=114-18 die Lösung hergibt, weiß ich nicht. Zufall?

Ferner muss 19 auch 20+19n -1 teilen. Bei n=53 kommt man ebenfalls auf 1025.
Auch liegt die 96 für x genau auf der Linie: 96=20+19n. ( 96 ist durch 6 teilbar, was durch die 114 = 19*6 auch noch gelten muss )
Hidden
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2242
Erhaltene Danke: 55

Win10
VS Code, Delphi 2010 Prof.
BeitragVerfasst: Do 06.12.18 23:44 
Ich habe zuerst 1025 eingetippt und war sehr verwundert, was falsch gelaufen sein könnte :lol: Nachdem ich alles nochmal durchgerechnet habe, ist mir dann aufgefallen dass nach x² und nicht nach x gefragt war :wall:

OT: Ein paar ziellose Überlegungen

x^2 = 114 * y^2 + 1

Da 2, 3, 19 Teiler von 114 y^2 sind, können sie keine Teiler von 114 y^2 + 1 sein. Damit sind sie dann auch nicht Teiler von x.

Da x weder durch 2 noch durch 3 teilbar ist, ist x von der Form 6n +- 1.

Zahlen von dieser Form haben eine interessante Eigenschaft: Ihr Quadrat ist immer 1 mehr als ein Vielfaches von 24. (Kurzer Beweis im Anhang.)
Damit ist x^2 = 24 k + 1 = 114 y^2 + 1, oder anders ausgedrückt ist 19 y^2 = 4 k, also ist y gerade.

PS: user profile iconpzktupel vielleicht willst du die Rollen von x und y in deiner Rechnung austauschen? user profile iconMathematiker hatte sie umgekehrt verwendet
Einloggen, um Attachments anzusehen!
_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)


Zuletzt bearbeitet von Hidden am Fr 07.12.18 00:00, insgesamt 1-mal bearbeitet

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2611
Erhaltene Danke: 1400

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Do 06.12.18 23:54 
user profile iconHidden hat folgendes geschrieben Zum zitierten Posting springen:
... oder anders ausgedrückt ist 19 y^2 = 4 k, also ist y gerade.

:zustimm:
Sehr interessant, denn damit ist k garantiert durch 19 teilbar. Damit sind nur noch etwa 2500 Werte für k zu testen.

Nachtrag: Ich wollte es gerade programmieren und bin mir auf einmal nicht mehr sicher, dass es schneller wird, denn der Test auf Quadratzahl dauert ja auch seine Zeit.
Ich muss mal genauer darüber nachdenken. :suspect:

@Hidden: Ich habe deine Idee im "Matheplaneten" eingestellt. Vielleicht hat ein "Matheprofi" eine Idee, wie man deinen schönen Vorschlag zur endgültigen Lösung führen kann.

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1583
Erhaltene Danke: 230


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Fr 07.12.18 01:55 
Die Wichtelquadrate löste ich mit nur einer Inkrementierungsschleife, ganz ohne Pell: Seiten"länge" (Wichtelanzahl an der Quadratseite) mit 1 begonnen, quadriert, mit 114 multipliziert, um 1 erhöht, Wurzel gezogen. War diese ganz(rational), den Radikanten als Lösung ausgegeben, ansonsten Seiten"länge" um 1 inkrementiert und hinein in das nächste Schleifendurchlaufsvergnügen!

_________________
Ordnung ist das halbe Leben - und sie zu schaffen die andere Hälfte.
pzktupel
Hält's aus hier
Beiträge: 127
Erhaltene Danke: 28



BeitragVerfasst: Fr 07.12.18 05:42 
@ Hidden

Also ich habe mich nicht vertan, nur unschön ausgedrückt.
Denn es sind in den beiden Formeln die Zahlen 1026 und 1024 gemeint , was (y+1) und (y-1) bedeutet. Y ist also 1025.

114*x^2 hat den Teiler 19 und 6, die müssen in (y-1) oder (y+1) einfach drin sein, was sie auch sind.

6 und 19 beziehen sich auf 1026.

LG

P.S. Achso, die Variablen x und y waren schon richtig in meiner Formel gewesen.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8411
Erhaltene Danke: 432

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.2 CE
BeitragVerfasst: Fr 07.12.18 09:46 
user profile iconDelphi-Laie hat folgendes geschrieben Zum zitierten Posting springen:
Was ist denn Deiner Ansicht nach eine unerlaubte Hilfe?

Ich habe das "cheaten" ja mit Absicht in Gänsefüßchen gesetzt. Unerlaubt ist ist das, was ich getan habe, sicher nicht. :angel:

Mein Problem war halt, dass ich "nur durch Verschieben" auf keinen grünen Zweig gekommen bin, weil diese magischen Quadrate ja nicht greedy lösbar sind (d.h. zuerst die erste Zeile auf 30 bringen, dann die nächste etc.).

Daher habe ich mir schnell ein Programm gebastelt (und eines, das auch schnell fertig ist, trotz 16! vielen Möglichkeiten), das mir gewissermaßen eine Hälfte der Aufgabe abnimmt. Meine Frage wäre nun, ob es bei diesem Schiebe-Quadrat noch einen Trick gibt, wie man das ohne diese Hilfe elegant lösen kann. :idea:

_________________
Oel ngati kameie.
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1583
Erhaltene Danke: 230


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Fr 07.12.18 11:54 
user profile iconGausi hat folgendes geschrieben Zum zitierten Posting springen:
Mein Problem war halt, dass ich "nur durch Verschieben" auf keinen grünen Zweig gekommen bin, weil diese magischen Quadrate ja nicht greedy lösbar sind (d.h. zuerst die erste Zeile auf 30 bringen, dann die nächste etc.).


Das bloße Verschieben gab auch meine Wenigkeit schnell auf. Simple Rätsel sind in diesem Adventskalender nunmal Mangelware. Wir werden eben von einem Gymnasiallehrer, der bestimmt auch Leistungskurse gibt, entsprechend gefordert.

user profile iconGausi hat folgendes geschrieben Zum zitierten Posting springen:
Daher habe ich mir schnell ein Programm gebastelt (und eines, das auch schnell fertig ist, trotz 16! vielen Möglichkeiten), das mir gewissermaßen eine Hälfte der Aufgabe abnimmt.


Das war ganz gewiß keine unerlaubte Hilfe. Da wir hier in einem Programmierforum zu Hause sind, ist es nur legitim, die (informationsverarbeitenden) Routineaufgaben an Maschinen zu delegieren. Dafür müssen wir umso mehr intellektuelle Energie in präzise Aufgabenstellungen für diesselben investieren. Programmierhilfe wurde in der Ankündigung des Adventskalenders zudem auch "explizit zugelassen".

user profile iconGausi hat folgendes geschrieben Zum zitierten Posting springen:
Meine Frage wäre nun, ob es bei diesem Schiebe-Quadrat noch einen Trick gibt, wie man das ohne diese Hilfe elegant lösen kann. :idea:


Warten wir auf die Auflösung, die vielleicht auch dazu mit ein paar Zaunpfählen winkt.

_________________
Ordnung ist das halbe Leben - und sie zu schaffen die andere Hälfte.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1640
Erhaltene Danke: 234

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 07.12.18 12:33 
Hallo,

user profile iconGausi Kann ich sehr gut verstehen.
Die Lösungsmenge ist ja schon enorm eingeschränkt, wenn man rekursiv zeilenweise 3 Werte aus dem Restpool einfügt und dann den fehlenden auf 30 einfügt, falls der noch vorhanden ist.
Die letzte Zeile passt ja dann immer und bei der ersten kann man eine beliebige Zahl wegen Kongruenzen vorab festlegen.
Ich habe es dennoch nicht gelöst :-( War auch zu spät für mich.

Heute habe ich wohl zum ersten Mal diese Art von Rätsel ohne user profile iconFietes Programm gelöst :-)

Gruß Horst
Symbroson
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 382
Erhaltene Danke: 67

Raspbian, Ubuntu, Win10
C, C++, Python, JavaScript, Lazarus, Delphi7, Casio Basic
BeitragVerfasst: Fr 07.12.18 13:43 
Mein Programm zu Tag 05:

ausblenden C++-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
int main() {
    unsigned int n = 0;
    float f;
    
    do f = sqrt(114.0 * ++n * n + 1);
    while (f != floor(f));
    
    printf("Result: n = %i %i\n"114 * n * n + 1, n);
}


Zu Tag 6 sag ich erstmal nichts weil ich nicht weiß ob der nicht noch bei manchen läuft.

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)
Fiete
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 524
Erhaltene Danke: 226

W7
Delphi 6 pro
BeitragVerfasst: Fr 07.12.18 14:47 
Moin,
die Lösungsidee war schnell da: magische Quadrat der Ordnung 4, alle Zahlen um eins verringern ==> fertig!
Die Schieberei ist für mich Rentner zeitaufwendig gewesen, Skatrunde und Einkaufen mussten eingeplant werden.
Die Zahlen direkt an die richtige Stelle platzieren zu können wäre eine grosse Hilfe gewesen.
Der Kalender macht immer noch viel Spaß!

Gruß Fiete

_________________
Fietes Gesetz: use your brain (THINK)

Für diesen Beitrag haben gedankt: Symbroson
pzktupel
Hält's aus hier
Beiträge: 127
Erhaltene Danke: 28



BeitragVerfasst: Fr 07.12.18 16:47 
.... gelöscht , zu gefährlich
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2611
Erhaltene Danke: 1400

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Fr 07.12.18 18:30 
user profile iconSymbroson hat folgendes geschrieben Zum zitierten Posting springen:
Zu Tag 6 sag ich erstmal nichts weil ich nicht weiß ob der nicht noch bei manchen läuft.

Läuft noch. Im Moment sind noch einige Lösungsmöglichkeiten offen.
Gegen 22 Uhr, denke ich, kann ich auflösen.

LG Steffen

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2611
Erhaltene Danke: 1400

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Fr 07.12.18 22:15 
Hallo,
das Rätsel "Magisches Quadrat + Loyds Puzzle" hatte wohl die bisher größten Probleme gemacht. Es gibt aber 33 Lösungen. Sehr schön.

In vorhergehenden Beiträgen wurde schon viel gesagt. Zuerst braucht man ein magisches Quadrat der Ordnung 4. Entweder berechnet man dies, z.B. mit
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
procedure magisches_quadrat(n:integer); //n = 4,8,12,16,20
type
    matrix = array[1..20,1..20of integer;
var
    a:matrix;
  
procedure quadrat;
var n2:integer;
  procedure markieren;
  var i,j,k,m,sgn:integer;
  begin
    k:=n div 2;
    n2:=n*n;
    sgn:=1;
    m:=k;
    for i:=1 to k do begin
      for j:=1 to k do begin
        a[((m-j)div n)+1,((m-j)mod n) +1]:=sgn;
        a[((m+j-1)div n)+1,((m+j-1)mod n) +1]:=sgn;
        sgn:=-sgn;
      end;
      m:=m+n;
      sgn:=-sgn;
    end;
  end;
  procedure einsetzen;
  var i,h:integer;
  begin
    for i:=1 to n2 div 2 do begin
      h:=i;
      if a[(i-1div n+1,(i-1mod n +1]<0 then h:=n2+1-i;
      a[(h-1div n+1,(h-1mod n+1]:=i;
      a[(n2-h)div n+1,(n2-h)mod n+1]:=n2+1-i;
    end;
  end;
begin
  markieren;
  einsetzen;
end;

begin
  fillchar(a,sizeof(a),0);
  if n mod 4 = 0 then quadrat;
  //in a steht magisches quadrat;
end;

oder man wählt eines, z.B. das magische Quadrat Dürers aus "Melancholia":
duerer1
oder man berechnet es mit Fietes Programm.

Diese Quadrate beginnen alle mit 1 und enden bei 16. Hier braucht man aber 0 bis 15, d.h. man reduziert jedes Feld um 1. In dem hier angehängten einfachen Programm wird dies sofort gemacht.
Anschließend müssen die 15 Steine noch durch Mausklick an die richtige Position gebracht werden.
Mehr ist das nicht und einen einfacheren "Trick" kenne ich nicht.

Übrigens sind bei dem hier genutzten Loyds Puzzle die 14 und 15 vertauscht. Damit können die Zahlen nicht(!) von links oben = 1 bis rechts unten = 15 sortiert werden. Aber nur für diese Variante gibt es die Möglichkeit zum magischen Quadrat.

LG Steffen

Nachtrag: Ich hatte noch vergessen vorsorglich für das morgige Rätsel "um Entschuldigung zu bitten". :flehan:
Es könnte sein, dass einige es als "unlösbar" ansehen. :mrgreen:
Einloggen, um Attachments anzusehen!
_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein


Zuletzt bearbeitet von Mathematiker am Fr 07.12.18 22:46, insgesamt 2-mal bearbeitet
pzktupel
Hält's aus hier
Beiträge: 127
Erhaltene Danke: 28



BeitragVerfasst: Fr 07.12.18 22:35 
So hatte ich es gemacht, mit dem von Dürer :-)
Symbroson
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 382
Erhaltene Danke: 67

Raspbian, Ubuntu, Win10
C, C++, Python, JavaScript, Lazarus, Delphi7, Casio Basic
BeitragVerfasst: Fr 07.12.18 22:42 
Gelöst habe ich es auch durch ein fertiges Quadrat. Allerdings habe ich mich auch mal an das programmatische Lösen rangesetzt:

Variante 1 wäre, schrittweise alle möglichen Züge des aktuellen Quadrates durchzufüren, bis die gesuchte Permutation erreicht ist. Das habe ich aber nicht zu Ende gebracht.

Stattdessen habe ich versucht, das Quadrat komplett aufzufüllen. Jedoch kommt bei meinem Programm nur eine einzige Lösung heraus. Ich weiß aber nicht, warum. Meine Idee:

1. Es werden für jede Zeile 4 Elemente aus der Verbleibenden Menge an Zahlen ausgewählt, die die Summe 30 aufweisen.
2. Die Elemente jeder Zeile werden so permutiert, dass nacheinander die Summe der Spalten ebenfalls 30 ergibt.
3. war 2. erfolgreich werden schließlich noch die Diagonalen überprüft und dann das Quadrat ausgegeben.

Das Ergebnis ist auch im Rätsel lösbar. Es gibt jedoch auch Varianten, bei denen zwei Felder getauscht werden müssen, was jedoch nur in Verbindung mit dem Tausch eines weiteren Paares möglich ist, was einen das Quadrat im Rätsel nicht einstellen lässt.
Hier ist das Ergebnis meines Programms:
ausblenden Quelltext
1:
2:
3:
4:
5:
6:
     4  8  3 15 = 30
    11 14  5  0 = 30
     6  1 10 13 = 30
     9  7 12  2 = 30
   = =  =  =  = =
30  30 30 30 30   30


Der wesentliche Quelltext: (vollst. im Anhang)

ausblenden volle Höhe C++-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
#define NUMS 16

// row:  current row index
// p:    current mag.sq. number selection
// perm: selected permution for current row
uint8_t row = 0, p[16], used[16], **avail, perm[4];

int main() {
    // remaining range for rows
    uint8_t i, av1[16], av2[12], av3[8], av4[4],
        *av[4] = {av1, av2, av3, av4};
    avail = av;
    
    // reset used states
    for(i = 0; i < NUMS; i++) used[i] = 0;
    row = 0;
    fillrow();
}

void fillrow() {
    // save remaining range to list
    uint8_t i, n = 0;
    for(i = 0; i < NUMS; i++)
        if(!used[i])
            avail[row][n++] = i;
    select_mn(40);
}

// select d elements of remaining range starting from s
// range = 16 - 4 * row (first row(0): 16, last row(3): 4) remaining
void select_mn(uint8_t d, uint8_t s) {
    uint8_t i;
    
    if (d) {
        // pick next element from remaining range
        for (i = s; i < 16 - 4 * row; i++) {
            perm[4 - d] = avail[row][i];    // save chosen element
            used[(uint) avail[row][i]] = 1// store used state
            select_mn(d - 1, i + 1);        // fill next element
            used[(uint) avail[row][i]] = 0// reset used state
        }
        // check sum of chosen selection
    } else if(perm[0] + perm[1] + perm[2] + perm[3] == 30) {
        memcpy(p + (4 * row), perm, 4);
        
        if(row == 3) checkCol(p, 0);
        else { // fill next row
            row++;
            fillrow();
            row--;
        }
    }
}

// permute rows to solve coloumns
void checkCol(uint8_t *p, uint8_t col) {

    if(col == 3) { // finished.
        if(p[3] + p[6] + p[ 9] + p[12] == 30 &&
           p[0] + p[5] + p[10] + p[15] == 30)
            print(p);
        return;
    }
    
    uint8_t a, b, c, d, sum;
    uint8_t tp[16];
    
    // permute first 3 elements of coloumn
    for(a = col + 0; a <  4; a++) {
    for(b = col + 4; b <  8; b++) {
    for(c = col + 8; c < 12; c++) {
        
        // sum of first 3 elements < 30 || >= 15
        // otherwise 30 not reachable
        sum = p[a] + p[b] + p[c];
        if(sum + p[c] >= 30 || sum + p[c] < 15continue;
        
        // permute last element of coloumn
        for(d = col + 12; d < 16; d++) {
            if(sum + p[d] == 30) {
                // if sum = 30 -> swap elements to correct position
                memcpy(tp, p, 16);
                swap(tp, col +  0, a);
                swap(tp, col +  4, b);
                swap(tp, col +  8, c);
                swap(tp, col + 12, d);
                checkCol(tp, col + 1); // check next coloumn
            }
        }
    }}}
}

// print found square
void print(uint8_t* p) {
    uint8_t sum1, sum2[4] = {0000};
    printf("   ");
    
    for(uint8_t i = 0; i < NUMS; i++) {
        sum1 += p[i];
        sum2[i % 4] += p[i];
        printf("%3i", p[i]);
        
        if(i % 4 == 3) {
            printf(" = %i\n   ", sum1);
            sum1 = 0;
        }
    }
    
    printf("= =  =  =  = =\n");
    printf("%2i%4i%3i%3i%3i%5i\n",
        p[3] + p[6] + p[ 9] + p[12],
        sum2[0], sum2[1], sum2[2], sum2[3],
        p[0] + p[5] + p[10] + p[15]);
}
Einloggen, um Attachments anzusehen!
_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)
Symbroson
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 382
Erhaltene Danke: 67

Raspbian, Ubuntu, Win10
C, C++, Python, JavaScript, Lazarus, Delphi7, Casio Basic
BeitragVerfasst: Fr 07.12.18 22:47 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Nachtrag: Ich hatte noch vergessen vorsorglich für das morgige Rätsel "um Entschuldigung zu bitten". :flehan:
Es könnte sein, dass einige es als "unlösbar" ansehen. :mrgreen:

Umso mehr freue ich mich darauf :D

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)
pzktupel
Hält's aus hier
Beiträge: 127
Erhaltene Danke: 28



BeitragVerfasst: Fr 07.12.18 22:50 
Ich möchte der Fairness halber doch die Lösung für 114x^2+1=y^2 einstellen.

Heute nachmittag, bin ich auf einen universellen Lösungsweg gekommen, der direkt x und y liefert, sowie generell x und y liefert , bei einem zulässigem a von ax^2+1=y^2.

114x^2+1=y^2

Periode Wurzel(114) ist: 10,1,2,10,2,1,20

Man erhält: 21194 / 1985

und für 10,1,2,10,2,1,21

erhält man: 22219 / 2081

Differenzen Zähler und Nenner bilden: 1025=y , x=96

Lösung: 114∗96^2+1=1025^2

fertig !


Mehr hier: matheplanet.de/mathe...lps=1740149#v1740149
Hidden
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2242
Erhaltene Danke: 55

Win10
VS Code, Delphi 2010 Prof.
BeitragVerfasst: Fr 07.12.18 23:06 
Für das kombinierte Magische Quadrat / 15-Puzzle habe ich zuerst auf Wikipedia nach einem Pandiagonalen Magischen Quadrat der Ordnung 4 gesucht und von jedem Feld 1 abgezogen. Das ist dann bei mir der Teil, den Gausi zurecht als "cheaten" bezeichnet hat. Wenn man das Rätsel auf voller Schwierigkeitsstufe spielen will, sollte man das Internet natürlich weglassen :lol:

Wie man ein 15-Puzzle löst, wusste ich noch. Allerdings erlaubt so ein Puzzle (wie auch ein Rubiks-Cube) nur gerade Permutationen als Züge. Ich dachte dann zuerst ich muss eine andere Lösung suchen, aber dann habe ich das magische Quadrat einfach um 90° gedreht, was mir effektiv eine ungerade Permutation gab und das Puzzle für diese Zielkombination lösbar machte.

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
Symbroson
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 382
Erhaltene Danke: 67

Raspbian, Ubuntu, Win10
C, C++, Python, JavaScript, Lazarus, Delphi7, Casio Basic
BeitragVerfasst: Fr 07.12.18 23:27 
user profile iconSymbroson hat folgendes geschrieben Zum zitierten Posting springen:
Jedoch kommt bei meinem Programm nur eine einzige Lösung heraus. Ich weiß aber nicht, warum.


Hab den Fehler gefunden. Das Array perm wurde in tieferen Permutationen irgendwie so verändert, dass es frühere mitbeeinflusst. Ich kann stattdessen einfach die Permutation direkt an p durchführen, was auch an anderen Stellen nochmal einiges vereinfacht. Also hier der funktionierende Code:

ausblenden volle Höhe C++-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
#define uint uint8_t

// p:    current magic square
uint p[16], used[16], **avail;
int c = 0;

int main() {
    // remaining range for rows
    uint i, av1[16], av2[12], av3[8], av4[4],
        *av[4] = {av1, av2, av3, av4};
    avail = av;
    
    // reset used states
    for(i = 0; i < 16; i++) used[i] = 0;
    fillrow(0);
    printf("found %i solutions!\n",c);
}

void fillrow(uint row) {
    // save remaining range to list
    uint n = 0;
    for(uint i = 0; i < 16; i++){
        if(!used[i])
      avail[row][n++] = i;
  }
    select_mn(40, row);
}

// select d elements of remaining range starting from s
// range = 16 - 4 * row (first row(0): 16, last row(3): 4) remaining
#define RP(i) p[4 * row + i]
void select_mn(uint d, uint s, uint row) {
    if (d) {
        // pick next element from remaining range
        for (uint i = s; i < 16 - 4 * row; i++) {
            RP(4 - d) = avail[row][i];      // save chosen number
            used[(uint) avail[row][i]] = 1;  // set number used
            select_mn(d - 1, i + 1, row);   // fill next element
            used[(uint) avail[row][i]] = 0;  // set number unused
        }
        // check sum of chosen selection
    } else if(RP(0) + RP(1) + RP(2) + RP(3) == 30) {
        if(row == 3) checkCol(p, 0);
        else fillrow(row + 1);
    }
}

// permute rows to solve coloumns
void checkCol(uint *p, uint col) {

    if(col == 3) { // finished.
        if(p[3] + p[6] + p[ 9] + p[12] == 30 &&
           p[0] + p[5] + p[10] + p[15] == 30)
            print(p);
        return;
    }
    
    uint a, b, c, d, sum, tp[16];
    
    // permute first 3 elements of coloumn
    for(a = col + 0; a <  4; a++) {
    for(b = col + 4; b <  8; b++) {
    for(c = col + 8; c < 12; c++) {
        
        // sum of first 3 elements < 30 && >= 15
        // otherwise 30 not reachable
        sum = p[a] + p[b] + p[c];
        if(sum + p[c] >= 30 || sum + p[c] < 15continue;
        
        // choose last element of column
        for(d = col + 12; d < 16; d++) {
            if(sum + p[d] == 30) {
                // if sum = 30 -> swap elements to correct position
                memcpy(tp, p, 16);
                swap(tp, col +  0, a);
                swap(tp, col +  4, b);
                swap(tp, col +  8, c);
                swap(tp, col + 12, d);
                checkCol(tp, col + 1); // check next coloumn
            }
        }
    }}}
}

// print found square
void print(uint* p) {
    uint sum1 = 0, sum2[4] = {0000};
    printf("---%3i--------------\n   ", ++c);
    
    for(uint i = 0; i < 16; i++) {
        sum1 += p[i];
        sum2[i % 4] += p[i];
        printf("%3i", p[i]);
        
        if(i % 4 == 3) {
            printf(" = %i\n   ", sum1);
            sum1 = 0;
        }
    }
    
    printf("= =  =  =  = =\n%2i%4i%3i%3i%3i%5i\n\n",
        p[3] + p[6] + p[ 9] + p[12],
        sum2[0], sum2[1], sum2[2], sum2[3],
        p[0] + p[5] + p[10] + p[15]);
}


Nachtrag: Code geändert - hatte vorher den falschen Code kopiert :lol:
Einloggen, um Attachments anzusehen!
_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)
pzktupel
Hält's aus hier
Beiträge: 127
Erhaltene Danke: 28



BeitragVerfasst: Sa 08.12.18 01:10 
Rätsel 8 ging doch, nach 2 Liter Bier :D
Eine wirklich nette Idee, ausgezeichnet !