Rätsel

Mathematischer Durchbruch in der Sudoku-Forschung

9. Jänner 2012, 17:21

Welche ist die geringste Anzahl an vorgegebenen Ziffern, um Sudokus eindeutig lösen zu können?

Dublin/London/Boston - Die meisten Sudokus - so auch diejenigen im Standard - haben rund 25 vorgegebene Zahlen. Je weniger es sind, desto schwieriger sind die japanischen Zahlenrätsel mit ihren insgesamt 81 Feldern zu knacken. Doch welche ist die geringste Anzahl an vorgegebenen Ziffern, um Sudokus eindeutig lösen zu können?

An dieser Frage haben sich zahlreiche Sudoku-Mathematiker versucht. Die meisten einschlägigen Experten gingen bisher davon aus, dass es mindestens 17 vorgegebene Ziffern seien. Doch gibt es dafür noch keine Beweise. Einen solchen will nun der irische Mathematiker Gary McGuire mithilfe eines komplexen Algorithmus und sieben Millionen Stunden Rechenzeit an Supercomputern gefunden haben. Auf einer Fachkonferenz am Sonntag in Boston haben Kollegen seine am arXiv-Server publizierte Arbeit jedenfalls positiv gewürdigt und für "wahrscheinlich korrekt" eingeschätzt, berichtet Nature News. (tasch, DER STANDARD, Print-Ausgabe, 10. Jänner 2012)

Kommentar posten
Posting 1 bis 25 von 85
1 2 3
Hansjacob
10
13.1.2012, 14:23
Jämmerlich!

Das soll ein "mathematischer Durchbruch" sein?

"The only realistic way to do it was the brute force approach,” says Gordon Royle"

Das hat mit Mathematik so viel zu tun als würde ich 100.000 Dreiecke mit Lineal und Winkelmesser daraufhin untersuchen, ob der Sinussatz wirklich immer stimmt.

Ein Beweis sieht schon etwas anders aus als der brute force approach.
Letzterer ist für die eher Denkschwachen gut geeignet. Dass man ihn als mathematischen Durchbruch bejubelt, finde ich schade.

Und 1+1 ist 2 +/- 0,00000005 sagt der Taschenrechner.

Cuchullain
00
18.1.2012, 13:45
"2 +/- 0,00000005"

2 ± 0,00000005

ALT + 241 (am Ziffernblock!)

esistnichtwasesist
01
11.1.2012, 08:59
ich habe einen eleganten und rigorosen beweis gefunden

allerdings reichen die 750 zeichen eines postings leider nicht aus...

Rahoul
00
13.1.2012, 19:14

Hic Rhodus, hic salta.

woifee 0.0
03
10.1.2012, 22:49

Ich habe auch letztens einen Durchbruch bei StarCraft II erreicht, wo bleiben meine Forschungsgelder :D

angelvoices
20
10.1.2012, 15:47
es ist schon schwierig das Problem zu verstehen

die Lösung ist um so schwieriger...und wahrscheinlich nur von einem einzigen Menschen verständlich...

mit_abstand
00
10.1.2012, 21:55

was ist an diesem problem schwierig zu verstehen?

wat?
00
10.1.2012, 14:20

Serious or just trollin?

Kate Austen
12
10.1.2012, 10:41
erscheint mir sehr nummerisch zu sein, dieser Beweis, und wenig elegant

Prof. Gerald Lambeau hätte damit keine Freude

her wig
01
10.1.2012, 17:39
Brute force

Ist aber egal, das Ergebnis zählt.

Ein wirklich eleganter Beweis müsste sowieso die Anzahl der Felder als Variable enthalten.

Arjuna, the beautiful
151
10.1.2012, 09:40
Durchbruch der Wissenschaft

Und wieder ist dieser Planet ein Stückchen lebenswerter und sicherer geworden.

Mit solchen schönen Erfolgen der Wissenschaft werden wir sicher in wenigen Millenien Armut und Umweltzerstörung in unserer Welt zum Verschwinden bringen.

Danke!

Zinsenfeger
01
10.1.2012, 15:36
war auch schon Zeit

Normalerweise wird dieser Schwachsinn in der Abteilung für Geisteswissenschaften gepostet, jetzt ist er endlich auch einmal in der Mathematischen gelandet.
...za wos brauch des, mia kochn Erdäpfl?

The Celt
01
10.1.2012, 09:27
Supercomputers..

Für die Leute die wissen möchten welche "Supercomputers" verwendet worden sind.
http://www.ichec.ie/infrastructure/
http://www.ichec.ie/infrastru... ure/stokes

Und bitte nicht vergessen wenn z.B. bei einem quad core CPU gilt 1 Std als 4 Computing hours usw.

Also man könnte theoretisch mit 4 quad core CPUs 384 Std an einem Tag Rechenzeit schaffen.

Ich nehme an der Stokes verwendet worden ist mit 3840 cores!! Also das wäre ca. 76 Tage (ohne downtime).

Cuchullain
00
18.1.2012, 13:58
Bild 4:

Eignet sich der Boden für ein paar batterings?

_ricko_
02
10.1.2012, 13:09
3840 cores sind auch nicht die welt

rechnete gerade mit 4000 cores und anschließend mit 8k am VSC2 der tu wien

Dr. Seltsam
 
10
10.1.2012, 09:20

So viel Rechenpower für einen kleinen Beweis! Das ist nicht sehr elegant!

Carlos Clementin
42
10.1.2012, 07:18
Da hilf kein Supercomputer !!

sieben Millionen Stunden Rechenzeit .... und das auf einem Supercomputer.. ..
Welche Rechnung haben die für 7.000.000 h = ca. 800 JAHRE !!! Rechenzeit bekommen ... denn die ist auf solchen Geräten sehr teuer!

Magic Washroom
00
10.1.2012, 16:52
ich zitiere den hansi weiter unten:

""K" hat 705.024 Kerne => 7.000.000 Stunden / 705.024 Kerne = 9,93 Stunden / Kern, wenn ich das richtig verstanden habe..."

Carlos Clementin
00
10.1.2012, 19:01

So war mein Posting gemeint - dass eben diese Angabe "sieben Millionen Stunden Rechenzeit an Supercomputern gefunden haben" falsch ist sondern --- es müsste ein Äquivalent angegeben werden wie zB bei Mannjahr -
Als auf welchem gerät hätte es 7 Mio Studen gedauert _ auf dem Taschenrechner einem C64 oder dem Cray oder dem Singlekern des selben Rechner oder per Hand ...

Zinsenfeger
00
10.1.2012, 15:37

das ist immer noch schneller als Deep Thought

Calimero22
02
10.1.2012, 17:47

aber nicht so spaßig wie deep throat ...

dr semmel
07
10.1.2012, 08:58

Da spricht der Experte ...

forex
01
10.1.2012, 08:47

ganz einfach - er hats auf 7 mio. supercomputern innerhalb einer stunde berechnet.

sowieso
11
10.1.2012, 07:35
buaha!

vorallen: welchen Supercomputer haben sie vor 800 Jahren mit dieser Berechnung betraut?

Avatar
10

Sudokus letzter Satz. Mal sehen ob es irgendwann einer mit 9 Ziffern schafft zu lösen oder ob es dann vielleicht sogar mehrere Lösungen bereits geben kann.

Kommentar posten
Posting 1 bis 25 von 85
1 2 3

Die Kommentare von Usern und Userinnen geben nicht notwendigerweise die Meinung der Redaktion wieder. Die Redaktion behält sich vor, Kommentare, welche straf- oder zivilrechtliche Normen verletzen, den guten Sitten widersprechen oder sonst dem Ansehen des Mediums zuwiderlaufen (siehe ausführliche Forenregeln), zu entfernen. Der/Die Benutzer/in kann diesfalls keine Ansprüche stellen. Weiters behält sich die derStandard.at GmbH vor, Schadenersatzansprüche geltend zu machen und strafrechtlich relevante Tatbestände zur Anzeige zu bringen.