- Start
- |
- Gemeinschaft
- |
- Modelle
- |
- Infos
- |
- Markt
- |
- Hilfe+Kontakt
- |
- |
Hallo,
jetzt hat's mich auch gepackt und ich hab auch ein Progrämmchen geschrieben (bzw. 3 Varianten, jeweils angepasst). 
Vorgehensweise:
- 2 Listen erstellen, in denen für jeden Stein angegeben ist, welcher rechte bzw. untere Nachbar möglich ist
- nach und nach Felder durchgehen, bei möglichen Steinen weiterprobieren mit den nächsten Feldern, ansonsten zurück. (Ist das Backtracking?)
Und das ganze schön optimiert in x86-Assembler. Die 2-Farb-Variante (dafür reichen die normalen 32-Bit-Register (sogar 16 Bit würden reichen)) findet die 800 Lösungen nach ca. 80.000 Versuchen in ca. 2 Millisekunden.
Die 3- und 4-Farb-Variante benutzen die 256-Bit-Register von AVX2 - allerdings mit dem Problem, dass die Suche des nächsten möglichen Steins nicht so schön effizient ist wie mit den normalen Registern. Oder kennt jemand eine gute BSF-Variante für AVX2-ymm-Register?
Wobei ich sagen muss, dass das recht schnelle Versuche waren - ich hab zwar einige gefundene (Teil-)Lösungen kontrolliert, kann mir aber gerade bei den 3- und 4-Farb-Varianten nicht wirklich 100% sicher sein, dass alles stimmt... theoretisch sollte es jedenfalls.
Das 3-Farben-Programm läuft noch, nach 41 Minuten war's bei 560.000 Lösungen und 100 Mrd. Versuchen angelangt. Na hoffentlich stimmt das auch...
Das 4-Farben-Programm läuft noch nicht so lange, das hat nach 7,5 Sekunden schon 246 Steine nach 350 Mio. Versuchen verbaut und eben nach ca. 7,5 Minuten waren's 250 Steine nach 19,8 Mrd Versuchen. Aber noch keine komplette Lösung.
Grüße,
Andreas
