Gestelltes Problem
Ich glaube, ich bin ein komischer Typ. Komisch hier im Sinne von merkwürdig. Ich denke mir nämlich gern Lösungen für Probleme aus. So kam mir unlängst in einer Rätselzeitschrift meiner Mutter ein “Finde die zehn Unterschiede”-Bilderrätsel unter. Das habe ich dann mit der Digiknipse fotografiert. Jetzt müssten, in der einfachen Lösungsvariante, nur beide Bilder aus dem Gesamtbild ausgeschnitten und dann abwechselnd angezeigt werden. Dabei würden dann die Unterschiede “blinken”. Die etwas fortgeschrittenere Variante würde direkt eine Bildsubtraktion durchführen.
Meine Mutter fand diesen rechnergestützten Lösungsansatz unmoralisch und vielleicht bewegt mich auch Faulheit dazu, Probleme abschliessend lösen zu wollen.
Dieses Mal war es Minesweeper. Mir ging schon länger im Kopf herum, dass und wie man da etwas machen könnte. Ich wollte ein Programm schreiben, welches Minesweeper fernsteuert.

Algorithmus
Zunächst musste ich ein Minesweeperfenster finden und mir das Spielfeld kopieren. Dieses wurde dann nach diesen Bitmaps:
  
  
  
  
  

durchsucht. Damit hatte ich also in meinem Programm ein Abbild der aktuellen Spielsituation. Diese wurde auf zwei verschiedene Weisen analysiert.
1. Dumm
Dabei wird nach Zahlen-Zellen gesucht, die genau so viele geschlossene Zellen in ihrer Umgebung haben, wie es ihrem Zahlenwert entspricht. Wenn also eine 1er-Zelle nur ein geschlossenes Feld in ihrer Umgebung hat, wird dieses markiert. Das Markieren geschieht, indem ein rechter Mausklick mit den passenden Koordinaten an das Minesweeper-Fenster geschickt wird. Danach wird für alle Zahlenzellen ein Klick mit beiden Maustasten, der alle offensichtlich gelösten Felder aufdeckt, geschickt.
2. Schlau
Hier wird ein Ausschnitt von 4×4 Zellen über das Spielfeld bewegt. Es werden dann für alle geschlossenen Zellen alle Belegungsmöglichkeiten durchiteriert. Die Iteration sieht so aus:
int NextIt( int pos )
{
if ( pos >= ITW * ITW )
return false;

if ( IterationsZellen[ pos / ITW ][ pos % ITW ].ZelleOrig == CVALZU )
{
// Wenn sie 0 ist, auf 1 und raus
if ( IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert == 0 )
{
IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert = 1;

return true;
}
// Sonst auf 0 und nächsthöhere erhöhen
IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert = 0;
}

return NextIt( pos + 1 );
}
Rekursion muss nicht immer sein, aber hier ist sie echt lecker. Es werden dann alle möglichen Belegungen anhand der Zahlenfelder bewertet, wobei entschieden wird, ob sie eine gültige Minenverteilung darstellen. Wenn ein Feld bei allen gültigen Minenverteilungen leer ist, wird es geöffnet. Ein Feld, welches bei allen gültigen Minenverteilungen eine Mine hat, wird markiert.

Tja, trotz der Massen an Mausklicks und der vielen Bildschirmabzüge ist das Programm dann doch relativ schnell. Wieder ein Problem gelöst…

Screenshots:

Gestelltes Problem
Freecell macht mich immer ganz kirre, da hat man dann mit dem falschen Stapel angefangen und auf einmal ist nichts mehr frei, Statistik: “30%, aktuell 17-mal verloren”. Das ist Stress pur!
Warum kostbare Freizeit verschwenden, wenn man solche Probleme per Programm lösen kann?

Algorithmus
Vor der Frage nach dem Algorithmus stand die nach dem Aussehen der Anwendung. Einfach nur Text “Zug von Stapel drei nach vier.” erschien mir nicht ausreichend. Deswegen habe ich erst einmal alle Karten bei Freecell geklaut und als einzelne .bmp-Dateien abgelegt. Da ich mittlerweile auch ganz gern mal den Borland-C++-Compiler benutze, ging der Teil mit der Anzeige der Karten auf einem grünen Spieltisch relativ schnell. Wie in Freecell aus der ausgewählten Spielnummer die Anfangsstellung entsteht, habe ich noch nicht ergründen können. Deshalb wurde das Spiel 21145 fest im Programm verdrahtet. Jetzt mussten ja nur noch zu einer Stellung alle möglichen Züge ermittelt und dann für jeden Zug rekursiv das Gleiche getan werden, bis man auf eine Stellung stiess, wo alle Karten abgelegt waren. Pustekuchen. Die ersten Läufe dieser Version schafften über 100.000 Stellungen, ohne zu einer Lösung zu kommen. Bei Freecell gibt es nämlich reversible Züge. Deshalb wurde eine Liste der schon besuchten Positionen hinzugefügt. Damit konnten auch andere Formen der Stellungswiederholung ausgeschlossen werden. Trotzdem hatte ich ein Programm welches es schaffte in 10 Sekunden 200-mal zu verlieren, aber trotzdem nicht zur Lösung fand. Das lag daran dass es bei Freecell sehr viele Stellungen gibt. Es war notwendig, dem Programm auf der Ebene der möglichen Züge eine Richtung vorzugeben. Statt alle Zugmöglichkeiten wahllos durchzuprobieren, wurde für jeden Zug eine Bewertung berechnet. Die Züge mit der besten Bewertung wurden dann als erste ausprobiert. Eine gute Stellung hat folgende Eigenschaften: möglichst viele freie Plätze, möglichst gut sortierte Stapel, keine eingeklemmten Karten mit kleinem Wert. Damit gings dann. Hat ja auch immerhin fünf Tage gebraucht.
So sieht das dann aus:

(451 Positionen getestet, Rekursionstiefe 318, gemerkt 450 Stellungen, bis jetzt 38-mal verloren)

Gestelltes Problem
Als Kind hatte ich eine Autorennbahn der Firma Faller.

Eigentlich ein Zwei-Personen-Spielzeug, aber leider wollte niemand ein zweites Mal gegen mich antreten. In Ermangelung eines menschlichen Gegners musste ich deshalb den zweiten Wagen immer mit auf einer mittleren Position arretierten “Gasgriff” fahren lassen. Es zeigte sich, dass ich diesen Wagen zwar leicht überholen konnte, sich die Sache aber recht schnell drehte, wenn mein Auto aufgrund eines Fahrfehlers herausflog. Speziell wenn ich dadurch in Rückstand und Stress geriet, folgten dann oft weitere Fehler meinerseits.
Wie dem auch sei, um 2000 rum holte ich das Ding aus dem Keller und baute es nach langer Zeit einmal wieder auf. Meinen Mangel an Sparringspartnern hatte die Zeit nicht heilen können.
Vielleicht konnte da der Computer helfen, einen Gegner zu emulieren?

Algorithmus
In den 1980ern schwebte mir schon einmal eine automatische Fahrzeugsteuerung vor. Damals hätte man jedoch jede einzelne Fahrbahnschiene um einen elektronischen Melder ergänzen müssen, um ermitteln zu können, wo sich der Wagen gerade befindet. Aber mittlerweile gabs ja Webcams. Damit musste es doch möglich sein, herauszufinden wo sich der Renner gerade auf der Strecke befand. Der erste Ansatz war, den Streckenaufbau Schiene für Schiene am PC zu erfassen. Dann sollte jeder Schiene eine Maximalgeschwindigkeit zugeordnet werden. Ein Streckenmodellierprogramm das sämtliche Faller-Schienen eingebaut bekam und Strecken grafisch darstellen konnte, hatte ich schon geschrieben. Wie jetzt das von der Webcam aufgenommene Bild dieser Strecke zugeordnet werden sollte, war mir noch zunächst unklar. Später kam mir bei nochmaligem Nachdenken der Gedanke, dass man eigentlich drauf pfeifen kann, wie der Streckenaufbau ist. Aus der Sicht der Kamera beschreibt das Fahrzeug eine irgendwie geartete Schleife. Jedem Segment dieser Schleife muss eine Geschwindigkeit zugeordnet werden. Die Form dieser Schleife kann durch einigen Testrunden ermittelt werden. Bei diesen Testrunden fährt nur das vom Rechner zu steuernde Auto. Dadurch ist dem Programm bekannt, in welchem Bereich sich das Fahrzeug befinden kann. Diese Schleife wird in Segmente eingeteilt. In der nächsten Phase, dem Training, wird die für jedes Schleifensegment maximal zulässige Geschwindigkeit ermittelt. Die Geschwindigkeit ist dann zu hoch, wenn der Wagen rausfliegt.

Hardware
Damit der PC keinen Vorteil besitzt, musste auf jeden Fall der Standard-“Gasgriff” angesteuert werden. Deshalb erwarb ich ein über USB ansteuerbares Experimentierboard mit zwei 0-5 Volt Analogausgängen.

In meiner Naivität ging ich davon aus, dass man damit ein Servo, wie es aus dem RC-Bereich bekannt ist, ansteuern könne. Nun brauchen diese Servos aber ein PWM(Pulsweitenmodulation)-Signal. Deshalb musste ich noch einen Bausatz für einen “Servotester” ranflicken.

Damit liess sich das Servo jetzt vom PC aus ansteuern. Der Winkel war nicht unbedingt proportional zum an die USB-Karte angelegten Wert, aber es würde reichen.
Jetzt mussten Gasgriff und Servo zusammengebracht werden. Laubsäge raus und eine entsprechende Halterung gebastelt.

Damit war an Hardware alles Nötige verfügbar.

Software
Zunächst für jeden Teil erst einmal Prototypen erstellt. Das Übertragen der jeweils gewünschten Servostellung an die USB-Karte, das Einlesen der Bilder von der Webcam. Die einzelnen Komponenten kommunizieren dabei über Sockets miteinander. Es stellte sich dabei heraus, dass die Bilder von der Webcam mit einer Verzögerung von ungefähr einer halben Sekunde eintrafen. Das ist ein Problem, welches man sich sehr gut für später aufbewahren kann.

Hier ein Screenshot des Prototypen für den Zugriff auf die Webcam und die Bewegungserkennung: 

Wieder einmal zeigte sich, dass die grobe Vorstellung eines Algorithmus noch kein fertiges Programm ergibt. Und wieder einmal musste ich mich jedes kleinen Problemchens annehmen (Alter: 39, gelöste EDV-Probleme: 18.250, gefühlt: 3 Milliarden). Bezeichnenderweise waren die Erkennung der Fahrzeugposition und auch die Beschränkung der Bewegungserkennung auf die Fahrzeugspur ein Klacks. Schwer getan habe ich mich dann aber mit dem Aufbau der Sektorenliste. Wie sollten die über mehrere Runden gesammelten X,Y-Positionen zu einer gerichteten Liste konsolidiert werden? Was ist mit Fahrbahnkreuzungen? Viel Gefummel, aber irgendwann ging auch das.
Als Nächstes war die Erkennung zu langsam, d.h. die eingehenden Frames konnten nicht in Echtzeit verarbeitet werden.
Da bin ich noch bei.

Gestelltes Problem
Seit meinem 12. Lebensjahr bin ich begeisterter Besitzer einer Faller-AMS-Auto-Rennbahn. Ich hatte jedoch immer Probleme, Gegner zu finden, da sich meine Freunde meistens nur auf ein Rennen einliessen. Letztes Jahr habe ich eine Webcam erworben. Nun stellte sich mir die Frage, wie man eine PC-Steuerung eines Rennautos bewerkstelligen könnte.

Algorithmus
Mir schwebt vor, mehrmals pro Sekunde eine Aufnahme der Rennstrecke zu erzeugen. Durch Differenzbildung zwischen der aktuellen und der vorherigen Aufnahmen würde eine schwarze Bitmap entstehen, die an zwei Stellen weiss wäre, dem Standort des Fahrzeuges zum Zeitpunkt der ersten Aufnahme und dem Standpunkt des Fahrzeuges zum Zeitpunkt der zweiten Aufnahme. In einer Kalibrierungsphase wäre es möglich, den Bereich zu bestimmen, in dem sich das computer-gelenkte Fahrzeug bewegt. Dadurch entfällt also eine separate Erfassung der Streckenparameter, sicherlich könnte man eine Anwendung erstellen, bei der dem Computer die einzelnen Streckenabschnitte, enge Kurve 90 Grad, Gerade, normale Kurve, 45 Grad… bekannt gemacht würden, aber dieser Ansatz erscheint mir nicht sehr elegant. Stattdessen soll der Rechner seinen Wagen einige langsame Runden drehen lassen und so ein Abbild der durchfahrenen Strecke erstellen. Die so erfasste Strecke wird dann in Sektoren eingeteilt, die Länge eines solchen Sektors ergibt sich aus dem zeitlichen Abstand zwischen zwei Aufnahmen. Nun muss für jeden Sektor die Maximalgeschwindigkeit bestimmt werden. Diese ist nur experimentell zu erfassen. Das bedeutet, dass der Rechner den Wagen schrittweise immer schneller fahren lassen muss, bis er an einer bestimmten Stelle “rausfliegt”. Anhand der so erfassten Sektorparameter kann dann ein sicheres und schnelles Rennen gefahren werden. Bevor ich nun die erforderliche Hardware für die Geschwindigkeitssteuerung des Fahrzeugs besorge, mir schwebt eine Steuerung durch ein am Gasgriff angebrachtes Servo vor, ist zunächst einmal ein Prototyp zu erstellen, der die Machbarkeit belegt. Dabei ist der komplette Ablauf im Rechner zu simulieren. Einen ersten Schritt stellt ein Streckeneditor dar. Hier habe ich alle bekannten zweispurigen AMS-Schienen in Form eigener Klassen realisiert. Bis jetzt kann er die jeweilige Strecke nur darstellen. Der nächste Schritt wird sein, Fahrzeuge hinzuzufügen und diese dann auf der Strecke fahren zu lassen. Die dabei entstehenden Streckenbilder werden dem zuvor erklärten Programm zugeführt. Wenn sich zeigt, dass eine Echtzeitsteuerung möglich ist, werden als Input die Aufnahmen der Digitalkamera verwendet.
Mehr zu diesem Projekt hier.

Screenshot:

Gestelltes Problem
Das Sudoku war also prinzipiell gelöst. Es zeigte sich jedoch, dass für manche Rätsel recht viele Kombinationen ausprobiert werden mussten. Bei einem Rätsel waren es 45253, was für die heutige Hardware ein Witz ist, aber in Zusammenhang mit der Ausgabe jeder Position auf dem Monitor dann doch zu Laufzeiten von über 10 Minuten führte. Da kann man dann natürlich tricksen und nur jede fünfte oder zehnte Position ausgeben. Es zeigte sich jedoch dass bei einer vertikal gespiegelten Version des obigen Rätsels statt 45253 Versuchen nur noch 199 nötig waren. Die Methode, die jeweils erste freie Zelle von links oben durchzuiterieren war offensichtlich suboptimal.

Algorithmus
Der Grundalgorithmus blieb gleich, freie Zelle suchen und für jede mögliche Ziffer Rekursion mit der nächsten freien Zelle. Geändert wurde lediglich das Auffinden dieser Zelle. Unter allen noch freien Zellen wird die genommen, deren Kasten, Zeile und Spalte am meisten gefüllt sind. Bei der Optimierung von rekursiven Programmen habe ich immer eine gewisse Scheu, zusätzliche Anweisungen einzufügen, aber letzten Endes hängt die Gesamtlaufzeit nur von einer möglichst niedrigen Anzahl Rekursionen ab. Mein Referenzrätsel wird jetzt jedenfalls mit 315 Versuchen gelöst.

Screenshot:

Gestelltes Problem
Ein Programm zum Lösen von Kreuzworträtseln habe ich eigentlich schon lange auf meiner ToDo-Liste. Dabei bin ich aber immer vor den notwendigen Wörterbüchern zurückgeschreckt. Bei den japanischen Zahlenrätseln ist die erforderliche Datenbasis viel schmaler. In Zukunft muss ich jedenfalls keine wertvolle Freizeit für das Lösen dieser Dinger mehr aufwenden.

Algorithmus
Erst einmal die Regeln: in jeder Zeile, in jeder Spalte und in jedem der markierten 3×3-Kästchen darf jede Ziffer nur einmal vorkommen.
Der Algorithmus ist nicht besonders knifflig, für die jeweils erste freie Zelle werden die Ziffern von 1 bis 9 ausprobiert. Falls das Rätsel dabei noch erfüllt ist, wird rekursiv mit der nächsten freien Zelle fortgesetzt.

Screenshot:

Wenn ich jemandem gegenüber erwähne, dass ich nach Feierabend gern das eine oder andere Programm schreibe, dann ernte ich regelmässig ein Paar hochgezogener Augenbrauen. Das kommt daher weil ich tagsüber mein Brot mit der Bedienung und Programmierung von EDV-Maschinen verdiene. Deswegen müsste ich eigentlich Abends etwas anderes tun, z.B. hm, mir fällt gerade nichts ein. Nun ist es aber so, dass ich schon in meiner Jugend gern programmiert habe, auch ohne damit Geld zu verdienen.
Als Warnung muss ich noch vorausschicken, dass ich die folgenden Programm nur für mich geschrieben habe und es deshalb sein kann, dass sie nicht allzu benutzerfreundlich sind.

Jetzt möchte ich eine Anwendung, die ich als Freelancer erstellt habe, vorstellen.
Gestelltes Problem
Eine Tochter eines grossen, deutschen Luftfahrtkonzerns brauchte zur Klärung von Sonderfällen bei der Ticketabrechnung eine Anwendung, mit der mehrere Flugtickets mit einem an den PC des Bearbeiters angeschlossenen Scanner aus einer ABAP-Anwendung heraus eingescannt und per FTP in das dortige Image-Archiv übertragen werden können.

Algorithmus
Da es sich um manuelle Einzelscans handelte, kam die TWAIN-Schnittstelle zum Einsatz. Damit die Anwendung aus SAP heraus gesteuert werden konnte, musste sie in Form eines ActiveX-Controls realisiert werden. Der Scanvorgang per TWAIN geschieht normalerweise in zwei Schritten, es wird zunächst ein Preview in niedriger Auflösung gemacht, dann wird vom mitgelieferten, scannerspezifischen TWAIN-GUI (Graphical User Interface) in der gescannten Seite eine Suche nach den zu scannenden Objekten durchgeführt, wobei der Anwender noch eine Korrekturmöglichkeit hat. Erst danach wird dann der finale Scan durchgeführt.
Dieses Verfahren erschien mir aus den folgenden Gründen nicht praktikabel:
a) verschiedene Scanner-Modelle würden unterschiedliche GUIs haben, womit sich eine uneinheitliche Benutzerführung ergäbe
b) durch das doppelte Scannen, zusammen mit der mittendrin notwendigen Benutzerinteraktion würde zuviel Zeit verbraucht werden.
Deshalb entschloss ich mich, jeweils eine DIN A4-Seite komplett einzuscannen und die Tickets in der eingescannten Seite selbst zu lokalisieren. Es wurde ein Kontrasterkennungsalgorithmus implementiert, der eine gescannte Seite auf “Kanten” untersuchte. Die gefundenen Tickets wurden dann dem Anwender dargestellt und mit einer Markierung zur Durchführung eventueller Korrekturen (die aber im Praxisbetrieb selten notwendig sind) versehen. Die Scanzeit für drei Tickets inklusive Bereichssuche liegt mit einem aktuellen HP-Scanner bei vorgewärmter Lampe bei 11 Sekunden.

Screenshot:

(Noch eine Anmerkung zu den etwas blassen Farben. Erstens hat man mir zum Testen einen alten Schrottscanner auf den Schreibtisch gestellt und zweitens werden die extrahierten Images vor dem Speichern selbstredend noch kontrastoptimier

Mit meinen Rechnern habe ich immer gerne Bilder gemacht. Das fing schon mit dem Commodore VC-20 an..
Früher mussten die Bilder komplett von einem selbstgemachten Programm erzeugt werden. Dann bin ich aber auf ein Programm gestossen, mit dem man tolle Effekte erzielen kann. Seitdem lasse ich meine Programme hauptsächlich schwarz-weiss-Bilder erzeugen, die ich dann von Hand nachbearbeite. Die folgenden Bilder sind aus Gründen der Platzersparnis im JPG-Format abgelegt.

Techniken

Am Anfang steht immer eine schwarz-weiss-Vorlage.

Die einzelnen Bereiche dieser Vorlage werden dann gefüllt. Mittlerweile habe ich für diesen Zweck ein eigenes Programm geschrieben. Beim Füllen einer Fläche gibt es drei Faktoren: Vordergrundfarbe, Hintergrundfarbe und der Füllalgorithmus.

Hier einige Beispiele für Füllalgorithmen:
   
Der Erste berechnet für jeden Punkt die Entfernung vom Mittelpunkt der Fläche. Je grösser diese ist, desto stärker wird der Punkt mit der Hintergrundfarbe eingefärbt. Beim Zweiten spielt nur der Abstand in Y-Richtung eine Rolle. Der dritte Algorithmus färbt die Punkte aufgrund des Winkels zur Vertikalen ein. 0 Grad ergibt die Vordergrundfarbe, 180 Grad die Hintergrundfarbe. Der Letzte arbeitet wie der Erste über den Abstand, berechnet jedoch den Sinus des Abstandes vom Flächenmittelpunkt.
Hier obige Vorlage unter Verwendung des zweiten Algorithmus mit der Vordergrundfarbe Weiss und der Hintergrundfarbe Blau gefüllt:

Spirograph

Wenn ich mich recht entsinne, war ein Spirograph eine Sammlung von zahnradbesetzten Schablonen mit Löchern für einen Stift drin. Ein entsprechendes Programm für solche Muster war schnell verfertigt.

Solche Bilder kommen da heraus.
Sie werden dann manuell weiterverarbeitetet:

Das Ergebnis einiger (vieler!) Fülloperationen der vorhergehenden Maske.

Um noch eins draufzusetzen habe ich dann ein Programm geschrieben welches alle BMP-Dateien eines Verzeichnisses einliest und sie Pixel für Pixel addiert. Da kommen dann alle möglichen Bilder heraus: