Zweidemensionales Array auf zwei gleiche Zahlen prüfen

[OiM86]

Hallo liebe Forum Mitglieder (und natürlich auch Gäse )

Ich komm grad bei eine Aufgabe nicht weiter. Mir fehlt einfach grad eine Idee.
Ich hab ein zwei demensionales Array mit insgesamt 36 Feldern.

[Java]
static int[][] a = new int[6][6];
[/code]

Das Feld 0,5 und 5,0 ist mit einer 1 belegt:

a[0][5] = 1;
a[5][0] = 1;

Jetzt soll ich den Array mit 10 weiteren Einsen füllen (so das ich am ende 12 Einser hab). Dabei ist die Bedinnung dass in jeder Horinzontalen in jeder Vertikalen und Diagonalen nur ZWEI einser stehen.

Also das es zum Schluss z.B so aussieht:

1 0 0 0 0 1
0 0 1 1 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 0 1 1 0 0
1 0 0 0 0 1

Ich komm einfach nicht drauf wie ich die Schleifen bauen soll.
Für paar Tips wär ich sehr dankbar

Danke im vorraus !

 

[Marco13]

Ganz einfach:

a[0][0] = 1;
a[1][2] = 1;
a[2][1] = 1;
... usw...

Wenn man davon ausgeht, dass das ein allgemeineres Problem ist, und die Aufgabe lautet "Für einen Array der größe n x n soll eine Verteilung gefunden werden, so dass in jeder Spalte/Zeile nur k Einsen stehen", muss man sich was überlegen. Das kann dann aber schon ziemlich untrivial werden...

 

[OiM86]

ja ne. Also es gib ja mehrer Lösungsmöglichkeiten ! Daher soll ich Prüfen ob die 1 an der gegeben Positon stehen kann, wenn ja dann 1 eintragen wenn nein dann nähste Position prüfen.

Und mir fehlt eben die Idee wie ich das Prüfen mach. Vor allem in der Diagonalen !

 

[Dag B.]

Hallo,

ich würde es mit 2 Zählern machen. Müssten glaube ich Zählerarrays sein. :rtfm:

Und deren Index dann über 2 ineinander verschachtelte for-Schleifen erhöhen.

Wenn beide Zähler an der Position kleiner als 2 sind kann er die 1 schreiben, sonst eben nicht.

Mal so als grobe Idee.

 

[Marco13]

ja ne. Also es gib ja mehrer Lösungsmöglichkeiten ! Daher soll ich Prüfen ob die 1 an der gegeben Positon stehen kann, wenn ja dann 1 eintragen wenn nein dann nähste Position prüfen.

... und wenn man durch das Eintragen einer 1 an einer bestimmten Stelle eine Lösung unmöglich gemacht hat, aber eine Lösung möglich gewesen wäre, wenn man diese 1 an einer anderen Stelle eingetragen hätte, ist man beim Backtracking .... und darauf wollte ich hinaus...

 

[Landei]

Ist nicht immer eine "Treppe" eine gültige Lösung?

000011
000110
001100
011000
110000
100001

 

[eRaaaa]

und Diagonalen nur ZWEI einser stehen

 

[Dag B.]

Und mir fehlt eben die Idee wie ich das Prüfen mach. Vor allem in der Diagonalen !

Naja, für die Diagonalen (hatte ich ganz überlesen ^^ ) musst du dir halt auch irgendeine Regelmäßigkeit überlegen.

Dazu schau dir mal die Diagonalen an bzw deren Indizes. zB von unten rechts nach oben links:
0:0 -> 1:1 -> 2:2 -> 3:3 -> 4:4 -> 5:5
oder auch: 0:1 -> 1:2 -> 2:3 -> 3:4 -> 4:5
Fällt dir was auf, wie sich die Indizes verändern?

Und dann eben noch schauen, wies mit den Indizes der anderen möglichen Diagonalen aussieht. Wird natürlich ein ziemliches Abfragengewusel, aber was besseres fällt mir aktuell dazu nicht ein. ^^

 

[Marco13]

aber was besseres fällt mir aktuell dazu nicht ein. ^^

*räusper* ... Backtracking *räusper* (oder gleich sowas wie AC3-Constraint-Satisfaction...)

 

[Dag B.]

Über Backtracking kriegste doch aber auch nicht die Belegung der Diagonalen ohne ihm zu sagen, "was" die Diagonalen sind.

Wenn das Programm nicht weiß, dass es auch 0:0 mit 1:1 vergleichen muss, kann es auch nicht prüfen ob der Weg zu einer Lösung führen würde.
Und mehr als das, habe ich ja nicht ausgeführt.
Wie man sein Abfragengewusel und den Rest baut (backtracking, unendlich viele if-Schleifen etc. pp.) steht auf einem anderen Blatt geschrieben. ^^

 

[Marco13]

Hmmmjjaaa... kommt drauf an, was das Ziel dieser Aufgabe(?) ist. Natürlich könnte man hinschreiben

if      (a[0][0]==1 && a[1][1]==0 && a[2][2]==0 && a[3][3]==0 && a[4][4]==0 && a[5][5]==0) a[1][1] = 1;
else if (a[0][0]==0 && a[1][1]==1 && a[2][2]==0 && a[3][3]==0 && a[4][4]==0 && a[5][5]==0) a[0][0] = 1;
else if (a[0][0]==0 && a[1][1]==0 && a[2][2]==1 && a[3][3]==0 && a[4][4]==0 && a[5][5]==0) a[0][0] = 1;
...
 //  Viel Spass damit...

Ich gehe aber davon aus, dass es fast unmöglich ist, dieses Abfragemonster so systematisch und konsistent hinzuschreiben, dass es wirklich funktioniert....

Wenn man statt eines Programmes, das das Problem für
- ein 6x6-Array
- mit 2 vorgegebenen 1en
- mit der Bedingung: Max. 2 einsen senkrecht, waagerecht, diagonal
löst, und dafür 1000 unwartbare, unverstehbare, und (vermutlich) unmöglich "richtig" hinzuschreibende Zeilen wie die open angedeuteten verwendet, EINmal ein kleines Backtracking implementiert (was für so ein Problem reichlich trivial ist) und dafür nur 100 Zeilen benötigt, von denen eine eben die Zeile

boolean isValid = currentConfigurationIsValid();

ist, ist das sicher sinnvoller.

Stell dir vor, das Programm ist fertig, und dann ist der Lehrer fies und sagt: "Sooo, das ganze jetzt auf einem 7x7-Array", oder "Jetzt darf in den Diagonalen nur noch jeweils EINE 1 stehen". Wenn man das Problem "speziell" gelöst hat, ist man dann ... "gefickt", wie der Lateiner sagt. Im anderen Fall würde man in der "currentConfigurationIsValid"-Methode aus einer 2 eine 1 machen, und wäre fertig.

Ohne jetzt einen Flamewar zwischen den Verfechtern von You Are Gonna Need It und You Arent Gonna Need It anzetteln zu wollen: So eine Aufgabe stellt man nicht, weil sie speziell gelöst werden soll (sonst kann man das so machen wie ich in meiner ersten Antwort angedeutet hatte), sondern vermutlich eher, weil man einen Algorithmus zur allgemeinen Lösung finden und implementieren soll....

 

[Dag B.]

Hmmmjjaaa... kommt drauf an, was das Ziel dieser Aufgabe(?) ist. Natürlich könnte man hinschreiben

if      (a[0][0]==1 && a[1][1]==0 && a[2][2]==0 && a[3][3]==0 && a[4][4]==0 && a[5][5]==0) a[1][1] = 1;
else if (a[0][0]==0 && a[1][1]==1 && a[2][2]==0 && a[3][3]==0 && a[4][4]==0 && a[5][5]==0) a[0][0] = 1;
else if (a[0][0]==0 && a[1][1]==0 && a[2][2]==1 && a[3][3]==0 && a[4][4]==0 && a[5][5]==0) a[0][0] = 1;
...
 //  Viel Spass damit...

Du musst doch nur (rekursiv?) abfragen, ob zB bei der Diagonalen von rechts oben nach links unten alle Vorgänger (-1:-1) und nachfolger (+1:+1) mit 1 belegt sind. Das meinte ich mit der Regelmäßigkeit.

Also irgendwie

if(Feld[index1 + i][index2 + i] == 0)
    //Erneuter aufruf mit i + j erhöht/erniedrigt.

Damit wäre deine Monsterabfrage schonmal kleiner.

Und dort dann unter den erneuten aufruf vllt einen Zähler, welcher im else um 1 erhöht wird. Beträgt der 2, darf man nichts schreiben.

Also irgendwie so, in Pseudocode (fehlt noch bissel was, aber zur Illustration) :

count := 0;
while(count kleiner 2)
   for(i := 1; i < 6; i++)
         if(Feld[index1 + i][index2 + i] gleich 1)
            Erhöhe count um 1
         end if
   end for
end while
if(count kleiner 2)
   Schreibe 1 an Stelle Feld[i][j]

Wird immer noch ein ziemlicher Wust, weil man ja Feld[i-1][j-1] auch checken muss und zusätzlich die Prüfung fehlt, ob i+1 und j+1 überhaupt noch kleiner als die Arraylänge sind.
Und dann hat man nur eine einzige Diagonale. ^^"
Aber es war ja auch nur eine grobe Idee, ich wollts nur nochmal ausführen, weil ich mit keinem Wort gesagt habe der soll den Schmarn einzeln prüfen. :shock:

Schließlich wollte ich anregen, nicht die Aufgabe komplett für OiM86 lösen.

 

[Apokalypse]

Hallo ich habe gerade interesiert diesen Thread gelesen.
Vielleicht schaust, du dir mal das Damenproblem an.
Das geht in die gleiche Richtung wie dein Problem

Gruß Apo

 

[Marco13]

Also irgendwie so, in Pseudocode (fehlt noch bissel was, aber zur Illustration) :

count := 0;
while(count kleiner 2)
   for(i := 1; i < 6; i++)
         if(Feld[index1 + i][index2 + i] gleich 1)
            Erhöhe count um 1
         end if
   end for
end while
if(count kleiner 2)
   Schreibe 1 an Stelle Feld[i][j]

Ja, und dann halt...

if (irgendwann wurde an Position (i,j) gesetzt und jetzt gibt es keine Lösung)
{ 
    Mache alles rückgängig was seit dem Setzen bei (i,j) gemacht wurde
    Schreibe 1 an eine andere Stelle als (i,j)
    Schau' nach ob es jetzt eine Lösung gibt........
}

Apokalypse hat schon recht. Das Damenproblem kann man genau so wie dieses Problem lösen (also mit demselben Quellcode!) - nur die Methode "currentConfigurationIsValid" muss etwas anders implementiert werden.

 

[Dag B.]

Ich weiß, sowohl das Dame- als auch das Springerproblem musste ich schon selbst lösen.
Ist aber schon ewig her. ^^

Meins war wie gesagt kein kompletter Lösungsansatz sondern nur ein Hinweis, wie man die Zeilen, Spalten und Diagonalen prüfen >könnte<.

 

[OiM86]

Vielen Dank für euren zahlreichen Antworten ! Dank Dag B. bin ich auf die Lösung gekommen.