Sudoku

Da das Sudoku-Spiel im Grunde nur stupides Herumprobieren und Ausschliessen ist, hat es mich nie wirklich angesprochen. Diese Einfachheit praedestiniert es aber zur Implementierung in C++.

Zur Vorbereitung auf meine Pruefung in der Anfaengervorlesung in Computer Science hier in Saskatoon habe ich ein Programm erstellt, das Sudokus loesen kann. Leider ist es in einem rudimentaeren Zustand verblieben, da mich die Motivation nach dem erfolgreichen Schreiben des Loesungsalgorithmus' verlassen hat. Was das Programm nicht kann ist: neue Sudokus ausgeben, Interface zur Loesungseingabe und Benutzerstatistik. Die Ausgangsfelder muessen direkt im Quellcode geaendert werden und es gibt keine grafische Oberflaeche (Kommandozeile!). Das richtige Sudokuspielen ist also nicht moeglich.

Dennoch mag es fuer den einen oder anderen interessant sein, wie man dieses Problem angehen kann, ohne erweiterte Informatikkenntnisse wie Baeume und Inferenz zu benutzen (Ich kenne nur Structures, Schleifen und Variablen!).

Der Algorithmus ist wie folgt (der Einfachheit halber eine Kopie aus der englischen Erklaerung des Programms):

    validation:
        it boils down to verify that in a set of 9 numbers,
          each number from 1-9 appears only once.
        to do that, an array is created, that holds 
          numbers which have already been found.
        if a number is about to add, which is already in there,
          the board is not valid.
        challenging was to manage the nine little 3x3 squares.

    solving:
        in the structure sudokuBoard, there is a 9x9 array
          of 9 booleans which indicate the possibility of
          the 9 numbers to fit into the spot.
        it is an recursive algorithm:
            updating possibilities:
                go over the whole board, if a number!=0 is found,
                  mark all corresponding booleans in row, column and square as false.
            if there are no possibilities to insert numbers left
                and the board is solved: set isSolved = true.
                and the board is not solved: do nothing.
            if there is still something to add:
                find the spot with least possibilities left and try
                  them one by one by calling the function with the value added.
                before going into recursion a copy of the board is made.
                  otherwise data written by the following recursion steps
                  could not be distingushed from current data and thus 
                  knowledge of the current status would be lost.

        in most cases, an unambiguous spot is found, and the
          sequential trying is obsolete.

Das Programm besteht aus drei Dateien:

auxFunctions.h
sudoku.cpp
sudokuFunctions.h

Es kompiliert problemlos auf Linux-Systemen, unter Windows habe ich es nicht getestet, es sollte aber auch dort keine Probleme geben.