Projekt SuDoKu

Sudoku – Eine Weltreise

Die meisten denken bei Sudoku wahrscheinlich gleich an Japan. Es kam in den vergangenen Jahrzehnten von dort zwar zu uns, aber der Ursprung liegt wo anders. Die ersten sudokuähnlichen Rätsel stammen von dem Schweizer Mathematiker Leonard Euler(1707-1783). Sie entstanden im 18. Jahrhundert. Bezeichnet wurden sie als „carré latin“ (lateinische Quadrate). Sie waren allerdings noch nicht in Unterquadrate unterteilt.

Die französischen Zeitungen „Le Siècle“ und „La France“ veröffentlichten von 1882 bis 1914 regelmäßig so genannte „ Carré magique diabolique“ (Teuflische magische Quadrate). Diese besaßen jedoch ebenso keine Unterblöcke. Sie konnten sich nicht durchsetzen.

Das Sudoku, wie wir es heute kennen erschien 1979 in der Zeitschrift „Dell Pencil Puzzles & Word Games“ (Bleistifträtsel & Wortspiele). Es trug den Namen „Number Place“(Zahlenplatz). Zunächst wurde es anonym veröffentlicht. Später fand man heraus, dass der am 2. März 1905 in Connersville, Indiana, geborene Amerikaner Howard Garns der Vater dieser faszinierenden Rätsel war. Der damals 74-Jährige Architekt starb zehn Jahre später. Er erlebte nicht mehr, welche Begeisterung sein „Zahlenrätsel“ auslöste.

Anfangs in den USA publiziert erlebte das Sudoku seinen Durchbruch zwischen 1984 und 1986 in Japan. Dort erhielt es auch seinen heutigen Namen. Aus der etwas umständlichen Bezeichnung

„Sūji wa dokushin ni kagiru“ (dt. etwa: „Isolieren Sie die Zahlen; die Zahlen dürfen nur einmal vorkommen“) kreierte Maki Kaij den Namen Sudoku. Der Herausgeber der Zeitschrift „Nikoli“, welche diese Rätsel in Japan regelmäßig abdruckte, bediente sich dabei jeweils der ersten Schriftzeichen der ursprünglichen japanischen Bezeichnung.
Auf Japanisch sieht das Ganze so aus: 数独!

Doch den ganz große „Boom“ des Sudokuspiels verdanken wir einem Neuseeländer. Der pensionierte Richter Wayne Gould (*03.07.1945) begegnete 1997 dem Zahlenspiel auf einer Reise durch Japan und widmete sich sechs Jahre lang der Entwicklung eines Computerprogramms, mit dem man Sudokus generieren konnte. Diese Rätsel wurden 2004 in der Londoner Times veröffentlicht und machten Gould im Lauf der Jahre zum Millionär.

Damit wurde die große Sudoku-Begeisterung geweckt. Österreichische Zeitungen wie „Der Standard“ und „Die Kronen-Zeitung“ veröffentlichten 2005 regelmäßig Sudokus. Im gleichen Jahr erschienen auch in Deutschland in „Die Zeit“ und der „Hamburger Morgenpost“ die beliebten Zahlenrätsel. Im folgenden Jahr schlossen sich auch andere deutsche Zeitungen wie der „Stern“, die „Frankfurter Rundschau“ und die „Süddeutsche Zeitung“, mit Sudoku- Publikationen an. Heute sind Sudokus ein fester Bestandteil der Rätselrubrik vieler Zeitungen und Zeitschriften.

Auch in der Unterhaltungselektronik hat das Sudoku einen festen Platz eingenommen. Für Handys und Computer gibt es die verschiedenen Sudoku-Varianten. Die erste wurde schon von Softdisk 1989 für den C64 unter dem Namen „Digihunt“ veröffentlicht. Im Internet findet man eine Flut an Sudokus und auch für diverse Spielkonsolen existiert ein Überangebot des beliebten Zahlenratespiels. Sudoku ist ebenso als Brettspiel erhältlich.

2006 wurde in Italien die erste Sudoku-Weltmeisterschaft ausgetragen. Ein Jahr zuvor fand die erste deutsche Meisterschaft statt.

Erstaunlich, was für einen Weg dieses Zahlenratespiel gegangen ist, bis es so berühmt wurde: Von der Schweiz über Frankreich in die USA, von dort weiter nach Japan, dann von einem Neuseeländer nach England gebracht, bis es über Österreich dann auch nach Deutschland kam.

Mittlerweile erscheint das Sudoku in über 350 Zeitungen in fast 60 Ländern und in mehr als 25 Varianten.

Autor des Artikels "Sudoku – Eine Weltreise": Simon van Stek
Quellenangaben: wikipedia | wikipedia | wikipedia | sudoku-plus | sudoku

Lösungs Wege

Zur Lösung des Problems Sudoku werden im Folgenden einige Algorithmen diskutiert. Allen Verfahren ist gemein, dass sie zu einer gegebenen zulässigen Instanz x eine Instanz aus der Lösungsmenge L(x) liefern. Dabei kann und muss nicht garantiert werden, dass stets die gleiche Instanz als Lösung ermittelt wird. Unterscheidungskriterien zur Bewertung der Algorithmen sind dabei jeweils Laufzeit und Güte, darüber hinaus ist eine Spezifikation in Pseudocode angegeben. 5.1 ExhaustiveSearch Die Idee des ExhaustiveSearch ist, sämtliche theoretisch in Frage kommenden Ergänzungen von x auf ihre Zulässigkeit und damit auf das Enthaltensein der Lösungsmenge L(x) zu prüfen. Dazu wird anfangs jede Zelle, welche das Symbol 0, also blank, enthält auf den Wert 1 gesetzt, überprüft ob dies eine Lösung darstellt und dann Schritt für Schritt jede Zelle solange hochgezählt, bis alle Zellen den Wert k2 haben. Sollte unterwegs keine Lösung gefunden worden sein und auch die letzte Belegung nicht zulässig sein, so wird als Ergebnis nicht lösbar ausgegeben, andernfalls stoppt der Algorithmus bei der ersten gefundenen Lösung und gibt lösbar sowie die gefundene Lösung zurück. Eingabe: Ein Paar x = (k, S) Ausgabe: Ein Paar y = (k, S0) mit S0 2 L(x) oder nicht lösbar

5.2 CandidateSearch

Eine Variante des Exhaustive Search ist der Candidate Search. Hierbei wird als Möglichkeit für jede Zelle nicht die Menge aller Zahlen angenommen, sondern es wird anfangs für jede Zelle eine Liste erstellt, welche Zahl noch möglich scheint, also ein Kandidat im Sinne der obigen Definition ist. Das Ermitteln der Kandidaten findet lediglich einmal am Anfang des Algorithmus statt. Für das komplett leere Sudoku ist dabei kein Unterschied zum Exhaustive Search, da an keiner Stelle eine Zahl bereits ausgeschlossen werden kann. Für teilgelöste Sudoku ist an den Nachbarzellen einer mit einem Wert vergebenen Zelle diese Möglichkeit kein Kandidat mehr, wird also im Algorithmus nicht betrachtet. Eingabe: Ein Paar x = (k, S) Ausgabe: Ein Paar y = (k, S0) mit S0 2 L(x) oder nicht lösbar

5.3 Backtracking

Ein weiteres in der Informatik weit verbreitetes allgemeines Verfahren zum Lösen von Problemen ist das Backtracking. Prinzipiell ist der Candidate Search der erste Schritt vom Exhaustive Search zum Backtracking. Die Einschränkung der Kandidaten für eine Zelle wird jedoch nicht nur einmal am Anfang des Verfahrens, sondern nach jedem Setzen eines Wertes gemacht. Dabei geht der Algorithmus stets von der ersten freien Zelle links oben aus und versucht anhand der Kandidaten diese mit einem Wert zu vergeben. Sollte dies gelingen wird für die folgende Zelle zunächst die Kandidatenliste neu berechnet und dann die jeweils erste Möglichkeit vergeben, und so fort. Sollte jedoch an einer Zelle keine Möglichkeit mehr bestehen eine Zahl zu vergeben, also die Kandidatenliste leer sein, wird der Wert der vorhergehenden Zelle gelöscht und an dieser Stelle entweder ein folgender Wert vergeben oder, sollte nun auch hier keinen weiteren Wert geben weiter zurück gegangen. Der Algorithmus liefert die gefundene Lösung, sollte auch die letzte in der Eingabe nicht belegte Zelle vergeben worden sein oder nicht lösbar, wenn bereits für die erste Zelle keine Möglichkeit mehr besteht. Eingabe: Ein Paar x = (k, S) Ausgabe: Ein Paar y = (k, S0) mit S0 2 L(x) oder nicht lösbar

5.4 HumanSolving

Das Human Solving ist dem menschlichen Lösen eines Sudoku nachempfunden. Dabei werden aufgrund der bereits vorgegebenen Zahlen und der damit verbundenen Einschränkungen Zellen gesucht, welche mit kleinem Rechenaufwand bereits eindeutig erkennbar sind. Die Vorgehensweise ist dabei regelbasiert. Es gibt in diesem Verfahren n Regeln, welche man zum lösen auf ein teilgelöstes Sudoku anwenden kann. Die Regeln werden der Reihe nach abgearbeitet. Sollte eine Regel zu einem Erfolg führen, also mindestens einen Kandidaten in einer Zelle streichen, wird wieder mit der ersten Regel begonnen. Sollte das nicht der Fall sein, wird mit der nächsten Regel weitergemacht. Die Regeln sind dabei so sortiert, dass einfache, leicht nachvollziehbare Gedanken zuerst überprüft werden und erst im Mißerfolgsfall auf schwieriger zu verstehen und zu berechnende Methoden zurückgegriffen wird. Darüber hinaus wird im Erfolgsfall noch eine Wertigkeit für ein Sudoku angegeben. Sie ist umso höher, je öfter auf spätere Regeln zurückgegriffen werden muss und bezeichnet die menschliche Lösungsschwierigkeit des Sudoku. Eingabe: Ein Paar x = (k, S) Ausgabe: Ein Tupel (w, y) mit w >= 0 und y = (k, S0) 2 L(x) oder nicht lösbar

Die vorliegenden Algorithmen unterscheiden sich in ihrer Laufzeit und in ihrer Güte stark. Für den praktischen Einsatz sind lediglich Backtracking und Human- Solving denkbar, ExhaustiveSearch sowie CandidateSearch sind sowohl auf heutigen wie auch auf zukünftigen Rechnern deutlich zu langsam. Da Backtracking neben seiner überzeugenden Laufzeit auch noch eine fehlerfreie Klassifikation bietet sowie stets zusätzlich zur Ermittlung der Lösbarkeit auch eine Lösung angeben kann ist der Backtrackingalgorithmus zur Berechnung der Lösung eines Sudokus die beste Wahl. Von den diskutierten Varianten sollte hierbei im Algorithmus stets neusortierende Variante gewählt werden. Das HumanSolving ist zwar von der Laufzeit her im ähnlichen Bereich und von der Worst-Case Komplexität sogar besser, muss jedoch Einschränkungen hinsichtlich der Güte hinnehmen. Dafür hat es andere Vorzüge. Die Ermittlung der Schwierigkeit sowie die Angabe eines logischen Lösungsweges kann kein anderes Verfahren leisten. Gerade für menschliche Spieler ist dieses Wissen sehr wichtig. Neben der Hilfestellung beim Generieren ist es z.B. denkbar, dieses Verfahren einzusetzen um einen am Rechner spielenden Menschen einen Hinweis zu geben.

Autor des Artikels "Lösungswege": Marvin Wirth

PHP Quell-Code

Autor des Artikels "PHP Quell-Code": Ausbildungsklasse 2711 2921
Quellenangaben: flamm.me