Bauen mit Microsoft - Sudoku

Sudoku, ein japanisches Spiel, bei dem es gilt die Zahlen 1 bis 9 auf einem Spielfeld aus 9 mal 9 Feldern so zu verteilen, dass a) in jeder Reihe, b) in jeder Spalte und c) in 3 mal 3 Unterfeldern jeweils jede Zahl nur einmal vorkommt. Klingt einfach, ist es aber nicht.

Gut, dass wir einen Rechner haben und Visual C# 2005 Express Edition. Wir wollen ein Programm bauen, dass uns beliebige Sudokus löst. Der Algorithmus dahinter wird im Laufe des Bauens klar.

Schritt 1: Am Anfang war das Fenster…

Wir starten Visual C# Express und erzeugen im Menü „Datei“ ein neues Projekt, Typ Windows-Anwendung und verpassen dem Ding den Namen Sudoko-Löser und los geht’s.

im Menü „Datei“ ein neues Projekt erzeugen

Zunächst einmal soll der Benutzer seine InitializeGrid fügen wir in die Klasse SudokuControl: Aufgabe eingeben können, dann mit einer Schaltfläche den Lösungsvorgang starten und danach die Lösung sehen. Also brauchen wir zunächst etwas, das die Spielfläche darstellt. Dazu Rechtsklick auf Sudoku-Löser rechts oben in der Projektmappe und im Menü „Hinzufügen Benutzersteuerelement“ wählen. Wir werden nach dem Namen gefragt, SudokuControl soll das Baby heißen.

Schritt 2: Der Arbeiter

Unser Control sieht noch sehr langweilig aus, daher gehen wir in die Vollen: Rechte Maustaste auf die graue Fläche und „Code anzeigen“ wählen. Unser Spielfeld besteht aus 9 mal 9 Textfeldern. Aber unsere Textfelder können mehr, sie helfen uns bei der Lösung. Dazu müssen Sie sich merken können, welche möglichen Werte das Spielfeld hier haben kann. Daher fügen wir direkt vor dem Text public partial class SudokuControl folgendes ein:

public class GameBoardCell : TextBox { public bool IsBlocked; protected SudokuControl _Mother; protected int _Value; public int Value { get { return _Value; } } protected List<int> _PossibleValues; public GameBoardCell(SudokuControl Mother) { _Value = 0; _Mother = Mother; } public void SetPossibleValues(List<int> possibles) { _PossibleValues = possibles; _Value = _PossibleValues[0]; _PossibleValues.RemoveAt(0); this.Text = _Value.ToString(); } public bool StepNextPossibleEntry() { if (IsBlocked == true) return false; if (_PossibleValues.Count > 0) { _Value = _PossibleValues[0]; _PossibleValues.RemoveAt(0); this.Text = _Value.ToString(); return true; } _Value = 0; return false; } protected override void OnTextChanged(EventArgs e) { _Value = Int16.Parse(this.Text); if (_Mother.IsInEditMode == true) IsBlocked = true; base.OnTextChanged(e); } }

Klicken Sie auf die Abbildung um den Code zu erhalten!

Man sieht, dass wir die Klasse „Textbox“ verwenden und erweitern. Die neue Klasse kann weitere mögliche Werte verwalten und kennt einen Modus zum Editieren und einen zum Berechnen.

Schritt 3: Darstellung

Weiter unten im Text erweitern wir die Klasse SudokuControl, so dass sie ein 9 mal 9 Felder großes Spielfeld darstellt. Natürlich wollen wir nicht jedes Feld einzeln malen, das soll der Rechner erledigen:

public partial class SudokuControl : UserControl { public int nSizeSubBoard; public int nSizeBoard; public bool IsInEditMode; private GameBoardCell[,] GameBoard; public SudokuControl() { nSizeSubBoard = 3; nSizeBoard = 9; GameBoard = new GameBoardCell[nSizeBoard, nSizeBoard]; IsInEditMode = true; InitializeComponent(); InitializeGrid(); } private void InitializeGrid() { for (int nZeile = 0; nZeile < nSizeBoard; nZeile++) for (int nSpalte = 0; nSpalte < nSizeBoard; nSpalte++) { GameBoardCell newBox = new GameBoardCell(this); newBox.Width = this.Width / nSizeBoard; newBox.Height = this.Height / nSizeBoard; newBox.Location = new System.Drawing.Point((this.Width / nSizeBoard) * nSpalte, (this.Height / nSizeBoard) * nZeile); this.Controls.Add(newBox); GameBoard[nZeile, nSpalte] = newBox; } } }

Komponenten. Doppelklick auf SudokuControl und das Control liegt in unserem Fenster. Jetzt kann man mit dem grünen Pfeil in der Leiste oben das Programm starten und sieht sein Spielfeld.

Schritt 4: Die Aufgabe knacken…

Zurück zum SudokuControl.cs Fenster. Direkt unter der Funktion InitializeGrid fügen wir in die Klasse SudokuControl:

public void Solve() { IsInEditMode = false; Compute(0, 0); IsInEditMode = true; } private bool FindNextCell(ref int Zeile, ref int Spalte) { Zeile++; if (Zeile == nSizeBoard) { Spalte++; Zeile = 0; if (Spalte == nSizeBoard) return true; } return false; } private bool Compute(int ActZeile, int ActSpalte) { int NextZeile = ActZeile; int NextSpalte = ActSpalte; bool ValueFound; List<int> PossibleValues; if (GameBoard[ActZeile, ActSpalte].IsBlocked == false) { PossibleValues = new List<int>(); for (int Value = 1; Value <= nSizeBoard; Value++) { ValueFound = false; //Teste Zeilen for (int Zeile = 0; Zeile < nSizeBoard && ValueFound == false; Zeile++) { if (GameBoard[Zeile, ActSpalte].Value == Value) ValueFound = true; }

Klicken Sie auf die Abbildung um den Code zu erhalten!

//Teste Spalten for (int Spalte = 0; Spalte < nSizeBoard && ValueFound == false; Spalte++) { if (GameBoard[ActZeile, Spalte].Value == Value) ValueFound = true; } //Teste SubGameBoard int ZeileSubBoardStart = (ActZeile/nSizeSubBoard)*nSizeSubBoard; for (int Zeile = ZeileSubBoardStart; Zeile < ZeileSubBoardStart + nSizeSubBoard; Zeile++) { int SpalteSubBoardStart = (ActSpalte / nSizeSubBoard) * nSizeSubBoard; for(int Spalte = SpalteSubBoardStart; Spalte < SpalteSubBoardStart+nSizeSubBoard; Spalte++) if (GameBoard[Zeile, Spalte].Value == Value) ValueFound = true; } if (ValueFound == false) PossibleValues.Add(Value); } if (PossibleValues.Count == 0) return false; GameBoard[ActZeile, ActSpalte].SetPossibleValues(PossibleValues); } if (FindNextCell(ref NextZeile, ref NextSpalte) == true && GameBoard[ActZeile, ActSpalte].Value!=0 ) { return true; // We are done } do { if (Compute(NextZeile, NextSpalte) == true) return true; } while (GameBoard[ActZeile, ActSpalte].StepNextPossibleEntry() == true); return false; } }

Klicken Sie auf die Abbildung um den Code zu erhalten!

Was treiben wir hier? Die Funktion Compute wird aufgerufen und ermittelt für jede Position auf dem Spielfeld die möglichen Zahlenwerte. Danach setzt sie einen möglichen Wert auf die Position und ruft sich selbst für die Nachbarposition auf. Schaffen wir es einen Wert für alle Zellen zu ermitteln, haben wir es geschafft. Gehen uns unterwegs die möglichen Zahlen aus, müssen wir einen Schritt zurück und es mit einem anderen Wert weiter probieren. Wir gehen zurück zu Form1.cs [Entwurf] und fügen aus der Toolbox einen Button hinzu. Doppelklick auf den Button und den Code sudokuControl1.Solve();

Fertig.

Mit dem grünen Pfeil starten, Sudoku Aufgabe eingeben und lösen lassen…