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.

Wettersturz zum Wochenende

Der Spiegel schreibt heute in einer Meldung, dass zum Wochenende schlimmes zu erwarten ist:

Deutschland drohen zum Wochenende Gewitter, Schnee und schwere Stürme. Der Deutsche Wetterdienst sagt einen heftigen Wintereinbruch und Verkehrschaos voraus.
[...]
Innerhalb einer Stunde können aus Regen und nassen Straßen plötzlich Schneesturm und schneebedeckte, vereiste Fahrbahnen werden. Autofahrer sollten im Mittelgebirgsraum ab Mittag ihren Wagen möglichst stehen lassen, warnen die Meteorologen. Bis zum Abend kann in einigen Mittelgebirgslagen bis zu 15 Zentimeter Schnee fallen.

Lustig, denke ich mir da, hier in Kanada waere das kaum der Rede wert.

Musik...

Um am vorangegangenen Eintrag anzuknuepfen und aus gegebenem Anlass will ich ueber den Chor berichten, der mich hier aufgenommen hat.

Wie so mancher der Leser vielleicht weiss, habe ich eine grosse Leidenschaft fuer das gemeinsame Singen. Da mir Sachen meistens nur Spass machen, wenn sie gewissen Anspruechen genuegen, bin ich auch hier auf die Suche nach einem einigermassen guten Chor gegangen und eine Gruppe gefunden, die eigentlich nicht zu verachten ist.

Die Mitglieder der Greystone Singers (Man beachte das neue Chorfoto!) sind vorwiegend Studenten aus den ersten Semestern, aber auch ein paar aeltere sind mit dabei. Das Durchschnittsalter ist dementsprechend bei vielleicht 21 Jahren. Die meisten sind Musikstudenten, die durch ihre Teilnahme am Chor wahrscheinlich eine Wahlpflichtveranstaltung, wie z.B. Ensemble, abhandeln. Dennoch ist die Gruppe ziemlich heterogen, so kommen zwei Leute aus der Physik, einige aus den Sprachen und weitere aus anderen Fachbereichen. Die Stimmung ist zu jeder Zeit sehr locker und nicht stressig, worunter die zum Proben noetige Konzentration aber nicht leidet.

Um in den Chor aufgenommen zu werden, muss man ein Vorsingen bestehen. Das alleine garantiert zwar noch nicht einen guten Klang oder eine gute musikalische Interpretation und Aufarbeitung der Werke, ist aber ein guter Schritt in diese Richtung. Und in der Tat klingt die Gruppe nicht allzu schlecht (meint: ziemlich gut), es fehlt mir notorisch Unzufriedenem aber immer noch das Tuepfelchen auf dem i, das es mir erlauben wuerde, befreit und zufrieden zu sein. Mit Sicherheit ist das aber auch dem engen Zeitplan zuzuschreiben, der einem Chor auferlegt ist, der nach der Sommerpause frisch zusammenkommt und gleich nach wenigen Wochen die ersten Konzerte bestreiten soll.
Verstaendlich ist auch, dass sich die Probenarbeit fuers erste auf Notenlernen und das Verstehen der Musik konzentrieren muss. Die Saenger sind schliesslich keine Profis, die alles vom Blatt lesen koennen. Die kontinuierliche Korrektur fuer einen besseren Klang und die Beharrlichkeit beim Suchen nach Verbesserung eines Stefan Claas fehlt mir doch ziemlich. Meiner Meinung nach, ist die Stimmbildung keine Draufgabe, die ein gutes Stueck noch weiter verbessern kann, sondern eine notwendige Vorraussetzung, dass das Stueck ueberhaupt gut werden kann. Wenn ich Stimmen in meiner Umgebung hoere, die einfach technisch ungeschickt und ungesund singen, laeuft es mir regelmaessig kalt den Ruecken hinunter. Leider wird wenig davon korrigiert.

Ich hatte das Glueck in der ersten Woche den deutschen Musikprofessor Walter Kreyszig, der hier seit bald 20 Jahren lehrt, zufaellig kennenzulernen. Als ich ein Bewerbungsformular auf eine Tutorenstelle fuer Deutschstudenten beim Sekreteriat fuer die Sprachen abgeben wollte und dieses leider schon geschlossen hatte, habe ich Bekanntschaft geschlossen und bin gleich zu seiner Anfaengervorlesung ueber Musikgeschichte eingeladen worden, die ich aber mittlerweile wieder aufgegeben habe. Es hat sich allerdings noch einige Male die Gelegenheit zum Gespraech ergeben, bei der er ziemlich viel und ich ziemlich wenig gesagt habe, wie das so seine Art ist. Bei diesen Unterhaltungen, um zum Punkt zu kommen, hat er oft die "konservatoriumsartige" Lehrweise beklagt, die in Nordamerika gepflegt wird. Das meint beispielsweise, dass Regeln ueber die Ausfuehrung von Musik absolut sind (Wo ein Akzent steht, wird auch einer gemacht, egal ob er als Akzent gemeint ist oder nur den Sprachrhythmus einer fremden Sprache verdeutlichen soll. Alte Musik wird direkt transskribiert gelehrt ohne den Studenten Interpretationsfreiraeume zu lassen.) oder dass Konkurrenz in der Studentenschaft gefoerdert wird. Ich denke, darin ist auch die Arbeitsweise des Dirigenten zu begruendet: Zuvorderst wird an der Tonhoehe probiert, dann am Klang. Vielleicht mag ich mich auch irren, aber wenn einer der seltenen Hinweise auf bessere Tonformung gegebenwird, klingt der Chor gleich soviel besser - auch in Bezug auf Intonation! -, dass ich mich frage, warum das nicht gemerkt wird.

Ich hatte bisher zwei Auftritte mit den Greystones, die mir viel Spass gemacht haben. Den groessten Beitrag haben dazu wahrscheinlich die doch ziemlich geilen Roben gemacht, die wird zu diesen Gelegenheiten haben: gruener Samt mit Seidenfutter in beige, dazu ein cremefarbenes Halstuch, schwarze Hose und Schuhe. Wir sind uns einig, dass nur noch das Wappen von Slytherin auf der linken Brust fehlt. Als wir zum Fototermin vor das Gebaeude der Verwaltung marschiert sind, vorbei am Thorvaldson Building, ueber den Bowl mit all den interessiert schauenden Studenten, habe ich mich fast wie in Hogwarts gefuehlt.

Um die vielen Veranstaltungen und vor allem die Chorfahrt im Februar finanzieren zu koennen ist der Chor auf die Mithilfe der Saenger angewiesen. Dazu arbeiten die Leute auf freiwilliger Basis bei den verschiedensten Gelegenheiten fuer den Chor. So war beispielsweise ein universitaetsweites Fest vor zwei Wochen, wo man einige Sachen machen konnte. Der Lohn fuer die vier bis fuenf Stunden Arbeit ging dann in die Chorkasse.
Auch sonst wird fleissig ehrenamtlich geholfen. Heute war ich zum Beispiel bei einer Altistin zu Hause um mit ein paar anderen Leuten zusammen 1400 Briefe zu falten und zu kouvertieren. Die Briefe sind Einladungen und gingen an Alumni des Chores anlaesslich des 50-jaehrigen Bestehens des Chores. Man glaubt nicht, wie angenehm es ist, mal aus diesem Wohnheim herauszukommen und in einem normalen Haus ein paar Stunden mit netten Leuten zu verbringen, sehr erholsam!
Was ich dann allerdings wieder nicht verstehe, ist die Notwendigkeit verschiedener bezahlter Stellen fuer Chormitglieder, die per Wahl und auf freiwillige Nominierung vergeben werden. Da waere zum beispiel der Equipment Manager, der sich darum zu kuemmern hat, dass zu Probenbeginn, die korrekte Anzahl an Stuehlen auf der Buehne steht und wehe wenn nicht. Ein ueberzaehlicher Stuhl bekommt mindestens eine Minute Aufmerksamkeit. Bezahlt wird auch der Job des Solisten, des Begleiters am Piano, Schatzmeister und andere. Anfangs war ich doch ueber die teilweise rigide Organisation an der einen Stelle, die Planlosigkeit an anderer irritiert.

Trotz des Unbehagens, das ich manchmal empfinde, bin ich jedoch sehr froh, dem Chor beigetreten (bzw. aufgenommen worden zu sein) zu sein! Es ist schoen, zweimal die Woche etwas Musik zu machen, auch wenn bei 1,5 Stunden keine richtige Probenstimmung aufkommen kann. Die Leute sind sehr nett und auch wenn ich mir meinen eigenen Teil denke, kann ich ja immer noch Spass haben. Und den hab ich auch!

Lust auf Musik? Goldgrube entdeckt!

Ich denke das ist so zwei bis drei Wochen her, als im Rechnerraum der hiesigen Uni beim arbeiten war und gute Musik vermisst habe. Dann ist mir last.fm wieder eingefallen, das mein Bruder vor einer Zeit mal benutzt hat. Trotz der Musiksammlung, ueber die ich verfuege, hoere ich seitdem vorwiegend die Sender dieses Internetdienstes. Wer mag, kann sich gerne mal meine persoenliche Bibliothek ansehen, und jener wird sehen, dass ich ein geschmackloser Allesfresser bin, was Musik angeht. Nunja, fast, ein bisschen selektiere ich schon.

In letzter Zeit hat sich elektronische Musik in meinem Ohr eingenistet und wird jetzt solange gehoert, bis es mir wieder rauskommt. Nun quaele ich meine Mitbewohner mit Techno nicht unerheblicher Lautstaerke ueber die neu erworbenen Boxen. Fuer $30 kann man hier schon anstaendige Stereo-Lautsprecher von Logitech bekommen, die einen schoenen Bass haben, aber dennoch nicht dumpf rueberkommen.

Beim naechsten Eintrag wird dann etwas aus folgenden Themen behandelt: Georgischer Mitreisender im Flugzeug, Wohnungsprobleme, Mitbewohner, akademische Veranstaltungen, Greystone Singers, Stammtisch, Bekannte.

So long,
Simon

der Schnee ist da (und der Blog auch...)

Hallo ihr lieben, die euch mein Blog erreicht!

Ich habe den ersten Schneefall in Kanada zum Anlass genommen, mich um einen Blog zu bemuehen. Die Kaelte ist zwar schon laenger hier, aber da Niederschlaege hier bekanntlich rar sind, ist bisher noch kein gefrorenes Wasser vom Himmel gefallen. Heute war es soweit und ich habe gleich Massnahmen ergriffen und mir endlich eine Winterjacke und zwei schoene Lederhandschuhe gekauft.

Mittlweile kann ich sagen, dass ich mich in Saskatoon gut eingelebt habe. Ich bin mit meiner Wohnung zufrieden, habe interessante Menschen kennengelernt und komme gut im Alltagsleben zurecht. Auch die universitaeren Aufgaben gehen verglichen mit den deutschen Veranstaltungen leicht von der Hand, was gleichzeitig Zuversicht auf gute Noten und Zweifel am akademischen Fortkommen spendet. Nun, die Erfahrung zeigt, dass bisher die meisten Sachen problemlos oder mit ein wenig Nachdruck in Darmstadt anerkannt worden sind, also sollte man sich nicht beunruhigen lassen.

Auf dem eingebetteten Bild sieht man Ausblicke aus Tagen schoeneren Wetters, die etwa drei Wochen zurueckliegen. Das mittlere der Hochhaeuser ist bis Mai mein Zuhause: Ich wohne im achten Stock mit fuenf anderen Menschen zusammen. Doch dazu bei anderer Gelegenheit mehr.
Mittlerweile hat uns die Winter­daemmerung eingeholt, die aber auch nicht schlimmer als in Deutschland ist, da Berlin auf gleicher Hoehe mit uns liegt. In den naechsten Tagen kommt dann vielleicht mehr und aktuelles dazu. Vor allem Bilder bin ich schuldig, wenn ich den Schnee als Aufhaenger fuer diesen ersten Eintrag waehle.

Bis dahin alles Gute!

Simon