Ruprecht Karls Universität Heidelberg

Fun Sudoku

From Informatik-Vorkurs
Jump to: navigation, search


Zum Spaß: Ein Sudoku lösen

Bei einem Sudoku sind 9×9 Felder teilweise mit Zahlen von 1-9 gefĂŒllt, wie im folgenden Beispiel:

. 7 8   . 2 .   . . 5
9 . 3   . . 4   . . 6
6 . .   9 . .   . 1 .
 
. . 9   . . 2   . 7 .
. . .   . 6 .   . . .
. 1 .   8 . .   . . .
 
. 9 .   . . 8   . . .
4 . .   6 . .   7 . 2
2 . .   . 9 .   1 8 .

Die Aufgabe ist es, die noch freien (hier mit '.' markierten) Felder ebenfalls mit Zahlen zwischen 1 und 9 zu fĂŒllen, so dass in jeder Zeile, Spalte und 3×3-ergruppe (s. oben) jede Zahl genau ein Mal vorkommt.

Es ist recht einfach, ein Programm zu schreiben, das ein Sudoku 'brute force', also durch konsequentes Ausprobieren löst. Eine kompakte (aber nicht sehr effiziente) Lösung von M. Ritzert benötigt nur ca. 100 Zeilen Code. Die verwendete Klasse Sudoku hat folgendes Header-File:

class Sudoku
{
  public:
    bool read( const std::string & filename );      // fĂŒlle 'field' mit Werten aus einem File
    bool solve();
 
  private:
    std::set< char > allowed( int x, int y );       // Menge der im Feld (_x,_y) erlaubten Werte
    bool solve_recursive( int x, int y );
 
    friend std::ostream& operator<<( std::ostream &, const Sudoku & );
 
    char field[ 9 ][ 9 ];
};
std::ostream & operator<<( std::ostream & os, const Sudoku & s);

TrivialitÀten:

  • Die Zahlen im Sudoku-Feld werden in einem zweidimensionalen Array von Buchstaben gespeichert.
  • Die 'read' Methode liest Daten aus einem File ein.
  • Der Stream Operator '<<' wird zur Ausgabe eines Feldes auf die Konsole ĂŒberschrieben. Um ihm den Zugriff auf das 'private' Array 'field' zu ermöglichen, wird er als 'friend' deklariert.
  • Die Methode 'allowed' bestimmt alle Zahlen (bzw. chars von '1' bis '9'), die auf dem Feld an der Stelle (x/y) erlaubt sind und gibt diese in einer Menge zurĂŒck. Ein einfacher Algorithmus, um das zu erreichen, ist z.B., die Menge zunĂ€chst mit allen möglichen Werten zu fĂŒllen und dann die in Zeile, Spalte und Block schon vorhandenen Werte wieder zu löschen.

Zur eigentlichen Lösung arbeitet man sich Feld fĂŒr Feld durch das Sudoku. Man nutzt dazu die Methode solve_recursive(x,y), die das Sudoku 'ab' Feld (x/y) löst:

  • Wenn das Feld bei (x/y) schon mit einer Zahl belegt ist, so ist fĂŒr dieses Feld nichts zu tun. Ist es sogar das letzte Feld, so sind wir fertig. Andernfalls geht man zum nĂ€chsten Feld weiter und löst dieses durch einen erneuten Aufruf von solve_recursive.
  • Ist das Feld bei (x/y) noch frei, so sucht man alle möglichen EintrĂ€ge (mit allowed).
    • Beim letzten Feld nimmt man einfach irgendeinen möglichen Wert.
    • Bei allen anderen Feldern probiert man alle erlaubten Werte aus, indem man das Feld auf den Wert setzt und dann das nĂ€chste Feld löst. Findet man so keine Lösung, so setzt man das Feld auf '.' zurĂŒck.
  • Um die Steuerung zu vereinfachen gibt die Methode solve_recursive true zurĂŒck, wenn eine Lösung gefunden wurde, sonst false.

Ein Ausschnitt aus solve_recursive könnte so aussehen:

if( field[x][y] != '.' ) {
  if( ..(letztes Feld).. )
    return true;                                             
  else
    return solve_recursive( ..(nÀchstes Feld).. );     
}
...

Die 'Hauptmethode' solve ruft einfach solve_recursive fĂŒr das erste Feld auf...

Wie gesagt ist dieser 'brute force' Ansatz nicht elegant. Eine offensichtliche Verbesserung ist es, zunĂ€chst einmal die 'trivialen' Felder zu suchen, bei denen es nur eine verbleibende Möglichkeit gibt, und diese dann zu fĂŒllen. Da durch FĂŒllen eines Feldes ein anderes Feld dann eindeutig werden kann, muss man das solange machen, bis es keine 'trivialen' Felder mehr gibt. Dann startet man die rekursive Lösung.


Personal tools