Sudoku Rätsel und japanische Lebensweisheiten

Wie viele Felder müssen in einem Sudoku Rätsel mindestens vorbelegt sein?

Im Jahr 2012 stellten Wissenschaftler an der Universität Dublin fest, dass mindestens 17 Felder vorbelegt sein müssen, um ein Sudoku eindeutig – also ohne raten – lösen zu können.

Der klassische mathematische Beweis wurde noch nicht erbracht, aber die Forscher haben die Zahl 17 nach dem Ausschlußverfahren ermittelt.

Das 17 die minimale Sudoku Rätsel Vorbelegung ist, wurde schon länger vermutet, da einfach kein Sudoku mit nur 16 Ziffern gefunden werden konnte.

Also haben die Wissenschaftler einen Supercomputer alle ca. 34 Billiarden möglichen Kombinationen mit 16 Zahlen durchrechnen lassen, und anschliessend überprüft, ob eines der Sudoku Rätsel eindeutig zu lösen wäre.

Das Ergebnis: Es wurde kein Sudoku Rätsel mit 16 Zahlen gefunden.

Für die Berechnung hat der Supercomputer übrigens ca. 1 Jahr benötigt. Ein handelsüblicher PC wäre damit ca. 800 Jahre beschäftigt gewesen.

Interessant ist, das es auch Sudoku Rätsel mit einer sehr hohen Vorbelegung gibt, die trotzdem nicht eindeutig zu lösen sind. So kann selbst ein Sudoku mit 77 vorbelegten Zahlen zwei mögliche Lösungen haben.

 

Kommentar hinterlassen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.