Anzahl der möglichen Android Speermuster eines 4x4-Gitters berechnen?

[das weiß ich!]

Guten Abend,

hat jemand einen Plan, wie das funktionieren könnte oder wie man an diese Fragestellung herangehen könnte? Thy for any help : )

 

[KonradN]

Das ist doch eine Größenordnung, die man durch einfache Tests herausfinden kann.

• Formuliere die exakten Regeln, was erlaubt ist (also keine Dopplungen, überspringen einer gezogenen Zahl ist erlaubt und nur vertikal, horizontal oder diagonal)
• Dann probierst du es einfach aus in einem Programm - geh dazu einfach alle Möglichkeiten durch (4 Schleifen, die verschachtelt sind, die von 0…15 gehen und immer die Gültigkeit prüfen … das sind dann max 16^4 Kombinationen, die zu prüfen wären (da jede Schleife bis auf die erste direkt prüft, deutlich weniger - auf die erste Ziffer gibt es halt max. 8 gültige Folgeziffern und damit wird bei mind 8 Fällen direkt abgebrochen …Evtl. Macht es auch Sinn, die Schleifen einfach so aufzubauen:
• erste Schleife 0…15
• 2-4 Schleife von 0…8 (die 8 erlaubten Richtungen - so es diese sein sollen. Evtl. Erlaubt man ja mehr Richtungen wie „Springerzüge“?)

So ein Algorithmus sollte also einfach und schnell aufgebaut werden können …

 

[KonradN]

Wenn du natürlich auch Längen von mehr als 4 Ziffern haben willst, dann wird das einfach erweitert um weitere Schleifen … mit dem Ansatz der 8 Richtungen hat man dann max. zu prüfen: 33.554.432 - das ist also noch eine machbare Größe denke ich, da vieles schnell entfällt ….

 

[Hansen_07]

Bevor Tobi noch mehr Zeit in Anspruch nimmt: Crosspost (Byte-Welt)

 

[mihe7]

Bei 16 Möglichkeiten und einer Länge von 16 ist 16^16 eine absolute obere Schranke, die aufgrund der Einschränkungen bei weitem niemals erreicht werden kann: 18.446.744.073.709.551.616, also knapp 18,5 Trillionen.

Das kann man besser abschätzen, wenn man die Einschränkung berücksichtigt, dass jeder Knoten im Grid nur einmal besucht werden kann. Bei einem 4x4-Grid gibt es "16 über n"-Möglichkeiten, n Zahlen auszuwählen. Jeder dieser Kombinationen kann in n! Reihenfolgen dargestellt werden. Eine obere Grenze ist also 16!/(16 - n)!. Bei einem 3x3-Grid entsprechend 9!/(9 - n)!.

Aber auch das ist noch weit von den tatsächlichen Möglichkeiten entfernt, da weitere Einschränkungen gelten. Schon bei einem Muster der Länge 2 stimmt der Spaß nicht mehr, weil in dem Fall ausschließlich "benachbarte" Knoten gewählt werden können. Und ab da wird es halt kompliziert.

In einem 3x3-Grid sind von einem Punkt aus 8 Knoten erreichbar, allerdings gilt die Einschränkung, dass kein Knoten übersprungen werden darf. Die 8 Nachbarn sind also tatsächlich nur vom Mittelpunkt aus erreichbar. Von einem Eckpunkt aus sind die anderen drei Eckpunkte nicht erreichbar (es bleiben 5 Möglichkeiten), von einem Randpunkt aus ist der gegenüberliegende Randpunkt nicht erreichbar (7 Möglichkeiten). Es gibt vier Eckpunkte, vier Randpunkte und einen Mittelpunkt, macht also 4 * 5 + 4 * 7 + 8 = 56 Möglichkeiten.

In einem 4x4-Grid sieht das ganz anders aus. Da gibt es keinen Mittelpunkt, sondern 4 "Innenpunkte", 8 Randpunkte und 4 Eckpunkte. Von einem Eckpunkt aus sind 6 Knoten nicht erreichbar, bleiben 9 Nachbarn übrig. Von einem Randpunkt aus sind es 4 (2 horizontal, 1 vertikal, 1 diagonal), die nicht erreicht werden können, verbleiben 11 Nachbarn. Und von einem inneren Punkt aus kann eben nur noch 1 horizontal, 1 vertikal und 1 diagonal nicht erreicht werden, bleiben 12 Nachbarn. Zusammen macht das 4 * 12 + 8 * 11 + 4 * 9 = 172 Möglichkeiten.

Und das war jetzt nur einmal die noch verhältnismäßig einfache Überlegung für 2 Knoten. Noch lustiger wird das bei 3 Knoten, denn ab da können Knoten übersprungen werden, außerdem muss man den bisherigen Pfad berücksichtigen...

Bleiben wir mal beim 4x4-Grid. Wenn ich bei drei Knoten einen Knoten überspringen möchte, kann das nur der Startpunkt sein. Startet man in einem Eckpunkt ist ein Überspringen somit nicht möglich, bei Randpunkten ist das entlang des Rands möglich und bei inneren Punkten geht es in jede Richtung.

Beginnen wir also mit einem Eckpunkt, kann ich 9 Nachbarn erreichen. Davon sind 3 innere Punkte, der Rest sind Randpunkte. Habe ich einen inneren Punkt erreicht, so sind es jetzt keine 12 Nachbarn mehr, sondern nur noch 11, weil der Startpunkt ja wegfällt, bei einem Randpunkt sind es 10. Von einem Eckpunkt aus kann ich also 3 * 11 und 6 * 10 Punkte erreichen, macht 93 Punkte. Es gibt vier Eckpunkte, also 372 Punkte.

Starten wir mit einem Randpunkt, kann ich 11 Nachbarn erreichen, diese teilen sich in 3 Eckpunkte, 5 Randpunkte und 3 innere Punkte auf. Nach der Überlegung von oben wüden für jeden Eckpunkt 8, für jeden Randpunkt 10 und für jeden inneren Punkt 11 Nachbarn übrig bleiben. Allerdings kommt jetzt hinzu, dass der Randpunkt von zwei Punkten aus übersprungen werden kann. Macht also 3 * 8 (Eckpunkte) + 5 * 10 (Randpunkte) + 3 * 11 (innere Punkte) + 2 (Überspringer) = 109 Möglichkeiten. Es gibt 8 Randpunkte, also 872 Möglichkeiten.

Wenn wir mit einem inneren Punkt starten, können wir 12 Nachbarn erreichen, das sind 3 Eckpunkte, 3 innere Punkte, und 6 Randpunkte. Im 4x4-Grid ist ein Überspringen nur von den direkt angrenzenden Knoten aus möglich, das sind 8 Stück.

Macht also 3 * 8 (Eckpunkte) + 3 * 11 (innere Punkte) + 6 * 10 (Randpunkte) + 8 (Überspringer) = 125 Möglichkeiten. Es gibt 4 innere Punkte, also 500 Möglichkeiten.

Zusammen: 372 (Start im Eck) + 872 (Start am Rand) + 500 (Start innen) = 1744 Möglichkeiten

Bis dahin war das ja noch einigermaßen machbar, aber schon bei vier Knoten hört es auf, denn jetzt müsste man zusätzlich berücksichtigen, wo genau der Startknoten liegt. Das wären übrigens 16.880 Möglichkeiten, bei fünf Knoten 154.680, bei sechs 1.331.944, bei sieben 10.690.096, acht (da fängt es auf meiner Möhre an, dass man die Berechnung merkt) 79.137.824, bei neun (dauert schon 35 Sekunden) 533.427.944, bei zehn (knapp 4 Minuten) 3.221.413.136. Und den Rest überlasse ich anderen 😂

Allerdings kann man sehen, dass das Verhältnis der Möglichkeiten bei Zunahme der Länge abnimmt: von 16 auf 172 sind es 10.75, von 172 auf 1744 sind es etwa 10.14, von 1744 auf 16880 sind es ca. 9.68, es folgen 9.16, 8.61, 8.02, 7.22, 6.74, 6.04. Man kann also schon abschätzen, dass es bei 11 etwas weniger als 19.457.335.341 sein werden. Ich würde mich sogar aus dem Fenster lehnen und behaupten, dass es weniger als 17.511.601.807 sind.

Okay, ich lass die Möhre mal die 11 noch berechnen...

23 Minuten später: 17.068.504.632, gar nicht mal so schlecht geschätzt.

Genug des Blödsinns.

 

[war ich das?]

4 Schleifen, die verschachtelt sind, die von 0…15 gehen und immer die Gültigkeit prüfen

Hallo, meinen Sie das in etwa so?

        for (int a = 1; a <= 16; a++) {
            for (int b = 1; b <= 16; b++) {
                for (int c = 1; c <= 16; c++) {
                    for (int d = 1; d <= 16; d++) {
                        // 4
                    }
                }
            }
        }

        for (int a = 1; a <= 16; a++) {
            for (int b = 1; b <= 16; b++) {
                for (int c = 1; c <= 16; c++) {
                    for (int d = 1; d <= 16; d++) {
                        for (int e = 1; e <= 16; e++) {
                            // 5
                        }
                    }
                }
            }
        }

        for (int a = 1; a <= 16; a++) {
            for (int b = 1; b <= 16; b++) {
                for (int c = 1; c <= 16; c++) {
                    for (int d = 1; d <= 16; d++) {
                        for (int e = 1; e <= 16; e++) {
                            for (int f = 1; f <= 16; f++) {
                                // 6
                            }
                        }
                    }
                }
            }
        }

        for (int a = 1; a <= 16; a++) {
            for (int b = 1; b <= 16; b++) {
                for (int c = 1; c <= 16; c++) {
                    for (int d = 1; d <= 16; d++) {
                        for (int e = 1; e <= 16; e++) {
                            for (int f = 1; f <= 16; f++) {
                                for (int g = 1; g <= 16; g++) {
                                    // 7
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int a = 1; a <= 16; a++) {
            for (int b = 1; b <= 16; b++) {
                for (int c = 1; c <= 16; c++) {
                    for (int d = 1; d <= 16; d++) {
                        for (int e = 1; e <= 16; e++) {
                            for (int f = 1; f <= 16; f++) {
                                for (int g = 1; g <= 16; g++) {
                                    for (int h = 1; h <= 16; h++) {
                                        // 8
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

Brauche ich nicht noch eine zusätzliche Datenstruktur oder ähnliches?

Und ich habe mich im Titel verschrieben, es sollte Sperrmuster lauten, nicht "Speer...", Danke

 

[KonradN]

Ich habe nur Anregungen gegeben und keinen ganz konkreten Algorithmus vorgeschlagen. Hier muss man natürlich verfeinern, wie die weiterführenden Erläuterungen doch zeigen sollten.

Ok, Tobias will wohl nur trollen, aber falls da jemand über den Thread kommt kann man ganz dumme Fehler direkt aufzeigen:

a) Bei Fehlschlägen muss direkt abbrechen. Also wenn man in den Schleifen 1,1 hat, dann ist der Anfang ungültig … also ist es Quatsch, weiter vor zu gehen.
b) wieso mehrmals so verschachtelte Schleifen? Die 4 verschachtelten Schleifen sind ja in den 5en auch drin. Und diese in den 6 und so weiter … also doch ganz offensichtlich doppelter Code und damit auch doppelte Ausführung ….
c) Man sollte die Größe der Schleifen auch klein halten … eine Schleife über 8 Elemente ist deutlich schneller als über 16 Elemente … daher macht es Sinn, die Richtungen zu nutzen … Der Vorteil ist schnell klar: 8^8 und 16^8 - das macht schon einen deutlichen Unterschied …

Und wenn man sich überlegt, was für Checks man machen muss, dann ist das mit den Richtungen auch deutlich einfacher zu handhaben …

Und dann überlegen wir uns doch mal wirklich, wie wir sowas aufbauen könnten. 4x4 Felder - kann man nummerieren von 0..15 was Hexadezimal wäre … passt gut, denn da haben wir dann 4 Bit und die ersten zwei geben die Reihe und die anderen beiden die Spalte so dass wir schnell umrechnen können.
Datenstrukturen? Man kann sowas in ein Array oder eine Liste schreiben … oder wir nutzen einfach Strings mit Zeichen 0..F

Das kann man mit Schleifen machen, aber Brute Force parallelisiert man am Besten. Schleifen sind da aber eher ungeeignet. Also denken wir das einfach neu. Wir bauen in den Schleifen doch (Teil)Codes auf um diese dann zu erweitern. Und diese fangen am Anfang an mit 0 1 2 … F …
Wenn wir einen Code probieren, nehmen wir so einen Teilcode und schauen, ob wir den erweitern können … dazu prüfen wir die 8 Richtungen …
Haben wir eine Richtung, die geht, dann hängen wir das gefundene Element ab und haben einen neuen Teilcode.

• Hat dieser die notwendige Länge (das war als 4 Zeichen angegeben), dann haben wir einen gültigen Code und den wollten wir zählen.
• Hat dieser noch nicht die maximale Länge, dann haben wir einen Code, den wir weiter verarbeiten müssen.

Also haben wir eine Codeverwaltung als eine Queue welche am Anfang mit 0..F gefüllt wird.
Da können. beliebige Worker sich Elemente entnehmen, um diese zu prüfen:

• das letzte Zeichen des Codes wird genommen um den Platz (Spalte und Reihe) zu ermitteln.
• da können wir dann die 8 Richtungen probieren: Ist das neue Feld ungültig: continue. Ist der Wert schon im String drin: Richtung erneut probieren und neu checken. Haben wir ein gültiges Feld, dann den Wert an den String anhängen. Minimale Länge erfüllt: zählen, keine maximale Länge erreicht: in Queue stecken

So haben wir nur Java Framework verwendet. Eigene Klassen machen aber natürlich Sinn zur Strukturierung des Codes. Und man kann es beliebig ausbauen: Statt nur ein Prozess mit mehreren Threads kann man das sogar in einem hpc Cluster laufen lassen… Oder so ausbauen, dass weltweit alle User mithelfen könnten …

Ist also eigentlich ein einfaches Teile und Herrsche Problem … ok, nicht für jeden …

 

[qmniodajaysp]

Ich glaube die Idee könnte sein einen Backtracking Ansatz zu verfolgen, ich befeile dass dies mit nur einer Schleife möglich ist, so schön Konrads Wall of text auch sein mag.

 

[KonradN]

Ja, wenn man Probleme hat, Texte zu verstehen, dann sind Antworten im Forum eine Herausforderung… und wenn jemand ausführliche Antworten schreibt, dann müssen die eine wahre Herausforderung sein für jemanden wie unseren Tobias.

Was für Erfahrungen hast du den mit einer KI gemacht, dir sowas erklären zu lassen? Zumal eine KI die Basics kann und daher kein Problem hat, die Lösung mit nur „einer Schleife“ zu verstehen … die KI wird vermutlich auch direkt sehen, dass es auch einfach nur der rekursiven Version entspricht und wird Dir dann auch die Kernelemente (was entspricht der Abbruchbedingung und dem rekursivem Aufruf) identifizieren und erklären können …

Aber das kannst du dann ja im anderen Forum diskutieren bzw. Dir da etwas helfen lassen können … Du scheinst da derzeit ja nicht gebannt zu sein …