8-Damen-Problem

[glkgereon]

ich hab mich mal wieder dran gegeben und versuche es zu lösen...

wenn ich weiss welche dame als letztes dazugekommen ist, kann ich ja wesentlich schneller überprüfen ob eine stellung gültig ist.
ist dieser code korrekt? kann man ihn noch optimieren?

Delphi-Quellcode:

function TForm1.IsValid(Feld:TFeld; NewX, NewY: Byte):Boolean;
var i:Integer;
    Failed:Boolean;
begin
  for i:=1 to Newy-1 do Failed:=Failed or Feld[i,NewY];
  if not Failed then 
    for i:=NewY+1 to 8 do Failed:=Failed or Feld[i,NewY];
  if not Failed then 
    for i:=1 to NewX-1 do Failed:=Failed or Feld[NewX,i];
  if not Failed then 
    for i:=NewX+1 to 8 do Failed:=Failed or Feld[NewX,i];
  if not Failed then 
    for i:=NewX-1 downto 1 do
      if NewY-i>0 then Failed:=Failed or Feld[NewX-i,NewY-i];
  if not Failed then
    for i:=1 to 8-NewX do
      if NewY+i>0 then Failed:=Failed or Feld[NewX+i,NewY+i];
  Result:=Failed;
end;

[Binärbaum]

Was hat hierbei die Varaible/Array Feld zu erledigen? Prüft die, ob auf dem jeweiligen Feld schon eine Dame steht?

MfG
Binärbaum

[glkgereon]

Delphi-Quellcode:

TFeld = array[1..8,1..8] of boolean;
//True = Dame
//False = Keine Dame

hoffe das hilft weiter ;)

[Binärbaum]

Naja, das hilft erstmal.

Mal eine ganz andere Idee: ich habe dieses Problem auch schon mal bearbeitet (allerdings in Real auf einem richtigen Schchbrett). Soweit ich mich erinnere, standen die Damen dort alle so, dass man von der einen Dame zurnächsten durch den Rösselsprung kam (der L-förmige zug, den sonst der Springer macht). Vielleicht hilft dir das ja weiter.

Und zur Code-Optimierung: man könnte alle for-Schleifen durch entsprechende while-Schleifen ersetzen und in die Durchlaufbedingung Failed mit einbeziehen. Dann würde die Schleife nicht noch mehrmals durchlaufen, wenn z.B. schon nach dem ersten Durchlauf klar ist, dass die eingegebene Position nicht die richtige ist. Dadurch hätte man zwar erstmal ein paar Zeilen mehr Code, da die Laufvariable i "manuell" hochgezählt werden muss, aber dafür müsste der Code dann auch schneller sein.

MfG
Binärbaum

[glkgereon]

ja, ich "kann" schach spielen, und nein, das mit dem rösselsprung funzt so astrein nicht (man darf auf jeden fall nicht in der ecke anfangen...)

ich werd das nochmal alles durchgucken

[Binärbaum]

Hab ich etwa behauptet, dass du nicht Schach spielen kannst? Kann mich nicht daran erinnern. :gruebel:
Das mit dem Rösselsprung sollte übrigens nur ein Denkanstoss sein. Inwiefern man das auf dem PC umsetzen kann (und ob es schneller ist als die bisherige Funktion), dass hab ich nicht gesagt.

MfG
Binärbaum

[glkgereon]

sollte kein angriff sein

ich wollte nur hierauf eine antwort geben

Zitat:

Soweit ich mich erinnere, standen die Damen dort alle so, dass man von der einen Dame zurnächsten durch den Rösselsprung kam (der L-förmige zug, den sonst der Springer macht).

;)

[Binärbaum]

Das sollte nicht heißen, dass du nicht Schach spielen kannst. Ich wollte nur sichergehen, dass ich auch richtig verstanden werde. Man weiß ja nicht, inwiefern sich der Gegenüber mit Schach auskennt. Also nichts für ungut.

MfG
Binärbaum

[freak4fun]

Hallo,
ich spiel kein Schach. Wieso 8 Damen, ich denke sind nur 2. :gruebel:

:wiejetzt:

MfG
fR34k

[Binärbaum]

@freak
Das Acht-Damen-Problem beschäftigt sich damit, wie man 8 Damen so auf einem leeren Schachbrett platzieren kann ,dass sie sich nicht gegenseitig schlagen können. Hat also mit dem eigentlichen Schachspiel wenig zu tun. (Bis auf die Damen natürlich :wink: )

MfG
Binärbaum

[freak4fun]

Achso, dankeschön! :thumb:

Und das Problem ist ob es geht, oder wie es geht? :pale:

Sry, steh irgendwie auf meinem DSL-Modem. :mrgreen:

MfG
fR34k

[Binärbaum]

Die Antwort auf die Frage, ob es geht ist ja (sonst würde man es wohl kaum probieren :) ). Das Interessante ist, wie es geht, also wo man die Damen jeweils aufstellen muss. Und das soll das Programm von glkgereon rausfinden.

MfG
Binärbaum

[bigg]

Klar geht es, er will aber jetzt einen algo entwerfen, der das für ihn macht.
Er bekommst nur nicht hin :mrgreen:

[freak4fun]

Also "Warum" darf man hier ja nicht unbedingt fragen, aber wenn es eine Lösung gibt brauch er es doch nicht nochmal machen, oder?
Aber interessant ist das schon. Schade das ich keine Zeit für sowas hab. :roll:

MfG
fR34k

[bigg]

Naja freiwillig macht man solche Spielereien sicherlich nicht, ich denke da eher so an Hausaufgaben. :roll:

[Binärbaum]

Zitat:

Zitat von bigg

Klar geht es, er will aber jetzt einen algo entwerfen, der das für ihn macht.
Er bekommst nur nicht hin :mrgreen:

Wenn du dir mal den Quellcode von oben angesehen hättest, würdest du wissen, dass das Prog eigentlich schon laufen müsste. Nur ist das Problem ziemlich aufwendig, da er alle Möglichkeiten überprüfen muss. Also versucht er, das irgendwie zu optimieren.

MfG
Binärbaum

[mika]

@freak

das hat wirklcih meistens was mit hausaufgaben zu tun, ist ne beliebte aufgabe für "backtracking" (hoffe ich erinnere mich grade richtig), man probiert eine lösung zu finden indem man immer ein schritt zurück geht und andere wege ausprobiert (in schleifenform)

hatten wir damals im Fach Programmieren im ersten Jahr, erstes Halbjahr, ist ne lustige Aufgabe wenn man die Lösung net kennt ;) Hab die noch irgendwo als Pascal Quelltext liegen :)


gruß, michael


(jaja ich weiss, es gibt sowas wie groß und kleinschreibung aber mir reicht eins von beiden in den meisten fällen :)

[Binärbaum]

Ich hätte da noch eine Optimierungsidee:
Eigentlich reicht ja als Feld ein eindimensionaler Array mit 8 Elementen (z.B. array [1..8] of Byte), da ja auf jeder Zeile/Spalte des Schachbretts nur eine Dame stehen kann. Also gibt der Index des Arrays an, um wleche zeile es sich handelt, und der Wert selbst steht für die Spalte. Damit müsste man nicht soviele Chechks durchführen, ob die Dame an der gegenwärtigen Position geschlagen werden kann. So beduetet z.B der Code:

Delphi-Quellcode:

var Feld: array[1..8] of Byte;
...

 Feld[1]:= 5;

dass in der ersten Zeile in der fünften Spalte eine Dame steht (also auf dem Feld a5).
Danach könnte man sofort zur nächsten Zeile gehen, und dort alle Positionen durchprobieren. Also ist der (Backtracking-) Aufwand viel geringer, als wenn der Algorithmus jedes einzelne Feld des Schachbrettes durchläuft.

MfG
Binärbaum

[dadu]

@freak4fun
Warum setzt du dich nicht mal hin und löst es im Kopf??? (Falls du das natürlich in Info aufhast, vergiss meine Ausage: Ich habs aber in 15 min gelöst)

DaDu

[freak4fun]

Zitat:

Zitat von dadu

@freak4fun
Warum setzt du dich nicht mal hin und löst es im Kopf??? (Falls du das natürlich in Info aufhast, vergiss meine Ausage: Ich habs aber in 15 min gelöst)

DaDu

:roll:

[Delphi_Fanatic]

Hey, an diesem 8-Damen-Problem hab' ich mich mal (als ich noch in der Ausbildung war) auch
versucht.

Wenn Du damit fertig bist, kannst Du ja mal posten, wie viele Möglichkeiten Dein Programm
gefunden hat. :???:

[Flogo]

Wir hatten das auch mal in Info. Die einzige Optimierung, an die ich mich noch erinnern kann war, das (Spiel-)Feld in jede Richtung um ein Feld zu erweitern also kein Array [1..8, 1..8] sondern [0..9, 0..9].
Ich weiß nicht mehr genau warum dass den Code so sehr optimieren sollte, aber es hatte was mit dem Ausprobieren neuer Positionen für die nächste Dame zu tun. Ich glaube es lag daran, dass das Überprüfen, ob das Nachbarfeld noch auf dem Brett ist, einfacher wird.
Aber wie gesagt es ist schon ne Weile her und ich erinnere mich nicht mehr so genau,... :gruebel:
Vielleicht hilfts ja als Denkanstoß

[omiT]

Wir hatten vor weinigen Monaten auch das 8-Damen-Problem in der Schule und mit Delphi programmiert. Allerdings haben wir nicht ein Array genommen, sondern drei: Eins, in dem gespeichert wird welche Reihe noch besetzt werden darf, und jeweils eins für die Diagonalen (von links unten nach rechts oben und von links oben nach rechts unten). Bei interesse kann ich ja das Programm / den Quelltext nachher mal hochladen.

Zitat:

Warum setzt du dich nicht mal hin und löst es im Kopf??? (Falls du das natürlich in Info aufhast, vergiss meine Ausage: Ich habs aber in 15 min gelöst)

Du hast also in 15 Minuten mal auf die Schnelle 92 mögliche Positionen gefunden? :roll:

[dadu]

nein! natürlich nicht! ich hab EINE Möglichkeit gefunden: Weis ja nicht das es so viele gibt: dann würde ich auch ein prog schreiben

DaDu

[Delphi_Fanatic]

Zitat:

Allerdings haben wir nicht ein Array genommen, sondern drei: Eins, in dem gespeichert wird welche Reihe noch besetzt werden darf, und jeweils eins für die Diagonalen

So kann man's natürlich auch machen.

Ich hab's damals über eine Rekursion gelöst.

Eigentlich heisst es ja "Rekursiv geht immer schief", aber das 8-Damen-Problem ist die einzige "Anwendung", die mir
jemals untergekommen ist und bei der eine Rekursion aus meiner Sicht sogar mal Sinn macht ...