Algorithmus für Zifferngruppierung

cfHxqA

Lieutenant
Registriert
Feb. 2012
Beiträge
621
Hallo!,

ich habe ein Spielfeld, das eine festgelegte Höhe und Breite besitzt. In diesem Spielfeld sind Zahlen festgelegt, welche Horizontal als auch Vertikal mit der gleichen, Gruppiert werden können - das Minimum ist jedoch Drei.

Kennt jemand einen passenden Algorithmus um das zu bewerkstelligen!? Am besten wäre noch in C#. ;)
 
Zuletzt bearbeitet:
1. Die Beschreibung deines Problems ist nicht sehr verständlich. Das solltest du vielleicht etwas genauer beschreiben, möglicherweise mit einem Beispiel veranschaulichen.
2. Wie weit bist du denn bis jetzt gekommen? Was ist dein Ansatz?
3. Fertigen C# Code wirst du wohl eher nicht bekommen, irgend etwas musst du ja schließlich auch selber machen. Nur andere für dich arbeiten lassen läuft nicht.

Gruß
BlackMark
 
Für mich klingt das was Du fragen wolltest nach einem Algorithmus zum Mienen verteilen bei Minesweeper, stimmt das? Oder ist es wenigstens so ähnlich?
 
Sorry!

Das Spielfeld hat stets eine feste größe von 8x8 Feldern. Jedes Feld kann Zahlen von 1-64 festhalten, die Zahlen in den Feldern sind natürlich willkürlich durch das gesamte Spielfeld gewürfelt. Es geht darum, die Zahlen zu Gruppieren. Das heißt, es dürfen nur gleiche Zahlen miteinander verknüpft werden. Demzufolge, 64 + 64, 1 + 1, etc. Es müssen jedoch mindestens Drei oder mehr sein. Ob es nun Vertikal oder Horizontal ist, spielt keine Rolle.

Ich bin jetzt auf der Suche nach einem Algorithmus, um die Möglichen Kombinationen in einem Spielfeld zu ermitteln, die mindestens eine Gruppierung von Drei oder mehr Möglichkeiten geben, oder um eben diese Aufzulisten..
 
Zuletzt bearbeitet:
Du hast 8x8 (8*8=64) Felder und belegst jedes Feld mit einer zufälligen Zahl zwischen 1 und 64? Das heißt im Worst Case hast du 64 verschiedene Zahlen und kannst gar nichts gruppieren?!
Außerdem wie funktioniert das Gruppieren? Kann man diese Felder beliebig anordnen? Oder immer nur zwei vertauschen? Kann man nur dann Felder ändern wenn dadurch eine Dreiergruppe entsteht? Oder ist das Ziel nur, dass alle möglichen Dreiergruppen gebildet werden und die restlichen Felder egal sind?
Eine Dreiergruppe kann nur vertikal oder horizontal gebildet werden? Also nicht diagonal, oder als Rechteck?

Komm schon, du musst dein Problem schon genau darstellen, sonst kann dir niemand helfen!

Gruß
BlackMark
 
BlackMark schrieb:
Du hast 8x8 (8*8=64) Felder und belegst jedes Feld mit einer zufälligen Zahl zwischen 1 und 64? Das heißt im Worst Case hast du 64 verschiedene Zahlen und kannst gar nichts gruppieren?!

Glaskugel: Er würfelt für jedes Feld erstmal "1 + RAND(0,1) * 64" und scheibt es dann dort rein. Jetzt vergleicht er alle Felder und sucht nach N Clustern (Felder mit gemeinsamer "Kante") mit gleichen Zahlen der Clustergröße M >= 3, ohne periodische Randbedingungen zu berücksichtigen. Klar, kann die Clustergrößenverteilung auch 0 x oder 64 x "1" o. ä. lauten ;)

Insgesamt hat er also 64^64 (~ 4 x 10^115) Möglichkeiten. Viel Spass.
 
Zuletzt bearbeitet:
blöderidiot schrieb:
Insgesamt hat er also 64^64 (~ 4 x 10^115) Möglichkeiten. Viel Spass.
Oh lol .. so schwer ist das nun auch wieder nicht, hier ein kleines Beispiel in C#
Code:
        private void TestArray() {
            Random rnd = new Random();

            // Array erstellen
            int[][] array = new int[8][];
            for (int i = 0; i < 8; i++)
                array[i] = new int[8];

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    // Zufallswerte hier auf 1-3 beschränkt damit die Warscheinlichkeit das mehrere gleiche Neben/Übereinanderstehen höher ist
                    int rndval = rnd.Next(3) + 1;
                    array[i][j] = rndval;
                    sb.Append(rndval);
                    sb.Append('|');
                }
                sb.Append('\n');
            }

            // Ganzes Array ausgeben damit man sehen kann wo gleiche sind ..
            Console.WriteLine(sb.ToString());

            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    // Gleiche Treffer rechts suchen
                    int count = SearchRight(array, i, j, 0);
                    if (count >= 3) {
                        // 3 oder mehr gleiche? Dann ausgeben
                        Console.WriteLine("Position:" + i + "," + j + ": " + array[i][j] + " horizonal " + (count+1) + " mal");
                        // Und Position in X erhöhen damit nicht bei z.B 4 gleichen auch nochmal 3 gleiche ausgegeben wird ..
                        j += count - 1;
                    }
                }
            }
            for (int j = 0; j < 8; j++) {
                for (int i = 0; i < 8; i++) {
                    // Gleiche Treffer unten suchen
                    int count = SearchDown(array, i, j, 0);
                    if (count >= 3) {
                        // 3 oder mehr gleiche? Dann ausgeben
                        Console.WriteLine("Position:" + i + "," + j + ": " + array[i][j] + " vertikal " + (count + 1) + " mal");
                        // Und Position in Y erhöhen damit nicht bei z.B 4 gleichen auch nochmal 3 gleiche ausgegeben wird ..
                        i += count - 1;
                    }
                }
            }
        }

        private int SearchRight(int[][] array, int i, int j, int count) {
            // Arraygrenze noch nicht überschritten und dieses Feld gleich dem nächsten daneben ?
            if (j < 7 && array[i][j] == array[i][j + 1]) {
                // Anzahl erhöhen
                count++;
                // X erhöhen
                j++;
                // Weitersuchen
                return SearchRight(array, i, j, count);
            }
            return count;
        }

        private int SearchDown(int[][] array, int i, int j, int count) {
            // Arraygrenze noch nicht überschritten und dieses Feld gleich dem nächsten darunter ?
            if (i < 7 && array[i][j] == array[i + 1][j]) {
                // Anzahl erhöhen
                count++;
                // Y erhöhen
                i++;
                // Weitersuchen
                return SearchDown(array, i, j, count);
            }
            return count;
        }
 
So schwer ist das nicht? Denkst du nicht auch, dass der Speicher- und Rechenzeitbedarf doch etwas variiert, je nach dem, ob man - wie in deinem Beispiel - 262 144 Möglichkeiten hat oder aber 39402006196394479212279040100144000000000000000000000000000000000000000000000000000000000000000000000000000000000000?

Davon ab testest du in dem Code ja nur 64 zufällige Verteilungen und nicht mal alle 262000 Fälle.
Wenn es also darum geht, zu errechnen, wie viele solcher Möglichkeiten es gibt ist mMn Brute Force nicht wirklich geeignet.
 
lynxx schrieb:
Oh lol .. so schwer ist das nun auch wieder nicht, hier ein kleines Beispiel in C#
Code:
        private void TestArray() {
            Random rnd = new Random();

            // Array erstellen
            int[][] array = new int[8][];
            for (int i = 0; i < 8; i++)
                array[i] = new int[8];

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    // Zufallswerte hier auf 1-3 beschränkt damit die Warscheinlichkeit das mehrere gleiche Neben/Übereinanderstehen höher ist
                    int rndval = rnd.Next(3) + 1;
                    array[i][j] = rndval;
                    sb.Append(rndval);
                    sb.Append('|');
                }
                sb.Append('\n');
            }

            // Ganzes Array ausgeben damit man sehen kann wo gleiche sind ..
            Console.WriteLine(sb.ToString());

            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    // Gleiche Treffer rechts suchen
                    int count = SearchRight(array, i, j, 0);
                    if (count >= 3) {
                        // 3 oder mehr gleiche? Dann ausgeben
                        Console.WriteLine("Position:" + i + "," + j + ": " + array[i][j] + " horizonal " + (count+1) + " mal");
                        // Und Position in X erhöhen damit nicht bei z.B 4 gleichen auch nochmal 3 gleiche ausgegeben wird ..
                        j += count - 1;
                    }
                }
            }
            for (int j = 0; j < 8; j++) {
                for (int i = 0; i < 8; i++) {
                    // Gleiche Treffer unten suchen
                    int count = SearchDown(array, i, j, 0);
                    if (count >= 3) {
                        // 3 oder mehr gleiche? Dann ausgeben
                        Console.WriteLine("Position:" + i + "," + j + ": " + array[i][j] + " vertikal " + (count + 1) + " mal");
                        // Und Position in Y erhöhen damit nicht bei z.B 4 gleichen auch nochmal 3 gleiche ausgegeben wird ..
                        i += count - 1;
                    }
                }
            }
        }

        private int SearchRight(int[][] array, int i, int j, int count) {
            // Arraygrenze noch nicht überschritten und dieses Feld gleich dem nächsten daneben ?
            if (j < 7 && array[i][j] == array[i][j + 1]) {
                // Anzahl erhöhen
                count++;
                // X erhöhen
                j++;
                // Weitersuchen
                return SearchRight(array, i, j, count);
            }
            return count;
        }

        private int SearchDown(int[][] array, int i, int j, int count) {
            // Arraygrenze noch nicht überschritten und dieses Feld gleich dem nächsten darunter ?
            if (i < 7 && array[i][j] == array[i + 1][j]) {
                // Anzahl erhöhen
                count++;
                // Y erhöhen
                i++;
                // Weitersuchen
                return SearchDown(array, i, j, count);
            }
            return count;
        }

Du bist mein Retter! Hat super geklappt! Ich habe mich tatsächlich zu schwammig ausgedrückt. Ich werde mir den Quellcode zu gemühte führen und mich damit intensiv auseinandersetzen! Herzlichen Dank noch einmal!!

Das ganze geht fast in die Richtung, wie Candy Crush. Nur das ich eben die Zahlen vorgegeben habe, statt irgendwelcher Bilder. Da hätte ich eher auf FloodFill, oder wie sich das alles schimpft, zurückgreifen können. Dennoch danke für eure bemühungen! ;)
 
Äh, ja.
Dass er aus deinem Geschwurbel überhaupt ableiten konnte was du wolltest grenzt schon an Gedankenleserei O.o Nur so fürs nächste mal: -Spielfeld kann über den Rand erweitert werden? Was heißt gruppieren? Was willst du überhaupt (Liste aller Spielfelder, Liste aller Lösungen, nur gucken ob ein Spielfeld eine Gruppierung enthält), warum ist die Aufgabe wie sie ist(8x8 Spielfelder ist bei 64 möglichen Werten totaler Bullshit, da hast du Glück wenn überhaupt eine Gruppierung dabei ist) und was soll das für ein Spiel sein, bei dem du einfach nur guckst, ob was gruppierbar ist?

Bei jedem Spiel liegt ein Buch mit Regeln bei, zumindest das hättest du uns geben müssen um irgendwas mit deiner Frage anfangen zu können...
 
Also so wie ich das jetzt verstanden habe:
Es gibt ein Spielfeld mit Zahlen. In gewissen Abständen (nach jedem Zug oder so) soll geprüft werden, ob sich 3 Ziffern in irgendeiner Weise berühren?

Falls ja ist es recht einfach:
1. gehe alle Felder der Reihe nach durch
2. gucke, ob das Feld links oder darüber den selben Wert hat wie das aktuelle Feld
2.1. falls ja: speichere das aktuelle Feld in der Liste des entsprechenden anderen Feldes
2.1.1. falls an beiden Kanten verschiedene Listen mit dem selben Wert angrenzen, verbinde die Listen zu einer neuen
2.2. falls nein, lege eine Liste für dieses Feld an

Am Ende hast du dann 1 bis 64 Listen mit Feldern die sich berühren und die selben Werte besitzen.

Falls diese Zahlen per Zufall in die Felder eingetragen werden: Das geht nicht lange gut.
Bei 64 Feldern, 64 Möglichkeiten pro Feld und einer Gruppierung von mindestens 3 ist es schon recht unwahrscheinlich auch nur eine Gruppe zu finden. Ich würde sagen 8 Möglichkeiten sollten hier das Höchstmaß sein.
 
Zurück
Oben