Microsoft-Sudoku: Optimieren von UMPC-Anwendungen für Berührungs- und Freihandeingaben

Artikel
06/26/2008

Veröffentlicht: 06. Jul 2006

Von Stephen Toub

Stephen Toub erläutert das Zahlenrätsel Sudoku und zeigt, wie eine Anwendung zum Lösen und Erstellen von Rätseln entwickelt wird und wie Spiele für ultramobile PCs und Tablet PCs optimiert werden können. (60 Seiten).

Klicken Sie hier, um den Beispielcode zu diesem Artikel herunterzuladen.

Auf dieser Seite

Einführung
Was ist Sudoku?
Anwendungsinfrastruktur
Sudoku-Algorithmen
Windows Forms und Hardwareinteraktionen
Erweitern von Sudoku
Danksagung
Biografie

Einführung

Vor einem Jahr lernte ich in West Village in New York City ein Rätsel für Stift und Papier kennen, von dem mein Freund Luke völlig fasziniert war. Nur die angeregte Unterhaltung mit anderen Bekannten hat mich davor bewahrt, in dieselbe Falle zu geraten. Mir war jedoch nur ein kurzer Aufschub vergönnt. Einige Monate später, im Juli 2005, kam ich bei einem Besuch bei meinem Bruder und meinem ehemaligen Zimmergenossen in London wieder mit Sudoku in Berührung. Jetzt war das Spiel überall. Und es gab kein Entrinnen. Ich war begeistert, abhängig und nahezu besessen. Wie bei vielen Entwicklern wurde aus dem Hobby bei mir ein Programmierungsprojekt. Kurz nach dem Rückflug in die USA war die erste Version meiner C#-Sudoku-Implementierung fertig.

Ich war jedoch noch nicht zufrieden mit dieser Version. Es fehlte etwas. Es war spannend, die logisch ermittelten Zahlen mit dem Stift klar und deutlich auf das Papier zu schreiben. Dieses Erlebnis ging bei der Übersetzung des Spiels in Windows-Formulare verloren. Und dann hatte ich die Idee. Sudoku ist die ultimative Anwendung für Tablet PCs. Nach dem Herunterladen des Tablet PC-SDKs wandelte ich das Tastatur- und Mausspiel in ein per Stift spielbares Spiel um.

Abbildung 1: Microsoft Sudoku

In diesem Artikel wird meine Tablet PC-Implementierung von Sudoku ausführlich erläutert. Es ist dieselbe Implementierung, die ich für das Touch Pack geschrieben habe, ein Softwarepaket, das auf Ultra-Mobile PCs (UMPCs) vorinstalliert ist. Der Artikel behandelt den Aspekt der Algorithmen beim Implementieren eines Sudoku-Spiels sowie spezifische Informationen, die bei der Implementierung anderer Anwendungen für Tablet PC nützlich sein können.

Was ist Sudoku?

Sudoku ist ein Zahlenrätsel, das zurzeit in Japan und Europa sehr beliebt ist. Das Spiel wird auch in den USA gerade populär und ist in den Regalen aller Buchläden zu finden und wird in vielen Zeitungen abgedruckt. Das typische Rätsel besteht aus einem 9x9-Raster, das in neun 3x3-Blöcke aufgeteilt ist, die wiederum aus jeweils 9 Feldern zusammengesetzt sind. In Abbildung 2 wird das gesamte Raster mit den 81 Feldern dargestellt.

Abbildung 2: Leeres Sudoku-Raster

Das Ziel des Rätsels besteht darin, jedes Feld mit einer Zahl von 1 bis 9 aufzufüllen, und zwar so, dass in jeder Zeile, Spalte und jedem Block jede Zahl von 1 bis 9 nur einmal stehen darf (ein schwierigeres Rätsel, auch als Super-Sudoku bekannt, kann mit einem 16x16-Raster und den Zahlen von 1 bis 9 und den Buchstaben von A bis G konstruiert werden).

In Abbildung 3 wird eine gültige Sudoku-Lösung dargestellt.

Abbildung 3: Eine gültige Sudoku-Lösung

Es wurde errechnet, dass mehr als 10²¹ gültige 9x9-Sudoku-Lösungen möglich sind (weitere Informationen über diese Berechnungen unter http://www.afjarvis.staff.shef.ac.uk/sudoku/). Das Interessante an Sudoku ist, dass am Anfang jedes Rätsels einige Felder des Rasters bereits durch Zahlen vorgegeben sind. Durch diesen Anfangszustand gibt es nur eine einzige Lösung für das Rätsel. Es kann mit logischem Denken gelöst werden, indem alle fehlenden Zahlen eingefügt werden.

Sehen Sie sich Abbildung 4 an (Ich habe hier zur Veranschaulichung einige Felder in gelber und roter Farbe hervorgehoben). Wie bereits erwähnt, muss jeder Block die Zahlen 1 bis 9 enthalten. In dieser Abbildung ist im oberen linken Block keine 2 vorhanden. Das Feld für die 2 in diesem Block kann jedoch durch einfache Kombination ermittelt werden. Ich weiß, dass die 2 nicht in der obersten Zeile stehen darf, da bereits eine 2 in dieser Zeile vorhanden ist (die 2 in der oberen rechten Ecke, die gelb umrandet ist). Ich weiß auch, dass sie nicht in der mittleren Zeile stehen darf, da dort ebenfalls eine 2 ist (die 2 in der zweiten Zeile, vierte Spalte). Auch in der dritten Zeile der zweiten Spalte kann die 2 nicht stehen, da sich dort die 7 befindet (gelb umrandet), und sie kann nicht rechts von der 7 stehen, da bereits eine 2 in dieser Spalte vorhanden ist (in der achten Zeile in gelb hervorgehoben). Aus diesem Grund muss die 2 in der dritten Zeile der ersten Spalte stehen, d. h. in dem Feld, das rot umrandet ist. Ich kann nun die 2 hier eintragen und bin so der Lösung des Rätsels einen Schritt näher gekommen.

Abbildung 4: Ausgangssituation eines Sudoku-Rätsels

Da Sie nun mit den Spielregeln vertraut sind, wird im Folgenden die Implementierung von Sudoku für Tablet PC erläutert. Am Anfang wird auf einige typische Anforderungen von Tablet PC-Anwendungen eingegangen und so erläutert, wie die Anforderungen in Sudoku erfüllt werden und wie Sie dies in eigenen Anwendungen umsetzen können. Danach werden die Besonderheiten der Implementierung eines Sudoku-Spiels ausführlich behandelt, wobei besonders Algorithmen berücksichtigt werden, die für viele Sudoku-Aufgaben verwendet werden können, wie beispielsweise Rätselerstellung und -lösung. Anschließend werden Tablet PC-spezifische Details dargestellt, insbesondere die Verwendung von Tablet PC-APIs zur Unterstützung von Stiftinteraktionen. Am Ende werden einige Ideen und unterhaltsame Beispiele sowie weitere Projekte aufgeführt, die Sie zur Erweiterung des Spiels nach Ihrem Geschmack verfolgen können.

Anwendungsinfrastruktur

Die Konzepte in diesem Abschnitt beziehen sich auf Tablet PC-Anwendungen im Allgemeinen und nicht ausschließlich auf das Sudoku-Spiel.

Plattformerkennung

Die meisten Programme, die spezifisch für Tablet PC-Funktionen geschrieben sind, funktionieren am besten auf Tablet PCs oder einem Entwicklungscomputer, der entsprechend konfiguriert ist. Auf einem solchen Entwicklungscomputer ist idealerweise sowohl das Microsoft Windows XP Tablet PC Edition Software Development Kit 1.7 als auch das Microsoft Windows XP Tablet PC Edition 2005 Recognizer Pack installiert (beide im Mobile PC Developer Center verfügbar). Diese sollten wegen der Zuverlässigkeit der Microsoft.Ink.dll-Assembly installiert sein, die mit der Windows XP Tablet PC Edition 2005 verteilt wird. Jede Tablet PC-Anwendung sollte überprüfen, ob die erforderlichen Bibliotheken und Funktionen zur Verfügung stehen, bevor Code ausgeführt wird, der diese verwendet. Dies sollte auch dann geschehen, wenn die Anwendung die Bibliotheken nur dann lädt und verwendet, wenn sie gefunden werden, da die Plattformerkennung genau für diesen Vorhandenseins-Test erforderlich ist.

Hinweis Sie müssen die Tablet PC-Binärdateien nicht überprüfen, wenn Sie die Dateien tpcman17.msm und mstpcrt.msm verteilen. Sie könnten auch sicherstellen, dass Sie die Anwendung nur auf Computern mit Windows XP Tablet PC Edition 2005 bereitstellen. Wenn Sie jedoch die Tablet PC-Binärdateien nicht verteilen können und die Anwendung auf einem Computer installiert wird, auf dem keine Tablet PC-Binärdateien vorhanden sind, sollten Sie diese Überprüfungen durchführen, damit die Anwendung funktioniert. Dies ist beispielsweise wichtig, wenn die Anwendung eine Freihandsteuerung enthält und auf einer Website bereitgestellt wird.

Im Beispielcode steht der Plattformerkennungs-Code in der PlatformDetection-Klasse der Datei PlatformDetection.cs, die sich im Ordner Utilities befindet. In dieser Klasse steht der Code, mit dem verschiedene Überprüfungen vorgenommen werden können, deren Ergebnisse dann für andere Bereiche der Anwendung verfügbar sind.

Kurz nach dem Starten sollte die Anwendung zuerst überprüfen, ob die Microsoft.Ink.dll-Assembly verfügbar ist. Diese Überprüfung würde implizit stattfinden, wenn der Code, der auf Klassen der Microsoft.Ink.dll-Assembly verweist, das erste Mal kompiliert wird. Sie sollten es jedoch nicht so weit kommen lassen, da es schwierig sein kann, unerwartete Ausnahmen zu behandeln, die der JIT-Compiler auslöst. Eine Möglichkeit ist, explizit nach den Methoden Assembly.Load und Assembly.LoadWithPartialName zu suchen, um eine gültige Microsoft.Ink.dll-Assembly zu ermitteln.

public static bool InkAssemblyAvailable 
{
  get { return _inkAssemblyAvailable; } 
}

private static bool _inkAssemblyAvailable = 
  (LoadInkAssembly() != null);

private static Assembly LoadInkAssembly()
{
  try 
  {
    Assembly a = Assembly.Load(
      "Microsoft.Ink, Version=1.7.2600.2180, " + 
      "Culture=neutral, PublicKeyToken=31bf3856ad364e35");
    if (a == null)
    {
      a = Assembly.LoadWithPartialName(
        "Microsoft.Ink, PublicKeyToken=31bf3856ad364e35");
      if (a != null && a.GetName().Version < 
        new Version("1.7.2600.2180")) a = null;
    }
    return a;
  }
  catch(IOException){}
  catch(SecurityException){}
  catch(BadImageFormatException){}
  return null;
}

Die öffentliche, statische InkAssemblyAvailable-Eigenschaft gibt einen Wert zurück, der in einem privaten, statischen, booleschen Wert gespeichert ist und mit dem Rückgabewert des Aufrufs LoadInkAssembly initialisiert wird. LoadInkAssembly verwendet die Reflektions-APIs, um die Microsoft.Ink-Assembly zu laden, indem ihr vollständiger Name einschließlich Versionsnummer, Kultur und Token des öffentlichen Schlüssels angegeben wird. Wenn das Ladeprogramm die Assembly mit diesen Informationen nicht finden kann, versucht LoadInkAssembly, die Microsoft.Ink-Assembly anhand eines Teilnamens zu laden, d. h. es werden Informationen bei der Suche weggelassen. In diesem Fall wurde die Versionsnummer weggelassen. Der Grund dafür ist, dass die Sudoku-Implementierung auch mit einer neueren Version der Microsoft.Ink.dll verwendet werden könnte (beispielsweise, wenn das Spiel die Version der Tablet PC-APIs in Windows Vista ausführt). Außerdem findet das Ladeprogramm durch das Weglassen der Versionsnummer jede Version der Assembly. Natürlich ist es gefährlich, jede beliebige Version zu suchen. Das Spiel könnte dann auf einer älteren Version ausgeführt werden, bei der eine wichtige Funktion nicht vorhanden ist. Der JIT-Compiler würde beim Kompilieren der Anweisungen, die auf die fehlenden Funktionen verweisen, wiederum Fehler ausgeben. Etwas sicherer ist es (jedoch nicht hundertprozentig sicher), wenn jede neuere Version akzeptiert wird. Daher wird nach dem Laden der Assembly anhand des Teilnamens die Versionsnummer überprüft, um zu gewährleisten, dass es sich um die Version zur Kompilierungszeit oder eine neuere Version handelt.

Eine andere, möglicherweise bessere (im Beispiel verwendete) Möglichkeit ist, die CLR mit ihrer Standardlogik eine geeignete Microsoft.Ink.dll-Assembly suchen und laden zu lassen und dann die Situation zu behandeln, in der die Assembly fehlt und nicht geladen werden kann. Wie bereits erwähnt, ist es oft schwierig, unerwartete Ausnahmen beim Laden von Assemblys und Typen abzufangen. Wenn Sie jedoch wissen, dass diese auftreten und sie in einer kontrollierten Umgebung behandeln können, ist es meistens am besten, sich auf die Funktionen der CLR zu verlassen. Die Beispielimplementierung könnte durch Umschreiben der LoadInkAssembly-Methode folgendermaßen geändert werden.

private static Assembly LoadInkAssembly()
{
  try { return LoadInkAssemblyInternal(); }
  catch(TypeLoadException) {}
  catch(IOException){}
  catch(SecurityException){}
  catch(BadImageFormatException){}
  return null;
}
[MethodImpl(MethodImplOptions.NoInlining)]
private static Assembly LoadInkAssemblyInternal()
{
  return typeof(InkOverlay).Assembly;
}

In der Main-Methode des Programms (in der Datei Program.cs) wird die InkAssemblyAvailable-Eigenschaft verwendet, um zu ermitteln, ob die Ausführung fortgesetzt werden soll. Main zeigt eine Meldung an und beendet das Programm, wenn die Ausführung nicht mehr zulässig ist.

bool validSystem = PlatformDetection.InkAssemblyAvailable && 
          PlatformDetection.RecognizerInstalled;
if (!validSystem)
{
  MessageBox.Show(ResourceHelper.NotRunningOnTablet,
    ResourceHelper.DisplayTitle, MessageBoxButtons.OK, 
    MessageBoxIcon.Error, MessageBoxDefaultButton.Button1);
  return 1;
}

Beachten Sie, dass nicht nur die Freihand-Assembly erforderlich ist. Es muss auch eine Freihanderkennungs-Assembly installiert sein. Auf einer typischen Tablet PC-Installation impliziert die erste Assembly die zweite. Es kann jedoch vorkommen, dass die Freihanderkennung entfernt wurde. Es ist auch möglich, dass die Tablet PC-APIs ohne Freihanderkennung installiert wurden, z. B. in einer Entwicklungsumgebung. Daher werden mit dem folgenden Code beide Bedingungen überprüft.

public static bool RecognizerInstalled
{
  get
  {
    if (!InkAssemblyAvailable) return false;
    return GetDefaultRecognizer() != null;
  }
}

Die RecognizerInstalled-Eigenschaft überprüft zuerst, ob die Freihand-Assembly verfügbar ist. Dies ist wichtig, da die Implementierung von GetDefaultRecognizer auf den Typen in Microsoft.Ink.dll basiert. Diese Methode wird von der RecognizerInstalled-Eigenschaft verwendet, um zu ermitteln, ob eine Erkennung verfügbar ist.

[MethodImpl(MethodImplOptions.NoInlining)]
public static Recognizer GetDefaultRecognizer() 
{
  Recognizer recognizer = null;
  try 
  { 
    Recognizers recognizers = new Recognizers();
    if (recognizers.Count > 1)
    {
      try { recognizer = recognizers.GetDefaultRecognizer(); } 
      catch {}

      if (recognizer == null)
      {
        try 
        { 
          recognizer = 
            recognizers.GetDefaultRecognizer(1033); 
        }
        catch {}
      }
    }
  }
  catch {} 
  return recognizer;
}

GetDefaultRecognizer instanziiert die Microsoft.Ink.Recognizers-Sammlung und stellt sicher, dass mindestens eine Freihanderkennung darin verfügbar ist. Dann wird die Sammlung zum Abrufen der Standarderkennung verwendet. Wenn dies aus irgendeinem Grund nicht funktioniert, wird versucht, die Standarderkennung für LCID 1033 (US-Gebietsschema) abzurufen. (Da bei Sudoku nur Ziffern erkannt werden müssen, reicht dies völlig aus.)

Beachten Sie, dass ein System.Runtime.CompilerServices.MethodImplAttribute für GetDefaultRecognizer verwendet wurde, um sie nicht in das "Inlining" einzubeziehen. Inlining ist ein Prozess, bei dem ein Compiler den Inhalt einer Zielfunktion in eine aufrufende Site kopieren kann und nicht einen direkten Methodenaufruf durchführen muss. Bei kleinen Methoden, bei denen die Belastung durch die Ausführung der Methode unverhältnismäßig groß ist, kann durch Inlining eine bedeutende Leistungsverbesserung erzielt werden. In der Realität wird der JIT-Compiler aufgrund der Codemenge in der GetDefaultRecognizer-Methode kaum ein Inlining durchführen.

Hier sollte jedoch für GetDefaultRecognizer kein Inlining zugelassen werden. Wenn JIT eine Methode kompiliert, versucht der JIT-Compiler, alle Assemblys zu laden, die die Typen in dieser Methode enthalten. Wenn daher beispielsweise der JIT GetDefaultRecognizer kompiliert, versucht der JIT-Compiler die Microsoft.Ink.dll zu laden. Wenn für GetDefaultRecognizer jedoch ein Inlining in RecognizerInstalled vorgenommen wird, findet der Ladeversuch beim Kompilieren von RecognizerInstalled statt, also bevor RecognizerInstalled die Möglichkeit hat, das Vorhandensein der Freihand-Assembly zu überprüfen. Daher wird MethodImplAttribute für GetDefaultRecognizer verwendet, um sicherzustellen, dass kein Inlining stattfindet. Dadurch wird auch ermöglicht, dass RecognizerInstalled zuerst das Vorhandensein der Assembly überprüft.

Diese Sudoku-Implementierung unterstützt die Durchstreichbewegung zum Radieren von zuvor eingegebenen Zahlen. Leider fehlt in den meisten Beispielcodes die Behandlung von Ausnahmen bei Stiftbewegungen, wenn keine gültige Stiftbewegungs-Erkennung installiert ist. Daher wird in diesem Beispielcode mit der PlatformDetection das Vorhandensein einer Stiftbewegungs-Erkennung überprüft.

public static bool GestureRecognizerInstalled
{
  get
  {
    return InkAssemblyAvailable && 
      GestureRecognizerInstalledInternal;
  }
}
private static bool GestureRecognizerInstalledInternal 
{
  [MethodImpl(MethodImplOptions.NoInlining)]
  get
  {
    try
    {
      Recognizers recognizers = new Recognizers();
      if (recognizers.Count > 0)
      {
        using(new GestureRecognizer()) return true;
      }
    }
    catch { } 
        return false;
  }
}

Wie die RecognizerInstalled-Eigenschaft führt die öffentliche, statische GestureRecognizerInstalled-Eigenschaft die Überprüfung nicht explizit durch. Sie hängt aufgrund ihrer Abhängigkeiten von der Microsoft.Ink-Assembly auch von einem Hilfsmember ab, das als NoInlining gekennzeichnet ist. Die GestureRecognizerInstalledInternal-Eigenschaft überprüft, ob eine Erkennung vorhanden ist. Dann instantiiert sie explizit eine Microsoft.StylusInput.GestureRecognizer und gibt zurück, ob diese erfolgreich erstellt werden konnte. Wenn keine Erkennung erfolgreich instanziiert werden konnte wird eine InvalidOperationException mit einer Meldung ausgelöst, dass die angeforderte Erkennung in der aktuellen Installation oder Konfiguration nicht verfügbar ist (deshalb die try-catch-Umgebung in der Instanziierung).

Der letzte Funktionsbereich von PlatformDetection wird verwendet, um die Rechts- oder Linkshändigkeit des Benutzers zu ermitteln. Das Tablet PC-Betriebssystem ermöglicht dem Benutzer, das System für Rechts- oder Linkshänder zu konfigurieren. Anwendungen können diese Einstellung abfragen und ihre Benutzeroberfläche daraufhin anpassen.

public static bool UserIsRightHanded
{
  get
  {
    if (IsRunningOnTablet)
    {
      bool rightHanded = true;
      if (NativeMethods.SystemParametersInfo(
        NativeMethods.SPI_GETMENUDROPALIGNMENT, 0, 
          ref rightHanded, 0))
      {
        return rightHanded;
      }
    }
    return true;
  }
}
private static bool IsRunningOnTablet
{ 
  get 
  {
    return NativeMethods.GetSystemMetrics(
      NativeMethods.SM_TABLETPC) != 0; 
  }
}

Die Eigenschaft überprüft zuerst, ob das aktuelle System ein Tablet PC ist. Hierfür wird nicht InkAssemblyAvailable verwendet, da das Vorhandensein der Freihand-Assembly nicht voraussetzt, dass das System ein Tablet PC ist und diese Einstellung zur Abfrage zur Verfügung steht. Die Eigenschaft verwendet stattdessen die GetSystemMetrics-Funktion aus der user32.dll.

[DllImport("user32.dll", CharSet=CharSet.Auto)]
internal static extern int GetSystemMetrics(int nIndex);

Wenn der Funktion der SM_TABLETPC-Wert (86) übergeben wird, gibt sie einen Wert ungleich Null zurück, sofern das aktuelle Betriebssystem Microsoft Windows XP Tablet PC Edition ist. Andernfalls gibt sie Null zurück. Wenn bekannt ist, dass die Anwendung auf einem Tablet PC ausgeführt wird, kann die Händigkeitseinstellung mit der SystemParametersInfo-Funktion aus der user32.dll abgefragt werden. Die Benutzereinstellung wird durch die SPI_GETMENUDROPALIGNMENT-Einstellung angegeben, die festlegt, ob Popupmenüs links- oder rechtsbündig zum Menüleisteneintrag dargestellt werden.

Entwerfen von Anwendungen für Ultra-Mobile PCs

Der von Microsoft und verschiedenen OEMs angekündigte Ultra-Mobile PC (UMPC) – ein Computer im Geräteformat – bietet Entwicklern, die bereits Tablet PCs verwenden, zahlreiche Vorteile. Die bei der Entwicklung von Tablet PC-Software gesammelten Erfahrungen können auch bei Entwicklungen für UMPCs genutzt werden, da auf den Geräten Windows XP Tablet PC Edition ausgeführt wird. So sind alle UMPCs mit den erforderlichen APIs ausgestattet, um die Entwicklung umfangreicher Pen-Anwendungen zu unterstützen. Auch Anwendungen, die Sie für einen Tablet PC entwickelt haben, können in der Regel problemlos ausgeführt werden. Es gibt jedoch einige Besonderheiten zu beachten, wenn Sie neue Software für UMPC-Geräte entwickeln oder bereits entwickelte Software für die Verwendung auf UMPC-Geräten optimieren.

Zum einen ist der Bildschirm eines UMPC kleiner (in der Regel 800 x 480). Daher sollten Sie die erforderliche Anzeigegröße der Anwendung im Voraus festlegen. Wenn die Anwendung sowohl auf UMPCs als auch auf Standard-Tablet PCs ausgeführt werden soll, müssen Sie dies ebenfalls beim Entwurf berücksichtigen, damit die Anwendung auf verschiedenen Bildschirmen optimal angezeigt wird. Einen Lösungsansatz für diese Anforderungen erläutere ich am Beispiel von Sudoku im Abschnitt Windows-Formulare und Hardwareinteraktionen.

Die meisten Tablet PCs verfügen über elektromagnetische Bildschirme, die eine benutzerfreundliche Interaktion mithilfe spezieller Stifte ermöglichen. Im Gegensatz dazu verfügen UMPCs über Touchscreens. Dadurch wird die Verwendung des Geräts vereinfacht, da nun die Interaktion mit dem UMPC mithilfe des Fingers oder eines beliebigen Zeigegeräts möglich ist. Im Gegensatz zu Tablet PCs mit elektromagnetischer Digitalisierung kann der Benutzer beim Eingabevorgang auf einem UMPC jedoch nicht die Handfläche auf dem Bildschirm ablegen. Dies muss beim Entwerfen der Benutzeroberfläche der Anwendung berücksichtigt werden. Meine Implementierung von Sudoku ermöglicht verschiedene Eingabemethoden. Zahlen können mithilfe einer Tastatur oder eines Stifts in das Rätsel eingefügt werden. Zusätzlich gibt es große Schaltflächen für die Zahlen. Auf diese Schaltflächen kann problemlos mit einem Finger getippt werden. Durch ein zweites Fingertippen in ein Feld des Sudoku-Rätsels wird die Zahl in dieses Feld eingefügt.

Weiterhin ist zu berücksichtigen, dass die Stifte für UMPCs keine elektromagnetischen Geräte, sondern einfache Zeigegeräte sind. Dadurch werden der Anwendung bei der Stifteingabe weniger Informationen übermittelt als bei der Interaktion mit Tablet PCs und elektromagnetischer Digitalisierung. Stellen Sie daher sicher, dass die für UMPCs entwickelten Anwendungen nicht auf diese erweiterten Eingabemöglichkeiten (z. B. Eingabe, ohne dass der Stift die Bildschirmoberfläche berührt und Druckstärke des Stifts) angewiesen sind, um ordnungsgemäß ausgeführt werden zu können.

Trotz dieser Unterschiede können Sie Ihre Erfahrungen aus dem Entwickeln von Tablet PC-Anwendungen vollständig nutzen. Wenn Sie zusätzlich die hier erläuterten Überlegungen berücksichtigen, können Sie die Benutzerfreundlichkeit Ihrer Anwendungen für UMPCs weiter verbessern. Ich habe Sudoku so entwickelt, dass es sowohl auf gewöhnlichen Tablet PCs als auch auf UMPCs ordnungsgemäß ausgeführt werden kann.

Codezugriffssicherheit

Auf den ersten Blick erscheint es nicht notwendig, sich bei der Implementierung eines Spiels wie Sudoku über Sicherheitsfragen Gedanken zu machen – doch das Gegenteil ist der Fall! Als Entwickler muss man Sicherheitsaspekte stets im Auge behalten und sich über mögliche Sicherheitsrisiken für den Benutzer im Klaren sein.

Sudoku z. B. verwendet verschiedene Win32-APIs. Für den Zugriff auf diese APIs sind nicht verwaltete Codeberechtigungen erforderlich. Das ist unproblematisch, wenn Sudoku auf einem lokalen Laufwerk ausgeführt wird und die Standardeinstellungen für die Codezugriffssicherheit (Code Access Security – CAS) nicht geändert wurden. Wenn Sudoku jedoch von einer Netzwerkfreigabe ausgeführt werden soll, wird es komplizierter. In der Standardeinstellung werden für Intranetanwendungen nicht verwaltete Codeberechtigungen nicht gewährt. Wenn Sudoku also versucht, auf diese nicht verwalteten APIs zuzugreifen, wird das System zahlreiche Sicherheitsausnahmen auslösen.

Anstatt Sudoku so zu entwickeln, dass es in einer Umgebung mit teilweiser Vertrauenswürdigkeit ausgeführt werden kann, ist für die Anwendung – wie für die meisten verwalteten Anwendungen – volle Vertrauenswürdigkeit erforderlich. Allerdings kann man kaum von Benutzerfreundlichkeit sprechen, wenn Benutzer versuchen, Sudoku in einer teilweise vertrauenswürdigen Umgebung auszuführen und die Anwendung abstürzt. Stattdessen überprüft Sudoku, ob volle Vertrauenswürdigkeit gewährt wird und zeigt eine Warnung an, wenn die aktuelle Umgebung nicht kompatibel ist. Hier kommt die Main-Methode ins Spiel.

[STAThread]
public static int Main()
{
  Application.EnableVisualStyles();
  Application.DoEvents();
  if (!HasFullTrust)
  {
    MessageBox.Show(ResourceHelper.LacksMinimumPermissionsToRun, 
      ResourceHelper.DisplayTitle, MessageBoxButtons.OK, 
      MessageBoxIcon.Error, MessageBoxDefaultButton.Button1);
    return 1;
}

Es wird überprüft, ob Sudoku volle Vertrauenswürdigkeit gewährt wurde. Ist dies nicht der Fall, wird dem Benutzer eine Fehlermeldung von Sudoku angezeigt, und die Anwendung wird beendet. Die Eigenschaft HasFullTrust wird wie folgt implementiert:

private static bool HasFullTrust
{
  get
  {
    try
    {
      new PermissionSet(PermissionState.Unrestricted).Demand();
      return true;
    }
    catch (SecurityException) { return false; }
  }
}

Die Eigenschaft instanziiert den Berechtigungssatz System.Security.PermissionSet für uneingeschränkten Zugriff und volle Vertrauenswürdigkeit und fordert diese Berechtigung an. Die Demand-Methode löst eine SecurityException aus, wenn die angeforderte Berechtigung nicht verfügbar ist. Daher ist dieser Code in einen try-Block eingeschlossen. Wenn die Demand-Methode erfolgreich ausgeführt wurde, gibt HasFullTrust den Wert true zurück. Wenn die Methode mit einer Ausnahme fehlschlägt, gibt HasFullTrust den Wert false zurück.

Beachten Sie, dass die Anwendung bei einem Fehler der Überprüfung voller Vertrauenswürdigkeit versucht, eine Meldung anzuzeigen. Die Möglichkeit, Meldungen anzuzeigen, wird durch eine Berechtigung gesteuert. Wenn für SafeSubWindows nicht UIPermission festgelegt wurde und eine Anwendung versucht, eine Meldung anzuzeigen, wird eine Sicherheitsausnahme ausgelöst. Dies kann durch verschiedene Maßnahmen verhindert werden. Eine Möglichkeit besteht darin, die ausgelöste Ausnahme abzufangen und das Programm zu beenden. Allerdings erfährt der Benutzer auf diese Weise nie, dass ein Problem vorliegt. Wenn sie in Microsoft Windows Explorer auf die Anwendung doppelklicken, wird nichts geschehen (genauer gesagt: Benutzer erkennen nicht, welche Vorgänge ausgeführt werden. Windows öffnet die Anwendung im Hintergrund und schließt sie wieder, ohne dass es für die Benutzer sichtbare Hinweise gibt). Stattdessen habe ich die Assembly so gekennzeichnet, dass sie die Berechtigung SafeSubWindows als absolute Mindestanforderung benötigt.

[assembly: UIPermission(SecurityAction.RequestMinimum, 
  Window=UIPermissionWindow.SafeSubWindows)]

Wenn der Anwendung also nicht wenigstens diese Berechtigung gewährt wird, wird von der CLR ein eigenes Dialogfeld angezeigt. Dadurch wird der Benutzer darüber informiert, dass die Anwendung aufgrund fehlender notwendiger Berechtigungen nicht geladen werden konnte. Wird wenigstens diese Berechtigung gewährt, wird die Anwendung geladen und mit der Logik der Main-Methode überprüft, ob volle Vertrauenswürdigkeit vorliegt.

Behandlung schwerwiegender Ausnahmen

Die Main-Methode überprüft, ob volle Vertrauenswürdigkeit vorliegt, ob die Microsoft.Ink-Assembly verfügbar ist und ob Erkennungen installiert sind. Nach diesem Vorgang ruft sie die MainInternal-Methode auf, mit der das Hauptformular erstellt und gestartet wird. MainInternal aktiviert die Hauptmeldungsschleife für die Anwendung. Aus diesem Grund werden sämtliche unbehandelten Ausnahmen, die durch Interaktionen über die Benutzeroberfläche während des Spiels ausgelöst werden, von MainInternal weitergereicht. Um diese Ausnahmen für Diagnose- und Debugvorgänge ordnungsgemäß zu protokollieren, werden sie von der Main-Methode abgefangen und protokolliert. Anschließend wird die Methode beendet.

try
{
  return MainInternal() ? 0 : 1;
}
catch(Exception exc)
{
  ShutdownOnException(new UnhandledExceptionEventArgs(exc, false));
  return 1;
}
catch
{
  ShutdownOnException(new UnhandledExceptionEventArgs(null, false));
  return 1;
}

In dem hier erläuterten Programm werden alle schwerwiegenden Fehlerbedingungen mit der ShutdownOnException-Methode protokolliert und die Anwendung schnellstmöglich geschlossen.

internal static void ShutdownOnException(UnhandledExceptionEventArgs e)
{  
  try
  {
    string message = (e.ExceptionObject != null) ?
      e.ExceptionObject.ToString() : 
      ResourceHelper.ShutdownOnError;
    EventLog.WriteEntry(ResourceHelper.DisplayTitle, message, 
      EventLogEntryType.Error);
  }
  catch {}

  try
  {
    MessageBox.Show(ResourceHelper.ShutdownOnError, 
      ResourceHelper.DisplayTitle, MessageBoxButtons.OK, 
      MessageBoxIcon.Hand, MessageBoxDefaultButton.Button1);
  } 
  catch {}
  
  if (!e.IsTerminating) Environment.Exit(1);
}

Viele dieser Vorgänge hätten mit der System.Environment.FailFast-Methode, die in .NET Framework 2.0 verfügbar ist, eleganter gelöst werden können. Diese Implementierung ist jedoch für .NET Framework 1.1 konzipiert.

Die ShutdownOnException-Methode akzeptiert einen System.UnhandledExceptionEventArgs-Parameter mit einer Fehlerbeschreibung. Die Methode versucht zuerst, mithilfe der statischen System.Diagnostics.EventLog.WriteEntry-Methode Informationen zur Ausnahme, einschließlich der Stapelüberwachung, im Anwendungsprotokoll zu protokollieren. Danach versucht die Methode, eine Meldung anzuzeigen, die den Benutzer über das Auftreten einer Ausnahme informiert. Wird die Anwendung nicht bereits beendet, wird sie durch die Environment.Exit-Methode geschlossen.

Wie bereits erläutert, wird die ShutdownOnException-Methode nur aufgerufen, wenn unbehandelte Ausnahmen im Haupt-UI-Thread auftreten. Wie wird mit schwerwiegenden Ausnahmen in anderen Threads verfahren? Um diese Ausnahmen zu behandeln, verknüpft die MainInternal-Methode zuerst Ereignishandler mit dem aktuellen UnhandledException-Ereignis der AppDomain und dem Application.ThreadException-Ereignis von Windows Form.

AppDomain.CurrentDomain.UnhandledException += 
  new UnhandledExceptionEventHandler(
    CurrentDomain_UnhandledException);
Application.ThreadException += 
  new ThreadExceptionEventHandler(Application_ThreadException);

Diese Ereignisse werden von den Ereignishandlern an ShutdownOnException weitergeleitet.

private static void Application_ThreadException(
  object sender, ThreadExceptionEventArgs e)
{
  ShutdownOnException(new UnhandledExceptionEventArgs(
    e.Exception, false));
}
private static void CurrentDomain_UnhandledException(
  object sender, UnhandledExceptionEventArgs e)
{
  ShutdownOnException(e);
}

Durch diesen Code werden sämtliche Abstürze oder schwerwiegenden Ausnahmen, die beim Verwenden der Anwendung auftreten, protokolliert, sodass das Debuggen von Abstürzen wesentlich einfacher wird. Die meisten dieser Aufgaben werden in .NET Framework 2.0 übrigens automatisch ausgeführt. Wenn unbehandelte Ausnahmen auftreten, wird der Vorgang abgebrochen, und Dr. Watson erstellt ein Anwendungsabbild für spätere Analysen und Debugvorgänge.

Einzel-Instanz-Anwendungen

Viele Anwendungen, vor allem Anwendungen für Tablet PCs, sind als Einzel-Instanz-Anwendungen konzipiert. "Einzel-Instanz-Anwendung" bedeutet, dass stets nur ein Anwendungsprozess auf einmal ausgeführt wird. Abhängig von der Definition von "Einzel-Instanz" und den Anforderungen der Anwendung gilt diese Einschränkung entweder für einen bestimmten Desktop oder den gesamten Computer. Sudoku ist so konzipiert, dass jeder Benutzer eines Computers nur jeweils eine Instanz von Sudoku ausführen kann. Wäre Sudoku mithilfe von Microsoft Visual Studio 2005 und .NET Framework 2.0 implementiert worden, würden Einzel-Instanz-Anwendungen automatisch unterstützt. In .NET Framework 1.1 musste ich diese Unterstützung jedoch selbst einrichten. Weitere Informationen zur Unterstützung von Einzel-Instanz-Anwendungen finden Sie in der Kolumne .NET Matters des MSDN-Magazins vom September 2005.

Die Unterstützung von Einzel-Instanz-Anwendungen wurde in die Klasse SingleInstance integriert, die im Verzeichnis Utilities in der SingleInstance.cs-Datei verfügbar ist. Im Folgenden wird beschrieben, wie SingleInstance von MainInternal verwendet wird.

using(SingleInstance si = new SingleInstance())
{
  if (si.IsFirst)
  {
    // Create the main form and run the app
    ...

    // Finished game successfully
    return true;
  }
  else
  {
    // Not the first Sudoku instance... show the other one
    si.BringFirstToFront();
    return false;
  }
}

Zuerst wird eine neue Instanz dieser Klasse erstellt und deren IsFirst-Eigenschaft abgefragt, um festzustellen, ob derzeit weitere Instanzen dieser Anwendung ausgeführt werden. Wenn es sich um die erste Instanz der Anwendung handelt, wird die Anwendung ordnungsgemäß ausgeführt und das Hauptformular der Anwendung erstellt und angezeigt. Wenn bereits eine andere Instanz ausgeführt wird, zeigt die BringFirstToFront-Methode die erste Instanz von Sudoku im Vordergrund an und beendet die zweite Instanz.

Für Einzel-Instanz-Funktionen ist prozessübergreifende Kommunikation (IPC – Inter-Process Communication) erforderlich, da eine Instanz einer anderen mitteilen muss, dass bereits eine Instanz ausgeführt wird und die zweite Instanz beendet werden soll. Die Klasse SingleInstance benötigt sogar zwei verschiedene IPC-Mechanismen: einen prozessübergreifenden primitiven Synchronisierungstyp und eine Datei mit zugewiesenem Speicher.

Das Erstellen grundlegender Einzel-Instanz-Funktionen ist einfach und erfordert nur wenige Zeilen Code.

static void Main()
{
  string mutexName = "2ea7167d-99da-4820-a931-7570660c6a30";
  bool grantedOwnership;
  using(Mutex singleInstanceMutex = 
    new Mutex(true, mutexName, out grantedOwnership)
  {
    if (grantedOwnership)
    {
      ... // core code here
    }
  }
}

Wenn mehrere Threads gleichzeitig auf eine freigegebene Ressource zugreifen müssen, ist ein Synchronisierungsmechanismus erforderlich, damit die Threads nacheinander auf die Ressource zugreifen. In diesem Fall handelt es sich eher um eine logische "Ressource" als um eine physische. Damit ist die Möglichkeit gemeint, eine Instanz der Anwendung auszuführen. Der in der Klasse System.Threading.Mutex implementierte Mutex ist ein primitiver Synchronisierungstyp, mit dem jeweils einem Thread exklusiver Zugriff gewährt wird. Wenn ein Thread einen Mutex erhalten hat und ein weiterer Thread ebenfalls diesen Mutex anfordert, wird der zweite Thread so lange angehalten, bis der erste Thread den Mutex freigibt. Eine weitere Möglichkeit besteht darin, den zweiten Thread nach Anforderung der Mutex-Freigabe nicht anzuhalten, sondern darüber zu informieren, dass diese bereits vergeben ist.

In diesem Fall wurde der Mutex mit einer GUID als Namen erstellt (von jeder Anwendung, die Code wie den hier erläuterten ausführt, wird ein eigener eindeutiger Namen vergeben). Wenn ein Mutex mit einem Namen erstellt wurde, kann dieser für die Synchronisierung von Threads aus separaten Vorgängen verwendet werden. Dabei fordert jeder Vorgang die Freigabe mithilfe des festgelegten und bekannten Namen des Mutex an. Einer der Mutex-Konstruktoren akzeptiert nicht nur den Namen, sondern auch einen booleschen out-Parameter, mit dem angegeben wird, ob der Mutex zugewiesen werden kann. Dadurch wird das Erstellen von Einzel-Instanz-Funktionen deutlich vereinfacht. Durch den Code wird ein Mutex erstellt und überprüft, ob dieser zugewiesen werden kann. Wenn der Mutex zugewiesen werden kann, ist diese Instanz die erste Instanz und kann weiter ausgeführt werden. Wenn der Mutex nicht zugewiesen werden kann, handelt es sich um die zweite Instanz, die beendet werden sollte.

Grundsätzlich wurde auch SingleInstance nach diesen Prinzipien erstellt, allerdings wurde die Klasse weiter verbessert. Anstatt eine hartcodierte GUID zu verwenden, erstellt SingleInstance eine ID auf Grundlage der Identität der Startassembly der aktuellen Anwendung.

private static string ProgramID
{
  get
  {
    Assembly asm = Assembly.GetEntryAssembly();
    Guid asmId = Marshal.GetTypeLibGuidForAssembly(asm);
    return asmId.ToString("N") + asm.GetName().Version.ToString(2);
  }
}

Die ID setzt sich aus der GUID der Assembly-Typbibliothek und der Version der Assembly zusammen. Im Folgenden wird erläutert, wie mithilfe dieser ID der Name des Mutex erstellt wird.

string mutexName = "Local\\" + ProgramID + "_Lock";

Wie im vorigen Beispiel instanziiert der SingleInstance-Klassenkonstruktor einen Mutex, der allerdings in einer Membervariable und nicht in einer lokalen Variable gespeichert wird.

_singleInstanceLock = new Mutex(true, mutexName, out _isFirst);

Der dritte Parameter des Konstruktors ist die boolesche Variable, in der gespeichert wird, ob dieser Mutex-Instanz die Freigabe zugewiesen werden konnte. Auf diesen booleschen Wert kann anschließend mithilfe der Eigenschaft IsFirst zugegriffen werden.

public bool IsFirst { get { return _isFirst; } }

Mithilfe der Implementierung der IDisposable.Dispose-Methode durch SingleInstance wird der Mutex geschlossen.

Wenn das alle Anforderungen an die Funktionen wären, könnte ich hier jetzt aufhören. Allerdings wird in vielen Einzel-Instanz-Anwendungen die bereits aktive Instanz im Vordergrund angezeigt, wenn der Benutzer versucht, eine zweite Instanz zu starten. Für diese Funktion müssen zusätzliche Informationen zwischen den Vorgängen ausgetauscht werden. Die zweite Instanz muss nicht nur erkennen, dass bereits eine Instanz ausgeführt wird, sondern in diesem Fall auch den Vorgang bestimmen können, der im Vordergrund angezeigt werden soll. In einigen Anwendungen wird dies erreicht, indem auf dem Desktop alle Fenster der obersten Ebene nach einem bestimmten Namen durchsucht werden. Diese Methode ist jedoch nicht sehr zuverlässig. Ich habe mich für eine Methode entschieden, bei der eine Datei mit zugewiesenem Speicher verwendet wird.

In diesem Szenario kann man sich Dateien mit zugewiesenem Speicher als eine Art gemeinsam genutzten Speicher vorstellen. So können durch einen Vorgang Informationen in den Speicher geschrieben werden, die später von einem anderen Vorgang gelesen werden können. In diesem Fall kann die erste Anwendungsinstanz ihre Vorgangs-ID in eine Datei mit zugewiesenem Speicher schreiben, sodass diese ID von weiteren Instanzen gelesen und die erste Instanz im Vordergrund angezeigt werden kann.

private void WriteIDToMemoryMappedFile(uint id)
{
  _memMappedFile = new HandleRef(this, 
    NativeMethods.CreateFileMapping(new IntPtr(-1), IntPtr.Zero, 
      PAGE_READWRITE, 0, IntPtr.Size, _memMapName));
  if (_memMappedFile.Handle != IntPtr.Zero && 
    _memMappedFile.Handle != new IntPtr(-1))
  {
    IntPtr mappedView = NativeMethods.MapViewOfFile(
      _memMappedFile.Handle, FILE_MAP_WRITE, 0, 0, 0);
    try
    {
      if (mappedView != IntPtr.Zero) 
        Marshal.WriteInt32(mappedView, (int)id);
    }
    finally
    {
      if (mappedView != IntPtr.Zero) 
        NativeMethods.UnmapViewOfFile(mappedView);
    }
  }
}

private uint ReadIDFromMemoryMappedFile()
{
  IntPtr fileMapping = NativeMethods.OpenFileMapping(
    FILE_MAP_READ, false, _memMapName);
  if (fileMapping != IntPtr.Zero && fileMapping != new IntPtr(-1))
  {
    try
    {
      IntPtr mappedView = NativeMethods.MapViewOfFile(
        fileMapping, FILE_MAP_READ, 0, 0, 0);
      try
      {
        if (mappedView != IntPtr.Zero)
          return (uint)Marshal.ReadInt32(mappedView);
      }
      finally
      {
        if (mappedView != IntPtr.Zero) 
          NativeMethods.UnmapViewOfFile(mappedView);
      }
    }
    finally { NativeMethods.CloseHandle(fileMapping); }
  }
  return 0;
}

Dateien mit zugewiesenem Speicher können – genau wie prozessübergreifende Mutexe – benannt werden, damit mehrere Vorgänge mithilfe des Namens auf diese Dateien zugreifen können. Eine Datei mit zugewiesenem Speicher wird mithilfe der Funktion CreateFileMapping erstellt, die über die kernel32.dll verfügbar ist. Die Datei mit zugewiesenem Speicher wird anschließend mithilfe der Funktion MapViewOfFile dem Adressbereich zugewiesen. Diese Funktion ist ebenfalls über kernel32.dll verfügbar. Mit MapViewOfFile wird die Startadresse für den Speicher festgelegt. Diese Adresse wird anschließend verwendet, um mithilfe der System.Runtime.InteropServices.Marshal-Klasse Daten aus diesem Speicher zu lesen bzw. in diesen Speicher zu schreiben. Wenn bereits eine Datei mit zugewiesenem Speicher erstellt wurde, können Sie diese mit der Funktion OpenFileMapping der kernel32.dll öffnen.

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr CreateFileMapping(IntPtr hFile, 
  IntPtr lpAttributes, int flProtect, int dwMaxSizeHi, 
  int dwMaxSizeLow, string lpName);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr OpenFileMapping(int dwDesiredAccess, 
  [MarshalAs(UnmanagedType.Bool)] bool bInheritHandle, 
  string lpName);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr MapViewOfFile(IntPtr hFileMapping, 
  int dwDesiredAccess, int dwFileOffsetHigh, int dwFileOffsetLow, 
  int dwNumberOfBytesToMap);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
[return: MarshalAs(UnmanagedType.Bool)]
internal static extern bool UnmapViewOfFile(IntPtr pvBaseAddress);

[DllImport("kernel32.dll", SetLastError=true)]
[return: MarshalAs(UnmanagedType.Bool)]
internal static extern bool CloseHandle(IntPtr handle);

Der SingleInstance-Konstruktor erstellt einen Mutex und überprüft, ob dies der erste ist. Wenn ja, speichert der SingleInstance-Konstruktor mithilfe der WriteIDToMemoryMappedFile-Methode die eigene Vorgangs-ID, die gegebenenfalls von weiteren Instanzen abgerufen werden kann. Wenn eine zweite Instanz ausgeführt und die BringFirstToFront-Methode abgerufen wird, greift diese Instanz mithilfe der ReadIDFromMemoryMappedFile-Methode auf die Vorgangs-ID der ersten Instanz zu. Mit dieser Vorgangs-ID und den Funktionen ShowWindowAsync und SetForegroundWindow, die über die user32.dll verfügbar sind, wird die erste Instanz im Vordergrund angezeigt.

public void BringFirstToFront()
{
  if (!_isFirst)
  {
    uint processID = ReadIDFromMemoryMappedFile();
    if (processID != 0)
    {
      const int SW_SHOWNORMAL = 0x1;
      const int SW_SHOW = 0x5;
      IntPtr hwnd = new ProcessInfo(processID).MainWindowHandle;
      if (hwnd != IntPtr.Zero)
      {
        int swMode = NativeMethods.IsIconic(new HandleRef(
          this, hwnd)) ? SW_SHOWNORMAL : SW_SHOW;
        NativeMethods.ShowWindowAsync(hwnd, swMode);
        NativeMethods.SetForegroundWindow(new HandleRef(
          this, hwnd));
      }
    }
  }
}

Sudoku-Algorithmen

In diesem Abschnitt werden die Aspekte der Anwendung beschrieben, die Sudoku-Rätsel betreffen.

Verwalten des Puzzlestatus

Beim Erstellen einer solchen Anwendung beginne ich gern damit, zunächst minimale Features zum Funktionieren zu bringen, auf die ich anschließend aufbauen kann. Bei Sudoku betrifft dies das Erstellen der erforderlichen Datenstrukturen zum Speichern des Rätselstatus.

Ein Rätsel kann einfach als zweidimensionales Array dargestellt werden. Jedes Feld muss eine Ziffer speichern oder leer sein können. .NET Framework 2.0 bietet eine gute Lösung in Form von Typen, die NULL-Werte zulassen. In .NET Framework 2.0 ermöglichen Typen, die NULL-Wert zulassen, dass Wertetypen auch einen NULL-Wert annehmen können. Sie werden mit einer neuen generischen Struktur dargestellt, Nullable<T>. Intern speichert Nullable<T> zwei Werte, einen vom Typ T (wobei T der generische Typparameter ist und einen beliebigen Werttyp haben kann, mit Ausnahme eines anderen Typs, der NULL zulässt), der den Wert der Instanz speichert, und einen Booleschen Wert, der angibt, ob die Instanz einen Wert hat oder nicht. Generische Typen sind in .NET Framework 1.1 nicht verfügbar, was jedoch nicht heißt, dass ich dann eben Pech gehabt habe. Für die wenigen Typen, für die ich NULL-Wert-Unterstützung benötige, erstelle ich eigene Ersatztypen, z. B. NullableByte und NullableInt. In jeder dieser Ersatzstrukturen ist ein Wert des entsprechenden Typs (z. B. byte in NullableByte und int in NullableInt) und ein Boolescher Wert enthalten, von denen letzterer angibt, ob der Integerwert einen verwendbaren Wert enthält. Dies ist zwar nicht so elegant wie die generische Lösung von .NET Framework 2.0, besonders da C# 2.0 syntaktische Unterstützung für Nullable<T> enthält, für meine Zwecke ist es jedoch ausreichend. Da jedes Feld des Rätsels entweder leer sein oder einen kleinen numerischen Wert enthalten kann, speichere ich das Raster als Array des Typs NullableBytes.

[Serializable]
public sealed class PuzzleState : ICloneable, IEnumerable
{
  private NullableByte[,] _grid;
  private readonly byte _boxSize;
  private readonly byte _gridSize;
  ...
}

Die PuzzleState-Klasse enthält verschiedene Informationen, wie die Größe des Rasters und seinen Inhalt. In der aktuellen Implementierung werden nur 9x9-Sudoku-Raster unterstützt, mit wenig mehr Aufwand kann die Anwendung jedoch erweitert werden, um größere und sogar nicht quadratische Raster zu unterstützen.

Einer der wichtigsten Aspekte von PuzzleState ist die Implementierung der Schnittstelle ICloneable. Diese Implementierung, mit der sich auf einfache Weise eine vollständige Kopie einer Instanz von PuzzleState erstellen lässt, wird für andere Aspekte dieser Lösung häufig verwendet, z. B. zur Lösung und Erstellung von Rätseln oder auch bei spielbezogenen Features wie einer Rückgängig-Funktion.

object ICloneable.Clone() { return this.Clone(); }
public PuzzleState Clone() { return new PuzzleState(this); }
private PuzzleState(PuzzleState state)
{
  _boxSize = state._boxSize;
  _gridSize = state._gridSize;
  _grid = (NullableByte[,])state._grid.Clone();
  ...
}

Analysieren und Lösen von Rätseln

Das Lösen eines Sudoku-Rätsels ist in Wirklichkeit eine besondere Art von Suche, daher kann ich normale Suchalgorithmen einsetzen. Ein gebräuchlicher Suchalgorithmus ist die Tiefensuche (Depth-First Search, DFS), gewöhnlich einer der ersten Algorithmen, die Studenten in einem Kurs zu Datenstrukturen und Algorithmen kennen lernen. Im Verlauf einer Suche gibt es Instanzen, in denen sich mehrere Pfade für die Abfrage anbieten, und bei einer Tiefensuche wird einer dieser Pfade in seiner Gesamtheit und einschließlich aller daraus abzweigenden Pfade erforscht, bevor die anderen Pfade untersucht werden. Obwohl DFS über einen expliziten Stapel implementiert werden kann, wird zum Implementieren einer Tiefensuche häufig eine Rekursion verwendet. Stellen Sie sich eine Strukturknoten-Datenstruktur vor, in der neben einer Liste der untergeordneten Knoten ein Wert gespeichert wird. Eine Tiefensuche nach einem bestimmten Wert in einer Struktur könnte wie folgt aussehen:

public class TreeNode<T> where T : IComparable
{
  public TreeNode(T value) { Value = value; }
  public T Value;
  public List<TreeNode<T>> Children = new List<TreeNode<T>>();

  public TreeNode<T> DfsSearch(T v)
  {
    if (Value.CompareTo(v) == 0) return this;
    foreach (TreeNode<T> child in Children)
    {
      TreeNode<T> rv = child.DfsSearch(v);
      if (rv != null) return rv;
    }
    return null;
  }
}

Beim Aufrufen von DfsSearch in einer TreeNode<T> wird überprüft, ob der im Knoten gespeicherte Wert dem gesuchten entspricht. Falls ja, wird der aktuelle Knoten zurückgegeben. Andernfalls wird die DfsSearch-Methode jedes untergeordneten Knotens aufgerufen, um zu überprüfen, ob der gesuchte Wert sich in der Teilstruktur des untergeordneten Knotens befindet. Auf diese Weise wird die gesamte Struktur durchsucht.

Auf genau dieselbe Weise können Sie nach einer Sudoku-Lösung suchen. Betrachten Sie einen bestimmten Status des Rätsels als einen Knoten in einer Struktur. Von diesem Status aus komme ich durch Eingeben einer Zahl in ein leeres Feld des Rasters zu anderen "untergeordneten" Status. Daher sind von jedem Status aus eine endliche Anzahl von untergeordneten Status erreichbar (jeweils ein Status für jeden Wert, der in ein leeres Feld eingegeben werden kann). Bei einem 9x9-Raster gibt es höchstens 729 untergeordnete Status, eine endliche Anzahl. Daher lässt sich eine Suche nach einer Lösung für ein beliebiges Sudoku-Rätsel mit nur wenig DFS-ähnlichem Code implementieren, ähnlich dem folgenden:

static PuzzleState DfsSolve(PuzzleState state)
{
  switch (CheckSolution(state))
  {
    case PuzzleStatus.Solved: return state;
    case PuzzleStatus.CannotBeSolved: return null;
    default:
      NullablePoint cell = FindFirstEmptyCell(state);
      if (cell == null) return null;
      for (byte n = 0; n < state.GridSize; n++)
      {
        state[cell.Value] = n;
        PuzzleState result = DfsSolve(state);
        if (result != null) return result;
      }
      state[cell.Value] = null;
      return null;
  }
}

Diese Methode, ähnlich der bei meiner Sudoku-Implementierung angewendeten, überprüft PuzzleState und ermittelt, ob das Rätsel gelöst ist, ob es einen ungültigen Status hat (also einen Widerspruch enthält) und definitiv unlösbar ist oder ob es weiterhin ein ungelöstes Rätsel ist. Das Durchführen dieser Prüfung erfolgt wie bei DfsSearch, wenn TreeNode<T> auf einen Knoten mit dem richtigen Wert überprüft wird, mit dem Unterschied, dass ich überprüfe, ob eine Lösung gefunden wurde. Wenn eine Lösung gefunden wurde, wird sie zurückgegeben. Wenn ein ungültiger Status angetroffen wird, bedeutet dies, dass ein Fehler vorhanden ist und aufgespürt werden muss. Wenn das Rätsel noch bearbeitet wird, muss ich eine Zahl in ein leeres Feld eingeben. Ich suche das erste leere Feld und probiere alle möglichen Werte aus, einen nach dem anderen. Wenn das Rätsel lösbar ist, muss einer dieser Werte gültig sein. Ich gebe in jedes Feld einen Wert ein und rufe dann rekursiv DfsSolve auf. Wenn das Rätsel lösbar ist, wird früher oder später eine Lösung gefunden.

Leider hat dieser Ansatz einen größeren Nachteil: die Ausführung dauert sehr, sehr, sehr lange. Bei einem 9x9-Raster müssen bis zu neun Werte für jedes Feld ausprobiert werden. Bei 81 auszufüllenden Feldern muss ich möglicherweise 9⁸¹ Spielflächen ausprobieren. Auch wenn eine Zahl pro Feld in einer Nanosekunde verarbeitet werden könnte, wären wahrscheinlich weder ich noch ein Leser dieses Artikels bei Abschluss des Vorgangs noch unter den Lebenden! Tatsächlich wäre unsere Sonne wahrscheinlich längst erloschen, bevor eine Lösung gefunden wird. Das wahre Problem besteht darin, dass ich den gesamten Suchraum durchforste, obwohl ich vieles tun kann, um die Suchstruktur zu verkleinern, z. B. durch Einschränken der Menge der Suchvorgänge. Beim Lösen eines Sudoku-Rätsels gibt es viele Möglichkeiten, von denen Sie wissen, dass sie nicht möglich sind. Warum soll der Computer sie also ausprobieren? Schließen Sie sie aus.

Es stehen eine Vielzahl von Techniken zur Verfügung, um dem Computer zum Beschränken der Suche zu bringen, und eine der einfachsten besteht darin, dem Computer mitzuteilen, welche Zahlen sich definitiv nicht in einem Feld befinden können. Beim Ausführen der Brute-Force-Suche müssen dann nur die noch möglichen Zahlen berücksichtigt werden.

Für jedes Feld im Raster erstelle ich ein Bit-Array. Die Idee dabei ist, für jedes Feld bestimmte Zahlen als Möglichkeiten auszuschließen, indem die anderen, automatisch eingestellten oder "vorgegebenen" Zahlen in der Spalte, Reihe und Kasten des Feldes überprüft werden, denn keine der dort vorhandenen Zahlen kann in das Feld gehören. Im Prinzip ist ein Bit-Array ein Satz von Schaltern – ein oder aus – der boolesche Werte für einen Satz von Elementen speichert. Die einfachste Möglichkeit der Darstellung eines Bit-Arrays in .NET Framework ist die Verwendung der Klasse System.Collections.BitArray. Nachdem ich diese Klasse jedoch in meiner Implementierung verwendet und einige Profiltests durchgeführt hatte, bemerkte ich, dass es einige Vorteile hätte, eine neue, auf meine speziellen Anforderungen zugeschnittene Implementierung zu erstellen. Also habe ich meine eigene Implementierung, FastBitArray erstellt, die sich im Verzeichnis Sammlungen in der Datei FastBitArray.cs befindet. (Wenn Sie jemals einen Bit Bucket geschrieben haben, sollte Ihnen die Implementierung vertraut vorkommen.) Da diese Implementierung von Sudoku nie mit großen Werten operieren muss (sofern sie ausschließlich 9x9-Rätsel unterstützt), dient FastBitArray als Wrapper für einen Wert des Typs unsigned integer, der bis zu 32 boolesche Werte enthalten kann. Schreib- und Lesevorgänge werden durch eine einfache Bitmanipulation implementiert.

public bool Get(int index) 
{
  return (_bits & (1u << index)) != 0;
}
public void Set(int index, bool value) 
{
  bool curVal = Get(index);
  if (value && !curVal) 
  {
    _bits |= (1u << index);
    _countSet++;
  }
  else if (!value && curVal)
  {
    _bits &= ~(1u << index);
    _countSet--;
  }
}

Daneben habe ich ein zweidimensionales Array von FastBitArray-Instanzen, entsprechend des zweidimensionalen Arrays mit den Werten der einzelnen Felder im Raster.

Dadurch, dass die möglichen Feldwerte bekannt sind, kann die Methode DfsSolve schneller ausgeführt werden. Anstatt jeden Wert in jedem Feld auszuführen, kann ich die Suche auf die in den einzelnen Feldern möglichen Werte einschränken. Außerdem wird bei der DfsSolve-Implementierung, die ich vorgestellt habe, das erste Feld gesucht und ausgefüllt – eine schlechte Heuristik. Da nur einer der Werte, die ich in einem bestimmten Feld ausprobieren kann, richtig ist, ist es sinnvoll, den Suchbaum zu beschneiden und mit dem Feld zu beginnen, von dem ich weiß, dass dort die wenigsten Zahlen in Frage kommen. Also kann DfsSolve weiter verbessert werden, indem das leere Feld mit den wenigsten möglichen Kandidaten aller leeren Felder ermittelt wird. Jedes Mal, wenn ein Feld in DfsSolve festgelegt wird, kann ich das Array der möglichen Zahlen aktualisieren und damit die soeben ermittelte Zahl als Möglichkeit für alle betroffenen Felder entfernen.

Während ich DfsSolve zu Erklärungszwecken herangezogen habe, ist die Implementierung für Sudoku in der Praxis sehr ähnlich. Im Folgenden sind leicht verkürzte Versionen der beiden Grundmethoden in meiner Solver-Klasse dargestellt, die in der Datei Solver.cs verfügbar ist. Beachten Sie die Ähnlichkeiten mit DfsSolve und die vorgeschlagenen Verbesserungen, die ich beschrieben habe.

private static SolverResults SolveInternal(
  PuzzleState state, SolverOptions options)
{
  state = state.Clone();

  FastBitArray [][] possibleNumbers = 
    FillCellsWithSolePossibleNumber(state, 
    options.EliminationTechniques);

  switch (state.Status)
  {
    case PuzzleStatus.Solved:
    case PuzzleStatus.CannotBeSolved:
      return new SolverResults(state.Status, state, 0);
    default:
      if (options.AllowBruteForce)
      {
        SolverResults results = BruteForceSolve(
          state, options, possibleNumbers);
        return results;
      } 
      else return new SolverResults(
        PuzzleStatus.CannotBeSolved, state, 0, null);
  }
}

private static SolverResults BruteForceSolve(PuzzleState state, 
  SolverOptions options, FastBitArray [][] possibleNumbers)
{
  // Find cells with fewest possible candidates
  ArrayList bestGuessCells = new ArrayList();
  int bestNumberOfPossibilities = state.GridSize + 1;
  for (int i = 0; i < state.GridSize; i++)
  {
    for (int j = 0; j < state.GridSize; j++)
    {
      int count = possibleNumbers[i][j].CountSet;
      if (!state[i, j].HasValue)
      {
        if (count < bestNumberOfPossibilities)
        {
          bestNumberOfPossibilities = count;
          bestGuessCells.Clear();
          bestGuessCells.Add(new Point(i, j));
        }
        else if (count == bestNumberOfPossibilities)
        {
          bestGuessCells.Add(new Point(i, j));
        }
      }
    }
  }

  // Pick one
  SolverResults results = null;
  if (bestGuessCells.Count > 0)
  {
    Point bestGuessCell = (Point)bestGuessCells[
      RandomHelper.GetRandomNumber(bestGuessCells.Count)];
    FastBitArray possibleNumbersForBestCell = possibleNumbers[
      bestGuessCell.X][bestGuessCell.Y];
    for(byte p=0; p<possibleNumbersForBestCell.Length; p++)
    {
      if (possibleNumbersForBestCell[p])
      {
        PuzzleState newState = state;
        newState[bestGuessCell] = p;
        SolverOptions tempOptions = options.Clone();
        if (results != null) 
        {
          tempOptions.MaximumSolutionsToFind = (uint)(
            tempOptions.MaximumSolutionsToFind.Value – 
            results.Puzzles.Count);
        }

        // Recur
        SolverResults tempResults = 
          SolveInternal(newState, tempOptions);

        if (tempResults.Status == PuzzleStatus.Solved)
        {
          if (results != null && results.Puzzles.Count > 0)
          {
            results.Puzzles.AddRange(tempResults.Puzzles);
          }
          else
          {
            results = tempResults;
            results.NumberOfDecisionPoints++;
          }
          if (options.MaximumSolutionsToFind.HasValue &&
            results.Puzzles.Count >= 
              options.MaximumSolutionsToFind.Value) 
            return results;
        }

        newState[bestGuessCell] = null;
      }
    }
  }
  return results != null ? results : new  
    SolverResults(PuzzleStatus.CannotBeSolved, state, 0, null);
}

Hier passiert eine Menge. Die Methode SolveInternal beginnt mit dem Erstellen einer Kopie von PuzzleState, und alle Operationen werden an dieser Kopie ausgeführt, nicht am Original. Auf diese Weise haben die von Solver initiierten Aktionen keine Auswirkungen auf die vom Aufrufer bereitgestellte Klasse PuzzleState. Dann wird FillCellsWithSolePossibleNumber zum Überprüfen des aktuellen Spielfelds auf Felder mit nur einer möglichen Zahl verwendet, die daraufhin ausgefüllt werden (auf diese Methode komme ich gleich zurück). Wenn an diesem Punkt das Rätsel entweder gelöst ist oder als unlösbar bewertet wird, wird die Methode beendet. Andernfalls wird die Brute-Force-Suche zum Ausfüllen eines Feldes angewendet. Das nächste auszufüllende Feld wird danach ausgewählt, welches Feld die wenigsten möglichen Zahlen hat (wenn dies für mehrere Felder gilt, wird eines davon nach Zufallsverfahren ausgewählt). Wenn das Feld ausgefüllt wurde, reagiert das System mit einem Aufruf von SolveInternal, und der Vorgang beginnt von neuem, mit dem Unterschied, dass ein Feld mehr ausgefüllt ist.

Sie werden bemerken, dass eine Instanz der Klasse SolverOptions während des Lösungsvorgangs bestimmte Entscheidungen vornimmt. Der folgende Code zeigt die öffentliche Schnittstelle von SolverOptions.

public sealed class SolverOptions : ICloneable
{
  public SolverOptions();
  public NullableUint MaximumSolutionsToFind { get; set; }
  public TechniqueCollection EliminationTechniques { get; }
  public bool AllowBruteForce { get; set; }
  public SolverOptions Clone();
}

MaximumSolutionsToFind ermöglicht es einem Client von Solver, anzugeben, wie viele Lösungen gefunden werden sollen. Solver hält erst an, wenn diese Anzahl von Lösungen gefunden oder festgestellt wurde, dass die angegebene Zahl nicht erreicht werden kann. Beachten Sie, dass MaximumSolutionsToFind eine meiner NullableUint-Typen ist. Bei dem Wert Null findet Solver unbegrenzt viele Lösungen, sofern dies möglich ist. Gewöhnlich wird dieser Wert jedoch entweder auf 1 oder auf 2 gesetzt. Durch die Suche nach einer Lösung kann ich schnell ermitteln, ob ein Rätsel noch lösbar ist. Durch eine Suche nach zwei Lösungen kann ich feststellen, ob ein Rätsel nur eine einzige Lösung hat (wenn der Solver zwei findet, weiß ich, auch wenn mehr gefunden werden könnten, dass es mehr als eine Lösung gibt). Die Eigenschaft AllowBruteForce legt fest, ob die Brute-Force-Suche im Solver überhaupt erlaubt ist oder ob ein Rätsel allein mit der Methode FillCellsWithSolePossibleNumber ausgefüllt werden muss. FillCellsWithSolePossibleNumber verwendet die Eigenschaft EliminationTechniques, um die möglichen Zahlen für ein Feld zu berechnen. (Sowohl AllowBruteForce als auch FillCellsWithSolePossibleNumber werden in Generieren von Rätseln näher beschrieben.)

Im Abschnitt zu DfsSolve habe ich CheckSolution ausgelassen. In meiner tatsächlichen Implementierung von Sudoku wird CheckSolution durch PuzzleState.Status ersetzt, eine Eigenschaft, die den aktuellen Status des Rätsels analysiert und zurückgibt, ob es gelöst oder unlösbar ist oder sich in einem Zwischenzustand befindet.

public PuzzleStatus Status
{
  get
  {
    if (_status == PuzzleStatus.Unknown) 
      _status = AnalyzeSolutionStatus();
    return _status;
  }
}
private PuzzleStatus AnalyzeSolutionStatus()
{
  FastBitArray numbersUsed = new FastBitArray(_gridSize);

  // Make sure no column has duplicates
  for (int i = 0; i < _gridSize; i++)
  {
    numbersUsed.SetAll(false);
    for (int j = 0; j < _gridSize; j++)
    {
      if (_grid[i, j].HasValue)
      {
        int value = _grid[i, j].Value;
        if (numbersUsed[value]) 
          return PuzzleStatus.CannotBeSolved;
        numbersUsed[value] = true;
      }
    }
  }

  // Same for rows
  for (int j = 0; j < _gridSize; j++)
  {
    numbersUsed.SetAll(false);
    for (int i = 0; i < _gridSize; i++)
    {
      if (_grid[i, j].HasValue)
      {
        int value = _grid[i, j].Value;
        if (numbersUsed[value]) 
          return PuzzleStatus.CannotBeSolved;
        numbersUsed[value] = true;
      }
    }
  }

  // Same for boxes
  for (int boxNumber = 0; boxNumber < _gridSize; boxNumber++)
  {
    numbersUsed.SetAll(false);
    int boxStartX = (boxNumber / _boxSize) * _boxSize;
    for (int x = boxStartX; x < boxStartX + _boxSize; x++)
    {
      int boxStartY = (boxNumber % _boxSize) * _boxSize;
      for (int y = boxStartY; y < boxStartY + _boxSize; y++)
      {
        if (_grid[x, y].HasValue)
        {
          int value = _grid[x, y].Value;
          if (numbersUsed[value]) 
            return PuzzleStatus.CannotBeSolved;
          numbersUsed[value] = true;
        }
      }
    }
  }

  // Now figure out whether this is a solved puzzle or a work 
  // in progress based on whether there are any holes
  for (int i = 0; i < _gridSize; i++)
  {
    for (int j = 0; j < _gridSize; j++)
    {
      if (!_grid[i, j].HasValue) return PuzzleStatus.InProgress;
    }
  }

  // If I made it this far, this state is a valid solution!  
  return PuzzleStatus.Solved;
}

PuzzleState.Status analysiert die aktuelle Lösung in mehreren Schritten. Zunächst wird überprüft, ob PuzzleStatus bereits berechnet und zwischengespeichert ist. Wenn ja, kann PuzzleStatus einfach den zwischengespeicherten Wert zurückgeben (durch alle Änderungen am Rätsel wird der Cache ungültig). Wenn der PuzzleStatus des Status berechnet werden muss, verwendet Status die Methode AnalyzeSolutionStatus, um zu ermitteln, ob gegenwärtig doppelte Zahlen in einer Spalte, Reihe oder in einem Kasten angegeben sind. Bei doppelten Zahlen kann das Rätsel offensichtlich nicht gelöst werden. Anschließend wird überprüft, ob sich leere Felder im Raster befinden. Ist dies der Fall, wird das Rätsel noch bearbeitet. Andernfalls ist das Rätsel gelöst. Beachten Sie, dass AnalyzeSolutionStatus nicht angibt, ob ein in Bearbeitung befindliches Rätsel gelöst werden kann, sondern nur, ob es gegenwärtig gelöst, definitiv unlösbar oder lösbar ist. Wie Sie gesehen haben, ist es die Aufgabe des Solvers, die Lösbarkeit festzustellen.

Das war im Grunde alles zu Solver. Eine öffentliche Methode Solve dient als Wrapper für die Methode SolveInternal, und eine zusätzliche Verarbeitung erfolgt zur Verfolgung der Statistik darüber, wie das Rätsel gelöst wurde. Diese Informationen sind beim Erstellen von Rätseln hilfreich. Der Umfang des für diese letztendlich sehr hilfreiche und leistungsfähige Klasse erforderlichen Codes ist dabei recht gering.

Generieren von Rätseln

Auch wenn das Generieren von Zufallsrätseln mit nur einer gültigen Lösung das schwierigste Problem zu sein scheint, lässt sich der Code tatsächlich vergleichsweise einfach schreiben, wenn die anderen Elemente vorliegen, auf denen aufgebaut werden kann. Ich bin mir sicher, dass sich im Internet viele Algorithmen zum Generieren von Rätseln finden lassen. Ich habe meinen Algorithmus jedoch aus verschiedenen Gründen ausgewählt: er ist elegant, mit den bis jetzt implementierten Klassen und Methoden ist er einfach zu codieren, er ist schnell genug und vor allem funktioniert er. Natürlich können Sie diesen Generator vom Code zu diesem Artikel entfernen und stattdessen Ihren eigenen verwenden, wenn Sie das möchten.

Die Idee ist einfach, der Algorithmus selbst besteht aus zwei Teilen. Zunächst muss ich eine vollständige und zufallsgenerierte Sudoku-Lösung erstellen, also eine Lösung nach Zufallsprinzip, in der alle 81 Felder des Rasters so ausgefüllt sind, das jede Reihe, jedes Feld und jeder Kasten nur eine der Zahlen von 1 bis 9 enthält. Zuerst mag dies als unglaublich schwieriges Problem erscheinen, daher überrascht es Sie vielleicht zu erfahren, dass ich den gesamten erforderlichen Code für diesen Ansatz bereits implementiert habe: Solver.Solve. Wie bereits im Abschnitt über das Lösen von Rätseln und das Suchen des nächsten Feldes mit der Brute-Force-Methode beschrieben, wähle ich ein zufälliges Feld unter den Feldern mit der geringsten Anzahl möglicher Zahlen aus. Um eine zufällige, vollständige Sudoku-Lösung zu erstellen, muss ich lediglich ein leeres Raster lösen! Nehmen Sie sich einen Moment Zeit, um darüber nachzudenken, denn es handelt sich um einen großen Schritt. Beim ersten Durchgang füllt Solver nach Zufallsprinzip eines der 81 Felder mit einem Wert aus, da alle 81 Felder dieselbe Anzahl möglicher Zahlen haben. Nach dem Ausfüllen dieses Feldes haben einige Felder nun eine geringere Anzahl in Frage kommender Zahlen als andere, und der Solver wählt eines dieser Felder nach dem Zufallsprinzip aus. Auf diese Weise wird eine zufällige Lösung generiert. Mit nur einer oder zwei Zeilen Code kann ich eine zufällige, gültige Lösung generieren.

PuzzleState newPuzzle = Solver.Solve(
  new PuzzleState(), new SolverOptions()).Puzzle;

Das ist auch schon alles! Auch wenn es hierfür eine effizientere Methode gibt, benötigt dieser Code für die Ausführung auf meinem Laptop nur ein paar Millisekunden und ist damit mehr als schnell genug für meine Zwecke.

Der nächste Schritt in meinem Algorithmus besteht darin, ausgehend von der vollständigen Lösung immer mehr Zahlen aus den Feldern zu entfernen, indem ein gefülltes Feld im Raster zufällig ausgewählt und sein Wert dann gelöscht wird. Nach jedem Löschvorgang verwende ich meinen Solver erneut, um zu ermitteln, ob es nun mehr als eine Lösung gibt. Das ursprüngliche Rätsel hat offensichtlich nur eine Lösung, und nach dem Entfernen einiger Zahlen sollte es auch weiterhin nur eine Lösung geben. Doch an einem bestimmten Punkt, nachdem mehrere Felder bereits geleert wurden, erreicht das Rätsel einen Zustand, in dem mehrere verschiedene Sudoku-Lösungen möglich sind. Da dies gegen unser Ziel verstößt, ein Rätsel mit nur einer Lösung zu erstellen, muss ich diese Zustände vermeiden. Nach jedem Löschvorgang informiert mich Solver daher, ob ich jetzt einen Punkt erreicht habe, an dem der Status mehrwertig ist. An dieser Stelle kann ich einen Löschvorgang rückgängig machen, um ein gültiges Rätsel zu erhalten. Der Kern dieses Ansatzes entspricht folgendem Code, wie in der Generator-Klasse in der Datei Generator.cs implementiert:

Point [] filledCells = GetRandomCellOrdering(newPuzzle);
int filledCellCount = filledCells.Length;
for(int filledCellNum=0;
  filledCellNum < filledCellCount && 
    newPuzzle.NumberOfFilledCells > _options.MinimumFilledCells; 
  filledCellNum++)
{
  byte oldValue = newPuzzle[filledCells[filledCellNum]].Value;
  newPuzzle[filledCells[filledCellNum]] = null;
  SolverResults newResults = Solver.Solve(
    newPuzzle, solverOptions);
  if (!IsValidRemoval(newPuzzle, newResults)) 
    newPuzzle[filledCells[filledCellNum]] = oldValue;
}

Mit der GetRandomCellOrdering-Methode wird eine Liste aller 81 Felder des Rätsels in zufälliger Reihenfolge erstellt. Die Methode IsValidRemoval überprüft, ob durch den letzten Löschvorgang Regeln verletzt wurden, z. B. die primäre Vorgabe, dass das Rätsel immer nur eine Lösung haben darf. Wie Sie im Code sehen können, wird eine Schleife für alle 81 Felder in der von GetRandomCellOrdering zurückgegebenen Reihenfolge durchlaufen. Bei jedem Feld versuche ich, es zu entfernen, und wenn der resultierende Status gemäß IsValidRemoval ungültig ist, füge ich den Wert wieder ein.

Mein Generator implementiert einen so genannten Greedy-Algorithmus. Das bedeutet, dass der Algorithmus jeden gefundenen gültigen Folgezustand auswählt, auch wenn keine Auswahl letztendlich zu einem besseren Gesamtergebnis führen würde. Wie bei vielen Greedy-Algorithmen produziert auch dieser kein optimales Ergebnis, sondern eines, das ausreichend gut ist. Abgesehen davon ist eine optimale Lösung für Sudoku schwer zu definieren, und optimale Lösungen sind sicherlich nicht erforderlich. Das ist gut, denn das Erstellen von Sudoku-Rätseln gehört in eine Kategorie von Problemen, die als NP-vollständig bezeichnet werden. Einfach gesagt, bedeutet dies, dass das Generieren eines optimalen Sudoku-Rätsels sehr viel Zeit in Anspruch nehmen kann. Daher wird eine Heuristik bevorzugt, die "ausreichend gute" Lösungen hervorbringt.

Wie bereits beim Solver, habe ich hierbei ein paar Dinge ausgelassen. Zunächst bemerken Sie möglicherweise in den Konfigurationsoptionen des Rätsels und in der Klasse GeneratorOptions möglicherweise, dass der Generator Rätsel mit Achsensymmetrie erzeugen kann. Dabei wird das Feld an Position [x,y] nur ausgefüllt, wenn das Feld [10-x,10-y] ausgefüllt ist (wenn z. B. das Feld in der ersten Spalte, zweite Reihe ausgefüllt wird, wird auch das Feld in der neunten Spalte, achte Reihe ausgefüllt und umgekehrt). Dies wird durch eine geringfügige Änderung des zuvor angegebenen Codes implementiert. Bei einem symmetrischen Aufbau wird zuerst die Rückgabe der Reihenfolge von der GetRandomCellOrdering-Methode geändert, um eine Zufallsreihenfolge von Felderpaaren anstelle einzelner Felder zu erstellen, sodass die symmetrischen Paare stets nebeneinander stehen. Dadurch kann der Code dann Werte paarweise – und nicht einzeln – entfernen, wobei diese Werte als Paare wiederhergestellt werden, falls ein Löschvorgang zu einem ungültigen Rätsel geführt hat.

Der Generator unterstützt außerdem verschiedene Schwierigkeitsstufen. Schwierigkeitsstufen basieren auf mehreren Konfigurationsoptionen, wie der Mindestanzahl auszufüllender Felder und den Techniken, die ein Spieler zum Lösen des Rätsels einsetzen muss. Diese Techniken bringen uns zurück zu Solver und der Eigenschaft SolverOptions.EliminationTechniques.

Wenn Sie ein Buch über Sudoku gelesen oder online nach Informationen gesucht haben, wissen Sie, dass es eine Reihe formaler Techniken gibt, mit denen Leute Rätsel lösen. Ich habe bereits eine Technik beschrieben, die darin besteht, eine mögliche Zahl in einem Feld auszuschließen, weil es diese Zahl in einem anderen Feld derselben Reihe, Spalte oder demselben Kasten gibt. Wenn Sie den Ordner Techniques im heruntergeladenen Quellcode durchsuchen, sehen Sie, dass ich mehrere Techniken implementiert habe, z. B. naked subset, hidden subset und x-wing. Diese Techniken werden dazu verwendet, Zahlen in Feldern des Rasters festzulegen und mögliche Zahlen aus den einzelnen Feldern zu eliminieren. Je nach dem für Generator konfigurierten Schwierigkeitsgrad darf Solver nur bestimmte Techniken verwenden, da für einige Techniken größere Fähigkeiten erforderlich sind als für andere.

Die Anzahl der Rätsel, die vom Generator erstellt werden, beeinflusst den Schwierigkeitsgrad ebenfalls. Anstatt nur jeweils ein Rätsel zu generieren, erstellt der Generator für bestimmte Schwierigkeitsgrade mehrere Rätsel und wählt dann das Rätsel aus, das als schwierigstes bewertet wurde. Der Generator fällt diese Entscheidung auf Basis einer von Solver zurückgegebenen Statistik, in der angegeben ist, welche Techniken zum Lösen des Rätsels verwendet wurden und wie oft sie jeweils eingesetzt wurden.

Wie Sie dem Quellcode entnehmen können, gibt es in der aktuellen Implementierung drei Schwierigkeitsstufen.

Bei der Schwierigkeitsstufe Einfach werden drei Rätsel generiert, mindestens 32 Felder müssen ausgefüllt bleiben, und nur eine Technik ist zum Lösen des gesamten Rätsels erforderlich.
Auf der Stufe Mittel werden 10 Rätsel generiert, es gibt keine Mindestanzahl ausgefüllter Felder, und es können mehrere Techniken erforderlich sein.
Für die hohe Schwierigkeitsstufe Difficult werden 20 Rätsel generiert, es gibt keine Mindestanzahl ausgefüllter Felder, und es können alle implementierten Techniken erforderlich sein. Bei diesem Schwierigkeitsgrad wird die Option AllowBruteForce für den Solver aktiviert. Das heißt, dass möglicherweise ein Rätsel erstellt wird, das nicht allein mit den vorhandenen Techniken gelöst werden kann, und für das sogar systematisches Probieren in Form von "Trial-and-Error"-Verfahren erforderlich sein kann. Wenn Sie diesen Ansatz nicht für gut befinden (wie einige Sudoku-Fans), können Sie den Code gerne ändern.

Windows Forms und Hardwareinteraktionen

In den folgenden Abschnitten werden die Aspekte des Sudoku-Spiels behandelt, die im Zusammenhang mit Tablet PC-Features und der Benutzeroberfläche stehen.

Entwerfen von Sudoku

Ein wichtiger Aspekt jeder Anwendung für Tablet PCs besteht im Rendern der Anwendung. Wie wird die Anwendung auf verschiedenen Bildschirmgrößen von Tablet PCs dargestellt? Wird die Anwendung mit verschiedenen Bildschirmausrichtungen richtig dargestellt? Kann die Anwendung mit hohen Auflösungen und großen Zeichensätzen korrekt umgehen? Diese Aspekte sind für eine erfolgreiche Anwendung von Bedeutung. Die Behandlung dieser Aspekte erfordert jedoch zunächst eine Betrachtung des Aufbaus der Anwendung.

Sudoku wurde als Windows Forms-Anwendung implementiert. Die gesamte Anwendung wird (mit Ausnahme des OptionsDialog, mit dem der Benutzer das Spiel konfiguriert) in einem Formular dargestellt: dem MainForm, das in der Datei MainForm.cs vorliegt. Das einzige Steuerelement der Controls-Auflistung von MainForm besteht aus einem angedockten, das Formular ausfüllenden ImagePanel. Es dient als Hintergrund für die gesamte Anwendung und als Container für untergeordnete Formularsteuerelemente. ImagePanel ist ein einfaches Steuerelement, der einzige Einsatzzweck besteht aus dem Zeichnen eines Bildes zum Ausfüllen des Steuerelements.

internal class ImagePanel : NoFlickerPanel
{
  public ImagePanel(){}

  [DesignerSerializationVisibility(
     DesignerSerializationVisibility.Hidden)]
  [Browsable(false)]
  public Image Image { get { return _img; } set { _img = value; } }
  private Image _img;

  protected override void OnPaint(PaintEventArgs e)
  {
    if (_img != null) 
    {
      e.Graphics.DrawImage(_img, 0, 0, Width, Height);
    }
    base.OnPaint(e);
  }
}

ImagePanel wurde vom NoFlickerPanel-Steuerelement abgeleitet, nicht direkt von System.Windows.Forms.Panel.

internal class NoFlickerPanel : Panel
{
  public NoFlickerPanel()
  {
    SetStyle(ControlStyles.DoubleBuffer | 
      ControlStyles.AllPaintingInWmPaint | 
      ControlStyles.UserPaint | ControlStyles.ResizeRedraw | 
      ControlStyles.SupportsTransparentBackColor, true);
  }
}

NoFlickerPanel dient als Basisklasse für viele spezialisierte Klassen, die von Panel abgeleitet wurden. Der einzige wirkliche Zweck besteht im Aktivieren der doppelten Pufferung, neben dem automatischen neuen Zeichnen nach einer Größenänderung des Steuerelements. Die doppelte Pufferung ist für die Darstellung der Anwendung von großer Bedeutung, da ein Flimmern beim neuen Zeichnen von Panel dadurch vermieden wird (daher der Name). Wenn Sie ein automatisches neues Zeichnen nach einer Größenänderung des Formulars aktivieren, ist die Unterstützung für das neue Zeichnen des Formulars problemlos möglich, wenn der Benutzer die Größe oder die Bildschirmausrichtung des Tablet PCs verändert.

Das Hintergrundpanel enthält vier weitere Panels:

Ein NoFlickerPanel, das als Container für das Rastersteuerelement dient (das Steuerelement, das letztendlich das Puzzle darstellt und Benutzerinteraktionen ermöglicht).
Zwei ImagePanels, die Steuerelemente für die "Bildschirme" zum Starten eines neuen Spiels oder zum Fortsetzen eines vorherigen Spiels beinhalten.
Ein ScalingPanel, abgeleitet von NoFlickerPanel, das das vollständige Layout der Steuerelemente kontrolliert, die zum Interagieren mit dem Spiel dienen (beispielsweise die Schaltflächen für Stift und Zahlen oder zum Beenden).

Ich habe mir bei dieser Sudoku-Implementierung zum Ziel gesetzt, einen ausgesprochen flüssigen Spielablauf zu realisieren. Die Benutzer sollen sagen: "Toll! Das sieht gut aus." Zur Unterstützung dieser Zielsetzung muss sichergestellt werden, dass die im Formular enthaltenen Steuerelemente nach einer Größenänderung des Hauptformulars unter Beibehaltung ihrer relativen Größe und Positionierung verschoben und in der Größe angepasst werden. Das ScalingPanel macht dies möglich.

internal class ScalingPanel : NoFlickerPanel
{
  public ScalingPanel(){}

  private Rectangle _initialBounds;
  private Hashtable _controlBounds;
  private bool _initialized;

  public void ConfigureByContainedControls()
  {
    _initialBounds = Bounds;
    _controlBounds = new Hashtable();
    foreach(Control c in this.Controls)
    {
      _controlBounds.Add(c, c.Bounds);
    }
    _initialized = true;
  }

  protected override void OnLayout(LayoutEventArgs levent)
  {
    if (_initialized && Width > 0 && Height > 0 && 
      levent.AffectedControl == this)
    {
      // Maintain original aspect ratio
      int newWidth = Width;
      int tmp = (int)(_initialBounds.Width / 
        (double)_initialBounds.Height * Height);
      if (tmp < newWidth) newWidth = tmp;

      int newHeight = Height;
      tmp = (int)(_initialBounds.Height / 
        (double)_initialBounds.Width * newWidth);
      if (tmp < newHeight) newHeight = tmp;

      // Keep track of max and min boundaries
      int minX=int.MaxValue, minY=int.MaxValue, maxX=-1, maxY=-1;

      // Move and resize all controls
      foreach(Control c in this.Controls)
      {
        Rectangle rect = (Rectangle)_controlBounds[c];

        // determine initial best guess at size
        int x = (int)(rect.X / (double)
          _initialBounds.Width * newWidth);
        int y = (int)(rect.Y / (double)
          _initialBounds.Height * newHeight);
        int width = (int)(rect.Width / (double)
          _initialBounds.Width * newWidth);
        int height = (int)(rect.Height / (double)
          _initialBounds.Height * newHeight);

        // set the new bounds
        Rectangle newBounds = new Rectangle(
          x, y, width, height);
        if (newBounds != c.Bounds) c.Bounds = newBounds;

        // Keep track of max and min boundaries
        if (c.Left < minX) minX = c.Left;
        if (c.Top < minY) minY = c.Top;
        if (c.Right > maxX) maxX = c.Right;
        if (c.Bottom > maxY) maxY = c.Bottom;
      }

      // Center all controls
      int moveX = (Width - (maxX - minX + 1)) / 2;
      int moveY = (Height - (maxY - minY + 1)) / 2;

      if (moveX > 0 || moveY > 0)
      {
        foreach(Control c in this.Controls) 
        {
          c.Location = c.Location + 
            new Size(moveX - minX, moveY - minY);
        }
      }
    }

    // Do base layout
    base.OnLayout (levent);
  }
}

ScalingPanel arbeitet unter der Voraussetzung, dass die ursprünglichen, im Formular-Designer von Visual Studio erstellten, relativen Größen und Positionen der Steuerelemente die relativen Größen und Positionen darstellen, die im gesamten Lebenszyklus der Anwendung beibehalten werden sollen. Nachdem alle untergeordneten Steuerelemente einer Instanz von ScalingPanel hinzugefügt wurden, ruft der Client die ConfigureByContainedControls-Methode des Steuerelements ScalingPanel auf. Diese Methode initialisiert einige Statusinformationen, die später beim Darstellen des Formulars verwendet werden. Zunächst werden die aktuellen Begrenzungen des Steuerelements gespeichert. Anschließend werden für alle untergeordneten Steuerelemente die jeweils aktuellen Begrenzungen in einer System.Collections.Hashtable gespeichert, die nach Control indiziert wird. Mit den Informationen über die Größe von ScalingPanel und die ursprüngliche Größe und Position jedes einzelnen Steuerelements kann ScalingPanel das Verhältnis der Größe der einzelnen Steuerelemente zur Größe des Containerpanels ermitteln, ebenso den relativen Abstand zwischen den Steuerelementen. Bei einer Größenänderung des Panels verwendet ScalingPanel diese Informationen zum Ändern der jeweiligen Position und Größe jedes enthaltenen Steuerelements unter Beibehaltung der ursprünglichen Verhältnisse.

Das ganze Geheimnis liegt in der überschriebenen OnLayout-Methode. Zunächst überprüft ScalingPanel, ob ConfigureByContainedControls bereits aufgerufen wurde, damit benutzerdefinierte Layoutvorgänge durch einen fehlenden Aufruf vermieden werden. Gleichzeitig wird überprüft, ob die Panelgröße größer Null ist, damit kein Layout durchgeführt wird, wenn das Formular minimiert ist oder vergleichbare Vorgänge durchgeführt wurden, die zu einer wesentlichen Verkleinerung des Steuerelements geführt haben. Schließlich stellt ScalingPanel sicher, dass das Zielsteuerelement des Layoutvorgangs das Panel selbst ist. Dadurch werden unnötige, redundante Layoutvorgänge vermieden, wenn mehrere, in Beziehung zum Panel stehende Steuerelemente zur Durchführung des Layouts notwendig sind.

Der Layoutvorgang besteht aus drei wesentlichen Schritten.

Er stellt sicher, dass die Seitenverhältnisse der jeweiligen Begrenzungen aller Steuerelemente konstant bleiben. Die Methode berechnet die neue Breite und Höhe der jeweiligen Begrenzung, basierend auf der aktuellen Breite und Höhe des Panels in Relation zur urprünglichen Breite und Höhe.
Nacheinander wird für jedes Steuerelement Position und Größe basierend auf dem Verhältnis des ursprünglichen zum neuen Begrenzungsrahmen ermittelt.
Der Rahmen für die Steuerelemente wird innerhalb des Panels zentriert. Auf diese Weise wird bei einer erheblichen Abweichung des aktuellen vom ursprünglichen Seitenverhältnisses sichergestellt, dass die Steuerelemente weiterhin zentriert im Panel dargestellt werden.

Diese Funktionalität von ScalingPanel bietet mehr, als nur ein ansehnliches Formular darzustellen, wenn der Benutzer die Formulargröße verändert hat. Da alle Berechnungen auf Grundlage von relativen Größen und Positionen durchgeführt werden, werden auch hochauflösende Darstellungen unterstützt (die oft von Tablet PCs verwendet werden). Die fehlende Unterstützung hoher Auflösungen ist ein verbreiteter Fehler in vielen Anwendungen, da zahlreiche Entwickler und Tester sich beim Arbeiten mit Anwendungen, die ursprünglich nicht für einen Tablet PC konzipiert waren, nicht bewusst sind, dass die DPI-Einstellungen in Windows geändert werden können.. Ein Implementieren von Steuerelementen wie ScalingPanel kann Entwicklung und Tests wesentlich vereinfachen.

Diese Funktionalitäten von ScalingPanel greifen natürlich nur bei einer Größenänderung des Panels selbst und bei einer Neuberechnung in Bezug auf die aktuelle Größe des Formulars. Wie bereits erwähnt, verfügt das Sudoku-Hauptformular über vier untergeordnete Panelsteuerelemente, von denen jedoch nur zwei an das Panel angedockt sind. Das Steuerelementepanel ist an den rechten Rand des Formulars angedockt, das Panel mit dem Rastersteuerelement ist so angedockt, das es den übrigen Formularbereich ausfüllt. Dadurch wird das Beibehalten der relativen Größen beider Panels – nach einer Größenänderung des Hauptformulars – unglaublich einfach. So wird sichergestellt, dass das Steuerelementepanel immer ein Drittel des Hauptformulars beansprucht, das Rastersteuerelement immer den verbleibenden Bereich.

protected override void OnLayout(LayoutEventArgs levent)
{
  pnlControls.Width = Width / 3;
  base.OnLayout(levent);
}

Betrachten Sie den Screenshot in Abbildung 5, um die Auswirkungen auf das Spielfeld zu beurteilen. Ein Verringern der Breite des Hauptformulars führt zum Layout in Abbildung 6, ein Verbreitern des Formulars zum Layout in Abbildung 7.

Abbildung 5: Standardlayout

Abbildung 6: Layout nach Verringern der Breite

Abbildung 7: Layout nach Vergrößern der Breite

Durch diesen Ansatz wird weiterhin die Anpassung an die Rechts- oder Linkshändigkeit eines Spielers sehr einfach. Die SetHandedness-Methode wird beim Starten der Anwendung und nach jedem Ändern der Windows-Händigkeitseinstellung durch den Benutzer aufgerufen.

private void SetHandedness()
{
  DockStyle targetStyle = PlatformDetection.UserIsRightHanded ? 
    DockStyle.Right : DockStyle.Left;
  if (targetStyle != pnlControls.Dock)
  {
    pnlControls.SendToBack();
    pnlControls.Dock = targetStyle;
  }
}

Es handelt sich um eine sehr einfache und gleichzeitig sehr leistungsfähige Methode. Mit wenigen Zeilen Code werden die aktuellen Händigkeitseinstellungen des Benutzers überprüft und dementsprechend das Andocken des Steuerelementepanels an den rechten oder linken Rand des Hauptformulars durchgeführt. Das war's! Die bereits beschriebene Layoutunterstützung macht den Rest, und das Spiel reagiert sofort auf Änderungen in den Benutzereinstellungen (der tatsächliche Aufruf dieser Methode wird in Energieverbrauch beschrieben).

In den Abbildungen 8 und 9 werden die Änderungen des Formulars nach einem Bearbeiten der Händigkeitseinstellung dargestellt.

Abbildung 8: Layout für Rechtshänder

Abbildung 9: Layout für Linkshänder

Wir haben die Größenanpassung der Steuerelemente innerhalb des Steuerelementepanels und die die verhältnismäßige Größenanpassung der beiden Hauptpanels behandelt. Der Rest der automatischen Layoutunterstützung wird von der in MainForm überschriebenen OnResize-Methode durchgeführt.

protected override void OnResize(EventArgs e)
{
  // Do the base resizing
  base.OnResize(e);

  // Put the new puzzle and saved puzzle panels in the middle
  pnlNewPuzzle.Location = new Point(
    backgroundPanel.Location.X + 
      (backgroundPanel.Width - pnlNewPuzzle.Width) / 2, 
    backgroundPanel.Location.Y + 
      (backgroundPanel.Height - pnlNewPuzzle.Height) / 2);
  pnlSavedOrNewPuzzle.Location = new Point(
    backgroundPanel.Location.X + 
      (backgroundPanel.Width - pnlSavedOrNewPuzzle.Width) / 2, 
    backgroundPanel.Location.Y + 
      (backgroundPanel.Height - pnlSavedOrNewPuzzle.Height) / 2);

  // Make sure when I resize the form that the puzzle grid
  // stays in the center and square, as big as it can be while
  // not exceeding its parent's bounds
  int width = pnlGrid.Width;
  int height = pnlGrid.Height;
  int margin = 25;
  Size gridSize = width > height ? 
    new Size(height - margin, height - margin) : 
    new Size(width - margin, width - margin);
  thePuzzleGrid.Bounds = new Rectangle(
    new Point((width - gridSize.Width)/2, 
    (height - gridSize.Height)/2),
    gridSize);

  // Make sure no matter how the form resizes that the
  // marquee progress bar ends up in the center of the form.
  marqueeBar.Location = new Point(
    backgroundPanel.Location.X + 
      (backgroundPanel.Width - marqueeBar.Width) / 2, 
    backgroundPanel.Location.Y + 
      (backgroundPanel.Height - marqueeBar.Height) / 2);
}

Diese Methode führt einige einfache Layoutvorgänge durch. Zunächst werden die Panels pnlNewPuzzle und pnlSavedOrNewPuzzle im Formular zentriert (diese Panels sind meistens ausgeblendet, lediglich beim Starten der Anwendung oder beim Starten eines neuen Spiels durch den Benutzer werden sie angezeigt). Gleichzeitig wird die Größe des Grid-Steuerelements für das Puzzle berechnet und entsprechend im Rasterpanel dargestellt (dies könnte möglicherweise ebenso einfach durch den Einsatz des Rasterpanels als ScalingPanel erreicht werden). Schließlich wird die zentrierte Darstellung der Statusanzeige für den Fortschritt der Puzzleerstellung im Formular sichergestellt.

Die Statusanzeige war eine interessante Herausforderung. Windows Forms 1.1 enthält eine Statusanzeige, die jedoch im Auslieferungszustand keine Unterstützung für den Marquee-Stil bietet. Unter Microsoft Windows XP ist dies allerdings möglich. (Der Marquee-Stil wird zur Darstellung eines Tasks ohne festgelegte Start- und Endpunkte verwendet. Die beim Starten von Windows angezeigte Statusanzeige ist eine Marquee-Statusanzeige.) Das Windows Forms-Steuerelement ProgressBar dient als Wrapper für die Statusanzeige der allgemeinen Steuerelemente in Windows XP, die Marquee-Einstellung wird jedoch nicht offengelegt (in Windows Forms 2.0 möglich). Daher wurde, statt die ProgressBar von Windows Forms zu verwenden, ein eigener Wrapper zum Verwenden des Marquee-Stils erstellt, wie in Abbildung 10 dargestellt (nach einem Aktualisieren auf Windows Vista wird dies sogar wesentlich ansprechender, wie Sie in Abbildung 11 sehen können).

internal sealed class MarqueeProgressBar : Control
{
  public MarqueeProgressBar()
  {
    SetStyle(ControlStyles.SupportsTransparentBackColor, true);
    SetStyle(ControlStyles.Selectable | 
      ControlStyles.UserPaint, false);
    BackColor = Color.Transparent;
    ForeColor = SystemColors.Highlight;
  }

  protected override CreateParams CreateParams
  {
    get
    {
      CreateParams cp = base.CreateParams;
      cp.ClassName = "msctls_progress32"; 
      if (!DesignMode) cp.Style |= PBS_MARQUEE;
      if (RightToLeft == RightToLeft.Yes)
      {
        cp.ExStyle |= WS_EX_LAYOUTRTL;
        cp.ExStyle &= ~(WS_EX_RIGHT | WS_EX_RTLREADING | 
                        WS_EX_LEFTSCROLLBAR);
      }
      return cp;
    }
  }

  protected override void OnForeColorChanged(EventArgs e)
  {
    base.OnForeColorChanged(e);
    if (base.IsHandleCreated)
    {
      SendMessage(PBM_SETBARCOLOR, 0, 
        ColorTranslator.ToWin32(this.ForeColor));
    }
  }

  protected override void OnBackColorChanged(EventArgs e)
  {
    base.OnBackColorChanged(e);
    if (base.IsHandleCreated)
    {
      SendMessage(PBM_SETBKCOLOR, 0, 
        ColorTranslator.ToWin32(this.BackColor));
    }
  }

  protected override ImeMode DefaultImeMode 
  { 
    get { return ImeMode.Disable; } 
  }

  protected override Size DefaultSize 
  { 
    get { return new Size(100, 23); } 
  }

  protected override void CreateHandle()
  {
    if (!RecreatingHandle)
    {
      NativeMethods.INITCOMMONCONTROLSEX icc = 
        new NativeMethods.INITCOMMONCONTROLSEX();
      icc.dwSize = 0;
      icc.dwICC = ICC_PROGRESS_CLASS;
      NativeMethods.InitCommonControlsEx(icc);
    }
    base.CreateHandle();
  }

  private IntPtr SendMessage(int msg, int wparam, int lparam)
  {
    return NativeMethods.SendMessage(new HandleRef(this, 
      this.Handle), msg, new IntPtr(wparam), new IntPtr(lparam));
  }

  protected override void OnHandleCreated(EventArgs e)
  {
    base.OnHandleCreated(e);
    SendMessage(PBM_SETRANGE, MINIMUM, MAXIMUM);
    SendMessage(PBM_SETSTEP, STEP, 0);
    SendMessage(PBM_SETPOS, VALUE, 0);
    SendMessage(PBM_SETBKCOLOR, 0, 
      ColorTranslator.ToWin32(BackColor));
    SendMessage(PBM_SETBARCOLOR, 0, 
      ColorTranslator.ToWin32(ForeColor));
    Start(DEFAULTSPEED);
  }

  private void Start(int speed)
  {
    if (!DesignMode && IsHandleCreated) 
      SendMessage(PBM_SETMARQUEE, speed == 0 ? 0 : 1, speed);
  }

  ... // constant definitions 

}

Abbildung 10: Marquee-Statusanzeige in Windows XP

Abbildung 11: Marquee-Statusanzeige in Windows Vista

Zeichnen von Sudoku

Das PuzzleGrid-Steuerelement in der PuzzleGrid.cs-Datei im Ordner Controls ist das wichtigste Steuerelement der Anwendung. Mit diesem Steuerelement wird das Sudoku-Rätsel angezeigt. Weiterhin werden die Hauptfunktionen der Maus und Tastatur zum Spielen von Sudoku bereitgestellt und die Stiftinteraktionen mit dem Spiel ermöglicht.

Gemäß der üblichen Vorgehensweise werden alle Steuerelementdarstellungen als Reaktion auf eine WM_PAINT-Nachricht ausgeführt. In Windows Forms bedeutet dies in der Regel, dass Sie entweder dem Paint-Ereignis des Steuerelements einen Ereignishandler hinzufügen oder die OnPaint-Methode überschreiben müssen. Ich habe mich für Letzteres entschieden.

protected override void OnPaint(PaintEventArgs e)
{
  base.OnPaint(e);
  e.Graphics.PixelOffsetMode = PixelOffsetMode.HighQuality;
  DrawToGraphics(e.Graphics, e.ClipRectangle);
}

Die Darstellungslogik wird in einer getrennten DrawToGraphics-Methode berücksichtigt, die das Graphics-Zielobjekt und das Rechteck akzeptiert, in dem die ungültig gewordenen Begrenzungen innerhalb des Steuerelements definiert sind. (Die Leistung einer Anwendung wird erheblich verbessert, wenn nur Elemente neu dargestellt werden, für die dies tatsächlich nötig ist. Nachdem ich diese Funktion in die ursprüngliche Implementierung integriert hatte, war die Leistungsverbesserung sofort bemerkbar.) Wenn Sie den Darstellungscode auf diese Weise anpassen, wird die Druckunterstützung sowie die Darstellung des Steuerelements als Bitmap-Objekt stark vereinfacht. Ich veranschauliche dies mit einer Lösungsanimation, in der diese Funktion verwendet wird, um dem Spieler nach dem Lösen eines Rätsels eine Glückwunschanimation anzuzeigen.

Trotz seiner Länge ist der Code zum Darstellen der Spielfläche sehr einfach. Zunächst werden die Hintergrundbilder dargestellt, die im Ordner Images des Codedownloads gespeichert sind.

graphics.DrawImage(ResourceHelper.BoardBackgroundImage, 
  0, 0, Width, Height);
graphics.DrawImage(ResourceHelper.BoardImage, rect);

Das erste Bild wird angezeigt, um das Steuerelement auszufüllen. Das zweite Bild wird auf der Grundlage des Rechtecks dargestellt, das von der privaten BoardRectangle-Eigenschaft zurückgegeben wird. Diese Eigenschaft gibt ein Rechteck zurück, das ein wenig kleiner als das Steuerelement ist, sodass an allen Seiten dünne Rändern vorhanden sind. Danach werden die Größen und Positionen der einzelnen Felder mit einer privaten GetCellRectangle-Methode festgelegt, die die bekannte Größe der einzelnen Feldbilder im Hintergrundbild relativ zur Größe des ganzen Bilds berücksichtigt. Weiterhin werden die Größen und Positionen der Lücken im Hintergrundbild relativ zur Größe des ganzen Bildes berücksichtigt. Mit der von GetCellRectangle zurückgegebenen Größe wird ermittelt, ob ein bestimmtes Feld weiter überprüft oder überhaupt dargestellt werden muss.

for (int i = 0; i < State.GridSize; i++)
{
  for (int j = 0; j < State.GridSize; j++)
  {
    RectangleF cellRect = GetCellRectangle(rect, new Point(i,j));
    if (clipRectangle.IntersectsWith(Rectangle.Ceiling(cellRect)))
    {
      ... // cell drawn here
    }
  }
}

Mit den clipRectangle-Informationen, die von OnPaint an DrawToGraphics übergeben werden, wird auf ähnliche Weise die Darstellung von Feldern verhindert, die nicht ungültig geworden sind. Da das Darstellen ein relativ aufwändiger Vorgang ist, und nur kleine Bereiche des Steuerelements regelmäßig ungültig werden (z. B. beim Eingeben einer Zahl in ein Feld oder beim Ändern eines ausgewählten Felds), wird die Brauchbarkeit des Steuerelements erheblich verbessert.

Wenn ein Feld dargestellt werden soll, finden einige Vorgänge statt. Unter der Annahme, dass das Rätsel noch nicht gelöst wurde, wird das Feld zunächst überprüft, um zu bestimmen, ob es derzeit ausgewählt ist. Wenn das Feld ausgewählt ist, wird das Feld mit einem der fünf grünen Bilder im Ordner Images ausgefüllt. Diese fünf Bilder entsprechen der Eigenschaft des Felds, eine der vier Ecken zu sein oder nicht.

Image selectedCellImage;
if (i == 0 && j == 0) 
  selectedCellImage = ResourceHelper.CellActiveUpperLeft;
else if (i == 0 && j == State.GridSize-1) 
  selectedCellImage = ResourceHelper.CellActiveUpperRight;
else if (i == State.GridSize-1 && j == 0) 
  selectedCellImage = ResourceHelper.CellActiveLowerLeft;
else if (i == State.GridSize-1 && j == State.GridSize-1) 
  selectedCellImage = ResourceHelper.CellActiveLowerRight;
else 
  selectedCellImage = ResourceHelper.CellActiveSquare;
graphics.DrawImage(selectedCellImage, 
cellRect.X, cellRect.Y, cellRect.Width, cellRect.Height);

Mit einer ähnlichen Logik wird das Bild suggested cell auf einem Feld dargestellt, wenn der Benutzer sich für einen Hinweis auf das als nächstes auszufüllende Feld entschieden hat, und das derzeit darzustellende Feld das vorgeschlagene ist. Das vorgeschlagene Feld wird mit den gleichen Techniken ermittelt, die von Solver und Generator zum Ermitteln des Schwierigkeitsgrads und der Lösbarkeit des Rätsels verwendet werden. Mit der privaten SuggestedCell-Eigenschaft wird das vorgeschlagene Feld auf der Grundlage dieser Techniken berechnet. Das Ergebnis wird zwischengespeichert, damit es nicht jedes Mal neu berechnet werden muss, wenn das Raster dargestellt wird. (Die Zwischenspeicherung wird ungültig, wenn der Spielstatus geändert wird.) SuggestedCell wird wie folgt implementiert.

TechniqueCollection tc = new TechniqueCollection();
FastBitArray [][] possibleNumbers = 
  PuzzleState.InstantiatePossibleNumbersArray(State);
foreach(EliminationTechnique et in 
  EliminationTechnique.AvailableTechniques)
{
  tc.Add(et);
  Hashtable ignored = null;
  State.ComputePossibleNumbers(tc, ref ignored, true, 
    true, possibleNumbers);
  for(int row=0; row<State.GridSize; row++)
  {
    for(int column=0; column<State.GridSize; column++)
    {
      if (possibleNumbers[row][column].CountSet == 1)
      {
        return _suggestedCell = new Point(row, column);
      }
    }
  }
}

Die Logik ruft alle verfügbaren Techniken ab, geordnet nach Schwierigkeit (grob festgelegt nach meiner Einschätzung der Schwierigkeit einer Technik). Beginnend mit der einfachsten Technik wird ermittelt, ob nach dem Ausführen dieser Technik leere Felder im Raster vorhanden sind, für die nur eine geeignete Zahl eingefügt werden kann. Wenn solche Felder vorhanden sind, wird das zuerst gefundene als vorgeschlagenes Feld zurückgegeben. Wenn keine Felder gefunden werden, wird die nächste Technik verwendet, und die geeigneten Zahlen werden neu berechnet. Wenn Felder gefunden werden, für die nur eine Zahl geeignet ist, wird wieder das zuerst gefundene Feld zurückgegeben. Dies wird fortgesetzt, bis ein vorgeschlagenes Feld gefunden oder alle Techniken verwendet wurden, ohne ein vorgeschlagenes Feld zu finden. (Letzteres kann nur bei schwerem Schwierigkeitsgrad auftreten, da auf diesem Schwierigkeitsgrad bei der Rätselerstellung die Brute-Force-Technik verwendet werden kann.) In diesem Fall wird das Feld mit den wenigsten verbleibenden, geeigneten Zahlen als vorgeschlagenes Feld zurückgegeben.

Wenn der Hintergrund eines Felds gezeichnet wurde, und bereits eine Zahl eingegeben war, wird diese gerendert.

if (State[i, j].HasValue)
{
  Brush b;
  if (ShowIncorrectNumbers &&
    State[i, j].HasValue && _solvedOriginalState != null && 
    State[i, j].Value != _solvedOriginalState[i, j].Value)
  {
    b = _incorrectValueBrush;
  }
  else if (_originalState != null && _originalState[i,j].HasValue)
  {
    b = _originalValueBrush;
  } 
  else b = _userValueBrush;

  graphics.DrawString((State[i, j] + 1).ToString(
    CultureInfo.InvariantCulture), setNumberFont, b,
    cellRect, _centerNumberFormat);
}

Der für DrawString zu verwendende Pinsel wird aus drei zwischengespeicherten Pinseln ausgewählt:

Ein roter Pinsel zeigt falsche Werte an.
Ein schwarzer Pinsel zeigt Werte an, die Teil des ursprünglichen Rätsels waren.
Ein blauer Pinsel zeigt eingegebene Werte an.

Die Pinsel werden zwischengespeichert, sodass sie nicht jedes Mal neu erstellt werden müssen, wenn das Rätsel dargestellt wird. Dies ist eine weitere Leistungsoptimierung. Der Pinsel, mit dem falsche Werte angezeigt werden, wird ausgewählt, wenn:

Der Benutzer sich entschieden hat, auf Fehler während des Spielens hingewiesen zu werden, und
Der Wert eines Felds nicht dem Wert im gelösten Rätsel entspricht, der bei der ersten Speicherung eines neuen Rätsels durch das Raster festgelegt wird.

public void SetOriginalPuzzleCheckpoint(PuzzleState original)
{
  _originalState = original;
  if (original != null)
  {
    SolverOptions options = new SolverOptions();
    options.MaximumSolutionsToFind = 2;
    SolverResults results = Solver.Solve(original, options);
    if (results.Status == PuzzleStatus.Solved && 
      results.Puzzles.Count == 1)
    {
      _solvedOriginalState = results.Puzzle; 
    }
    else _solvedOriginalState = null;
  }
}

Abschließend werden von DrawToGraphics Freihandeingaben gerendert, die auf dem Raster angezeigt werden sollen, indem ein Aufruf an die private RenderInk-Method ausgelöst wird. Dies führt uns zum Glanzstück dieser Sudoku-Implementierung: Unterstützung des Tablettstifts.

Ermöglichen der Tablet PC-Interaktion

Stiftinteraktionen müssen in jedem Spiel für Tablet PCs unterstützt werden. In einer Anwendung sollte zumindest die Verwendung des Stifts als Navigationsgerät möglich sein. Im Idealfall wird in der Anwendung Handschrifterkennung zur Dateneingabe unterstützt. Inwieweit diese Unterstützung tatsächlich stattfindet, ist jedoch unterschiedlich. Der Arbeitsaufwand zum Ermöglichen von Stiftinteraktionen variiert daher ebenfalls. Sie können in Anwendungen auch die Stiftbewegungserkennung verwenden, mit der bestimmte Stiftbewegungen als Aktionen anstatt als zu erkennende Freihandeingaben interpretiert werden. Hinsichtlich Anwendungen für Tablet PCs mit Touchscreen, z. B. Ultra-Mobile PCs, sollte während der Entwurfs- und Entwicklungsphase Unterstützung für Berührungseingaben in Betracht gezogen werden. In meiner Sudoku-Implementierung werden diese Grundsätze alle berücksichtigt.

Bei einem Sudoku-Spiel für Tablet PCs ist die Möglichkeit, Zahlen in die Felder schreiben zu können, eine der Hauptanforderungen. Das Spiel erhält hierdurch den typischen Stift-und-Papier-Charakter. Ob die handschriftlichen Zahlen nach der Eingabe in einen gerenderten Schriftsatz konvertiert oder als Freihandeingabe belassen werden, ist von der Implementierung abhängig. Ungeachtet dessen ist es wichtig, dass die Eingaben von der Anwendung erkannt werden. Ich habe mich für eine individuelle Erkennung der einzelnen Eingaben entschieden. Alle handschriftlichen Zahlen werden in Maschinenschrift gerendert und nicht als Handschrift dargestellt.

Alle Stiftinteraktionen werden vom PuzzleGrid-Steuerelement behandelt. PuzzleGrid verfügt über zwei private Member von Typen, die aus der Microsoft.Ink.dll-Assembly stammen.

private InkOverlay _inkOverlay;
private RecognizerContext _recognizerCtx;

Die InkOverlay-Klasse dient als Grundlage für die Verarbeitung aller Stiftinteraktionen. InkOverlay wird an alle vorhandenen Control-Objekte angehängt, sodass mit diesen Steuerelementen Stiftinteraktionen möglich sind. Die RecognizerContext-Klasse ist die Grundlage für die Handschrifterkennung, die zum Erkennnen der vom Benutzer eingegebenen Zahlen verwendet wird.

Die EnableTabletSupport-Methode des PuzzleGrid-Steuerelements initialisiert die beiden Klassen InkOverlay und RecognizerContext. Zunächst wird die zu verwendende Standarderkennung mithilfe der bereits erläuterten Logik aus der PlatformDetection-Klasse abgerufen. Das zurückgegebene Recognizer-Objekt wird dann zur Konfiguration von RecognizerContext verwendet.

Recognizer defaultRecognizer =
  PlatformDetection.GetDefaultRecognizer();
_recognizerCtx = defaultRecognizer.CreateRecognizerContext();
_recognizerCtx.Factoid = Factoid.Digit;

Die RecognizerContext-Klasse stellt eine Factoid-Eigenschaft zur Verfügung, mit der Informationen über die Art der zu erkennenden Eingabe an RecognizerContext übergeben werden können. Durch eine sinnvolle Begrenzung der Erkennung mit Factoid-Eigenschaften wird die Interaktion des Benutzers mit der Anwendung wesentlich verbessert. Die Erkennung wird auf festgelegte Eingabetypen beschränkt. Bei Sudoku wird von der Erkennung nur erwartet, dass die Zahlen 1 bis 9 als Eingabe erkannt werden. Die Erkennung wird auf diese Eingaben beschränkt, indem ihre Factoid-Eigenschaft auf Factoid.Digit festgelegt wird. Mit Factoid.Digit wird die Beschränkung der Erkennung auf eine einzige Ziffer festgelegt, sodass nur einstellige Werte erwartet und in der Regel nur einstellige Werte zurückgegeben werden. (Bedenken Sie, dass nur wenige Factoid-Eigenschaften für Erkennungen in allen Sprachen zuverlässig funktionieren. Glücklicherweise gehört Digit dazu.)

Nach der Konfiguration von RecognizerContext wird InkOverlay initialisiert.

_inkOverlay = new InkOverlay(this, true);
_inkOverlay.Ink.CustomStrokes.Add(ScratchpadStrokesID, 
  _inkOverlay.Ink.CreateStrokes());
_inkOverlay.Ink.CustomStrokes.Add(NormalStrokesID, 
  _inkOverlay.Ink.CreateStrokes());
_inkOverlay.DefaultDrawingAttributes.Color = _inkColor;

InkOverlay wird instanziiert und an PuzzleGrid gebunden (mit dem this-Verweis, da dieser Code in der PuzzleGrid-Klasse vorhanden ist). Ich füge zwei CustomStrokes-Auflistungen zu InkOverlay hinzu. Diese Auflistungen erläutere ich weiter unten im Artikel. Sie machen es jedoch einfacher, die verschiedenen Arten von Freihandeingaben des Benutzers zu trennen, und sie ermöglichen das einfache Beibehalten dieser Eingaben für gespeicherte Spiele. Anschließend werden die Farbe und die CollectionMode-Eigenschaft des Overlays konfiguriert.

Die CollectionMode-Eigenschaft zeigt dem Overlay an, ob Eingaben als Freihandeingaben, Stiftbewegungen (werden als bestimmte Aktionen anstatt als Inhalt interpretiert) oder beides behandelt werden sollen. Beim Versuch ein InkOverlay zum Erfassen von Stiftbewegungen zu aktivieren, tritt ohne eine Stiftbewegungs-Erkennung ein Fehler auf. Ich verwende daher erneut die PlatformDetection-Klasse, um zu ermitteln, ob eine Stiftbewegungs-Erkennung verfügbar ist. Wenn dies der Fall ist, lege ich CollectionMode.InkAndGesture fest, andernfalls CollectionMode.InkOnly.

bool gestureRecognizerInstalled = 
  PlatformDetection.GestureRecognizerInstalled;
_inkOverlay.CollectionMode = gestureRecognizerInstalled ? 
CollectionMode.InkAndGesture : CollectionMode.InkOnly;

Durch das Festlegen von CollectionMode wird InkOverlay angegeben, ob Stiftbewegungen akzeptiert werden. Es wird jedoch nicht festgelegt, welche bestimmten Bewegungen erwartet oder welche Aktionen beim Erkennen der Bewegungen durchgeführt werden Beim Sudoku ist nur ApplicationGesture.Scratchout wichtig. Mit dieser Stiftbewegung ist es Benutzern möglich, in das Raster eingegebene Zahlen durchzustreichen und somit zu löschen. Zum Aktivieren der Unterstützung für diese Stiftbewegung verwende ich die InkOverlay.SetGestureStatus-Methode und registriere einen Ereignishandler beim InkOverlay.Gesture-Ereignis, um die durchstreichende Stiftbewegung zu behandeln.

if (gestureRecognizerInstalled)
{
  _inkOverlay.SetGestureStatus(
    ApplicationGesture.AllGestures, false);
  _inkOverlay.SetGestureStatus(
    ApplicationGesture.Scratchout, true);
  _inkOverlay.Gesture += 
    new InkCollectorGestureEventHandler(HandleGesture);
}

Anschließend werden die Eigenschaften AutoRedraw und DynamicRendering der InkOverlay-Klasse konfiguriert. Wenn AutoRedraw auf true gesetzt ist, werden fertige, erfasste Striche von InkOverlay automatisch gerendert. Wenn DyamicRendering auf true gesetzt wird, rendert InkOverlay automatisch Striche, die gerade erfasst werden. Um eine doppelte Pufferung zum Rendern von Freihandeingaben zu ermöglichen, habe ich mich gegen die automatische Darstellung von erfassten Freihandeingaben entschieden. AutoRedraw wird daher auf false festgelegt. InkOverlay soll jedoch Freihandeingaben während der Eingabe durch den Benutzer rendern, daher hat DynamicRendering den Wert true.

_inkOverlay.AutoRedraw = false;
_inkOverlay.DynamicRendering = true;

Die Konfiguration von InkOverlay ist fast abgeschlossen. InkOverlay benötigt Anweisungen zum Reagieren auf bestimmte Stiftinteraktionen. Ich gebe diese Anweisungen mithilfe registrierter Handler für eine Reihe von Ereignissen in InkOverlay.

Das Stroke-Ereignis wird ausgelöst, wenn der Benutzer einen neuen Strich eingegeben hat.
Das CursorInRange-Ereignis wird ausgelöst, wenn ein Stift in den physischen Erkennungsbereich (die Nähe) der Eingabeoberfläche bewegt wird.
Das NewPackets-Ereignis wird ausgelöst, wenn InkOverlay neue Pakete mit Daten von einem Stift erhält, der den Bildschirm berührt.
Das NewInAirPackets-Ereignis wird ausgelöst, wenn InkOverlay Pakete mit Daten über Bewegungen von einem Stift erhält, der über den Bildschirm gehalten wird.
Das StrokesDeleting-Ereignis wird ausgelöst, wenn Striche aus der Strokes-Auflistung der InkOverlay-Klasse entfernt werden.

Hinweis Die Ereignisse CursorInRange und NewInAirPackets werden für elektromagnetische Digitalisierungsgeräte und die Maus ausgelöst, jedoch nicht für Digitalisierungsgeräte, die Oberflächenkontakt erfordern.

_inkOverlay.Stroke += new InkCollectorStrokeEventHandler(HandleStroke);
_inkOverlay.CursorInRange += 
  new InkCollectorCursorInRangeEventHandler(HandleCursorInRange);
_inkOverlay.NewPackets += 
  new InkCollectorNewPacketsEventHandler(HandleNewPackets);
_inkOverlay.NewInAirPackets += 
  new InkCollectorNewInAirPacketsEventHandler(HandleNewInAirPackets);
_inkOverlay.StrokesDeleting += 
new InkOverlayStrokesDeletingEventHandler(HandleStrokesDeleting);

InkOverlay ist nun aktiviert.

_inkOverlay.Enabled = true;

Erkennen von Zahlen aus mehreren Strichen

Zur Erkennung von Benutzereingaben verwende ich die RecognizeStrokes-Methode.

private bool RecognizeStrokes(Strokes strokes, out byte number)
{
  number = 0;
  if (_recognizerCtx != null && strokes.Count > 0)
  {
    _recognizerCtx.Strokes = strokes;
    _recognizerCtx.EndInkInput();

    RecognitionStatus rs;
    RecognitionResult rr = _recognizerCtx.Recognize(out rs);
    if (rr != null && rs == RecognitionStatus.NoError)
    {
      string inputNumberText = rr.TopString;
      if (inputNumberText != null && inputNumberText.Length > 0)
      {
        try
        {
          number = byte.Parse(inputNumberText, 
            CultureInfo.InvariantCulture);
        } 
        catch(OverflowException){}
        catch(FormatException){}
        if (number >= 1 && number <= 9) return true;
      }
    }
  }
  return false;
}

RecognizeStrokes akzeptiert zwei Parameter: die Auflistung der zu erkennenden Striche, und ein Ausgabebyte, das die erkannte Ziffer enthält. Die Methode verfügt über einen booleschen Rückgabewert, der angibt, ob die Eingabe ordnungsgemäß erkannt wurde, d. h. ob die ausgegebene Zahl verwendet und als Eingabe behandelt werden kann. RecognizeStrokes überprüft zunächst, ob eine gültige RecognizerContext-Klasse verfügbar ist und ob Striche eingegeben wurden. Wenn beide Bedingungen erfüllt sind, werden die Striche in RecognizerContext gespeichert, und RecognizerContext wird mithilfe der EndInkInput-Methode benachrichtigt, dass keine weiteren Eingaben zur Erkennung akzeptiert werden. Anschließend wird die Recognize-Methode aufgerufen, um die Erkennung durchzuführen.

Recognize stellt verschiedene Informationen zur Verfügung. Das von Recognize zurückgegebene RecognitionResult-Objekt enthält Informationen zum Ergebnis des Vorgangs. Sie können den als Ausgabeparameter von der Methode zur Verfügung gestellten RecognitionStatus-Enumerationswert verwenden, um festzustellen, ob bei der Erkennung ein Fehler und welche Art von Fehler aufgetreten ist. Die TopString-Eigenschaft des RecognitionResult-Objekts wird als Zeichenfolge mit dem erkannten Text zurückgegeben. In diesem Szenario sollte diese Zeichenfolge eine einzelne Ziffer sein. Anschließend wird die byte.Parse-Methode verwendet, um zu überprüfen, dass tatsächlich eine Zahl erkannt wurde. Wenn dies der Fall ist, wird die Zahl an die aufrufende Methode zurückgegeben.

RecognizeStrokes wird jedes Mal verwendet, wenn ein Benutzer einen Strich eingibt, genau wie in meiner ursprünglichen Sudoku-Implementierung. Dies stellt jedoch ein Problem bei Zahlen dar, die mit mehreren Strichen geschrieben werden. (Diese Problematik fiel mir zunächst nicht auf, da ich Zahlen mit einem einzigen, durchgehenden Strich schreibe.) Nach Eingabe des ersten Strichs wird RecognizeStrokes aufgerufen, und die Eingabe wird wahrscheinlich nicht ordnungsgemäß erkannt, da der noch nicht eingegebene Teil der Zahl fehlt.

In Sudoku löse ich dieses Problem mit einem Zeitgeber. Wenn InkOverlay ein Stroke-Objekt erhält, wird ein Zeitgeber mit einer Dauer von einer halben Sekunde gestartet. Wenn InkOverlay vor Ablauf des Zeitgebers ein weiteres Stroke-Objekt erhält, wird der Zeitgeber wieder auf eine halbe Sekunde zurückgesetzt. Früher oder später läuft der Zeitgeber ab, bevor der Spieler weitere Striche eingibt. Nachdem der Zeitgeber abgelaufen ist, wird der Ereignishandler für den Zeitgeber aufgerufen, mit dem die Benutzereingabe erkannt und in dem Feld des Rätsels gespeichert wird, das dem Eingabebereich der Striche des Spielers entspricht.

if (strokes.Count > 0)
{
  byte number = 0;
  bool recognized = false;

  Point cell = GetCellFromStroke(strokes[0]);
  if (CanModifyCell(cell)) 
  {
    recognized = RecognizeStrokes(strokes, out number);
  }

  _inkOverlay.Ink.DeleteStrokes(strokes);
  strokes.Clear();

  if (recognized) SetStateCell(cell, (byte)(number-1));
}

Beachten Sie jedoch, dass nicht alle Striche gleich behandelt werden. Insbesondere werden Striche ignoriert, die wahrscheinlich falsche Eingaben sind, z. B. eine versehentliche Berührung des Bildschirms mit dem Stift oder Tippen auf dem Bildschirm, um das aktuell ausgewählte Feld zu wechseln. Für diese Funktion wird der rechteckige Begrenzungsrahmen für das Stroke-Objekt abgerufen, wobei die Koordinaten der Freihandeingabe in Koordinaten für das Steuerelement konvertiert werden.

Rectangle boundingBox = e.Stroke.GetBoundingBox();
InkToPixelSpace(ref boundingBox);

Anschließend wird die Breite und Höhe dieses Begrenzungsrahmens mit der Breite und Höhe eines Felds im Raster verglichen. Wenn die Breite und Höhe des Begrenzungsrahmens kleiner als ein festgelegter Teil der Größe eines Felds ist, wird das Stroke-Objekt ignoriert. Hierfür wird die Cancel-Eigenschaft des Ereignisarguments auf true festgelegt, sodass der Strich automatisch von der Tablet PC-API gelöscht wird. Weiterhin muss sichergestellt werden, dass der Zeitgeber für Eingaben mit mehreren Strichen zurückgesetzt wird, wenn normale Striche eingegeben und noch nicht erkannt wurden.

RectangleF cellRect = GetCellRectangle(ClientRectangle, Point.Empty);
if (boundingBox.Width < 
    cellRect.Width * MINIMINUM_BOUNDING_RATIO_TO_RECOGNIZE &&
  boundingBox.Height < 
    cellRect.Height * MINIMINUM_BOUNDING_RATIO_TO_RECOGNIZE)
{
  e.Cancel = true;
  ...
}

Ich verwende außerdem eine Reihe anderer Ereignisse, um Striche zu erkennen. Wenn Benutzer den Stift mit oder ohne Bildschirmkontakt in ein anderes Feld bewegen, gehe ich davon aus, dass sie mit der Eingabe der Zahl im vorherigen Feld fertig sind. Daher wird an dieser Stelle der Zeitgeber angehalten. Die Striche werden automatisch erkannt, als ob der Zeitgeber abgelaufen wäre. (RecognizePreviousCellFromPacket überprüft, ob sich die aktuellen Striche in einem anderen Feld als demjenigen unter dem Stift befinden. Wenn dies der Fall ist, und die Striche in einem bearbeitbaren Feld sind, wird RecognizeStrokes aufgerufen.)

private void HandleNewInAirPackets(
  object sender, InkCollectorNewInAirPacketsEventArgs e)
{
  if (e.PacketData.Length >= 2)
  {
    RecognizePreviousCellFromPacket(
      new Point(e.PacketData[0], e.PacketData[1]));  
  }
}

Die gleiche Logik wird als Reaktion auf die Ereignisse NewPackets und Stroke verwendet. In Abbildung 12 sind die Striche für eine mit mehreren Strichen eingegebene Zahl dargestellt (z. B. zwei Striche zum Schreiben der Zahl 4). In Abbildung 13 ist das Ergebnis nach dem Erkennen und Rendern der Zahl dargestellt.

Abbildung 12. Zusammensetzung der Zahl 4 aus mehreren Strichen

Abbildung 13. Die mit mehreren Strichen eingegebene Zahl 4 wurde erkannt

Rückgängig-Unterstützung

Eine meiner Lieblingsfunktionen in Anwendungen ist die Möglichkeit, mehrere Vorgänge rückgängig machen zu können, daher habe ich diese Funktion natürlich in meine Sudoku-Anwendung integriert. Durch die Implementierung von PuzzleState.Clone lässt sich die Funktion relativ einfach einfügen.

Die grundlegende Idee ist, dass jedes Mal, wenn eine Änderung am Rästel vorgenommen wird, eine Kopie des aktuellen Spielstatus auf einen Rückgängig-Stapel verschoben wird.

private PuzzleStateStack _undoStates = new PuzzleStateStack();

Der PuzzleStateStack-Typ ist eine kleine, stark typisierte Klasse, die von der Stack-Klasse in System.Collections abgeleitet ist. Wenn ich einen Vorgang zu einem späteren Zeitpunkt rückgängig machen und zu einem früheren Status zurückkehren möchte, lege ich einen Status aus dem Rückgängig-Stapel als aktuellen Status fest.

public void Undo()
{
  if (_undoStates.Count > 0) this.State = _undoStates.Pop();
}

Die einzige Schwierigkeit dabei ist, sicherzustellen, dass jede Änderung am aktuellen Status den aktuellen Status auf den Rückgängig-Stapel verschiebt. Intern kann PuzzleGrid sicherstellen, dass der Status bei jeder vorgenommenen Änderung auf den Stapel verschoben wird. PuzzleGrid stellt jedoch die aktuelle PuzzleState-Instanz öffentlich zur Verfügung. Mit dieser Implementierung ist nicht gesichert, dass jede Änderung erfolgreich gespeichert wird. PuzzleGrid stellt daher einen SetUndoCheckpoint-Member zur Verfügung und macht es zur Aufgabe des Steuerelement-Consumers, sicherzustellen, dass SetUndoCheckpoint vor wesentlichen Änderungen am aktuellen Status aufgerufen wird.

public void SetUndoCheckpoint()
{
  _undoStates.Push(State.Clone());
}

Intern verwendet PuzzleGrid ebenfalls SetUndoCheckpoint. Betrachten Sie als Beispiel für den Aufruf die SetStateCell-Methode, die im Ereignishandler des Zeitgebers für Eingaben mit mehreren Strichen verwendet wird, wie im vorherigen Abschnitt erläutert.

private void SetStateCell(Point cell, byte number)
{
  if (State[cell] != number)
  {
    SetUndoCheckpoint();
    ClearTabletStateCell(cell);
    State[cell] = number;
  }
}

Die Methode überprüft zunächst, ob sich der neue Wert für das Zielfeld vom bereits vorhandenen Wert unterscheidet. Wenn eine Änderung notwendig ist, legt die Methode einen Rücksetzpunkt fest, wobei der aktuelle PuzzleState auf den Rückgängig-Stapel verschoben wird. Die Methode fügt den Wert dann in das Feld ein. Diese Methode ruft außerdem die ClearTabletStateCell-Methode auf. ClearTabletStateCell behandelt die Scratchpad-Funktionalität im Spiel.

Scratchpad-Unterstützung

Um die Wirkung zu verstärken, dass das Spiel auf Papier gespielt wird, habe ich in Sudoku eine Funktion zum Erstellen von Notizen mit dem Stift implementiert, auf die im Code als scratchpad verwiesen wird. Die Idee dahinter ist, mithilfe von Notizen die logischen Schlüsse bei der Lösung des Rätsels nachvollziehen zu können, wie bei Rätseln auf Papier mit einem Bleistift (siehe Abbildung 14). Diese Notizen werden nicht wie Freihandeingaben mit dem Stift (im Code als normal bezeichnet) erkannt, sondern zusammen mit dem PuzzleState als zusätzliche Tag-Daten gespeichert.

Abbildung 14. Erstellen von Notizen mit dem Scratchpad

Beim Erläutern der Instanziierung und Konfiguration von InkOverlay habe ich kurz zwei Anweisungen erwähnt.

_inkOverlay.Ink.CustomStrokes.Add(ScratchpadStrokesID, 
  _inkOverlay.Ink.CreateStrokes());
_inkOverlay.Ink.CustomStrokes.Add(NormalStrokesID, 
_inkOverlay.Ink.CreateStrokes());

Die Ink-Eigenschaft der InkOverlay-Klasse gibt das Ink-Objekt zurück, das zurzeit dem Overlay zugeordnet ist, und die CreateStrokes-Method dieser Klasse erstellt eine neue Strokes-Auflistung, die dem Ink-Objekt zugeordnet ist. Durch das Erstellen und Verwalten von zwei verschiedenen Strokes-Auflistungen können Striche leicht getrennt werden, die im normal-Stiftmodus bzw. im scratchpad-Stiftmodus erstellt wurden. So lassen sich Vorgänge für nur einen dieser Strichtypen einfach durchführen. Um die Auflistungen problemlos abrufen zu können und sicherzustellen, dass sie gemeinsam mit dem Ink-Objekt ordnungsgemäß serialisiert werden, werden diese Auflistungen zur CustomStrokes-Auflistung des Ink-Objekts hinzugefügt. (Als Serialisierung wird der Vorgang bezeichnet, mit dem ein Ink-Objekt zum Speichern in ein Bytearray umgewandelt wird. Ich verwende dies für zwei verschiedene Zwecke, wie ich weiter unten in diesem Artikel erläutern werde.) Die CustomStrokes-Auflistung enthält benannte Strokes-Auflistungen, die beibehalten und zur späteren Verwendung zur Verfügung gestellt werden. Ich habe einige Hilfseigenschaften definiert, um das Abfragen und die Arbeit mit diesen Auflistungen zu vereinfachen.

private Strokes NormalStrokes 
{
  get { return _inkOverlay.Ink.CustomStrokes[NormalStrokesID]; }
}
private Strokes ScratchpadStrokes
{
  get { return _inkOverlay.Ink.CustomStrokes[ScratchpadStrokesID];}
}
private bool HasScratchpadStrokes 
{ 
  get 
  {
    using(Strokes strokes = ScratchpadStrokes)
    {
      return strokes.Count > 0; 
    }
  }
}

Beachten Sie, dass HasScratchpadStrokes (gibt true zurück, wenn in der Scratchpad-Strichauflistung Striche vorhanden sind) die Strokes-Auflistung vom Scratchpad löscht, wenn diese nicht mehr verwendet wird. Dies erscheint ungewöhnlich, bis Sie die tatsächliche Funktionsweise des CustomStrokes-Indexers untersuchen. Hier ist der Pseudocode für die Implementierung des Indexers.

public Strokes this[string name]
{
  get { return new Strokes(this.m_CustomStrokes.Item(name)); }
}

Der Indexer gibt ein neues Strokes-Objekt statt des ursprünglich in der Auflistung gespeicherten Objekts zurück. Dieses Strokes-Objekt und nicht das ursprüngliche wird dann gelöscht. Dasselbe trifft für den Zugriff auf die Strokes-Hauptauflistung vom Ink-Objekt des InkOverlay aus zu. Hier ist der Pseudocode für den get-Accessor des Strokes-Objekts.

public Strokes Strokes
{
  get
  {
    if (this.disposed)
    {
      throw new ObjectDisposedException(GetType().FullName);
    }
    return new Strokes(this.m_Ink.Strokes);
  }
}

Für jeden Zugriff auf die Strokes-Eigenschaft wird wieder eine neue Strokes-Instanz zurückgegeben. Sie müssen sicherstellen, dass diese Objekte gelöscht werden, wenn sie nicht mehr notwendig sind. Als Beispiel wird in folgendem Code die RenderInk-Methode erläutert, die von PuzzleGrid zum manuellen Darstellen von Freihandeingaben verwendet wird. (Bedenken Sie, dass AutoRedraw für InkOverlay deaktiviert ist).

private void RenderInk(Graphics graphics)
{
  if (_inkOverlay != null)
  {
    using(Strokes strokes = _inkOverlay.Ink.Strokes)
    {
      if (strokes.Count > 0)
      {
        _inkOverlay.Renderer.Draw(graphics, strokes);
      }
    }
  }
}

PuzzleGrid verfolgt, ob sich das Raster im Scratchpad-Modus befindet oder nicht. Dieser Schalter wird von den Stiftschaltflächen auf dem Hauptformular gesteuert. Im Scratchpad-Modus wird vom Ereignishandler für das Stroke-Ereignis von InkOverlay die Logik für die Eingabe mit mehreren Strichen nicht ausgeführt. Stattdessen wird jeder erhaltene Strich der Strokes-Auflistung des Scratchpads hinzugefügt. Es ist jedoch noch ein wenig mehr Aufwand erforderlich.

Zunächst muss jeder Scratchpad-Strich im Rückgängig-Stapel als einzelne Änderung gespeichert werden, damit die Notizen rückgängig gemacht werden können. Das stellt ein Problem dar, da in InkOverlay kein Ereignis vorhanden ist, das vor dem Hinzufügen der Daten des Strichs zum Ink-Objekt ausgelöst wird. Zur Lösung dieses Problems ist ein kleiner Trick erforderlich. Ich muss den Strich aus dem Ink-Objekt löschen, einen Rücksetzpunkt festlegen und den Strich anschließend erneut hinzufügen. Leider können gelöschte Striche nicht verwendet werden. Die Lösung ist, den Strich zu serialisieren, das Original zu löschen und nach dem Festlegen des Rücksetzpunkts auf der Grundlage der Daten des alten Strichs einen neuen zu erstellen. Dieser neue Strich kann dann wieder zum Ink-Objekt hinzugefügt werden.

Stroke s = e.Stroke;
TabletPropertyDescriptionCollection tpdc = 
  new TabletPropertyDescriptionCollection();
foreach (Guid g in s.PacketDescription)
{
  TabletPropertyDescription tpd = new TabletPropertyDescription(
    g, e.Cursor.Tablet.GetPropertyMetrics(g));
  tpdc.Add(tpd);
}
int[] packetData = e.Stroke.GetPacketData();
_inkOverlay.Ink.DeleteStroke(e.Stroke);
SetUndoCheckpoint();
s = _inkOverlay.Ink.CreateStroke(packetData, tpdc);

Ein Stroke setzt sich aus einer Reihe von Punkten zusammen, wobei jeder einzelne das Ergebnis einiger Datenpakete ist. Mit der GetPacketData-Methode können Sie ein Array der Paketdaten des Stroke-Objekts abrufen. Die CreateStroke-Methode im Ink-Objekt verfügt über eine Überladung, die dieses Datenarray akzeptiert und daraus einen neues Stroke-Objekt erstellt. Zu Beachten ist dabei, dass für diese Methode auch eine Beschreibung des Inhalts der Paketdaten erforderlich ist. Für diese Beschreibung wird TabletPropertyDescriptionCollection verwendet. Bevor Sie also das Stroke-Objekt löschen, müssen Sie diese Informationen daraus ermitteln. Die PacketDescription-Eigenschaft des Stroke-Objekts gibt ein Array von GUIDs zurück, in dem für jeden Paketdatentyp, der im Stroke-Objekt gespeichert ist, eine GUID enthalten ist. Diese GUIDs können enumeriert werden, um die für das Aufrufen von CreateStroke erforderliche TabletPropertyDescriptionCollection-Klasse zu erstellen.

Nach der Programmierung der Rückgängig-Unterstützung weise ich den Scratchpad-Strichen eine andere Farbe zu, damit sie von normalen Strichen unterschieden werden können.

s.DrawingAttributes.Color = _scratchpadInkColor;

Hierzu ist weiterer Code erforderlich, der ein wenig komplizierter ist. In diesem Artikel habe ich bereits ausführlich die Bedeutung erläutert, die der Unterstützung von Formularen, deren Größe geändert werden kann, zukommt. Außerdem habe ich gezeigt, wie verschiedene Steuerelemente, z. B. PuzzleGrid, an die Größenänderung angepasst werden. Weiterhin müssen die einzelnen Stroke-Objekte in ihrer Größe angepasst und neu positioniert werden, damit Größe und Position relativ zu PuzzleGrid konstant bleiben. Das ist jedoch einfacher gesagt als getan. In meinem Lösungsansatz muss jedem Scratchpad-Strich zum Erstellungszeitpunkt die aktuelle Größe des Strichs und die aktuelle Größe des Rasters zugewiesen werden. Somit lässt der Strich entsprechend anpassen, wenn die Größe des Rasters geändert wird. Wenn diese Umwandlungen nicht anhand der aktuellen, sondern anhand der ursprünglichen Strichgröße und -position berechnet werden, können Rundungsfehler vermieden werden, die durch das Speichern der Daten als Gleitkommazahlen entstehen. Diese Rundungsfehler führen bei häufigen Größenänderungen möglicherweise zu einer allmählichen Positionsverschiebung der Freihandeingabe.

Diese gebundenen Informationen werden in ExtendedProperties im Stroke-Objekt gespeichert. Mithilfe von Stroke.ExtendedProperties können Anwendungen auf benutzerdefinierte Daten zugreifen, die im Stroke-Objekt gespeichert sind. Diese benutzerdefinierten Daten werden automatisch mit dem Objekt serialisiert. Darum speichere ich in ExtendedProperties sechs Informationen: Position (auf x- und y-Achse) und Größe (Breite und Höhe) des Begrenzungsrahmens des Stroke-Objekts sowie die aktuelle Größe des PuzzleGrid-Steuerelements (Breite und Höhe). Der erste Parameter der Add-Methode von ExtendedProperties ist eine GUID, mit der die von Ihnen erstellte erweiterte Eigenschaft identifiziert wird. Diese GUID können Sie frei wählen. Wenn Sie jedoch Stroke-Objekte in einen permanenten Speicher serialisieren und diese bei einem späteren Ausführen der Anwendung abrufen möchten, müssen Sie sicherstellen, dass die für Ihre erweiterten Eigenschaften verwendeten GUIDs nicht geändert werden, wenn die Anwendung erneut ausgeführt wird.

Rectangle boundingBox = s.GetBoundingBox();
using(Graphics graphics = CreateGraphics())
{
  InkSpaceToPixelSpace(graphics, ref boundingBox);
  s.ExtendedProperties.Add(OriginalStrokeBoundRectXGuid, 
    boundingBox.X);
  s.ExtendedProperties.Add(OriginalStrokeBoundRectYGuid, 
    boundingBox.Y);
  s.ExtendedProperties.Add(OriginalStrokeBoundRectWidthGuid, 
    boundingBox.Width);
  s.ExtendedProperties.Add(OriginalStrokeBoundRectHeightGuid, 
    boundingBox.Height);
  s.ExtendedProperties.Add(OriginalClientRectWidthGuid, 
    ClientRectangle.Width);
  s.ExtendedProperties.Add(OriginalClientRectHeightGuid, 
    ClientRectangle.Height);
}

Wenn anschließend die Größe von PuzzleGrid geändert wird, ändere ich mithilfe dieser Informationen die einzelnen Stroke-Objekte.

protected override void OnResize(EventArgs e)
{
  _cachedEmSize = -1;
  ResizeScratchpadInk();
  base.OnResize(e);
}
internal void ResizeScratchpadInk()
{
  if (_inkOverlay != null)
  {
    Rectangle currentClientRect = ClientRectangle;
    using(Strokes scratchpadStrokes = ScratchpadStrokes)  
    {
      foreach(Stroke s in scratchpadStrokes)
      {
        int originalBoundsX = (int)s.ExtendedProperties[
          OriginalStrokeBoundRectXGuid].Data;
        int originalBoundsY = (int)s.ExtendedProperties[
          OriginalStrokeBoundRectYGuid].Data;
        int originalBoundsWidth = (int)s.ExtendedProperties[
          OriginalStrokeBoundRectWidthGuid].Data;
        int originalBoundsHeight = (int)s.ExtendedProperties[
          OriginalStrokeBoundRectHeightGuid].Data;
        int originalClientRectWidth = 
          (int)s.ExtendedProperties[
            OriginalClientRectWidthGuid].Data;
        int originalClientRectHeight = 
          (int)s.ExtendedProperties[
            OriginalClientRectHeightGuid].Data;
        double scaleX = currentClientRect.Width / 
          (double)originalClientRectWidth;
        double scaleY = currentClientRect.Height / 
          (double)originalClientRectHeight;

        Rectangle newBounds = new Rectangle(
          (int)(originalBoundsX*scaleX), 
          (int)(originalBoundsY*scaleY), 
          (int)(originalBoundsWidth*scaleX), 
          (int)(originalBoundsHeight*scaleY));

        using(Graphics graphics = CreateGraphics())
        {                
          PixelSpaceToInkSpace(graphics, ref newBounds);
          s.ScaleToRectangle(newBounds);
        }
      }
    }
  }
}

Ich berechne für jeden Strich das Verhältnis zwischen der aktuellen Größe des Steuerelements und der Größe des Steuerelements zum Erstellungszeitpunkt des Strichs. (Diese Berechnung muss für jeden Strich ausgeführt werden, da die Striche möglicherweise mit verschiedenen "ursprünglichen" Steuerelementgrößen erstellt wurden – dies gilt insbesondere, wenn zwischen der Erstellung von Strichen die Größe von PuzzleGrid geändert wurde.) Anschließend berechne ich mithilfe dieses Verhältnisses und den ursprünglichen Begrenzungen des Strichs die neuen Begrenzungen. Diese Informationen werden dann an die ScaleToRectangle-Methode des Stroke-Objekts weitergeleitet, die die entsprechende Größenänderung für das Stroke-Objekt ausführt.

Das Erstellen einer eigenen Auflistung für die Scratchpad-Striche bietet sich an, wenn Sie zwischen normalem und Scratchpad-Modus wechseln. Freihandeingaben werden beispielsweise von der Anwendung je nach Modus unterschiedlich angezeigt: Im normalen Modus werden Scratchpad-Freihandeingaben abgeblendet, im Scratchpad-Modus hingegen schwarz angezeigt. Dies wird durch eine Änderung der DrawingAttributes für jede Scratchpad-Stroke-Instanz erzielt. Mit folgendem Code wird beispielsweise die Strichfarbe in Grau geändert.

using(Strokes strokes = ScratchpadStrokes)
{
  foreach(Stroke s in strokes)
  {
    s.DrawingAttributes.Color = Color.Gray;
  }
}

Das Speichern von Scratchpad-Strichen in einer eigenen Auflistung ermöglicht außerdem das Programmieren praktischer Funktionen, wenn der Benutzer Zahlen in Felder eingibt. Wenn ein Benutzer Zahlen in ein Feld eingibt, wird die (bereits erläuterte) SetStateCell-Methode aufgerufen. Diese Methode wiederum ruft die ClearTabletStateCell-Methode auf. ClearTabletStateCell entfernt sämtliche Scratchpad-Striche aus dem Feld. Dabei gehe ich davon aus, dass der Benutzer eine logisch hergeleitete Zahl in dieses Feld eingegeben hat und somit die Notizen, die mit diesem Feld verbunden sind, gelöscht werden können. Dadurch wird eine übersichtliche Anzeige gewährleistet. ClearTabletStateCell durchläuft bei diesem Vorgang alle Striche in der Scratchpad-Strichauflistung und löscht die Striche, die sich im Zielfeld befinden.

private void ClearTabletStateCell(Point cell)
{
  if (_inkOverlay != null)
  {
    // Delete any scratchpad strokes in that cell
    using(Strokes strokes = ScratchpadStrokes)
    {
      for(int i=strokes.Count-1; i>=0; --i)
      {
        Stroke s = strokes[i];
        if (GetCellFromStroke(s) == cell)
        {
          strokes.RemoveAt(i);
          _inkOverlay.Ink.DeleteStroke(s);
        }
      }
    }
  }
}

Radierer-Unterstützung

Eine praktische Funktion, die von vielen Tablet PCs unterstützt wird, ist der Stiftradierer. Wenn Sie den Stift umdrehen, können Sie das andere Ende als virtuellen Radierer verwenden – vorausgesetzt, die Anwendung unterstützt diese Funktion. Dies ist bei Sudoku der Fall.

Die InkOverlay-Klasse stellt eine EditingMode-Eigenschaft vom Typ InkOverlayEditingMode zur Verfügung. Der Standardwert dieser Eigenschaft ist InkOverlayEditingMode.Ink. Wird dieser Wert jedoch in InkOverlayEditingMode.Delete geändert, wird der Cursor als Radierer angezeigt. Wenn der Benutzer diesen Radierer über vorhandene Striche zieht, werden diese gelöscht und keine neuen Freihandstriche erstellt und gespeichert. Normalerweise verwendet eine Anwendung einen Ereignishandler für das Ereignis CursorInRange in der InkOverlay-Klasse, um den Wert für diese Eigenschaft zu überprüfen und entsprechend festzulegen. Dies gilt auch für Sudoku. Die InkCollectorCursorInRangeEventArgs-Instanz wird einem Ereignishandler als Parameter für das Ereignis CursorInRange zur Verfügung gestellt und verfügt über eine Cursor-Eigenschaft. Diese Eigenschaft gibt eine Microsoft.Ink.Cursor-Instanz zurück. Dieses Objekt verfügt über eine boolesche Inverted-Eigenschaft, mit der zurückgegeben wird, ob der Stift mit dem oberen Ende nach unten gehalten wird und der Benutzer den Radierer verwenden möchte. Mein Ereignishandler reagiert auf diese Informationen, indem er für InkOverlay den entsprechenden EditingMode-Wert einstellt.

Hinweis Die Erkennung von Eingaben, bei denen das Eingabegerät den Bildschirm nicht berührt, werden für elektromagnetische Digitalisierungsgeräte und die Maus unterstützt, jedoch nicht für Digitalisierungsgeräte, die Oberflächenkontakt erfordern.

Nach Erkennen eines Radiererstrichs wird das Stroke-Ereignis in der InkOverlay-Klasse ausgelöst. Anstatt jedoch die Logik zum Erkennen mehrerer Striche auszuführen, wie es der Fall ist, wenn der EditingMode auf InkOverlayEditingMode.Ink gesetzt ist, führe ich Code zum Löschen des Felds unterhalb des Radierers aus.

Point currentStrokeCell = GetCellFromStroke(e.Stroke);
if (CanClearCell(currentStrokeCell)) 
{
  ClearStateCell(currentStrokeCell);
}

Dadurch wird nur ein Feld gelöscht, da GetCellFromStroke mithilfe des Begrenzungsrahmens im Stroke-Objekt das wahrscheinlichste Zielfeld auswählt. Wenn der Benutzer den Radierer allerdings über mehrere Felder zieht, möchte er wahrscheinlich alle berührten Felder löschen. Um alle Felder zu löschen, über die der Benutzer den Radierer gezogen hat, wird einem Ereignishandler für das NewPackets-Ereignis in der InkOverlay-Klasse eine ähnliche Logik hinzugefügt.

if (_mode == PuzzleGridMode.Eraser || e.Cursor.Inverted)
{
  if (e.PacketData.Length >= 2)
  {
    Point cell = TabletToCell(
      new Point(e.PacketData[0], e.PacketData[1]));
    if (CanClearCell(cell) && State[cell].HasValue) 
    {
      ClearStateCellWithInvalidation(cell);
    }
    if (_selectedCell.HasValue) 
    {
      InvalidateCell(_selectedCell.Value);
    }
    SetSelectedCell(cell);
    InvalidateCell(_selectedCell.Value);
  }
}

Im Scratchpad-Modus wird eine andere Logik angewendet. Bei der Standardverarbeitung des InkOverlayEditingMode.Delete-Werts in der InkOverlay-Klasse werden alle Striche unterhalb des Cursors gelöscht. Genau dieser Vorgang soll auch im Scratchpad-Modus ausgeführt werden, daher führe ich InkOverlay aus. Dabei müssen allerdings zwei Punkte beachtet werden. Zum einen muss ich vor dem Löschen eines Strichs einen Punkt für die Rückgängig-Funktion festlegen, sodass der gelöschte Strich wiederhergestellt werden kann. Zum anderen muss ich gelöschte Striche manuell aus den benutzerdefinierten Auflistungen entfernen. Beide Vorgänge kann ich in einem Ereignishandler für das StrokesDeleting-Ereignis in der InkOverlay-Klasse ausführen.

private void HandleStrokesDeleting(
  object sender, InkOverlayStrokesDeletingEventArgs e)
{
  SetUndoCheckpoint();
  using(Strokes normalStrokes = NormalStrokes) 
  {
    normalStrokes.Remove(e.StrokesToDelete);
  }
  using(Strokes scratchpadStrokes = ScratchpadStrokes)
  {
    scratchpadStrokes.Remove(e.StrokesToDelete);
  }
}

Wie bereits angedeutet, kann der Benutzer eine Zahl, die er in ein Feld eingegeben hat, mithilfe einer Durchstreichbewegung löschen, wie in Abbildung 15 dargestellt. (Mit diesen Durchstreichbewegungen lassen sich auch Notizen löschen, die im Scratchpad-Modus erstellt wurden.)

Abbildung 15. Löschen einer Zahl durch Durchstreichen

Im normalen Modus muss dazu auf das Gesture-Ereignis reagiert werden, indem festgestellt wird, über welchem Feld die Durchstreichbewegung ausgeführt wurde. Dieses Feld wird anschließend gelöscht. Dabei ist jedoch zu beachten, dass bei jedem Löschvorgang in einem Feld ein Punkt für die Rückgängig-Funktion festgelegt wird. In diesem Punkt für die Rückgängig-Funktion sind alle Freihandeingaben enthalten, die zu diesem Zeitpunkt in InkOverlay gespeichert sind. Die Striche der Stiftbewegung sind immer noch im Overlay gespeichert. Darum lösche ich explizit die Striche der Stiftbewegung, bevor das Feld gelöscht wird.

void HandleGestureInNormalMode(
  object sender, InkCollectorGestureEventArgs e)
{
  switch (e.Gestures[0].Id)
  {
    case ApplicationGesture.Scratchout:
      Point cell = GetCellFromStroke(e.Strokes[0]);
      _inkOverlay.Ink.DeleteStrokes(e.Strokes);
      RecognizePreviousNormalStrokes();
      if (CanClearCell(cell)) ClearStateCell(cell);
      break;
    default:
      e.Cancel = true;
      break;
  }
  Invalidate();
}

Im Scratchpad-Modus ist das Behandeln von Durchstreichbewegungen noch einfacher. Die Anwendung ruft sämtliche Scratchpad-Striche ab, die die Durchstreichbewegungen kreuzen, und löscht sie.

Lösungsanimation

Spiele machen mehr Spaß, wenn die Leistungen eines erfolgreichen Spielers auch entsprechend gewürdigt werden. Gewiss ist man stolz, wenn man das letzte Feld ausgefüllt hat und sich im Sieg über die Logik sonnt. Es ist jedoch noch schöner, wenn dieses Gefühl über das Spiel selbst verstärkt wird, und der Spieler ein Schulterklopfen erhält, wie es etwa bei der Microsoft-Implementierung von Solitaire der Fall ist (siehe Abbildung 16).

Abbildung 16: Fenster von Solitaire bei einem gewonnen Spiel

Nachdem ich verschiedene Animationen für ein gelöstes Sudoku-Rätsel implementiert und einige gute Vorschläge meiner Verlobten Tamara (sie ist Sudoku-Fan und mein bester Betatester) erhalten hatte, entschied ich mich für eine Animation, bei der die Felder vom Spielfeld abheben, sich drehen und mit einem fettgelben Text zur Gratulation entschweben. Außerdem wird hinter den sich drehenden Zahlen ein abgeblendetes Bild des vollendeten Spielfelds angezeigt, da ich ein entsprechendes Feedback erhalten hatte. Die Spieler möchten, dass ihr abgeschlossenes Spiel zusätzlich zu den sich drehenden Feldern angezeigt wird. Ein Beispiel hierfür finden Sie in Abbildung 17.

Abbildung 17: Sudoku-Fenster nach dem Lösen eines Puzzles

Die Animation ist in das WinningAnimation-Steuerelement integriert, das Sie im Ordner Controls in der Datei WinningAnimation.cs finden. Beim Initialisieren des Hauptformulars wird im PuzzleGrid der Sammlung Controls eine Instanz von WinningAnimation hinzugefügt – angedockt zum Füllen des Rastersteuerelements und ausgeblendet.

_winningAnimation = new WinningAnimation(thePuzzleGrid);
thePuzzleGrid.Controls.Add(_winningAnimation);
_winningAnimation.Dock = DockStyle.Fill;
_winningAnimation.Visible = false;
_winningAnimation.BringToFront();

Wenn ein Spieler das Rätsel löst, wird das Animationssteuerelement und damit die Animation gestartet.

Die Animation selbst beruht auf einem Spritesystem. Als Sprites werden Bilder oder Animationen bezeichnet, die in eine größere Szenerie integriert sind. Sie können in der Regel ihren eigenen Status beibehalten, sich bewegen und mit anderen Sprites interagieren oder sich etwa selbst wiedergeben. Bei dieser Animation handelt es sich bei jedem fliegenden Feld jeweils um ein Sprite.

internal class ImageSprite : IDisposable
{
  Point _location;
  float _angle;
  float _flipPosition;

  Size _velocity;
  float _angularVelocity;
  float _flipSpeed;
  bool _rotateAroundCenter;

  private Bitmap _bmp;
  ...
}

Ich erstelle jedes Sprite mit einer Startposition im Steuerelement und einer Bitmap-Datei, die das vom Sprite darzustellende Hauptbild enthält. Während der Animation behalten Sprites ihre aktuelle Position, ihre lineare und Winkelgeschwindigkeit sowie die Umdrehungsgeschwindigkeit (ein von mir erfundener Begriff für die Winkelgeschwindigkeit um eine andere Drehachse) bei. Außerdem konfiguriere ich jedes Sprite mit einem booleschen Wert, der angibt, ob es sich um die Mitte oder um eine Ecke drehen soll.

Jedes Sprite rendert sich selbst. Beim Rendern des übergeordneten Steuerelements wird das Graphics-Zielobjekt für jedes Sprite bereitgestellt, und das Sprite gibt die Darstellung an dieses Graphics-Objekt weiter.

public void Paint(Graphics graphics)
{
  using(Matrix mx = new Matrix())
  {
    GraphicsState gs = graphics.Save();
    if (_rotateAroundCenter) mx.Translate(
      -_bmp.Width/2, -_bmp.Height/2, MatrixOrder.Append); 
    mx.Rotate(_angle, MatrixOrder.Append);
    if (_rotateAroundCenter) mx.Translate(
      _bmp.Width/2, _bmp.Height/2, MatrixOrder.Append); 
    mx.Translate(_location.X, _location.Y, MatrixOrder.Append);
    graphics.Transform = mx;

    // Draw the image
    float flipMult = ((float)
      Math.Cos(_flipPosition*Math.PI/180.0));
    if (flipMult > 0.001 || flipMult < -0.001)
    {
      graphics.DrawImage(_bmp, 
        new RectangleF(0, 1-Math.Abs(flipMult), 
        _bmp.Width, _bmp.Height*flipMult), 
        new RectangleF(0, 0, _bmp.Width, _bmp.Height), 
        GraphicsUnit.Pixel);
    }

    graphics.Restore(gs);
  }
}

Hierzu sind mehrere Schritte erforderlich. Zunächst erstelle ich ein System.Drawing.Drawing2D.Matrix-Objekt. Wenn Sie mit der linearen Algebra und deren Auswirkung auf Grafiken nicht vertraut sind, können Sie Matrizen verwenden, die häufig verwendet werden, um Übergänge von einem Koordinatenraum in einen anderen zu erstellen. Die Matrix-Klasse vereinfacht die Anwendung von Übergängen, wie z. B. Drehungen und Übersetzungen. Außerdem übernimmt sie alle zugrunde liegenden mathematischen Vorgänge. Die Graphics-Klasse vereinfacht anschließend das Zeichnen mit den angewendeten Übergängen.

Zunächst speichere ich den aktuellen Status des Graphics-Objekts, sodass ich es wiederherstellen kann, nachdem ich alle für den aktuellen Übergang erforderlichen Elemente gezeichnet habe. Anschließend drehe ich die Matrix um den aktuellen Winkel des Sprite. Beachten Sie, dass sich das Sprite um eine seiner Ecken dreht, da sich diese bei den Koordinaten [0,0] befindet. Wenn sich dieses Sprite um seine Mitte drehen soll, kann vor der Drehung eine Übersetzung angewendet werden, die die Mitte des Sprite auf [0,0] verschiebt. Nach dem Anwenden der Drehung wird die Übersetzung rückgängig gemacht.

Nachdem das Sprite über die gewünschte Drehung verfügt, wird es an die richtige Stelle verschoben (eine Übersetzungsumwandlung, die auf der aktuellen Spriteposition beruht). Abschließend möchte ich das Sprite zeichnen, was mithilfe von Graphics.DrawImage erfolgt. Um das Sprite drehen zu können, muss die vertikale Größe des Zielrechtecks geändert werden (stellen Sie sich ein Akkordeon vor, das beim Spielen abwechselnd wächst und schrumpft). Wenn die vertikale Größe negativ ist, rendert DrawImage das Bild auf dem Kopf stehend. Dadurch entsteht beim Spieler der Eindruck, durch die Rückseite des Felds zu blicken.

Die Darstellung des Steuerelements der Gesamtanimation beruht auf der Fähigkeit des Sprite, sich selbst zu rendern.

protected override void OnPaint(PaintEventArgs pe)
{
  // Do base painting
  base.OnPaint(pe);

  // Draw the base underlying image
  if (_underImage != null) 
  {
    pe.Graphics.DrawImage(_underImage, 0, 0);
  }

  // Render all of the sprites
  if (_sprites != null && _sprites.Count > 0)
  {
    for(int i=_sprites.Count-1; i>=0; --i)
    {
      ImageSprite s = (ImageSprite)_sprites[i];
      s.Paint(pe.Graphics);
    }
  }

  // Show the congratulatory text
  string text = ResourceHelper.PuzzleSolvedCongratulations;
  if (_sf != null && text != null && text.Length > 0)
  {
    float emSize = GraphicsHelpers.GetMaximumEMSize(text,
      pe.Graphics, Font.FontFamily, Font.Style, 
      ClientRectangle.Width, ClientRectangle.Height);
    using(Font f = new Font(Font.FontFamily, emSize))
    {
      pe.Graphics.DrawString(text, f, Brushes.Black, 
        new RectangleF(2, 2, ClientRectangle.Width, 
          ClientRectangle.Height), _sf);
      pe.Graphics.DrawString(text, f, Brushes.Gray, 
        new RectangleF(-1, -1, ClientRectangle.Width, 
          ClientRectangle.Height), _sf);
      pe.Graphics.DrawString(text, f, Brushes.Yellow, 
        new RectangleF(0, 0, ClientRectangle.Width, 
          ClientRectangle.Height), _sf);
    }
  }
}

Die Methode beginnt mit dem Rendern des zugrunde liegenden Bilds (siehe unten). Anschließend werden alle Sprites durchlaufen und gerendert, indem die einzelnen Paint-Methoden delegiert werden (siehe oben). Zum Abschluss rendert die Methode den Gratulationstext. Der Text wird mithilfe dreier Aufrufe an Graphics.DrawString gerendert – zweimal zum Zeichnen des Hintergrunds oder Schattens für den Text und einmal zur Darstellung der gelben Überlagerung. Die zum Rendern des Textes verwendete Schriftgröße muss entsprechend der Größe des Steuerelements angepasst werden. Die angegebene Schriftgröße wird mithilfe der statischen GetMaximumEMSize-Methode meiner GraphicsHelpers-Klasse abgerufen. Die Methode lässt den zu rendernden Text, das Zielgrafikobjekt, die angegebene Schriftartfamilie und den Schriftschnitt sowie die Höhe und Breite des Rechtecks zu, in das der Text eingepasst werden soll. Anschließend gibt sie den größten Schriftgrad aus, mit dem der angegebene Text in der festgelegten Schriftartfamilie und im angegebenen Schriftschnitt in das Begrenzungsfeld passt.

public static float GetMaximumEMSize(string text,
  Graphics graphics, FontFamily fontFamily, FontStyle fontStyle, 
  float width, float height)
{
  const float MAX_ERROR = .25f;
  float curMin = 1.0f, curMax = width;
  float emSize = ((curMax - curMin) / 2f) + curMin;
  while(curMax - curMin > MAX_ERROR && curMin >= 1)
  {
    using (Font f = new Font(fontFamily, emSize, fontStyle))
    {
      SizeF size = graphics.MeasureString(text, f);
      bool textFits = size.Width < width && size.Height < height;
      if (textFits && emSize > curMin) curMin = emSize;
      else if (!textFits && emSize < curMax) curMax = emSize;
    }
    emSize = ((curMax - curMin) / 2f) + curMin;
  }
  return curMin;
}

Den maximalen Schriftgrad kann ich mithilfe einer binären Suche ermitteln. Dabei gehe ich davon aus, dass der minimale Schriftgrad ein Punkt ist, während der maximale der Breite des Begrenzungsfelds entspricht. Die Methode überprüft zunächst, ob der angegebene Text in der festgelegten Schrift in einer Punktgröße in das Begrenzungsrechteck passt, die in der Mitte der Minimal- und Höchstwerte liegt. Wenn der zu rendernde Text passt, testet GetMaximumEMSize einen größeren Wert, der zwischen der Halbpunkt- und der Maximalgröße liegt. Wenn dieser Wert nicht passt, testet die Methode einen anderen Wert, der auf der Hälfte zwischen Halbpunkt- und Minimalgröße liegt. Dieser Hälftelungsansatz wird fortgeführt, bis die aktuellen Minimal- und Maximalgrößen sich bis auf eine kleine Entfernung (einen Viertelpunkt) angenähert haben. Nun gibt die Methode den Minimalwert als ausgewählten Schriftgrad zurück.

Diese Methode eignet sich jedoch nicht nur für die Wiedergabe des Gratulationstexts, sondern für den gesamten in der Anwendung gerenderten Text. Bei einer Änderung der Formulargröße wird für alle Steuerelemente der Anwendung, die Text rendern (z. B. Beschriftungen und Schaltflächen) der zu verwendende Schriftgrad anhand des Ergebnisses von GetMaximumEMSize neu berechnet. Dadurch werden die Schriften aktiviert (z. B. die Zahlen auf den Zahlenschaltflächen), um bei einer Größenänderung des Formulars optimal skaliert werden zu können.

Die Anwendung erstellt die Sprites bei der Anzeige des Steuerelements WinningAnimation. Das Steuerelement nimmt einen Snapshot der Darstellung des PuzzleGrid-Steuerelements zu diesem Zeitpunkt auf (dem Bild, das im Hintergrund der sich drehenden und bewegenden Sprites angezeigt werden soll). Anschließend werden aus diesem Bild 81 separate Bitmaps erstellt, die jeweils einem neuen Sprite zugeordnet werden.

using(Bitmap bmp = new Bitmap(
  _grid.ClientRectangle.Width, _grid.ClientRectangle.Height))
{
  // Take a snapshot of the underlying puzzle grid
  using(Graphics g = Graphics.FromImage(bmp))
  {
    _grid.DrawToGraphics(g, _grid.ClientRectangle);
  }

  // Set up each individual sprite based on pulling out a section
  // of the underlying grid snapshot
  for(int i=0; i<_grid.State.GridSize; i++)
  {
    for(int j=0; j<_grid.State.GridSize; j++)
    {
      RectangleF cellRect = PuzzleGrid.GetCellRectangle(
        _grid.BoardRectangle, new Point(i,j));
      Bitmap smallImage = new Bitmap( (int)cellRect.Width, 
        (int)cellRect.Height, PixelFormat.Format32bppPArgb);
      using(Graphics g = Graphics.FromImage(smallImage))
      {
        g.DrawImage(bmp, 0, 0, cellRect, GraphicsUnit.Pixel);
      }
      ImageSprite s = new ImageSprite(smallImage);
      ...
    }
  }
}

Für die Anzeige des Steuerelements erstelle ich außerdem einen Zeitgeber. Beim Erstellen der Sprites wird jedes einzelne für die gewünschte Position im Steuerelement initialisiert, sodass die jeweiligen Entsprechungen im zugrunde liegenden Raster exakt überlagert werden. Jedem Sprite wird anschließend eine zufällige lineare, Winkel- und Umdrehungsgeschwindigkeit zugewiesen. Für jedes Sprite wird außerdem festgelegt, ob es sich um seine Mitte oder eine Ecke drehen soll. Jedes Mal, wenn der Zeitgeber ausgelöst wird (24-mal pro Sekunde, sofern die CPU das schafft), verwende ich die Update-Methode des Sprites, um dessen Status entsprechend zu ändern (die Update-Methode verwendet die verschiedenen Spritegeschwindigkeiten, um die Positionsinformationen zu aktualisieren), und das Steuerelement wird als ungültig erkannt und neu gezeichnet.

for(int i=_sprites.Count-1; i>=0; --i)
{
  ImageSprite s = (ImageSprite)_sprites[i];
  s.Update();

  Rectangle bounds = ClientRectangle;
  if (s.Location.X > bounds.Right + s.Image.Width || 
    s.Location.X < -s.Image.Width ||
    s.Location.Y > bounds.Bottom + s.Image.Width || 
    s.Location.Y < -s.Image.Width) 
  {
    _sprites.RemoveAt(i);
    s.Dispose();
  }
}
if (_sprites.Count == 0) _timer.Stop();
Invalidate();

Wenn ein Sprite den sichtbaren Bereich des Steuerelements verlässt, wird es aus der Spritesammlung entfernt. Wenn keine Sprites mehr angezeigt werden können, wird der Zeitgeber angehalten. Das Anhalten des Zeitgebers ist aus Leistungsgründen wichtig. Auf tragbaren Geräten ist es außerdem aufgrund des Energieverbrauchs von Bedeutung. Zeitgeber, die häufig (z. B. mehrmals in der Sekunde) ausgelöst werden, können dazu führen, dass das System nicht in den Energiesparmodus versetzt wird. Wenn Sie also einen Zeitgeber verwenden müssen, der häufig ausgelöst werden soll (wie bei Spielen und Animationen üblich), sollten Sie sicherstellen, dass dieser deaktiviert wird, wenn er nicht unbedingt erforderlich ist.

Speichern von Status und Einstellungen

Für Sudoku werden im lokalen Anwendungsdatenspeicher des Benutzers bis zu zwei Dateien verwendet, um den Status der Anwendung beizubehalten. In einer Datei werden die Anwendungseinstellungen für das Spiel gespeichert, in der anderen der Status eines unvollständigen Rätsels, sodass dieses vom Benutzer bei einer späteren Ausführung des Programms fortgeführt werden kann. Alle Einstellungen und der Status werden aus Dateien serialisiert und deserialisiert, die die BinaryFormatter-Klasse verwenden, die Sie im Namespace System.Runtime.Serialization.Formatters.Binary finden.

Die Einstellungsdatei enthält Informationen zu den aktuell konfigurierten Optionen (ob falsche Werte angezeigt, ob Vorschläge für das nächste auszufüllende Feld gemacht, ob eine Warnung vor dem Löschen eines unvollständigen Rätsels angezeigt und ob neue symmetrische Rätsel erstellt werden sollen), zur aktuellen Größe und Position des Hauptformulars und zum Schwierigkeitsgrad des aktuellen Rätsels. Aus Gründen der vereinfachten Darstellung wurde die Ausnahmebehandlung übergangen, die SaveSettings-Implementierung gestaltet sich jedoch folgendermaßen.

private void SaveSettings()
{
  BinaryFormatter formatter = new BinaryFormatter();
  string path = Environment.GetFolderPath(
    Environment.SpecialFolder.LocalApplicationData) + 
    SAVED_SETTINGS_USER_PATH;

  DirectoryInfo parentDir = Directory.GetParent(path);
  if (!parentDir.Exists) parentDir.Create();
  
  ConfigurationOptions options = 
    _optionsDialog.ConfiguredOptions;
  PuzzleDifficulty difficulty = _puzzleDifficulty;
  Rectangle windowBounds = GetRestoreBounds(this);
  bool maximized = (WindowState == FormWindowState.Maximized);
  using(Stream s = File.OpenWrite(path))
  {
    formatter.Serialize(s, options);
    formatter.Serialize(s, difficulty);
    formatter.Serialize(s, windowBounds);
    formatter.Serialize(s, maximized);
  }
}

Die LoadSettings-Methode führt das Gegenteil durch: Informationen werden in Objekte der Einstellungsdatei deserialisiert und im Formular sowie in den konfigurierten Optionen wiederhergestellt.

Meine Methode SaveStateFile zum Speichern des Status eines derzeit aktiven Rätsels sieht folgendermaßen aus (erneut ohne Ausnahmebehandlung).

internal void SaveStateFile()
{
  if (thePuzzleGrid.PuzzleHasBeenModified)
  {
    string path = Environment.GetFolderPath(
      Environment.SpecialFolder.LocalApplicationData) + 
      SAVED_STATE_USER_PATH;
    DirectoryInfo parentDir = Directory.GetParent(path);
    if (!parentDir.Exists) parentDir.Create();
    using(Stream s = File.OpenWrite(path))
    {
      BinaryFormatter formatter = new BinaryFormatter();
      formatter.Serialize(s,
        Assembly.GetEntryAssembly().GetName().Version);
      formatter.Serialize(s, thePuzzleGrid.State);
      formatter.Serialize(s, thePuzzleGrid.OriginalState);
      formatter.Serialize(s, thePuzzleGrid.UndoStates);
      formatter.Serialize(s, thePuzzleGrid.InkData);
    }
  }
}

Vor der Serialisierung überprüft die SaveStateFile-Methode zunächst PuzzleGrid, um zu ermitteln, ob das Rätsel aktiv ist, d. h., dass der ursprüngliche Zustand geändert jedoch noch nicht gespeichert wurde. Wenn SaveStateFile die Statusdatei erstellt, werden darin gleichzeitig fünf Informationen gespeichert. Zunächst wird die aktuelle Sudoku-Version gespeichert. Dies ist stets sinnvoll, da Sie für eine zukünftige Version möglicherweise die in der Datei zu speichernden Informationen ändern, und die Informationen müssen dabei abwärtskompatibel mit den Statusdateien früherer Versionen sein. Anschließend werden der aktuelle PuzzleState und der ursprüngliche PuzzleState (der für PuzzleGrid bereitgestellt wird) gespeichert. Der Letztere ist wichtig, damit bekannt ist, welche der Zahlen im aktuellen Rätsel ursprünglich vorhanden waren. Anschließend wird der Rückgängig-Stapel in der Datei gespeichert. Zuletzt werden alle Ink-Daten des Overlays von PuzzleGrid ausserialisiert. Die InkData-Eigenschaft von PuzzleGrid gibt ein Bytearray zurück, das die serialisierte Freihandeingabe enthält.

_inkOverlay.Ink.Save(PersistenceFormat.InkSerializedFormat)

Wie bei den Einstellungen handelt es sich auch beim Ladeprozess im Grunde um das Gegenteil der Speichermethode. Beim Ladeprozess werden die einzelnen Informationseinheiten aus der Datei geladen und in PuzzleGrid wiederhergestellt.

Energieverbrauch

Bei der Implementierung von Anwendungen für tragbare Geräte ist der Energieverbrauch von großer Bedeutung. Der Benutzer sollte wissen, wann dem Gerät die Energie ausgeht, sodass Sie alle erforderlichen Schritte unternehmen können, damit dem Benutzer keine Daten verloren gehen. Wenn Sudoku erkennt, dass der Akku fast leer ist oder das System demnächst in den Bereitschafts- oder Ruhezustand übergeht, wird das aktuelle Rätsel gespeichert. Dies erfolgt im Hauptformular, indem die WndProc-Methode (die Hauptmethode eines Steuerelements zum Verarbeiten von Windows-Nachrichten) überschrieben wird. Dadurch wird das aktuelle Spiel gespeichert, wenn die Anwendung eine WM_POWERBROADCAST-Nachricht erhält (eine ähnliche Funktionalität kann mithilfe der Microsoft.Win32.SystemEvents-Klasse erreicht werden).

protected override void WndProc(ref Message m)
{
  base.WndProc (ref m);

  const int WM_POWERBROADCAST = 0x218;
  const int PBT_APMSUSPEND = 0x0004;
  const int PBT_APMSTANDBY = 0x0005;
  const int PBT_APMBATTERYLOW = 0x0009;

  switch(m.Msg)
  {
    case WM_POWERBROADCAST:
      switch((int)m.WParam)
      {
        case PBT_APMBATTERYLOW:
        case PBT_APMSTANDBY:
        case PBT_APMSUSPEND:
           SaveStateFile();
           break;
      }
      break;
    ...
}

Auf diese Weise kann der Spieler eine unterbrochene Sitzung an der Stelle wiederaufnehmen, an der er im Rätsel angelangt war.

Zusätzlich werden beim Überschreiben von WndProc einige weitere, nicht mit der Energieversorgung zusammenhängende Nachrichten behandelt. So habe ich z. B. bereits erwähnt, dass ich SetHandedness aufrufe, um die Benutzeroberfläche bei Änderungen an den aktuellen Händigkeitseinstellungen des Benutzers entsprechend zu aktualisieren. Die Anwendung wird von Windows über WM_SETTINGSCHANGE-Nachrichten auf Einstellungsänderungen hingewiesen. Meine WndProc-Implementierung prüft, ob die Änderungen an der Einstellung SPI_SETMENUDROPALIGNMENT vorgenommen wurden. Wenn dies zutrifft, wird SetHandedness aufgerufen.

case WM_SETTINGSCHANGE:
  if (SPI_SETMENUDROPALIGNMENT == (int)m.WParam) SetHandedness();
  break;

Erweitern von Sudoku

Es gibt unzählige Möglichkeiten, den Sudoku-Begleitcode zu erweitern. Im Folgenden finden Sie einige Ideen und Codebeispiele, die Sie dafür verwenden können.

Erweiterte Rückgängig-Unterstützung

Die implementierte Rückgängig-Unterstützung ist äußerst hilfreich, Sie können Sie jedoch erweitern. Hin und wieder mache ich beim Sudoku-Spielen einen Fehler (kaum zu glauben, nicht wahr?), indem ich einen falschen Schluss ziehe, übersehe, dass die ausgefüllte Zahl in der Reihe, der Spalte oder dem Block bereits vorhanden ist oder einen ähnlichen Verstoß begehe. Sobald ich den Fehler mache, habe ich das Spiel verloren. In der Regel bemerke ich den Fehler jedoch erst einige Spielzüge später und bin zu bequem, nach dem ursprünglichen Fehler zu suchen. Hier genügt eine einfache Rückgängig-Funktion nicht. Es bedarf vielmehr einer Funktion, mit der ich zu dem Punkt zurückkehren kann, an dem ich den ursprünglichen Fehler begangen habe. Sowohl mit der bereits implementierten Rückgängig- als auch mit der weiter oben erläuterten Solver-Funktionalität kann dies einfach implementiert werden.

public void UndoUntilSolvableState()
{
  SolverOptions options = new SolverOptions();
  while(Solver.Solve(State, options).Status != 
PuzzleStatus.Solved && Undo());
}

Ein weitere sinnvolle Funktion ist die Wiederholen-Unterstützung. Sie können eine solche Wiederholen-Unterstützung mit einem anderen PuzzleStateStack hinzufügen, dem bei Rückgängig-Vorgängen Zustände hinzugefügt werden. Versuchen Sie es. Beachten Sie jedoch, dass die Zustände beim Wiederholen wieder dem Rückgängig-Stapel hinzugefügt werden müssen.

Drucken von Rätseln

Das Erweitern von Sudoku um eine Druckunterstützung für das aktuelle Rätsel stellt so gut wie keinen Arbeitsaufwand dar. Sie können beispielsweise eine bestimmte Taste auswählen und die OnKeyDown-Methode von PuzzleGrid erweitern, um Code auszuführen, wenn diese Taste gedrückt wird.

using(PrintDialog pd = new PrintDialog())
using(PrintDocument doc = new PrintDocument())
{
  doc.PrintPage += new PrintPageEventHandler(HandlePrintPage);
  pd.Document = doc;
  if (pd.ShowDialog() == DialogResult.OK) doc.Print();
}

Sie können das PrintPage-Ereignis etwa mit folgendem Code verarbeiten.

private void Document_PrintPage(object sender, PrintPageEventArgs e)
{
  DrawToGraphics(e.Graphics, Bounds);
  e.HasMorePages = false;
}

Das war's. Natürlich erhalten Sie so keine außerordentlich beeindruckende Ausgabe. Die Größe des Rätsels beruht auf der aktuellen Größe von PuzzleGrid. Es wird nicht zentriert auf der Seite gedruckt und enthält Elemente wie das aktuell vorgeschlagene Feld. Dies lässt sich durch ein neues, nur für die Druckunterstützung verwendetes PuzzleGrid beheben.

private void Document_PrintPage(object sender, PrintPageEventArgs e)
{
  using(PuzzleGrid pg = new PuzzleGrid())
  {
    pg.State = State;
    pg.ShowSuggestedCells = false;
    pg.ShowIncorrectNumbers = false;
    if (e.MarginBounds.Width > e.MarginBounds.Height)
    {
      pg.Height = e.MarginBounds.Height;
      pg.Width = pg.Height;
    } 
    else
    {
      pg.Width = e.MarginBounds.Width;
      pg.Height = pg.Width;
    }
    using(Matrix m = new Matrix())
    {
      GraphicsState state = e.Graphics.Save();
      m.Translate((e.PageBounds.Width - pg.Width) / 2, 
            (e.PageBounds.Height - pg.Height) / 2);
      e.Graphics.Transform = m;
      pg.DrawToGraphics(e.Graphics, 
        new Rectangle(0, 0, pg.Width, pg.Height));
      e.Graphics.Restore(state);
    }
  }
  e.HasMorePages = false;
}

Sie können auch noch einen Schritt weiter gehen und eine ganze Sammlung von Rätseln drucken. Verwenden Sie bei jedem Aufruf des PrintPage-Handlers die Generator-Klasse, um eine neue PuzzleState-Klasse zu erstellen (statt wie im vorherigen Beispiel die PuzzleState-Klasse des aktuellen Rasters zu verwenden). Verwenden Sie anschließend zum Drucken in etwa diesen Code. Dadurch können Sie eine beliebige Anzahl an Rätseln drucken. Setzen Sie HasMorePages auf true, bis eine ausreichende Anzahl gedruckt wurde.

Unterstützung mehrerer Prozessoren

Die Erstellung von Rätseln erfordert viel Prozessorleistung. Bei Systemen mit mehreren Prozessoren ist es sinnvoll, die Infrastruktur zum Erstellen von Sudoku-Rätseln zu erweitern, um die Vorteile dieser Prozessoren nutzen zu können (die aktuelle Logik für das Erstellen von Rätseln verfügt nur über einen Thread). Das Hinzufügen dieser Unterstützung ist bedeutend einfacher als es klingen mag, da jedes angezeigte Rätsel tatsächlich aus mehreren Rätseln besteht, unter denen das schwierigste ausgewählt wird. Dies erfolgt derzeit in einer sequenziellen Schleife.

private PuzzleState GenerateInternal()
{
  ArrayList puzzles = new ArrayList();
  for(int i=0; i<_options.NumberOfPuzzles; i++) 
  {
    puzzles.Add(GenerateOne());
  }
  puzzles.Sort(new SolverResultsComparer(_options.Techniques));
  return ((SolverResults)puzzles[puzzles.Count-1]).Puzzle;
}

Ändern Sie diese Vorgehensweise, sodass die Aufrufe an GenerateOne im ThreadPool in der Warteschlange platziert werden, und schon wird das gleichzeitige Erstellen von Rätseln unterstützt. Diese Änderung erfordert natürlich eine zusätzliche Synchronisierung, da der Aufruf an puzzles.Sort verschoben werden muss, bis alle Hintergrundthreads ihre jeweiligen Rätsel erstellt und sicher in der Sammlung gespeichert haben. Der Zugriff auf diese Rätsel muss ebenfalls synchronisiert werden. Dies kann etwa mit meiner ThreadPoolWait-Klasse erfolgen, die ich im MSDN Magazine in meiner Kolumne .NET Matters vom Oktober 2004 beschrieben habe (in englischer Sprache).

Kopieren des Rätsels in die Zwischenablage

Möglicherweise möchten Sie eine Kopie des aktuellen Rätsels speichern. Eine einfache Methode besteht darin, eine Textentsprechung des Rätsels in der Zwischenablage zu speichern. Die entsprechende Unterstützung ist bereits in PuzzleState integriert, da die Überschreibung ToString eine Textentsprechung des Rätsels zurückgibt. Sie müssen lediglich die Zeichenfolge in der Zwischenablage speichern. Hierzu müssen Sie nur der Überschreibung OnKeyDown in MainForm ein wenig Code hinzufügen.

if (e.KeyCode == Keys.C && e.Control && 
  thePuzzleGrid.Visible && thePuzzleGrid.Enabled)
{
  if (!thePuzzleGrid.CollectingInk)
  {
    string text = thePuzzleGrid.State.ToString();
    try { Clipboard.SetDataObject(text, true); } 
    catch(ExternalException){ }
  }
}

Weitere Ideen...

Sie können zudem die folgenden Vorschläge in Betracht ziehen.

Implementieren Sie andere Algorithmen zum Lösen und Erstellen von Rätseln.
Implementieren Sie zusätzliche optionale Hinweise für den Spieler, oder ändern Sie den aktuellen Hinweis suggest a cell so, dass erläutert wird, warum dieses Feld vorgeschlagen wird.
Unterstützen Sie zusätzliche Stiftbewegungen.
Ermöglichen Sie Rätselraster, die größer sind als 9x9.
Fügen Sie eine WPF-Benutzeroberfläche (Windows Presentation Foundation) hinzu.
Verwenden Sie WCF (Windows Communication Foundation), um das gemeinsame Lösen von Rätseln über ein Netzwerk zu ermöglichen.
Erstellen Sie eine MCML-Schnittstelle (Media Center Markup Language) für Windows Media Center in Windows Vista. (Beachten Sie, dass meine Sudoku-Implementierung sich bereits gut mit einer Fernbedienung spielen lässt, indem Sie die Pfeiltasten zum Navigieren und die Zahlentasten zum Eingeben von Werten verwenden.)
Fügen Sie weitere spielrelevante Funktionen hinzu, z. B. eine Bestenliste und einen Spieltimer.

Es gibt viele Möglichkeiten, und ich freue mich bereits auf Ihre Ideen. Viel Spaß beim Programmieren!

Danksagung

Vielen Dank an das Tablet PC-Team für die Unterstützung bei diesem Projekt; an David Bessenhoffer für seine hervorragenden Bilder; an Calvin Hsia und Brian Goldfarb für ihre Ideen und Vorschläge; an John Keefe und Luke Stein dafür, dass Sie mir dieses faszinierende Spiel nahe gebracht haben; an Eliot Graff für seine Hilfe beim Veröffentlichen dieses Artikels und Codes; und an Tamara Spiewak für ihre Liebe und Unterstützung (sowohl für mich als auch für Sudoku).

Biografie

Stephen Toub ist Technical Lead des MSDN-Teams von Microsoft. Er ist technischer Redakteur des MSDN Magazine, für das er auch die Kolumne ".NET Matters" schreibt. Stephen hat die Implementierung von Sudoku geschrieben, die ein Teil des Touch Pack ist, einem Softwarepaket, das mit allen Ultra-Mobile PCs geliefert wird.