SUDOKU (beendet)
Sudokus - wer kennt die Zahlenquadrate nicht? Das Projekt der TU Graz sucht die kleinste Anzahl von vorgegebenen Zahlen, die das Sudoku noch eindeutig lösen lässt. Es gibt viele Beispiele dafür, dass noch 17 Gegebene eindeutig lösbar sind. Das haben japanische Rätselenthusiasten herausgefunden. Nicht bekannt oder bewiesen ist, ob es ein eindeutig lösbares Sudoku, mit nur 16 (oder sogar noch weniger) Gegebenen, gibt.
Das Projekt scheint seit April 2009 inaktiv zu sein. Es wurden keine Credits mehr vergeben und die Seite ist zur Zeit nicht erreichbar.
Im RCN-Forum schreibt der Admin: Der Server ist weg, es gibt keine Software für den nächsten Abschnitt. Die Zukunft ist somit ungewiss und er wird Fortschritte da ankündigen.
Siehe auch:
- Sudoku@vtaiwan, ein Projekt, das die Fragestellung auch zu lösen versucht
2012 wurde das Problem von Gary McGuire und seinen Kollegen gelöst. Sie haben mit einem Supercomputer nachgewiesen haben, dass man mindestens 17 Zahlen braucht um ein Sudoku eindeutig zu lösen. Sie mussten fast 5.500.000.000 Möglichkeiten durchprobieren. Eigentlich hätten sie 6,7*10^21 durch testen müssen, aber mit der Nutzung von Symmetrien ging es deutlich schneller. Seite, <ref>Paper</ref>
Inhalt
Die Regeln
Ziel eines Sudokus ist es, die vorhandenen Felder (i.d.R. 9x9) so mit Zahlen von 1 bis 9 auszufüllen, dass in jeder Zeile und in jeder Spalte jede Zahl nur einmal vorkommt. Zudem muss in jedem Unter-Quadrat (3x3 Felder) jede Zahl ebenfalls einmal vorkommen.
Projektübersicht
 Sudoku
| |
|---|---|
| Name | Sudoku |
| Kategorie | Spiele |
| Ziel | finden eines minimalen Sudokus |
| Kommerziell | nein |
| Homepage | dist2.ist.tugraz.at/sudoku/ |
|
Institut für Softwaretechnologie TU Graz, Österreich |
| Dieses Projekt wird in Österreich durchgeführt. |
Projektstatus
| Projektstatus
| |
|---|---|
| Status | wohl beendet |
| Beginn | 27.8.07 |
| Ende | April 2009 |
Projektlinks
Statistiken
| Wo | Übersicht | Top Teams | Top User |
|---|---|---|---|
| Projekt Home Page | Top Teams | Top User | |
| BOINCstats.com | Übersicht | Top Teams | Top User |
| BOINCsynergy.com: Der Service wurde eingestellt. | |||
| allprojectstats.com: Der Service wurde eingestellt. |
Clientprogramm
Betriebssysteme
| Windows | (XP+) | |
| Linux | ||
| Linux 64bit | ||
| DOS | ||
| MacOS X | ||
| BSD | ||
| Solaris | ||
| Java (betriebssystemunabhängig) |
WU-Informationen
Aktuelle und genaue Details für BOINC-Projekte gibt es bei WUProp.
| Name | RAM | Dauer | Deadline | Speicherplatz | Download | Upload | Mindestanforderung |
|---|---|---|---|---|---|---|---|
| Sudoku 5.39 | 1,7 MB | bis 100 h (AMDX2 32bit 3,0 GHz) | 300 Tage | MB | MB | MB | {{{mindestanforderung}}} oder besser
|
Die Dauer ist die durchschnittliche Rechenzeit, die auf entsprechender CPU (Taktung in der Klammer) gebraucht wird.
Die Deadline ist die Zeitspanne, in der die Work unit berechnet sein muss.
Installation
SUDOKU (beendet) benutzt die BOINC-Infrastruktur. Die Anmeldung, Installation und Konfiguration sind auf der allgemeinen BOINC-Seite beschrieben.
Veröffentlichte Versionen
- 15.11.2007: sudoku 5.39 (MacOS X)
- 12.11.2007: sudoku 5.39 (Windows)
- 09.11.2007: sudoku 5.39 (Linux, Linux 64bit)
- 29.08.2007: sudokutest 5.01 (Linux)
Client-Vorgehensweise
- Im Projekt arbeitet man sich von unten an die 17 Gegebenen heran. Man testet also nicht zuerst alle Sudokus mit 16 Gegebenen auf eindeutige Lösbarkeit, davon gäbe es zu viele. Unterste Schranke waren 8 Gegebene (bei 7 Gegebenen kann man z.B. in der Lösung die 8. und 9. Zahl vertauschen und erhält so eine andere Lösung). Bereits vor dem Projekt wurde intern alle Möglichkeiten von 8 Gegebenen untersucht, keines war eindeutig lösbar. Ebenso erging es 9 und 10 Gegebenen. Mit Hilfe von DC soll nun mit 11 beginnend weitergesucht werden, bis eine eindeutige Lösung gefunden wurde, oder man auch für 16 Gegebene keine eindeutige Lösung gefunden hat.
- 11 Gegebene wurden erfolgreich berechnet. Es gibt kein eindeutig lösbares Sudoku dazu. Wie im Forenthread erklärt wird, lässt sich die restliche Laufzeit in Tagen für das nächste Level bestimmen, in dem man die Zahl aus der System Summary (unten links auf der Seite : There are currently further X workunits to be inserted) durch die Anzahl der täglich berechneten WUs teilt (gleiche Seite oben).
- Das aktuelle Level erkennt man an den work unit-Namen. B1025303441_12__re2 ist eine work unit mit 12 Gegebenen.
Links
