SUDOKU (beendet)

Aus Rechenkraft
(Weitergeleitet von SUDOKU)
Wechseln zu: Navigation, Suche
Logo
eindeutig lösbares Sudoku mit 17 vorgegebenen Zahlen

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

InfoIcon.png Sudoku
Name Sudoku
Kategorie Spiele
Ziel finden eines minimalen Sudokus
Kommerziell   nein
Homepage dist2.ist.tugraz.at/sudoku/


Uni.jpg Institut für Softwaretechnologie
TU Graz, Österreich


 
Austria01.gif    Dieses Projekt wird in Österreich durchgeführt.


Projektstatus

InfoIcon.png 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

Icon windows 16.png   Windows Checkbox 1.gif   (XP+)
Icon linux 16.png   Linux Checkbox 1.gif  
Icon linux 16.png   Linux 64bit Checkbox 1.gif  
Icon dos 16.png   DOS Checkbox 0.gif  
Icon macos 16.png   MacOS X Checkbox 1.gif  
Icon freebsd 16.png   BSD Checkbox 0.gif  
Icon solaris 16.png   Solaris Checkbox 0.gif  
Icon java 16.png   Java (betriebssystemunabhängig)  Checkbox 0.gif  

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)
  • 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



Eigene Werkzeuge