Schachcomputer.info Community

Zurück   Schachcomputer.info Community > Schachcomputer / Chess Computer: > Die ganze Welt der Schachcomputer / World of chess computers


Antwort
 
Themen-Optionen Ansicht

  #11  
Alt 05.09.2017, 10:26
Drahti Drahti ist offline
Revelation
 
Registriert seit: 27.02.2016
Ort: An der Schleuse
Land:
Beiträge: 730
Abgegebene Danke: 602
Erhielt 390 Danke für 254 Beiträge
Aktivitäten Langlebigkeit
3/20 8/20
Heute Beiträge
1/3 ssssss730
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... 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
Mit Zitat antworten
  #12  
Alt 05.09.2017, 18:56
Benutzerbild von DarkStar
DarkStar DarkStar ist offline
Saitek RISC 2500
 
Registriert seit: 30.05.2010
Land:
Beiträge: 197
Bilder: 17
Abgegebene Danke: 30
Erhielt 264 Danke für 68 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss197
AW: Das Millionen Dollar Schachproblem

Hi Andreas,

 Zitat von Drahti Beitrag anzeigen
Ich bin der Meinung: eine Lösung zu finden, ist in relativ kurzer Zeit möglich.
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?

Stay tuned ...
Carsten
__________________
ChessLab BCS - http://google.com/+CarstenMeyer
Mit Zitat antworten
  #13  
Alt 05.09.2017, 19:47
d.hammes d.hammes ist offline
Mark V
 
Registriert seit: 19.10.2007
Beiträge: 15
Abgegebene Danke: 35
Erhielt 22 Danke für 7 Beiträge
Aktivitäten Langlebigkeit
0/20 17/20
Heute Beiträge
0/3 sssssss15
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
Mit Zitat antworten
  #14  
Alt 05.09.2017, 20:07
Benutzerbild von DarkStar
DarkStar DarkStar ist offline
Saitek RISC 2500
 
Registriert seit: 30.05.2010
Land:
Beiträge: 197
Bilder: 17
Abgegebene Danke: 30
Erhielt 264 Danke für 68 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss197
AW: Das Millionen Dollar Schachproblem

Hallo Detlef,

 Zitat von d.hammes Beitrag anzeigen
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.
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
__________________
ChessLab BCS - http://google.com/+CarstenMeyer
Mit Zitat antworten
  #15  
Alt 05.09.2017, 23:02
Benutzerbild von paulwise3
paulwise3 paulwise3 ist offline
Schachcomputer Koryphäe
 
Registriert seit: 19.02.2015
Ort: Eindhoven
Alter: 76
Land:
Beiträge: 1.510
Abgegebene Danke: 4.657
Erhielt 1.625 Danke für 725 Beiträge
Aktivitäten Langlebigkeit
3/20 10/20
Heute Beiträge
2/3 sssss1510
AW: Das Millionen Dollar Schachproblem

 Zitat von DarkStar Beitrag anzeigen
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
Das klingt wirklich sehr interessant. Wenn das klappt, dann sollte Detlef zumindestens ein teil von das million bekommen...!

Gruss, Paul
__________________
Wenn ich mich irre, sollte es ein Horizont Wirkung sein
Mit Zitat antworten
  #16  
Alt 06.09.2017, 09:13
Benutzerbild von Solwac
Solwac Solwac ist offline
Revelation
 
Registriert seit: 18.07.2010
Land:
Beiträge: 782
Abgegebene Danke: 189
Erhielt 338 Danke für 216 Beiträge
Aktivitäten Langlebigkeit
0/20 14/20
Heute Beiträge
0/3 ssssss782
AW: Das Millionen Dollar Schachproblem

Eine Million Gummibärchen?
Mit Zitat antworten
  #17  
Alt 06.09.2017, 10:09
Drahti Drahti ist offline
Revelation
 
Registriert seit: 27.02.2016
Ort: An der Schleuse
Land:
Beiträge: 730
Abgegebene Danke: 602
Erhielt 390 Danke für 254 Beiträge
Aktivitäten Langlebigkeit
3/20 8/20
Heute Beiträge
1/3 ssssss730
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...

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

Viele Grüße,
Andreas
Mit Zitat antworten
  #18  
Alt 06.09.2017, 11:43
Benutzerbild von paulwise3
paulwise3 paulwise3 ist offline
Schachcomputer Koryphäe
 
Registriert seit: 19.02.2015
Ort: Eindhoven
Alter: 76
Land:
Beiträge: 1.510
Abgegebene Danke: 4.657
Erhielt 1.625 Danke für 725 Beiträge
Aktivitäten Langlebigkeit
3/20 10/20
Heute Beiträge
2/3 sssss1510
AW: Das Millionen Dollar Schachproblem

Irgendwie liegen diese probleme mir auch nicht .
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
__________________
Wenn ich mich irre, sollte es ein Horizont Wirkung sein
Mit Zitat antworten
  #19  
Alt 06.09.2017, 18:38
d.hammes d.hammes ist offline
Mark V
 
Registriert seit: 19.10.2007
Beiträge: 15
Abgegebene Danke: 35
Erhielt 22 Danke für 7 Beiträge
Aktivitäten Langlebigkeit
0/20 17/20
Heute Beiträge
0/3 sssssss15
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
Mit Zitat antworten
Folgende 3 Benutzer sagen Danke zu d.hammes für den nützlichen Beitrag:
Drahti (07.09.2017), paulwise3 (07.09.2017), Solwac (06.09.2017)
  #20  
Alt 07.09.2017, 00:15
Benutzerbild von paulwise3
paulwise3 paulwise3 ist offline
Schachcomputer Koryphäe
 
Registriert seit: 19.02.2015
Ort: Eindhoven
Alter: 76
Land:
Beiträge: 1.510
Abgegebene Danke: 4.657
Erhielt 1.625 Danke für 725 Beiträge
Aktivitäten Langlebigkeit
3/20 10/20
Heute Beiträge
2/3 sssss1510
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
__________________
Wenn ich mich irre, sollte es ein Horizont Wirkung sein
Mit Zitat antworten
Antwort

Themen-Optionen
Ansicht

Forumregeln
Du bist nicht berechtigt, neue Themen zu erstellen.
Du bist nicht berechtigt, auf Beiträge zu antworten.
Du bist nicht berechtigt, Anhänge hochzuladen.
Du bist nicht berechtigt, deine Beiträge zu bearbeiten.

BB code ist An
Smileys sind An.
[IMG] Code ist An.
HTML-Code ist An.

Gehe zu

Ähnliche Themen
Thema Erstellt von Forum Antworten Letzter Beitrag
Hilfe: Mondial II - Problem Eckehard Kopp Technische Fragen und Probleme / Tuning 5 09.05.2016 22:48
Frage: MM I-Problem Eckehard Kopp Technische Fragen und Probleme / Tuning 1 26.03.2016 03:09
Frage: Problem mit einem Problem udo Teststellungen und Elo Listen / Test positions and Elo lists 10 29.05.2011 01:25


Alle Zeitangaben in WEZ +1. Es ist jetzt 11:42 Uhr.



Powered by vBulletin (Deutsch)
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
©Schachcomputer.info