Sehr geehrter Herr Taulien,

Zunächst einmal möchte ich mich sehr herzlich dafür bedanken, dass Sie sich
trotz Ferien und Feiertagen Zeit für uns genommen haben.

Hiermit möchte ich gerne versuchen, Ihnen Antworten auf Ihre Fragen zu geben.


Für das Thema "Sudoku" haben wir uns nach Rücksprache mit unseren
Kursteilnehmern und den AK-Leitern entrschieden. Eigentlich wollten wir ein
System zum Lösen von Gleichungen erstellen. Unsere AK-Leiter stimmten dann
jedoch mit uns überein, dass hierfür unsere Mathematik-Kenntnisse noch nicht
ausreichend seien. Wie Sie wissen, haben wir sehr viel Spaß am Programmieren
und hielten das Erstellen eines Sudoku-Programmes, das wir als
open-source-Programm verfügbar machen wollten, für überschaubar.


Einige der von Ihnen gestellten Fragen entstanden natürlich auch bei uns beim
Programmieren. Ich habe versucht, sie folgendermaßen zu lösen:


Für die Berechenbarkeit der Anzahl aller möglichen Sudokus stelle ich mir
folgenden Lösungsansatz vor:

Ich gehe dabei von den einzelnen Reihen eines Sudokus aus. Für die erste Reihe
gibt es also 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 ( = 362 880 = 9!)
Kombinationsmöglichkeiten, da es für das erste Kästchen 9 Möglichkeiten gibt,
im zweiten Kästchen nur noch 8, da eine Zahl durch das vorherige Kästchen
unmöglich gemacht wird, und so weiter.

Für die zweite Reihe gibt es dann noch ... Möglichkeiten, da ... . Dies wird
fortgesetzt, sodass man auf ein Endergebnis von 9! * ... * ...... ( = ...)
kommt.

Ob ich dabei allerdings alle möglichen Kombinationen bedacht habe, weiß ich
nicht genau.


Was die Lösbarkeit von Sudokus angeht, so definiere ich ein Sudoku als
"eindeutig lösbar", wenn alle Zahlen durch umliegende Zahlen (auch selbst
eingesetzte, d. h. zu Anfang mögen sicher einige Kästchen mehrere Lösungen
aufweisen) bestimmt sind. Allerdings macht es - zumindest meiner Meinung nach
- gerade den Reiz eines Sudokus aus, dass manche Zahlen nicht eindeutig
bestimmt sind, sondern dass sich für sie mehrere Möglichkeiten bieten; und
dass man durch logisches Weiterverfolgen eines solchen Falles Unmöglichkeiten
ausschließen kann, wobei dieser Fall natürlich auch nicht zu häufig auftreten
sollte. Bei unserem Programm wird das Sudoku nach dem Generieren auf solche
Fälle geprüft, es wird darauf geachtet, dass nicht zu viele auftreten und dass
das Sudoku endgültig nur eine richtige Lösung bietet.


Die erforderliche Rechenzeit zunächst einmal beim Generieren eines Sudokus ist
verschwindend gering, da der Computer einfach neun Zeilen zufällig erstellen
muss, die den Sudoku-Regeln gehorchen und zu den vorherigen passen. Es gibt
natürlich Möglichkeiten, bei denen das Sudoku ab einer bestimmten Position
keine Möglichkeit mehr bietet, weitere Zahlen einzusetzen, dies kommt aber
sehr selten vor und in diesem Fall wird einfach ein neues erstellt. Praktisch
gesehen benötigt der Computer damit etwa 0.2 Sekunden für ein Sudoku.

Beim Lösen eines Sudokus hängt die erforderliche Rechenzeit natürlich vom
Schwierigkeitsgrad, also von der Anzahl und Positionierung der Zahlen ab, zum
größten Teil jedoch davon, ob Fälle mit mehreren Lösungsmöglichkeiten (wie oben
beschrieben) eintreten, ist aber trotzdem sehr klein, im Durchschnitt etwa
eine halbe Sekunde.


Das größte Problem könnte für uns allerdings - wie Sie richtig bemerken -
sein, dass die Juroren das Thema für "ausgelutscht" halten. Wir hatten
gehofft, mir der Programmierleistung überzeugen zu können. Allerdings sind wir
nicht so vertraut mit dem ganzen Procedere bei "Jugend forscht".

Wir sind froh, wenn Sie uns helfen können, das ganze Thema auf einen guten Weg
zu bringen, da inzwischen die Zeit doch recht knapp geworden ist.