AdSense

Sunday, 5 October 2014

C# - Program to solve a sudoku

(Deutsche Version) To solve a sudoku by hand is not that difficult. But after some time, a programmer wants to write a program which can also do this. The basic principle is pretty easy. The first empty bracket is filled (with a 1). Afterwards, the program checks whether the sudoku is still correct. If so, the next bracket is filled, if not, the previous bracket is counted up about 1. This is continued until the Sudoku is completely filled.

First, I created a window which shows a sudoku:

<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>

And the corresponding 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;
        }


    }
}

This is now used to show the sudoku. The solver shows the actual sudoku and opens a new window for every found solution. MainWindow is empty, it is just used to start the program.

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;
        }
    }
}

No comments:

Post a Comment