Mathe-Rätsel: 1000 Damen auf 1000 mal 1000 Schachfeld so platzieren, dass sie sich nicht gegenseitig schlagen

Question

Habt ihr irgendeine Ahnung wie man dieses Rätsel lösen kann?

In diesem Video wird es erklärt:

Mathe-Rätsel:

1000 Damen auf 1000 mal 1000 Schachfeld so platzieren, dass sie sich nicht gegenseitig schlagen.

(sehr schwer)

Answer 1

Zunächst mal gibt es überhaupt 1000! = 4.024·10^2567 Möglichkeiten die in jeder Spalte und Zeile eine Dame zu plazieren. Hier gilt es die Möglichkeiten abzuziehen, bei denen sich jetzt noch Damen gegenseitig bedrohen.

Letztendlich könnte man das mit Brute-Force lösen. Allerdings gibt es halt so viele Möglichkeiten, dass deswegen die Rechner zu schwach dafür sind.

Comments

Ich habe früher selbst programmiert und auch ein Programm für ein normales 8x8 Schachfeld geschrieben. Algorithmus: Alle Möglichkeiten in Schleifen durchprobieren.
Derselbe Algorithmus würde auch auf einem 1000x1000 Feld funktionieren. Bloß halt die Zeit dafür.

---

Ich hab sowas auch mal auf einem C-64 geschrieben in einer Zeit als BASIC noch modern war :)

Später in der Uni hab ich das dann nochmal mit C gemacht und auch über Rekursive aufrufe. Die Methode war dann auch schon etwas schlauer und hat schon beim setzen einer Dame nur auf Felder gesetzt, die noch nicht von vorherigen Damen bedroht sind. Das ging auf einem 8x8 Feld sogar eigentlich recht flott.

Allerdings gibt es dort ja auch nur ca. 40000 Möglichkeiten die überhaupt zu prüfen sind. Wobei immer gleich sehr viele auch wegfallen.

---

@Georg:

Wie lange könnte sowas dauern? Könnte man da vielleicht auf eine Formel stoßen?

---

Wie lange könnte sowas dauern?

Die Abarbeitung aller Möglichkeiten in verschachtelten Schleifen dauert wahrscheinlich  länger als das Universum alt ist.

Eine " Formel " gibt es sicher nicht.

Die Optimierung von Algorithmen ist sicherlich, genau wie bei Schachprogrammen, möglich.

---

Na ja, bis zum Zerfall des letzten Protons hast du noch ca. 10^22 Jahre Zeit.

Ein Proton lebt angeblich 10^32 Jahre. Gut 10^10 Jahre sind ja nun schon vorbei seit es urgeknallt hat. :)

---

Falls du es auf die zu gewinnende Million abgesehen hast, bewirb dich lieber bei Günther Jauch "Wer wird Millionär". Da sind deine Chancen größer.

---

Bei meinem Glück würde es 10^100 Jahre (= Zeit, bis das letzte schwarze Loch verdampft ist) dauern, bis ich auf dem Stuhl bei Jauch lande. :)

---

Mein Bruder hat sich einmal beworben und kam auch in die Sendung. Er schied allerdings in der Anfangsrunde aus.

---

Am 27x27 Feld wurde schon gut ein Jahr gerechnet ... Selbst bei polynomialer Laufzeit würde man Jahrzehnte für die Lösung des 1000x1000 Feldes benötigen.

Computer sind für solche Aufgaben nicht geschaffen, da müssen wir wohl noch etwas auf die Quantencomputer Ära warten :(

---

Das Ganze sieht fast nach einem 1.Aprilscherz aus.

mfG

Moliets

Answer 2

Hallo

 Wenn einer von uns die hätte, würden wir es dir sicher nicht verraten, sondern die 1000.000 selbst holen ☺

Gruß ♪ lul