sicherlich kennen viele das bekannte denkspiel 'sudoku'.die aufgabenstellung klingt relativ einfach:
das spielfeld ist so auszufuellen, dass in jeder spalte, jeder reihe und in jedem einzelnen quadrat die ziffern 0 bis 9 nur einmal vorkommen.
soviel zu den regeln. sobald man aber beginnt, ein solch einfaches spiel selbst zu schreiben, stolpert man ueber die tuecken der mathematik, die sich hinter dem einfachen aufbau des spielfeldes ergeben.
ein feld vollstaendig und gueltig per zufall mit ziffern zu bestuecken, fuehrt nur sehr selten zum ziel. aus diesem grund haben auch viele programmierer von sudoku spielen einen sehr einfachen weg gewaehlt; und zwar gibt es nur eine bestimmte anzahl von fix im spiel gespeicherten karten - und nur die kann man spielen.
dieser weg war mir natuerlich zu primitiv.
eine ebenfalls einfache variante ein gueltiges feld zu erzeugen ist die, alle ziffern von 1 bis 9 - je quadrat zueinander versetzt - der reihe nach einzutragen.
in der ersten zeile also 1, 2, 3, 4, 5, usw..., in der zweiten 7, 8, 9, 1, 2, 3, 4, usw..., in der vierten dann mit 9, 1, 2, 3, 4, usw... beginnen; bis alle 9 zeilen gefuellt sind.
nachdem man innerhalb einer 3 x 9 spalte oder 9 x 3 reihe beliebig oft die 9 felder mit einer der beiden anderen 9er reihen vertauschen kann, sieht jedes spiel fuer den spieler anders aus, vor allem dann, wenn man noch zusaetzlich das spielfeld um 90 grad rotiert.
aus dieser einen vorgabe kann man mittels drehen, spiegeln und vertauschen, etliche millionen verschiedener sudoku's erzeugen; kaum jemand wird bemerken, dass alle spiele von einer einzigen tabelle abgeleitet sind.
dieser weg fuehrt zwar schnell zum ziel, allerdings waren mir reine ableitungen einer einzigen karte ebenfalls zu einfach.
bei meinem sudoku wird das spielfeld von einem gesteuerten zufallsgenerator ausgefuellt, und zwar so, dass immer jene zahlen neu eingetragen werden, bei denen aufgrund der durch die regeln gegebenen moeglichkeiten, am wenigsten falsch gemacht werden kann.
dadurch erhaelt man ein feld, das bereits von haus aus, mit sehr vielen richtigen und gueltigen zahlen gefuellt ist.
um das spielfeld vollstaendig fertigzustellen, werden bei ungueltigen feldern, bestimmte reihen und einzelfelder einer spalte geloescht, und wieder mit dem ausfuellen der noch freien felder begonnen.
der trick, um moeglichst schnell ein spielfeld zu errechnen, liegt genau in den feldern, die bei ungueltigen anordnungen geloescht werden.
loescht man zuviel, wird sehr wahrscheinlich wieder ein ungueltiges feld erzeugt werden; loescht man zuwenig gibt es kaum moeglichkeiten, die fehler zu beheben.
dieser algorithmus ist imstande, innerhalb weniger sekunden, ein 25 x 25 sodoku zu errechnen!
nachdem jetzt sicherlich einige leser etwas genaueres ueber dieses verfahren wissen wollen, hier eine anleitung der vorgehensweise:
- 1) zuerst ein 3 x 3 quadrat mit 1 bis 9 fuellen (bei einem 25 x 25 sudoku, 3 quadrate fuellen).
- 2) vor jeder zufaelligen zahl die eingefuegt wird, alle bestimmbaren
einsetzen; also:
- die letzte zahl einer reihe / spalte / quadrat
- alle felder fuellen, die nur mehr eine zahl enthalten koennen - 3) fuer zufaellig eingesetze zahlen immer ein feld nehmen, in dem es die wenigsten moeglichkeiten gibt.
- 4) die punkte 2 und 3 solange durchfuehren, bis keine zahl mehr eingesetzt werden kann.
- 5) bleiben leere felder uebrig, jede waagrechte reihe vollstaendig loeschen,
in der sich ein leeres feld befindet.
zusaetzlich in jeder reihe genau 1 feld loeschen, das eine x-position eines beliebigen leeren feldes hat, das nach punkt 4 uebriggeblieben ist (bei einem 25 x 25 sudoku, 2 oder 3 felder je reihe loeschen). - 6) wieder ab punkt 2 beginnen - bis das feld gueltig ist.
beispiel: feld ist bis auf (x,y) 4/2 und 7/8 komplett: die waagrechten reihen 2 und 8 loeschen, sowie in jeder reihe entweder die spalte 4 oder 7 loeschen.
nur durch dieses verteilte loeschen einzelner felder einer reihe, ergeben sich vollautomatisch genug moeglichkeiten, fuer eine gueltige variante.
trotz allem, einen zaehler mitlaufen lassen, der nach etwa 20 bis 30 loeschvorgaengen abbricht. bei ueber 95% ausgefuellten feldern, ist nicht jede karte loesbar.
das naechste problem sind die zahlen, die man bei spielbeginn vorgibt.
waehlt man zufaellig irgendwelche felder aus, gibt es fuer das spiel zu 90% mehr als eine loesung - und mehrdeutige sudoku's zu loesen ist irgendwie langweilig und uninteressant.
um mehrdeutige loesungen weitgehenst zu vermeiden, werden am anfang alle leicht erkennbaren mehrfach-kombinationen, die sich ueber 2 oder 3 quadrate erstrecken, durch vorgabe eines der betroffenen felder, eliminiert.
das betrifft anordnungen von 4 oder 6 feldern die beliebig vertauscht werden koennen, ohne dass sich an der gueltigkeit des spielfeldes etwas aendert. das schliesst zwar nicht kombinationen aus, die sich ueber alle 9 quadrate erstrecken koennen, aber solch komplexe mehrfachloesungen sind selten, und meistens bemerkt man sie gar nicht.
die restlichen felder werden nach und nach reduziert, bis keine eindeutige loesung mehr zu finden ist. dieses verfahren arbeitet mehr oder weniger nach zufall. einige tests haben gezeigt, dass es weitaus effizienter ist, felder wegzunehmen, als mit 0 zu beginnen und vorgegebene hinzuzufuegen.
diese funktionen sind selbstverstaendlich im assembler programmiert. die berechnungen erzielen meistens 20 bis 30 vorgegebene felder; in jeder situation in der kein eindeutig logischer weg mehr moeglich ist, werden rekursiv 2 bis 4 varianten bis ende (fertig oder ungueltig) durchgerechnet.
das fuehrt zu 100 bis 200 aufrufen der hauptfunktion und das gesamte feld wird bis zu 500.000 mal analysiert. dank assembler dauert es trotzdem nicht allzu lange.
selbstverstaendlich gibt es das fertige spiel zum download: und zwar wenn man hier draufklickt, oder auf meiner download page.
die bedienung meines sudoku's ist recht einfach:
- links klick auf ein feld bringt ein popup zahlenfeld zur auswahl,
- rechts klick loescht eine eingetragene zahl.
hat man das feld vollstaendig und richtig ausgefuellt, wird das spielfeld gruen (vor neid).
die funktion 'save' speichert das aktuelle feld in der textdatei 'sudoku.txt' (natuerlich nur die vorgegebenen ziffern). die datei wird nicht ueberschrieben, sondern neue saves werden an das ende der datei drangehaengt.
eine ausfuehrliche bedienungsanleitung gibt es hier
viel spass!