Das Millionen Dollar Schachproblem
 

Hallo, ich bin zufällig auf eine Seite der University of St. Andrews in Schottland über Umwegen gestoßen, wo es wohl darum geht, ein Algorithmus zu finden, um bei einem Schachbrett mit 1000x1000 Feldern Damen so zu verteilen, das sie sich nicht gegenseitig bedrohen, wenn ich das ganze richtig verstanden habe. Für Computer wohl nicht lösbar, bzw. sollte ein Deep Thought dafür angeblich 500.000.000 Jahre brauchen.
Das ganze soll mit 1 Millionen Dollar belohnt werden.

Durch eine ev. Lösung sollen widerrum andere Probleme besser lösbar sein.

https://www.st-andrews.ac.uk/news/ar...1539813,en.php

Tja, wer gerade mal nichts zu tun hat ;)

AW: Das Millionen Dollar Schachproblem
 

Hallo,
auf einem normalen Schachbrett ist das kein Problem,
aber bei 1000 x 1000 Feldern !? Das ist mir zu viel ..

Grüße
Gerd

AW: Das Millionen Dollar Schachproblem
 

Es ist nicht so schwierig ein rekursives Algorithmus dafür zu programmieren, habe ich schon mal gemacht. Aber das wird wohl sehr viel rechenzeit kosten für ein 1000 x 1000 brett...
Und dazu hat man auch noch gesagt eine lösung sei nicht genügend: es sollte ein neues, sehr effizientes algorithmus sein... So etwas wie ein alternatives Simplex algorithmus?!

Ein million ist aber das pondern wert... ;)

Gruss, Paul

AW: Das Millionen Dollar Schachproblem
 

Sehr viel ist eine gnadenlose Untertreibung. ;)
Der Algorithmus muss schon ausgefallener sein...

AW: Das Millionen Dollar Schachproblem
 

Was soll der Algorithmus denn finden bzw. beweisen? Eine (von möglicherweise vielen) Lösung(en) zu konstruieren ist doch vergleichsweise trivial. Es können nicht mehr als 1000 Damen sein. Jede Reihe und jede Spalte darf max. eine Dame enthalten... Zusätzlich sind die Diagonalen zu beachten. Wenn mich nicht alles täuscht, kann man die Damen einfach auf dem Brett aufstellen nach einem Schema "nächste Zeile 2 Felder rechts" und nach Überlauf in der letzten Spalte rechts dann wieder links entsprechend die nächste freie Spalte besetzen...

Also: was genau ist die Aufgabe und wo löst man dann den 1 Mio Scheck ein? ;)

AW: Das Millionen Dollar Schachproblem
 

Dein Algo ist völlig korrekt und Du brauchst nur eine gültige Lösung für den Scheck ...

Das "Problem" steckt einfach in der Fakultät von 1000. Sonst alles easy ...

Stay tuned ...
Carsten

AW: Das Millionen Dollar Schachproblem
 

:cool: ;)

AW: Das Millionen Dollar Schachproblem
 

Carsten, was ist das tatsächliche Problem? Muss man ALLE Lösungen finden? Oder die Anzahl der möglichen Lösungen? Möglicherweise reduziert um Spiegelungen und Drehungen? Wenn es so einfach wäre, hätte doch schon jemand das Geld abgeholt... :)

AW: Das Millionen Dollar Schachproblem
 

Wenn das nur so einfach wäre... Versuche es doch mal auf ein schachbrett 8 x 8, du wirst sehen das es einige zeit kostet bevor du eine lösung hast ;).

Wenn man weiter liest auf die website, wird es klar das man nicht nur eine (der möglich viele) lösung haben will, doch das man auch ein (wenn möglich neues) effizientes algoritmus sucht das man vielleicht auch für viele andere komplexe probleme nutzen kann.

Gruss, Paul

AW: Das Millionen Dollar Schachproblem
 

Hi,

Eigentlich wird bei der Fragestellung n-Damen auf einem n x n Feld immer gefordert, dass alle Lösungen gefunden werden (gesamt und um Symmetrien bereinigt, bei einem 8 x 8 Feld sind das 96 Lösungen und 12 bereinigt).

Bei n = 1000 hast du ca. 1000! (1000 Fakultät) Möglichkeiten. Da liegt das Problem. Ich glaube , Du hast dir über die Größe der Zahl noch keine Gedanken gemacht.

Das ein effizienter Algo gesucht wird (wie Paul schreibt), ist nicht die Aufgabe, sondern quasi der Nebeneffekt. Hast du nämlich einen Algo, der alle Lösungen in Polynominalzeit lösen könnte, wäre der automatisch sehr sehr effizient.

Ich würde dir allerdings schon einige Tüten Gummibärchen spendieren, wenn du bis Jahresende eine einzige Lösung für n = 1000 präsentierst Egal wie elegant der Algo ist ...

Stay tuned ...
Carsten

AW: Das Millionen Dollar Schachproblem
 

Ich bin der Meinung: eine Lösung zu finden, ist in relativ kurzer Zeit möglich. Im Prinzip ist das rekursiv programmierbar, mir fallen ad hoc mehrere Ansätze dafür ein. ALLE Lösungen zu finden, ist in der Tat eine Aufgabe... Ganz dunkel tauchen in der Erinnerung Begriffe wie NP-vollständig und NP-schwer auf... :D Das ist lange her und weitab von meinem momentanen Tätigkeitsfeld... insofern mag ich das nicht beurteilen.

Falls ich in der dunklen Jahreszeit etwas Zeit finde... kannst Du mir nach Prüfung meiner Lösung gerne ein paar Gummibärchen zusenden. Für meine Töchter... ;)

Viele Grüße,
Andreas

AW: Das Millionen Dollar Schachproblem
 

Hi Andreas,

Kannst du bitte mal kurz die Fakultät von 1000 hier als Antwort posten ... nur damit ich mir sicher bin, dass du die Zahl verstanden hast? :rolleyes:

Stay tuned ...
Carsten

AW: Das Millionen Dollar Schachproblem
 

Hallo Carsten und Andreas,

jetzt möchte ich doch mal ein paar eigene Informationen zu dem Thema beisteuern. Schon in meiner Schulzeit hatte ich mich mit dem 8-Damen-Problem auf dem regulären Schachbrett beschäftigt und einen bekannte Algorithmus auf einem TI-58 Taschenrechner implementiert. Fragt bitte nicht, wie lange das schon her ist.

Nach meinem Studium habe ich dann rekursiven Standardalgorithmus von Niklaus Wirth (in Pascal) mit Turbo Prolog 2.0 implementiert und nach algorithmischen Verbesserungen gesucht, sodass auch für "größere" n (d. h. damals n= 20 bis 100) Lösungen gefunden wurden, allerdings auf Kosten der Vollständigkeit.

Ich hatte mit der von Andreas skizzierten Strategie Erfolg und bin zu einem selektiven Algotihmus gekommen, der direkt auf eine Lösung zusteuert und danach viele weitere Lösungen ausgibt. Es wird dabei aber nur ein geringer Prozentsatz der tatsächlich möglichen Lösungen gefunden.

Schließlich ist es mir gelungen, für die eine direkt angesteuerte Lösung eine Formel zu entwickeln. Ich werde mal auf dem Speicher nach den Unterlagen dazu suchen. Dann gebe ich euch eine Lösung für das 1000-Damen-Problem.

Für das wissenschaftliche Problem (P = NP?) sollte das aber irrelevant sein.

Grüße von Detlef

AW: Das Millionen Dollar Schachproblem
 

Hallo Detlef,

Das klingt sehr interessant. Bitte auch die "Formel" bzw. den Algorithmus veröffentlichen, wenn Du sie / ihn noch findest. Die Gummibärchen gehören dann auf jeden Fall dir (falls Andreas nicht schneller ist .

Stay tuned ...
Carsten

AW: Das Millionen Dollar Schachproblem
 

Das klingt wirklich sehr interessant. Wenn das klappt, dann sollte Detlef zumindestens ein teil von das million bekommen...!

Gruss, Paul

AW: Das Millionen Dollar Schachproblem
 

Eine Million Gummibärchen? :D

AW: Das Millionen Dollar Schachproblem
 

Mir reichen 2 Tütchen... ;) Und nein: unter Druck setzen lass ich mich momentan nicht. Muss das in die dunkle Jahreszeit ab November verschieben. Zur Zeit keinen freien Kopf dafür.

1000! rechne ich NICHT aus. Ist auch nicht nötig, um eine (eine einzige!) Lösung zu konstruieren. Davon bin ich überzeugt und Detlefs Posting scheint das zu stützen.

Auf eine Veröffentlichung von Algorithmus oder Lösung bin ich gespannt. IMHO reicht dies aber nicht, die Mio $ abzuholen... da wird mehr für verlangt, auch wenn ich es noch nicht detailliert genug nachgelesen habe.

Wer mathematisch vorbelastet ist und Geld benötigt, der kann gerne auch mal hier drüberschauen, ob er für eins der sieben Probleme eine Lösung parat hätte. Hatte mich vor geraumer Zeit mal mit beschäftigt, aber irgendwie liegen mir diese Probleme nicht... :D

https://de.wikipedia.org/wiki/Millennium-Probleme

Viele Grüße,
Andreas

AW: Das Millionen Dollar Schachproblem
 

Irgendwie liegen diese probleme mir auch nicht :p.
Aber es gibt auch besser lösbare probleme auf https://projecteuler.net/
Leider gibt es dort aber keine finanzielle preise, nur die ehre...

Gruss, Paul

AW: Das Millionen Dollar Schachproblem
 

Hallo zusammen,

die Aufzeichnungen habe ich auf dem Speicher schnell gefunden. Hätte aber aber nicht gedacht, dass die Lösung doch etwas mühsam einzugeben ist.

Sei n = die Anzahl der zu setzenden Damen auf einem Schachbrett der Größe n*n

i bezeichnet die Nummer der Linie, auf die eine Dame gesetzt werden soll (z. B. g-Linie auf normalem Schachbrett hat die Nummer i=7). Es ist zugleich die Nummer der zu setzenden Dame.

D(i) ist die Nummer der Reihe, auf welche die i-te Dame gesetzt wird.

Die Lösung ist davon abhängig, welchen Rest man bei der Division von n durch 6 erhält:

Fall 1: n mod 6 in {0,1,4,5} (Das schließt das 1000-Damen-Problem mit ein)

D(i) = 2i für i <= n/2
D(i) = 2i-(n+1) für i >n/2 bei geradem n
D(i) = 2i-n für i>n/2 bei ungeradem n

Fall 2: n mod 6 = 2, aber erst ab n>=20 funktionierend (n=8 und n=14 gehen nicht)
D(i) = 4+2i für i<= n/2-2
D(i) = 2 für i = n/2-1
D(i) = 4 für i = n/2
D(i) = 2i-(n+1) für i > n/2

Fall 3: n mod 6 = 3, n >= 9
D(i) = 2+2i für i <= (n-1)/2-1
D(i) = 2 für i = (n-1)/2
D(i) = 2i-(n-1)+3
D(i) = 1 für i=n-1
D(i) = 3 für i=n

Beispiel: n=11 (n mod 6 = 5, also Fall 1) als Demo der typischen Springerabstände

D(1) = 2*1 = 2
D(2) = 2*2 = 4
D(3) = 2*3 = 6
D(4) = 2*4 = 8
D(5) = 2*5 = 10
D(6) = 2*6-11 = 1
D(7) = 2-7-11 = 3
D(8) = 2*8-11 = 5
D(9) = 2*9-11 = 7
D(10) = 2*10-11 = 9
D(11) = 2*11-11 = 11

So, jetzt hoffe ich, dass das auch stimmt, was ich mir damals notiert hatte. Ich hatte übrigens auch mit einem Beweis angefangen, der mir aber wegen der vielen Fallunterscheidungen zu aufwendig war.

Gruß Detlef

AW: Das Millionen Dollar Schachproblem
 

Vielen dank Detlef,

Leider bin ich die kommende tage sehr beschäftigt.
Ab Dienstag kann ich erst damit anfangen zu studieren und vielleicht ein programm dafür machen. Bin sehr neugierig wie schnell das geht!

Gruss, Paul