Sudoku

Aus Science and Research Hessen

Wechseln zu: Navigation, Suche
Projektlogo
Projektlogo
Screenshot des Bildschirmschoners
Screenshot des Bildschirmschoners
Forschungsart: Sucht die Mindestgrenze vorgegebener Zahlen eines Sudoku Rätsels mit nur einer Lösung
Beschreibung: Sudoku ist ein populäres Rätsel, deshalb googled danach und ihr bekommt eine Erklärung, Programe, u.s.w. . Eine wichtige Sache bei Sudoku ist es gibt immer eine Lösung und zwar wirklich nur eine Richtige ! Ein Programm zu schreiben was diese Lösung findet ist nicht allzu schwer und man kann sehr viele solcher Programme im Internet finden. Durchschnittliche Sudoku Rätsel (aus Zeitungen u.s.w.) haben zwischen 25-30 vorgegebene Zahlen. Normalerweise wird Sudoku schwerer wenn weniger Zahlen vorgegeben sind. Aber dies ist nicht immer richtig, es gibt schwere Sudoku Rätsel mit vielen Zahlen und leichte mit nur wenigen Vorgaben.

Eine interessante Frage ist, wie viele Vorgaben sind nötig, so das das Sudoku tatsächlich nur ein mögliches Ergebnis hat. Die gewöhnliche Grenze liegt bei 8: vorausgesetzt 7 Zahlen sind gegeben. Dann kann man in jeder Lösung alle Möglichkeiten für die zwei nicht vorgegebenen Zahlen durch testen, so dass man auf mindestens zwei verschiedene Lösungen kommt. Überraschenderweise konnte bisher noch keine bessere, niedrigere Grenze mathematisch bewiesen werden. Alle bisher bekannten Sudoku Rätsel mit nur einer Lösung haben 17 vorgegebene Nummern, schaut hier http://people.csse.uwa.edu.au/gordon/sudokumin.php bei einer Sammlung von 41.000 solcher Rätsel.
So dass die derzeitig kleinste Spanne für vorgegebene Hinweise (gegebenen Zahlen) für ein Sudoku Rätsel (mit nur einer Lösung) zwischen 8 und 17 liegt. Das Ziel unseres Projektes ist es diese Kluft zu schließen. Wir starten mit 92.248 Sets mit 8 vorgegebenen Zahlen und erhöhen indem wir nach und nach mehr Zahlen vorgeben und dann prüfen ob es für nur eine Lösung ausreicht. Während der ersten Entwicklungsphase unseres Programms waren wir in der Lage zu zeigen das mindestens 11 Zahlen gegeben sein müssen. Sodas die derzeitige Spanne nur noch 11..17 ist. Durch die Nutzung von verteiltem Rechnen werden wir Schritt für Schritt die minimale Grenze anheben bis ein User die kleinste mögliche Anzahl an Vorgaben findet oder wir beweisen können das es keine möglichen Rätsel mit weniger als 16 Vorgaben gibt.

Teilnehmen:
  • Zuerst müssen Sie BOINC installieren ANLEITUNG
  • Im Manager "Projekt hinzufügen" auswählen
  • Die Anmeldeadresse lautet

Homepage: http://dist2.ist.tugraz.at/sudoku/

Nehmen Sie bereits an dem Projekt teil, so können Sie sich hier unserem Team anschließen !

Platzbedarf: Diese Informationen liegen uns noch nicht vor !
Dauer: Diese Informationen liegen uns noch nicht vor !
Anwendung: sudokutest, Sudoku
Läuft mit: Bild:linux.jpg Linux 32 Bit / 64 Bit; Bild:win.jpg Windows 32 Bit ; Bild:mac.jpg Mac OS X
Leitung: Institute for Software Technology
Graz, University of Technology
Leiter: Diese Informationen liegen uns noch nicht vor !
SaR Teamleiter: FBoerner


team_11627_project53.gif


Zur Homepage News Feed Zu ihrem Konto Zur Teamstatistik Serverstatus


--Sandrik 00:34, 3. Jan 2008 (CET)

Persönliche Werkzeuge