C# - Programm zum Lösen von Sudokus

(English version) Ein Sudoku von Hand lösen ist nicht weiter schwer, irgendwann überkommt einen Programmierer aber dann die Lust, ein Programm zu schreiben, was Sudokus selber löst. Die Grundidee ist einfach. Das erste freie Kästchen wird ausgefüllt (mit einer 1). Dann wird geprüft ob das Sudoku noch korrekt ist. Falls ja, wird das nächste Kästchen ausgefüllt, falls nicht wird das vorige Kästchen eins hochgezählt. Das wird wiederholt, bis das Sudoku komplett ausgefüllt ist.

Zuallererst habe ich ein Fenster erstellt, welches das Sudoku anzeigt:

<Window x:Class="SudokuSolver.SudokuShowWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="SudokuShowWindow" Height="550" Width="550">
    <Grid Name="Grid1" HorizontalAlignment="Center" VerticalAlignment="Center">
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="50"></ColumnDefinition>
            <ColumnDefinition Width="50"></ColumnDefinition>
            <ColumnDefinition Width="50"></ColumnDefinition>
            <ColumnDefinition Width="50"></ColumnDefinition>
            <ColumnDefinition Width="50"></ColumnDefinition>
            <ColumnDefinition Width="50"></ColumnDefinition>
            <ColumnDefinition Width="50"></ColumnDefinition>
            <ColumnDefinition Width="50"></ColumnDefinition>
            <ColumnDefinition Width="50"></ColumnDefinition>
        </Grid.ColumnDefinitions>
        <Grid.RowDefinitions>
            <RowDefinition Height="50"></RowDefinition>
            <RowDefinition Height="50"></RowDefinition>
            <RowDefinition Height="50"></RowDefinition>
            <RowDefinition Height="50"></RowDefinition>
            <RowDefinition Height="50"></RowDefinition>
            <RowDefinition Height="50"></RowDefinition>
            <RowDefinition Height="50"></RowDefinition>
            <RowDefinition Height="50"></RowDefinition>
            <RowDefinition Height="50"></RowDefinition>
        </Grid.RowDefinitions>

    </Grid>
</Window>

Und der dazugehörige Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Shapes;

namespace SudokuSolver
{
    /// <summary>
   /// Interaktionslogik für SudokuShowWindow.xaml
    /// </summary>
    public partial class SudokuShowWindow : Window
    {
        public SudokuShowWindow()
        {
            InitializeComponent();
        }

        public int[] numbers;
        public TextBlock[] TextBlocks;

        public void refreshValues(int[] _numbers)
        {
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (_numbers[i * 9 + j] != numbers[i * 9 + j])
                    {

                        TextBlocks[i * 9 + j].Text = _numbers[i * 9 + j].ToString();
                    }
                }
            }
        }

        public static SudokuShowWindow newSudokuShowWindow(int[] numbers)
        {
            SudokuShowWindow window = new SudokuShowWindow();
            window.numbers = new int[81];
            window.TextBlocks = new TextBlock[81];
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    window.numbers[i * 9 + j] = numbers[i * 9 + j];
                    TextBlock tb = new TextBlock();
                    tb.Text = numbers[i * 9 + j].ToString();
                    tb.HorizontalAlignment = HorizontalAlignment.Center;
                    tb.VerticalAlignment = VerticalAlignment.Center;
                    Grid.SetRow(tb, i);
                    Grid.SetColumn(tb, j);

                    Thickness thk = new Thickness(0, 0, 0, 0);
                    if (i == 2 || i == 5)
                    {
                        thk.Bottom = 1;
                    }
                    if (i == 3 || i == 6)
                    {
                        thk.Top = 1;
                    }
                    if (j == 2 || j == 5)
                    {
                        thk.Right = 1;
                    }
                    if (j == 3 || j == 6)
                    {
                        thk.Left = 1;
                    }
                    Border border = new Border();
                    border.BorderThickness = thk;
                    border.BorderBrush = Brushes.Black;
                    Grid.SetRow(border, i);
                    Grid.SetColumn(border, j);

                    window.Grid1.Children.Add(border);
                    window.Grid1.Children.Add(tb);

                    window.TextBlocks[i * 9 + j] = tb;
                }
            }
            window.Show();
            return window;
        }


    }
}

Dies wird nun benutzt um das Sudoku anzuzeigen. Das Löseprogramm zeigt das aktuelle Sudoku und öffnet für jede gefundene Lösung ein neues Fenster. MainWindow ist leer, wird lediglich zum Starten des Programmes benötigt.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace SudokuSolver
{
    /// <summary>
   /// Interaktionslogik für MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();

            Thread thread = new Thread(workLoop);
            thread.Start();
        }

        private SudokuShowWindow window;
        private int numberCounter;
        private int[] initialNumbers;
        private int[] numbers;
        List<int[]> Solutions = new List<int[]>();

        private void workLoop()
        {
            //The initial Sudoku which should be solved
            initialNumbers = new int[81]
            {
                5,3,0,   0,7,0,   0,0,0,
                6,0,0,   1,9,5,   0,0,0,
                0,9,8,   0,0,0,   0,6,0,

                8,0,0,   0,6,0,   0,0,3,
                4,0,0,   8,0,3,   0,0,1,
                7,0,0,   0,2,0,   0,0,6,

                0,6,0,   0,0,0,   2,8,0,
                0,0,0,   4,1,9,   0,0,5,
                0,0,0,   0,8,0,   0,7,9
            };
            numbers = new int[81];
            for (int i = 0; i < 81; i++)
            {
                numbers[i] = 0;
            }

            //Invoke window actions because we are not in the main thread
            Application.Current.Dispatcher.BeginInvoke(new Action(() =>
            {
                window = SudokuShowWindow.newSudokuShowWindow(initialNumbers);
            }));

            //Position of the "cursor" in the sudoku
            numberCounter = 0;

            int ctr = 0;
            bool noi = false;


            while (true)
            {
                if (isItValid())
                {
                    noi = false;

                    //A valid solution!
                    if (numberCounter > 80)
                    {
                        int[] totalNumbers = new int[81];
                        for (int i = 0; i < 81; i++)
                        {
                            totalNumbers[i] = initialNumbers[i];
                            if (totalNumbers[i] == 0)
                            {
                                totalNumbers[i] = numbers[i];
                            }
                        }

                        bool eq = false;
                        foreach (int[] solution in Solutions)
                        {
                            bool leq = true;
                            for (int i = 0; i < 81; i++)
                            {
                                if (solution[i] != totalNumbers[i])
                                {
                                    leq = false;
                                }
                            }
                            if (leq)
                            {
                                eq = true;
                            }

                        }
                        if (!eq)
                        {
                            int[] tmp = new int[81];
                            for (int i = 0; i < 81; i++)
                            {
                                tmp[i] = totalNumbers[i];
                            }
                            Solutions.Add(tmp);
                        }
                        else
                        {
                            System.Console.WriteLine("Done!");
                            break;
                        }

                        Application.Current.Dispatcher.BeginInvoke(new Action(() =>
                        {
                            SudokuShowWindow.newSudokuShowWindow(totalNumbers);
                        }));

                        //Check for other solutions?

                        noi = true;
                        while (true)
                        {
                            numberCounter--;
                            if (initialNumbers[numberCounter] == 0)
                            {
                                if (numbers[numberCounter] >= 9)
                                {
                                    numbers[numberCounter] = 0;
                                }
                                else
                                {
                                    numbers[numberCounter]++;
                                    break;
                                }
                            }
                        }
                    }

                    if (numberCounter > 80)
                    {
                        break;
                    }

                    if (numbers[numberCounter] == 0 && initialNumbers[numberCounter] == 0)
                    {
                        iterateOne();
                    }
                    else
                    {
                        if (!noi)
                        {
                            increaseNumberCounter();
                        }
                    }
                }
                else
                {
                    if (numberCounter > 80 || numberCounter < 0)
                    {
                        break;
                    }
                    if (numbers[numberCounter] >= 9)
                    {
                        decreaseOne();
                        Application.Current.Dispatcher.BeginInvoke(new Action(() =>
                        {
                            int[] totalNumbers = new int[81];
                            for (int i = 0; i < 81; i++)
                            {
                                totalNumbers[i] = initialNumbers[i];
                                if (totalNumbers[i] == 0)
                                {
                                    totalNumbers[i] = numbers[i];
                                }
                            }
                            window.refreshValues(totalNumbers);
                        }));

                    }
                    else
                    {
                        iterateOne();
                    }
                }
                ctr++;
                if (ctr > 1000)
                {
                    ctr = 0;
                    Application.Current.Dispatcher.BeginInvoke(new Action(() =>
                    {
                        int[] totalNumbers = new int[81];
                        for (int i = 0; i < 81; i++)
                        {
                            totalNumbers[i] = initialNumbers[i];
                            if (totalNumbers[i] == 0)
                            {
                                totalNumbers[i] = numbers[i];
                            }
                        }
                        window.refreshValues(totalNumbers);
                    }));
                    Thread.Sleep(1);
                }
            }
            Application.Current.Dispatcher.BeginInvoke(new Action(() =>
            {
                window.Close();
            }));
        }

        void increaseNumberCounter()
        {
            numberCounter++;
            while (numberCounter <= 80 && initialNumbers[numberCounter] != 0)
            {
                numberCounter++;
            }
        }

        void iterateOne()
        {
            if (numberCounter > 80)
            {
                return;
            }
            while (initialNumbers[numberCounter] != 0)
            {
                numberCounter++;
            }
            numbers[numberCounter]++;
        }

        void decreaseOne()
        {
            if (numberCounter > 80)
            {
                numberCounter = 80;
            }
            numbers[numberCounter] = 0;
            if (numberCounter == 0)
            {
                return;
            }

            while (numberCounter >= 0)
            {
                numberCounter--;
                while (numberCounter > 0 && initialNumbers[numberCounter] != 0)
                {
                    numberCounter--;
                }
                if (numberCounter < 0)
                {
                    return;
                }
                if (numbers[numberCounter] < 9)
                {
                    numbers[numberCounter]++;
                    return;
                }
                else
                {
                    numbers[numberCounter] = 0;
                }
            }
        }

        bool isItValid()
        {
            int[] totalNumbers = new int[81];
            for (int i = 0; i < 81; i++)
            {
                totalNumbers[i] = initialNumbers[i];
                if (totalNumbers[i] == 0)
                {
                    totalNumbers[i] = numbers[i];
                }
            }
            //Check Horizontal
            List<int> testList;
            for (int i = 0; i < 9; i++)
            {
                testList = new List<int>();
                for (int j = 0; j < 9; j++)
                {
                    if (testList.Contains(totalNumbers[i * 9 + j]))
                    {
                        //Invalid
                        return false;
                    }
                    if (totalNumbers[i * 9 + j] != 0)
                    {
                        testList.Add(totalNumbers[i * 9 + j]);
                    }
                }
            }

            //Check Vertical
            for (int j = 0; j < 9; j++)
            {
                testList = new List<int>();
                for (int i = 0; i < 9; i++)
                {
                    if (testList.Contains(totalNumbers[i * 9 + j]))
                    {
                        //Invalid
                        return false;
                    }
                    if (totalNumbers[i * 9 + j] != 0)
                    {
                        testList.Add(totalNumbers[i * 9 + j]);
                    }
                }
            }
            //Check squares
            for (int ii = 0; ii < 3; ii++)
            {
                for (int jj = 0; jj < 3; jj++)
                {
                    testList = new List<int>();
                    for (int i = ii * 3; i < ii * 3 + 3; i++)
                    {
                        for (int j = jj * 3; j < jj * 3 + 3; j++)
                        {
                            if (testList.Contains(totalNumbers[i * 9 + j]))
                            {
                                //Invalid
                                return false;
                            }
                            if (totalNumbers[i * 9 + j] != 0)
                            {
                                testList.Add(totalNumbers[i * 9 + j]);
                            }
                        }
                    }
                }
            }
            //Valid
            return true;
        }
    }
}