Magisches Quadrat und Backtracking

[Loud Silence]

In letzter Zeit habe ich mich etwas intensiver mit magischen Quadraten befasst. Es ist mir inzwischen auch gelungen Quadrate mit ungerader Kantenlänge zu lösen.
Nun gibt es aber leider auch Quadrate mit gerader Kantenlänge.
Dabei bin ich dank Google auf Backtracking und rekursive Lösungsverfahren gestoßen.
Soweit ich das nun verstanden habe, geht man dabei zum letzten Schritt zurück wenn man in einer Sackgasse landet.
Leider habe ich keinen Ansatz wie man so etwas bei magischen Quadraten umsetzen kann.
Weiß jemand wie man da ran gehen muss?

Mfg
Loud Silence

 

[TryToHelp]

Hab mich zwar nicht, bzw noch nicht mit diesem Thema beschäftigt.
Aber generell würde ich so vorgehen

Starte links oben in der Ecke mit der kleinsten Zahl
gehe durch dein Array nach rechts und nehme nächste kleinste mögliche Zahl
schaue ob die Lösüng bisher incorrect ist
wenn nicht, mache weiter
wenn incorrect, nehme größere Zahl
wenn jetzt corekkt mache weiter
wenn nicht und es ist größte zahl, lösche diese, gehe zum feld vorher und erhöhe diese und fahre fort

;-)

 

[Marco13]

Backtracking an sich ist so allgemein, dass das Verfahren, das auf Backtracking ? Wikipedia beschrieben ist, für alles mögliche (d.h. auch ein magisches Quadrat) verwendet werden könnte. Schreib' vielleicht nochmal genauer, was die Frage ist.

 

[Loud Silence]

Gut, die Frage lautet:
Wie kann ich ein Quadrat mit beispielsweise der Länge 4 so mit Zahlen füllen, dass sowohl Zeilen-, Spalten- & Diagonalensumme 34 ergeben.
Wie ist eigentlich egal, ich dachte nur, dass sich Backtracking speichersparend umsetzen lassen würde.

 

[Landei]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class MagicSquare {

    private final int size;
    private final int[][] values;
    private boolean solved;

    public MagicSquare(int size) {
        this.size = size;
        values = new int[size][size];
        fill();
    }

    private void fill() {
        List<Integer> numbers = getNumberList();
        solved = fillPos(0, numbers);
    }

    private boolean fillPos(int pos, List<Integer> candidates) {
        if (pos == size * size) {
            return true;
        }
        if (pos == -1) {
            return false;
        }
        int x = pos % size;
        int y = pos / size;

        for (int c : candidates) {
            List<Integer> newCandidates = new ArrayList<Integer>(candidates);
            newCandidates.remove(Integer.valueOf(c));
            values[x][y] = c;
            if (isValid() && fillPos(pos + 1, newCandidates)) {
                return true;
            }
        }
        values[x][y] = 0;
        return false;
    }

    private boolean isValid() {
        int sum = size * (size * size + 1) / 2;
        for (int x = 0; x < size; x++) {
            int s = 0;
            for (int y = 0; y < size; y++) {
                s += values[x][y];
            }
            if (s > sum) return false;
        }
        for (int y = 0; y < size; y++) {
            int s = 0;
            for (int x = 0; x < size; x++) {
                s += values[x][y];
            }
            if (s > sum) return false;
        }
        int s = 0;
        boolean full = true;
        for (int d = 0; d < size; d++) {
            full &= values[d][d] != 0;
            s += values[d][d];
        }
        if ((full && s != sum) || s > sum) return false;
        s = 0;
        full = true;
        for (int d = 0; d < size; d++) {
            full &= values[d][size-d-1] != 0;
            s += values[d][size-d-1];
        }
        if ((full && s != sum) || s > sum) return false;
        return true;
    }

    private List<Integer> getNumberList() {
        List<Integer> numbers = new ArrayList<Integer>();
        for (int i = 1; i <= size * size; i++) {
            numbers.add(i);
        }
        Collections.shuffle(numbers);
        return numbers;
    }

    public int[][] getValues() {
        return values;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int[] row : values) {
            sb.append(Arrays.toString(row)).append("\n");
        }
        return sb.toString();
    }


    public static void main(String... args) {
        System.out.println(new MagicSquare(4));
    }
}

Ziemlich lahm, kann man sicher noch wesentlich schneller machen. Aber es geht ja um's Prinzip...

 

[Loud Silence]

Wow, Information Overflow.
Erstmal danke für diese Komplettlösung!
Leider blick ich da noch nicht ganz durch.
Könnten Sie vllt. in Worten beschreiben, wie sie das Problem gelöst haben?

 

[Landei]

Das Backtracking findet in fillPos statt. fillPos bekommt die zu besetzende Position und die "restlichen" Zahlen übergeben. Bin ich über das letzte Feld hinaus (size*size), bin ich fertig. Der Test mit pos == -1 ist Schwachsinn, sehe ich gerade (zumindest in dieser Version). Dann probiere ich für die erste Kandidatenzahl aus, ob sie die Bedingungen verletzt (isValid) und falls ja, versuche ich, rekursiv das nächste Feld zu füllen. Klappt das, bin ich fertig, klappt das nicht, probiere ich die nächste Kandidatenzahl aus.

In "astreinem" Backtracking würde ich jeweils die Änderungen zurücknehmen, wenn ich nicht weiterkomme. Das tue ich hier nur für values, aber nicht für die Kandidatenliste. Dadurch, dass ich sie mir "merke" (in dem ich dem rekursiven fillPos--Aufruf nur eine Kopie mitgebe), spare ich mir das. Das sollte z.B. mit einem Stack gehen. Genaugenommen ist das hier also "nur" eine Art Tiefensuche, aber die Arbeitsweise prinzipiell doch fast dieselbe wie bei "echtem" Backtracking.

 

[Loud Silence]

Was mir nur nicht so klar ist:
Nach welchem logischen Schema wird hier vorgegangen?
Das einzige, das mir einfallen würde ist die zahlen von eins bis 16 einzutragen und dann durchzutauschen.
Das erscheint mir nur sehr umständlich und zeitintensiv.

 

[Landei]

Na ja, Backtracking ist halt im Prinzip nur strukturiertes Durchprobieren. Wenn man eine "logische" Vorgehensweise ableiten könnte, würde man kein Backtracking nehmen. Entscheidend ist, wie gut man den Suchraum einschränken kann, und wie groß damit der Suchbaum wird.

 

[Loud Silence]

Aber ich verstehe nicht wie Sie durchprobieren.
Nach welcher Methode gehen sie vor?
Oben links die eins und dann weiter füllen?
Wenn ja wie?

 

[TryToHelp]

...

    private List<Integer> getNumberList() {
        List<Integer> numbers = new ArrayList<Integer>();
        for (int i = 1; i <= size * size; i++) {
            numbers.add(i);
        }
        Collections.shuffle(numbers);
        return numbers;
    }

...

Hier die Stelle könnte es dir erklären. er erstellt ein Array und tut den inhalt mischen

Collections.shuffle(numbers);

und danach geht er dann mit dieser lisste durch das zu füllende Feld und probiert solange bis er eine lösung findet ;-)

 

[Loud Silence]

Was ich nur noch nicht verstehe:
Wie kann ich frühzeitig feststellen, dass die gerade hineingeschriebene Zahl nicht gültig, also falsch, ist?
Und das ohne vorher alle Zahlen eingetragen zu haben.

 

[Marco13]

Das ist der Knackpunkt. Es gibt drei Möglichkeiten, beim Backtracking auch nur den Hauch einer Chance zu haben, für die nicht-ganz-schlechtesten Fälle eine einigermaßen vertretbare Laufzeit hinzubekommen:
- Pruning
- Pruning
- Pruning

Das heißt: Den "Suchbaum" möglichst klein zu halten, indem man möglichst früh feststellt, dass ein Zustand schon ungültig ist, und man gar nicht mehr weitersuchen muss. In etwas komplexeren Fällen driftet man da schnell in einen Bereich, wo es einen "Trade-Off" gibt:
- Mache ich eine aufwändige Überprüfung, die früh erkennt, dass die Suche abgebrochen werden kann? ODER
- Mache ich eine einfache Überprüfung, bei der zwar mehr durchsucht wird, die aber (weil sie so einfach ist) trotzdem schneller ist?

In diesem konkreten Beispiel: Landei hatte schon so eine 'isValid'-Methode gepostet. Ich habe sie nicht nachvollzogen, aber sie ist wohl sehr... straightforward. Ein Teil davon war

 private boolean isValid() {
        int sum = size * (size * size + 1) / 2;
        for (int x = 0; x < size; x++) {
            int s = 0;
            for (int y = 0; y < size; y++) {
                s += values[x][y];
            }
            if (s > sum) return false;
        }
...

Eine sehr offensichtliche Änderung, die möglicherweise (!!!) eine Optimierung sein könnte, wäre

 private boolean isValid() {
        int sum = size * (size * size + 1) / 2;
        for (int x = 0; x < size; x++) {
            int s = 0;
            for (int y = 0; y < size; y++) {
                s += values[x][y];
                if (s > sum) return false;
            }
        }
...

aber ob die schneller ist, ist ohne Benchmark praktisch nicht zu sagen.

 

[Loud Silence]

Wenn ich Landeis Quelltext richtig deute überprüft er damit Zeilen und Spaltensumme.
Wenn diese größer ist als die magische geforderte Zahl, so ist die eben eingetragene Zahl falsch.
Nur woher weiß ich dann welche Zahl ich korrigieren muss. Ich kann ja nicht einfach die zuletzt eingeschriebene Zahl löschen.

 

[Marco13]

Doch, genau das wird gemacht. Der Pseudocode für Backtracking ganz allgemein ist (aus dem Kopf, dürfte bei Wikipedia so ähnlich stehen)

Lösung findeLösung(Problem problem)
{
    if (problem.gelöst()) return lösung;
    else
    {
        List<Schritt> möglicheSchritte = findeAlleMöglichenSchritte();
        for (Schritt schritt : möglicheSchritte)
        {
            führeAus(schritt, problem);
            Lösung lösung = findeLösung(problem);
            if (lösung != null)
            {
                return lösung;
            }
            macheRückgängig(schritt, problem);
        }
    }
    return null;
}

Für das Magische Quadrat:

Quadrat findeLösung(Quadrat quadrat)
{
    if (quadrat.istRichtigAusgefüllt()) return quadrat;
    else
    {
        List<Feld> freieFelder = findeAlleFreieFelder();
        for (Feld feld : freieFelder)
        {
            setzeNächsteZahlAuf(feld, quadrat);
            Quadrat quadrat = findeLösung(quadrat);
            if (quadrat != null)
            {
                return quadrat;
            }
            nimmDieZuletztGesetzteZahlWiederWeg(feld, quadrat); // <- Da isses...
        }
    }
    return null;
}

 

[Landei]

Schön erklärt!

Für das Prinzip mal ein ganz einfaches Problem: Finde aufsteigende Zahlen, deren Summe 8 und deren Produkt 12 ist.

Fangen wir an...
1 ...
1,2 ...
1,2,3 -> Summe 6, Produkt 6
soweit so gut, aber wenn wir jetzt die 4 hinzunehmen, werden Summe und Produkt "überboten". Also ein Schritt zurück
1,2,4 -> Summe 7, Produkt 8
auch hier "überbietet" die nächste Zahl
1,2,5 -> Summe 8, Produkt 10
auch hier "überbietet" die nächste Zahl die Summe, und mit der 6 anstatt 5 haben wir auch sowieso schon zu viel bei der Summe. Also noch einen Schritt zurück!
1,3 ...
1,3,4 -> Summe 8, Produkt 12, Lösung gefunden.

 

[hüteüberhüte]

Gut, die Frage lautet:
Wie kann ich ein Quadrat mit beispielsweise der Länge 4 so mit Zahlen füllen, dass sowohl Zeilen-, Spalten- & Diagonalensumme 34 ergeben.
Wie ist eigentlich egal, ich dachte nur, dass sich Backtracking speichersparend umsetzen lassen würde.

Hier noch mal ein Vorschlag von mir:

    private static List<int[][]> bt(int[][] quadrat, int stufe, List<int[][]> quadrate) {
        if (stufe == 2 * 2) {
            // [0][0] [0][1]
            // [1][0] [1][1]
            if (quadrat[0][0] + quadrat[0][1] == 34
             && quadrat[1][0] + quadrat[1][1] == 34
             && quadrat[0][0] + quadrat[1][0] == 34
             && quadrat[0][1] + quadrat[1][1] == 34
          /* && quadrat[0][0] + quadrat[1][1] == 34 */
          /* && quadrat[0][1] + quadrat[1][0] == 34 */) {
                quadrate.add(new int[][]{{quadrat[0][0], quadrat[0][1]},
                                         {quadrat[1][0], quadrat[1][1]}});
            }
            return quadrate;
        }
        for (int i = 0; i <= 34; i++) {
            quadrat[stufe / 2][stufe % 2] = i;
            bt(quadrat, stufe + 1, quadrate);
        }
        return quadrate;
    }

    public static void main(String[] args) {
        List<int[][]> l = bt(new int[2][2], 0, new LinkedList<int[][]>());
        for (int[][] ises : l) {
            for (int[] is : ises) {
                for (int i : is) {
                    System.out.print(i);
                    System.out.print(' ');
                }
                System.out.println();
            }
            System.out.println();
        }
    }

Das funktioniert erst mal nur mit Quadraten der Länge 2. Prüfung der Diagonalensumme habe ich raus genommen:

Spoiler: Ausgabe

0 34 
34 0 

1 33 
33 1 

2 32 
32 2 

3 31 
31 3 

4 30 
30 4 

5 29 
29 5 

6 28 
28 6 

7 27 
27 7 

8 26 
26 8 

9 25 
25 9 

10 24 
24 10 

11 23 
23 11 

12 22 
22 12 

13 21 
21 13 

14 20 
20 14 

15 19 
19 15 

16 18 
18 16 

17 17 
17 17 

18 16 
16 18 

19 15 
15 19 

20 14 
14 20 

21 13 
13 21 

22 12 
12 22 

23 11 
11 23 

24 10 
10 24 

25 9 
9 25 

26 8 
8 26 

27 7 
7 27 

28 6 
6 28 

29 5 
5 29 

30 4 
4 30 

31 3 
3 31 

32 2 
2 32 

33 1 
1 33 

34 0 
0 34

Wenn abgebrochen werden soll, sobald genau ein Ergebnis gefunden wurde, muss dies zurückgegeben werden und innerhalb der For-Schleife geprüft werden, welches Ergebnis die nachfolgenden Aufrufe zurückgeben.

Jede Rekursion lässt sich auch iterativ schreiben, dazu einfach die i-s der jeweiligen Stufe merken/speichern.

 

[hüteüberhüte]

Ich hab dazu noch etwas, weils typischerweise am 8-Damen-Problem erklärt wird:

import java.util.Arrays;

public class AchtDamen {

    private static final int LÄNGE = 8;
    private final int[] brett = new int[LÄNGE];
    private int i = 1;

    public int[] nächsteLösung() {
        i--;
        return nächsteLösung2();
    }

    private int[] nächsteLösung2() {
        if (vollständig()) {
            if (richtig()) {
                return brett;
            } else {
                i--;
            }
        }
        if (brett[i] < LÄNGE) {
            brett[i++]++;
        } else {
            brett[i--] = 0;
        }
        return nächsteLösung2();
    }

    private boolean vollständig() {
        return i == LÄNGE;
    }

    private boolean richtig() {
        // Reihe, Spalte, Diagonale usw.
        return Math.random() < 0.001; // ~0,1%
    }

    public static void main(String[] args) {
        AchtDamen ad = new AchtDamen();
        for (int i = 0; i < 10; i++) {
            System.out.println(Arrays.toString(ad.nächsteLösung()));
        }
    }
}

Eine vollständige Lösung ist mit einer Wahrscheinlichkeit von 0,1% richtig. richtig-Methode müsste man entsprechend ergänzen, aber das war mir jetzt zu fummelig.

brett[i--] = 0;

und

i--;

ist der Schritt zurück. Hth.

Edit: Ach So, man müsste vielleicht noch einen System.arraycopy-Aufruf einbauen, damit der Aufrufer das zurückgegebene Array nicht manipulieren kann. Aber selbst wenn, die Klasse/Instanz würde trotzdem funktionieren.

 

[JohannisderKaeufer]

@hüteüberhüte Ähm, bei einem magischen Quadrat geht es darum das in jeder Zelle eine andere Zahl steht. Sonst ist das "Problem" trivial, weil dann macht man ein Quadrat mit lauter Einsen oder lauter Nullen.

Die 34 Rühren daher, dass bei einem 4x4 Quadrat die Zahlen von 1 bis 16 jeweils einmal vorkommen sollen. Und die Summe der Zahlen von 1 bis 16 ist 136, womit 34 als Summe für jede Zeile und Spalte übrigbleiben.

 

[hüteüberhüte]

@hüteüberhüte Ähm, bei einem magischen Quadrat geht es darum das in jeder Zelle eine andere Zahl steht. Sonst ist das "Problem" trivial, weil dann macht man ein Quadrat mit lauter Einsen oder lauter Nullen.

Ok, nur Einsen wäre ja auch straightforward. Aber normalerweise sollte meine Methode richtig() Lösungen mit nur Einsen ausschließen, wenn sie denn richtig implementiert worden wäre. Hier habe ich nochmal eine verbesserte Version:

import java.util.Arrays;

public class AchtDamen {

    private static final int LÄNGE = 8;
    private final int[] brett = new int[LÄNGE];
    private final boolean[] belegt = new boolean[LÄNGE + 1];
    private int i = 1;

    public int[] nächsteLösung() {
        i--;
        int[] lösung = new int[LÄNGE];
        System.arraycopy(nächsteLösungBT(), 0, lösung, 0, LÄNGE);
        return lösung;
    }

    private int[] nächsteLösungBT() {
        if (!richtig()) {
            i--;
            return nächsteLösungBT();
        }
        if (vollständig()) {
            return brett;
        }
        brett[i] = nächstesFeld();
        if (brett[i] == 0) {
            System.out.println("Hallo");
            i--;
        } else {
            i++;
        }
        return nächsteLösungBT();
    }

    private boolean richtig() {
        // Reihe, Spalte, Diagonale usw.
        return true;
    }

    private boolean vollständig() {
        return i == LÄNGE;
    }

    private int nächstesFeld() {
        final int altesFeld = brett[i];
        belegt[altesFeld] = false;
        for (int neuesFeld = altesFeld + 1; neuesFeld < LÄNGE + 1; neuesFeld++) {
            if (!belegt[neuesFeld]) {
                belegt[neuesFeld] = true;
                return neuesFeld;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        AchtDamen ad = new AchtDamen();
        for (int i = 0; i < 20; i++) {
            int[] lösung = ad.nächsteLösung();
            System.out.println(Arrays.toString(lösung));
        }
    }
}

Spoiler: Ausgabe

[1, 2, 3, 4, 5, 6, 7, 8]
Hallo
[1, 2, 3, 4, 5, 6, 8, 7]
Hallo
Hallo
[1, 2, 3, 4, 5, 7, 6, 8]
Hallo
[1, 2, 3, 4, 5, 7, 8, 6]
Hallo
Hallo
[1, 2, 3, 4, 5, 8, 6, 7]
Hallo
[1, 2, 3, 4, 5, 8, 7, 6]
Hallo
Hallo
Hallo
[1, 2, 3, 4, 6, 5, 7, 8]
Hallo
[1, 2, 3, 4, 6, 5, 8, 7]
Hallo
Hallo
[1, 2, 3, 4, 6, 7, 5, 8]
Hallo
[1, 2, 3, 4, 6, 7, 8, 5]
Hallo
Hallo
[1, 2, 3, 4, 6, 8, 5, 7]
Hallo
[1, 2, 3, 4, 6, 8, 7, 5]
Hallo
Hallo
Hallo
[1, 2, 3, 4, 7, 5, 6, 8]
Hallo
[1, 2, 3, 4, 7, 5, 8, 6]
Hallo
Hallo
[1, 2, 3, 4, 7, 6, 5, 8]
Hallo
[1, 2, 3, 4, 7, 6, 8, 5]
Hallo
Hallo
[1, 2, 3, 4, 7, 8, 5, 6]
Hallo
[1, 2, 3, 4, 7, 8, 6, 5]
Hallo
Hallo
Hallo
[1, 2, 3, 4, 8, 5, 6, 7]
Hallo
[1, 2, 3, 4, 8, 5, 7, 6]

Richtig schön wärs, wenn auch diesmal richtig() richtig implementiert worden wäre. Außerdem ist es jetzt ja ein Leichtes, die rekursive Methode in eine iterative umzuwandeln.

Die 34 Rühren daher, dass bei einem 4x4 Quadrat die Zahlen von 1 bis 16 jeweils einmal vorkommen sollen. Und die Summe der Zahlen von 1 bis 16 ist 136, womit 34 als Summe für jede Zeile und Spalte übrigbleiben.

Ehrlich gesagt kann ich mir noch nichts richtiges unter einem Magischen Quadrat vorstellen. Habe nur bis Backtracking gelesen und wollte dann ein typisches BT-Problem zur Demonstration schreiben.

Vielen Dank für deine Antwort