Sudoku Logik-Rätsel als Färbeproblem
Beliebtes Puzzle: Eine junge Frau füllt das Sudoku-Zahlenrätsel einer Tageszeitung aus (Archivfoto). Mathematiker haben die Aufgabenstellung in die Graphentheorie übertragen und festgestellt, dass hinter Sudoku bislang ungelöste Probleme stehen.
Minimal-Sudoku oder nicht? Dieses Zahlenrätsel hat nur 17 Einträge und besitzt genau eine Lösung. Ungeklärt ist, ob es auch Zahlenrätsel mit weniger als 17 ausgefüllten Feldern gibt, die ebenfalls nur eine Lösung haben.
Weitere Variante: Gordon Royle von der University of Western Australia hat Tausende Zahlenrätsel gesammelt, bei denen 17 Ziffern vorgegeben sind und nur eine Lösung exisitiert.
Färbung in der Graphentheorie: Diese Grafik, erstellt von John Lattanzio (Indiana University of Pennsylvenia), zeigt das Prinzip. Gefärbte Knoten dürfen nicht mit Knoten gleicher Farbe verbunden sein. Von einem roten Punkt beispielsweise führt keine Linie zu einem anderen roten Punkt. Dieser Graph enthält 17 Knoten. Ein neunmal neun Felder großes Sudoku-Feld auf diese Weise dargestellt, würde dies ein komplexes Liniengewirr ergeben.
Sudoku-Brettspiel: Mathematiker von der Queen's University beschreiben das Logik-Rätsel als Färbeaufgabe der Graphentheorie - finde eine gültige Knotenfärbung für das System.
