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: