Schrägen in einem zweidimensionalem Array durchlaufen

Die Programmiersprache C# und Programmierung im .NET Framework/Mono
Antworten
DerSamu
Beiträge: 35
Registriert: Sa Dez 23, 2017 3:15 pm

Schrägen in einem zweidimensionalem Array durchlaufen

Beitrag von DerSamu » Do Mär 15, 2018 7:49 pm

Hey mich plagt seit mehreren Tagen folgendes Problem:
Ich komme nicht darauf, wie man Schräge "Linien" in einem zweidimensionalem Array durchlaufen und überprüfen könnte.
Die Grundaufgabe ist das Damenproblem, also, dass 8 Damen auf einem 8x8 Schachbrett so platziert werden müssen, dass sie sich nicht gegenseitig schlagen können. Jetzt wollte ich einfach immer, wenn eine Dame gefunden wird(die Damenpositionen sind gegeben) überprüfen ob sich irgendwo vertikal, horizontal und eben schräg eine andere Dame befindet. Dann soll die Methode eben dementsprechend true oder false zurückgeben.
Aber wie kann ich das jetzt durchlaufen? Achja: Ich will nicht die Diagonalen durchlaufen, sondern eine beliebige Schräge in dem Array!
Hier ist zurzeit meine Methode IsValid, in der ich eben alles horizontal und vertikal durchlaufe.

Code: Alles auswählen

public static bool IsValid(bool[,] field) {
            bool isValid = true;         
            for (int i = 0; i < field.GetLength(0); i++) {      
                for (int j = 0; j < field.GetLength(1); j++) {
                    if (field[i, j]&&isValid) {
                        for (int k = 0; k < field.GetLength(0); k++) {
                            for (int l = 0; l < field.GetLength(1); l++) {
                                if (field[k, l]&&isValid) {
                                    isValid = false;
                                }
                            }
                        }
                    }
                }
            }
            return isValid;
        }
Ich hoffe das macht überhaupt Sinn was ich da gecodet habe...
lernender Programmierer, hauptsächlich C# und Java

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3076
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Schrägen in einem zweidimensionalem Array durchlaufen

Beitrag von cloidnerux » Do Mär 15, 2018 10:09 pm

Kleiner Code-Style Hinweis:
Du kannst dir das "isTrue" sparen und einfach mit

Code: Alles auswählen

return false; 
deine Funktion beenden, da sobald eine Bedingung nicht erfüllt ist das prüfen weiterer Bedingungen sein lassen kannst. Dann schreibst du am Ende

Code: Alles auswählen

return true;
weil wenn es bis dahin durchgelaufen ist, muss es valide sein.

Beliebige Schrägen durchlaufen ist etwas komplizierter, was aber gleich ist mit dem Problem von Linienrasterung: https://de.wikipedia.org/wiki/Rasterung_von_Linien
Eine andere Lösung ist, statt die Diagonalen Durchzulaufen, zu überprüfen ob eine Figur auf einer definierten Linie zu einer anderen steht. Die einfachste Möglichkeit dazu ist, mitt der Hessschen Normalenform zu arbeiten: https://de.wikipedia.org/wiki/Hessesche_Normalform
Wenn du den Normalenvektor (n = [sin phi, cos phi]) bestimmt hast und damit auch den Abstand "d", kannst du mit

Code: Alles auswählen

|n dot x - d|< e
bestimmen, ob der Punkt x weniger als e von der Linie entfernt ist.
Redundanz macht wiederholen unnötig.
quod erat expectandum

mfro
Beiträge: 302
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Schrägen in einem zweidimensionalem Array durchlaufen

Beitrag von mfro » Fr Mär 16, 2018 7:51 am

DerSamu hat geschrieben:... Achja: Ich will nicht die Diagonalen durchlaufen, sondern eine beliebige Schräge in dem Array!
eine "beliebige Schräge" auf einem Schachbrett *ist* eine Diagonale. Nur eben nicht zwingend die *Hauptdiagonale*.

Wie kommst Du nun von einem gegebenen Feld auf ein diagonal danebenliegendes? Die Randfelder mal beiseite gelassen, ein Bild sagt mehr als 1000 Worte:

Code: Alles auswählen

a    b
  \ /
   Z
  / \
c    d
Wenn Du von Z (x;y) auf ein diagonal anschliessendes Feld willst, führt
  • (x-1;y-1) nach a,
  • (x+1;y-1) nach b,
  • (x-1;y+1) nach c,
  • (x+1;y+1) nach d,
Die Randfelder wieder dazugenommen, musst Du nur noch prüfen, ob Du irgendwo anstösst. Macht's das für dich einfacher?
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

DerSamu
Beiträge: 35
Registriert: Sa Dez 23, 2017 3:15 pm

Re: Schrägen in einem zweidimensionalem Array durchlaufen

Beitrag von DerSamu » Di Mär 27, 2018 9:30 pm

Hey ich habe es jetzt verstanden wie ich es machen könnte, dank deiner Beschreibung. Das habe ich jetzt versucht:

Code: Alles auswählen

private static bool IsSolvedDiagonal(int colLength, int rowLength, int col, int row, int currentPlayer) {
            Boolean isSolved = false;
            int counter = 0;
            for (int i = 0; i < Board.GetLength(0); i++) {
                for (int j = 0; j < Board.GetLength(1); j++) {
                    if (Board.GetText(col, row) == player[currentPlayer] && (Board.GetText(col, row) == Board.GetText(col - 1, row + 1) || 
                         Board.GetText(col, row) == Board.GetText(col + 1, row - 1))) {
                        isSolved = true;
                        counter++;
                    } else {
                        counter = 0;
                    }
                    if (counter >= 4) {
                        return true;
                    }
                }
            }
            return isSolved;
            
        }
Das funktioniert aber nicht... Ich habe im Prinzip einfach immer versucht zu checken, ob eben schräg zu der aktuellen Position dasselbe Zeichen ist und wenn ja es dort weiterversucht.

Die Klasse Board ist sozusagen ein 2D-Array visualisiert, wenn ihr versteht wie ich das meine, aber da könnt ihr euch sicher sein dass es funktioniert, hab das jetzt schon einige Male problemlos nutzen können.
lernender Programmierer, hauptsächlich C# und Java

Orioner
Beiträge: 35
Registriert: Mo Dez 10, 2012 10:52 am

Re: Schrägen in einem zweidimensionalem Array durchlaufen

Beitrag von Orioner » Fr Jun 01, 2018 6:47 pm

Es wäre einfacher, wenn du das zwei-dimensionale Array auf ein ein-dimensionales mappst. Ausgehend von der Tatsache, dass du bei 8 Feldern in der Waaggerechten 8 Felder zu einer Position addieren musst, um ein Feld in der senkrechten nach oben zu wandern, oder 8 Felder subtrahieren, um ein Feld nach unten zu wandern, kannst du ganz einfach diagonal wandern, indem du nicht 8 Felder addierst oder subtrahierst, sondern nur 7 oder 9, je nachdem ob du nach rechts-oben, nach links-oben, nach recht-unten oder nach links-unten wandern willst.

Antworten