Schach
ArvedK
Hallo,
Der brühmte Mathematiker Gauss hat 92 Möglichkeiten gefunden 8 Damen so
auf einem Schachbrett anzuordnen, dass sie sich nicht schlagen können -
Fakt. Ist dieses nur durch logisches Denken herrauszufinden oder gibts
dafür auch eine Möglichkeit der Berechnung ?
Arved
Die Erde ist rund - daran kann keiner was ändern - oder doch ??
Thomas Uhl
ArvedK wrote:
> Der br=FChmte Mathematiker Gauss hat 92 M=F6glichkeiten gefunden 8 Dame=
n so
> auf einem Schachbrett anzuordnen, dass sie sich nicht schlagen k=F6nnen=
-
> Fakt. Ist dieses nur durch logisches Denken herrauszufinden oder gibts
> daf=FCr auch eine M=F6glichkeit der Berechnung ?
Klar: Ausprobieren (heutzutage am besten mit einem Computer). Aber 92 kan=
n
irgendwie nicht
die korrekte Anzahl sein, denn wegen der Symmetrien muss diese zumindest
durch 8 teilbar sein.
--
Thomas Uhl "Computers are not intelligent
uh...@informatik.uni-karlsruhe.de ...they only think they are."
David Kastrup
arv...@aol.com (ArvedK) writes:
> Hallo,
>
> Der brühmte Mathematiker Gauss hat 92 Möglichkeiten gefunden 8 Damen so
> auf einem Schachbrett anzuordnen, dass sie sich nicht schlagen können -
> Fakt. Ist dieses nur durch logisches Denken herrauszufinden oder gibts
> dafür auch eine Möglichkeit der Berechnung ?
Hat er da nicht 4 Möglichkeiten übersehen?
--
David Kastrup Phone: +49-234-700-5570
Email: d...@neuroinformatik.ruhr-uni-bochum.de Fax: +49-234-709-4209
Institut für Neuroinformatik, Universitätsstr. 150, 44780 Bochum, Germany
ArvedK
Im Artikel <m2bu0ce...@mailhost.neuroinformatik.ruhr-uni-bochum.de>,
David Kastrup <d...@mailhost.neuroinformatik.ruhr-uni-bochum.de> schreibt:
>
>Hat er da nicht 4 Möglichkeiten übersehen?
>
Er nicht, ich hab's falsch eingetippt ! - Hättest du denn 'ne Möglichkeit ?
Eva Kornmann
On 26 Oct 1997 05:42:39 GMT, arv...@aol.com (ArvedK) wrote:
>. Ist dieses nur durch logisches Denken herrauszufinden oder gibts
>dafür auch eine Möglichkeit der Berechnung ?
??? Ich dachte, das wäre das gleiche.
Gruß
Eva
Bitte "remove" in der eMail-Adresse entfernen.
ArvedK
Im Artikel <345321F8...@ira.uka.de>, Thomas Uhl <uh...@ira.uka.de>
schreibt:
>Klar: Ausprobieren (heutzutage am besten mit einem Computer). Aber 92 kan=
>n
>irgendwie nicht
>die korrekte Anzahl sein, denn wegen der Symmetrien muss diese zumindest
>durch 8 teilbar sein.
>
Jup, sind 96.
Aber durch ausprobieren ist ja klar, kann man das nicht geschickter
herrausfinden ?
Hartmut Rieg
Hallo Arved,
Du kannst etwa so vorgehen:
Jede Spalte des Bretts enthält genau eine Dame und wir schreiben die
Nummer der Reihe auf, in der sie steht. Wir beginnen mal links unten
und setzen fortan auf die nächstbeste freie Reihe:
(1 3 5 7 2 4 6 8)
Hups - schon ist es schiefgegangen: Die Damen in Spalte 1 und 8 können
sich gegenseitig schlagen. Also muss ein Teil der Damen vom Brett und
neu gesetzt werden, bis es aufgeht.
(1 3 5 7 2 8 6 4)
Du findest das Verfahren unter "Backtracking-Algorithmus". Nach dieser
Methode nmüsste man auch die Lösungen zählen können, ohne sie zu
berechnen:
1) Wieviele Anordnungen der Ziffern 1 bis 8 auf die 8 Plätze gibt es?
2) Wie kann man alle die Anordnungen ausscheiden, bei denen es zwei
Damen gibt, deren Reihen- und Spaltennummewrn bis aufs Vorzeichen die
selbe Differenz haben?
In sci.math findest Dui einen Thread zu diesem Thema "N-Queens
Problem"
Gruß
Hartmut
arv...@aol.com (ArvedK) wrote:
>Hallo,
>
>Der brühmte Mathematiker Gauss hat 92 Möglichkeiten gefunden 8 Damen so
>auf einem Schachbrett anzuordnen, dass sie sich nicht schlagen können -
>Fakt. Ist dieses nur durch logisches Denken herrauszufinden oder gibts
>dafür auch eine Möglichkeit der Berechnung ?
>
>Arved
>Die Erde ist rund - daran kann keiner was ändern - oder doch ??
--
Max-Planck-Gymnasium Karlsruhe
http://www.uni-karlsruhe.de/~za151
Axel Schwenke
In Artikel <19971026054...@ladder02.news.aol.com>,
schrieb arv...@aol.com (ArvedK):
A>Hallo,
A>
A>Der brühmte Mathematiker Gauss hat 92 Möglichkeiten gefunden 8 Damen so
A>auf einem Schachbrett anzuordnen, dass sie sich nicht schlagen können -
A>Fakt. Ist dieses nur durch logisches Denken herrauszufinden oder gibts
A>dafür auch eine Möglichkeit der Berechnung ?
Eine einfachere Variante sind die sogenannten Turmpolynome.
Die Frage ist: "Wieviele Möglichkeiten gibt es, n Türme auf ein gegebenes
Brett zu setzen ohne daß sie sich gegenseitig bedrohen? Das Brett ist eine
rechteckige Anordnung von Feldern das ansonsten beliebige Form haben darf.
Die Antwort ist das Turmpolynom: P(B) = a0 + a1*x + a2*x^2 + ...
Der Koeffizient vor x^n gibt dabei die Anzahl der Möglichkeiten für
n Türme an. Jetzt kann man rekursiv vorgehen. Man nehme das Ausgangs-
brett und suche sich ein (beliebiges) Feld aus.
Wenn wir einen Turm auf das Feld stellen, können wir auf der ganzen
Zeile und Spalte keinen mehr unterbringen und können diese Felder
deshalb auch gleich entfernen. Wenn wir keinen Turm auf das Feld stellen,
können wir das Feld auch gleich streichen.
Das Turmpolynom eines Brettes B ist nun: P(B) = x*P(B1) + P(B2) wobei
B1 das Feld mit einem gestrichenen Feld und B2 das Brett mit der
gestrichenen Zeile und Spalte ist. Das Turmpolynom für ein leeres
Brett ist 1, das für ein Brett mit einem Feld x+1.
Das kann man berechnen - richtig einfach und relativ schnell...
z.B. kann man herausfinden, wieviele Möglichkeiten es gibt, n Damen
auf einem herkömmlichen Schachbrett (8x8) anzuordnen (der Koeffizient
vor x^{n} ist die Anzahl der Varianten):
--------snip---------------------------------------------
Damenpolynom 8x8
92x^{8} + 3192x^{7} + 22708x^{6} + 46736x^{5} + 34568x^{4}
+ 10320x^{3}+ 1288x^{2} + 64x + 1
Command being timed: "turmpoly 8x8-dame.gra"
User time (seconds): 13.82
--------snip---------------------------------------------
Turmpolynom 8x8
40320x^{8} + 322560x^{7} + 564480x^{6} + 376320x^{5} + 117600x^{4}
+ 18816x^{3} + 1568x^{2} + 64x + 1
Command being timed: "turmpoly 8x8-turm.gra"
User time (seconds): 103.63
--------snip---------------------------------------------
Oben genutztes Programm ist ein Nebenprodukt unserer Forschung an
Graphen. Das Schachbrett wird in einen Graphen umgewandelt: Jedes
Feld wird ein Knoten; wenn die Spielfigur von Feld A nach Feld B
ziehen kann, kommt eine Kante von A nach B in den Graphen.
Mogliche Stellungen für Spielfiguren entsprechen dann "unabhängige
Knotenmengen" in diesem Graphen.
AxEL
--
|-----------------------------------------------------------------------|
| Dipl-Math. Axel Schwenke, HTW Mittweida ............ schw...@htwm.de |
| visit my LinuX site ................ http://datamill.mpi.htwm.de:4711 |
|____________ In A World Without Fences Who Needs Gates? _____________|
Stefan Kirchner
Zu folgenden Aussagen möchte ich mich hier äußern:
> Ist dieses nur durch logisches Denken herrauszufinden oder gibts
>dafür auch eine Möglichkeit der Berechnung ?
Also eine "einfache Formel", die die Anzahl der Möglichkeiten bestimmt, dürfte
es wohl nicht geben (Vermutung). Mit Rechnerhilfe bereitet dieses aber keine
Schwierigkeit. Dieses Problem erscheint oft als Standardbeispiel für die
Wirkungsweise von Backtracking.
>Jup, sind 96.
Nein, es sind nur 92. Normalerweise kann man durch Drehungen und Spiegelungen
weitere
sieben Lösungen finden. Bei einer Lösung (die Damen stehen auf folgenden
Feldern - nach
Schachnotation: f1 d2 g3 a4 h5 b6 e7 c8) ergeben sich durch Drehungen und
Spiegelungen
insgesamt nur vier Lösungen. Das kann leicht durch ausprobieren herausgefunden
werden. So ist z.B. diese Lösung invariant bezüglich einer Drehung von 180°.
>Der schlechteste Algorit[h]mus, den ich mir auf Anhieb vorstellen kann,
>(ich wuerde ihn brute force nennen;-) testet gerade mal 8!
>Moeglichkeiten.
Folgendes Programm habe ich vor einiger Zeit in Turbo Pascal zum Thema
"Backtracking"
einmal geschrieben. Was es für eine Laufzeit hat, kann ich nicht genau sagen,
jedoch
arbeitet es recht zügig. Ich habe versucht, den Algorithmus noch effiktiver zu
programmieren, es ist mir aber nicht gelungen. In der dritten Zeile kann durch
ändern der Variable n ein beliebiges n*n-Feld "durchforstet" werden. Die Lösung
1 5 8 6 3 7 2 4 muß so gelesen werden: 1. Reihe 1. Feld, 2. Reihe 5. Feld, usf.
Stefan
program dame;
uses wincrt;
const n=8;
var brett: array[0..n] of shortint;
brett1: array[0..n] of boolean;
Lfd : shortint;
Anzahl : integer;
procedure setzen(linie,reihe :shortint);
var Lfd1, Lfd2 : shortint;
begin
brett[reihe]:=linie; brett1[linie]:=true;
if reihe = n then begin
inc(Anzahl);
for Lfd1:= 1 to n do write(brett[Lfd1]:4);
writeln;{readkey;}end
else begin
for Lfd1:=1 to n do
if brett1[Lfd1]=false then begin
Lfd2:=reihe;
while (abs(reihe+1-Lfd2)<>abs(Lfd1-brett[Lfd2]))
and (Lfd2>0) do dec(Lfd2);
if Lfd2=0 then setzen(Lfd1, reihe+1);
end;
end;
brett[reihe]:=0; brett1[linie]:=false
end;
begin
anzahl:=0;
for Lfd:=0 to n do begin
brett[Lfd]:=0; brett1[Lfd]:=false;end;
for Lfd:=1 to n do setzen(Lfd,1);
writeln('Möglichkeiten ',anzahl);
end.
Hartmut Rieg
Es ging um die Zahl der Lösungen des 8-Damen-Problems, warum 92 und
nicht 96.
"Ronald G\"oggel" <r.go...@atos-group.de> wrote:
>Warum muß die Anzahl durch 8 teilbar sein ?!
>
>Unterscheidest du die einzelnen Damen voneinander ?!
>
>Näher dran wäre dann schon, daß die Anzahl durch 4 teilbar sein könnte, weil
>das Brett 4 Seiten hat.
>Geht aber auch nicht, weil die Positionen ja symmetrisch sein können.
Eine Lösung kann nicht achsensymmetrisch sein, weil sich symmetrisch
stehende Damen gegenseitig bedrohen. Drehsymmetrie ist aber erlaubt.
Das Schachbrett hat 4 Spiegel- und 4 Drehsymmetrien (0 Grad
einbezogen). Das Damenproblem hat 12 echt verschiedene Lösungen, die
ich jetzt nicht abtippen mag. 11 davon sind unsymmetrisch, haben also
je 8 Varianten. Eine hat eine innere Symmetrie, wodurch von den 8
Lösungen je 2 identisch sind. Deshalb gibt es 8*12 + 4 = 92
Möglichkeiten. Die symmetrische Lösung ist (3 5 2 8 1 7 4 6)
Eine Formel für dieses Ergebnis, die sich auf andere Brettgrößen
verallgemeinern liesse, gibt es nach meiner Quelle noch nicht (1971).
Leider habe ich dieses Schachmathikerbüchlein erst jetztt
wiedergefunden, sonst hätte ich es schon in meiner ersten Nachricht
genannt:
Bonsdorf/Fabel/Riihimaa, Schach und Zahl, Walter Rau Verlag
Düsseldorf, keine ISBN.
Gruss
Hartmut Rieg