Montag, 10. November 2014

Kompletter Quellcode und .exe für Sudoku Programm

Ich habe nun das komplette Programm zum Thema Sudoku, welches aus den Codeteilen der vorigen Posts besteht, hochgeladen, auf GitHub findet ihr einmal den Quellcode, und hier eine Installationsdatei, mit welcher das Programm auch ohne Visual Studio installiert gestartet werden kann.


Montag, 3. November 2014

Sudokus mit C# generieren

In diesem Post möchte ich die Erzeugung eines Sudokus beliebiger Schwierigkeit mit C# erklären. Es empfiehlt sich hierfür sehr, die vorigen Posts zum Thema Sudokus zu lesen.
Die Klasse SudokuCreator ist für das Generieren eines Sudokus zuständig, die Funktion CreateRandomSudoku() erledigt dies. Sie erwartet 2 Parameter, der erste gibt die gewünschte Schwierigkeit des Sudokus wieder, der zweite die Anzahl der zu löschenden Felder.
Zuerst wird ein zufälliges ausgefülltes Sudoku erstellt, hierbei wird das gleiche Prinzip wie beim Lösen eines Sudokus durch Ausprobieren verwendet.
Danach wird in einer Schleife immer jeweils ein zufälliges Feld gelöscht und geprüft, ob das Sudoku noch eindeutig lösbar (hierfür wird das Sudoku durch Ausprobieren gelöst und alle Möglichkeiten werden beachtet) und maximal so schwer wie die gewünschte Schwierigkeit ist. Falls ja, wird mit dem neuen Sudoku weitergemacht, ansonsten mit dem alten. Dies wird solange wiederholt, bis die gewünschte Anzahl an Feldern gelöscht wurde und das aktuelle Sudoku wird zurückgegeben.
Nun kann es aber natürlich sein, dass die Felder, besonders ungünstig gelöscht werden und ein Weiterarbeiten mit dem Sudoku nur schwer möglich ist. Deswegen wird die Anzahl der Versuche, ein Feld zu löschen, gezählt, steigt dieser Zähler zu hoch, wird mit dem komplett gelösten Sudoku neu begonnen.
Aber auch dieses Ereignis zählen wir, da es auch sein kann, dass das erzeugte Sudoku besonders ungünstig ist. Muss zu oft neu begonnen werden, erzeugen wir ein komplett neues Sudoku.
Und hier der Code:

    public class SudokuCreator
    {
        bool Finished;
        Random Rnd;
        Sudoku Result;

        public Sudoku CreateRandomSudoku(int Difficulty, int targetdels)
        {
            bool Start = true;
          
            bool Done = false;
            int Deleted = 0;
            int Tolerance = 10;

            // Various counters, we count the iterations we do in case the created instance somehow gets stuck, then we reset
            int FieldDelCounter = 0;
            int ResetCounter1 = 0;
            int ResetCounter2 = 0;
            Sudoku NewSudoku = null;
            Sudoku Fallback = null;
            int FallbackCounter = 0;

            while (!Done)
            {
                if (ResetCounter1 > 40)
                {
                    ResetCounter1 = 0;
                    Start = true;
                }
                if (ResetCounter2 > 40)
                {
                    ResetCounter2 = 0;
                    Start = true;
                }

                if (Start)
                {
                    // first, create a complete sudoku using brute force
                    NewSudoku = new Sudoku(new List<int>());
                    List<Sudoku.Field> ToDo = new List<Sudoku.Field>();
                    for (int i = 0; i < 9; i++)
                    {
                        for (int j = 0; j < 9; j++)
                        {
                            ToDo.Add(NewSudoku.Fields[i][j]);
                        }
                    }
                    Rnd = new Random();
                    Finished = false;
                    BruteForce(ToDo, 0, NewSudoku);
                    FallbackCounter = 0;
                    NewSudoku = Result.Copy();
                    Start = false;
                    Fallback = null;
                }

                Sudoku Cloned = NewSudoku.Copy();
                int difficulty = Difficulty;
                // take out one field and check if solutions still is unique and not harder than desired
                if (DeleteField(Cloned, ref difficulty))
                {
                    NewSudoku = Cloned;
                    Deleted++;

                    if (NewSudoku.Difficulty == Difficulty && Deleted >= targetdels)
                    {   // in this case we are done  
                        NewSudoku.Difficulty = difficulty;
                        return NewSudoku;
                    }
                    else if (difficulty == Difficulty && Deleted < targetdels)
                    { // matching difficulty found but more fields have to be deleted
                        Fallback = NewSudoku.Copy();
                    }
                    else if (Deleted >= targetdels + Tolerance) // enough fields deleted but not desired difficulty
                    {
                        if (FallbackCounter < 100 && Fallback != null) // first try fallback
                        {
                            NewSudoku = Fallback.Copy();
                        }
                        else
                        {
                            NewSudoku = Result.Copy();
                            ResetCounter1++;
                            FallbackCounter = 0;
                        }
                        Deleted = 0;

                    }
                }
                else
                {
                    FieldDelCounter++;
                    if (FieldDelCounter > 100) // probably no more field can be deleted to get the desired difficulty
                    {
                        FieldDelCounter = 0;
                        NewSudoku = Result.Copy();
                        Deleted = 0;
                        ResetCounter2++;
                    }
                    continue;
                }
            }

            return Result;
        }

        private bool DeleteField(Sudoku temp, ref int difficulty)
        {
            int i = Rnd.Next(0, 9); ;
            int j = Rnd.Next(0, 9); ;

            // select random not yet deleted field
            while (!temp.Fields[i][j].Filled) {
                i = Rnd.Next(0, 9);
                j = Rnd.Next(0, 9);
            }

            temp.Fields[i][j].Value = 0;
            temp.Fields[i][j].Filled = false;
            SudokuSolver Test = new SudokuSolver();
            int counter = 0;
            int Difficulty = difficulty;
            // check the desired characteristics
            Sudoku Temp = Test.Solve(temp.Copy(), true, Difficulty);
            if (Temp == null)
                return false;
            temp.Difficulty = Temp.Difficulty;
            if (Temp.NrSolutions > 1 || Temp.Difficulty > Difficulty)
                return false;
            else
                return true;
        }

        private void BruteForce(List<Sudoku.Field> ToDo, int pos, Sudoku Temp)
        {   // the brute force implementation for creating complete sudokus
            if (Finished)
                return;
            for (int i = 1; i <= 9; i++)
            {
                Sudoku Copied = Temp.Copy();
                Copied.Fields[ToDo[pos].i][ToDo[pos].j].Filled = true;
                Copied.Fields[ToDo[pos].i][ToDo[pos].j].Value = Rnd.Next(1, 10);
                bool Valid = true;
                foreach (Sudoku.Field f in Copied.GetGroup(ToDo[pos].i, ToDo[pos].j))
                {
                    if (f.Filled && f.Value == Copied.Fields[ToDo[pos].i][ToDo[pos].j].Value)
                    {
                        Valid = false;
                        break;
                    }
                }
                if (Valid)
                {
                    if (pos < ToDo.Count - 1)
                        BruteForce(ToDo, pos + 1, Copied);
                    else
                    {
                        Finished = true;
                        Result = Copied;
                    }
                }
            }
        }
    }

Montag, 27. Oktober 2014

Sudokus mit C# lösen

Nachdem sich die vorigen 2 Posts mit den Grundlagen zur Sudoku Generierung / Lösung beschäftigt haben, möchte ich im heutigen Post mit der Implementierung anfangen. Hierüber wird es auch 2 Posts geben, dieser behandelt die Lösung von Sudokus, der nächste die Generierung.

Die Klasse Sudoku dient der Handhabung von Sudokus. Sie enthält ein 2-dimensionales Array vom Typ Field. Diese Klasse repräsentiert ein einzelnes Feld im Sudoku und speichert dementsprechend Position im Sudoku, (eventuellen) Wert und die Kandidatenliste. Die beiden Indizes des Arrays bezeichnen natürlich Zeile und Spalte des Feldes im Sudoku. Die Klasse Sudoku bietet die nützlichen Methoden GetRow(), GetColumn() und GetBox(), welche alle Felder in der zum übergebenen Feld gehörigen Reihe, Spalte oder Box zurückgibt.
Die Klasse SudokuSolver ist für die Lösung des Sudokus zuständig, die Methode Solve() tut dieses. In dieser zählt die Variable Remaining die noch zu lösenden Felder. Anfangs wird die Methode InitCandidates() aufgerufen, in welcher Remaining korrekt gesetzt wird und die Kandidatenliste jedes  Feldes initialisiert wird. In Solve() läuft dann eine Schleife solange, bis Remaining = 0. Die Variable Difficulty speichert die aktuelle Schwierigkeit, anfangs ist diese auf 1. Der Reihe nach werden dann die im vorigen Post vorgestellten Methoden zum Lösen eines Sudokus aufgerufen, sofern ihre Schwierigkeit <= Difficulty. Ist eine der Methoden erfolgreich, d.h. kann eine Regel erfolgreich angewendet werden, wird Difficulty auf 1 gesetzt und die Schleife springt zum Anfang. Ist der Schleifenrumpf einmal durchlaufen worden ohne dass sich Remaining verändert hat, wird Difficulty um 1 erhöht. Bei Difficulty = 4 wird schließlich die Funkion NonLogic() aufgerufen, welche das Sudoku durch Brute Force löst.
Das Programm merkt sich die höchste Schwierigkeit und gibt diese zurück, sodass über diese Methode gesagt werden kann, wie "schwierig" das gelöste Sudoku ist.
Ich denke zu den einzelnen Lösungsfunktionen brauche ich nicht viel zu sagen, da die Implementierung einfach eine direkte Umsetzung des Lösungsprinzips ist, und hoffe, der folgende Quellcode ist somit verständlich:

    public class Sudoku
    {
        public class Field
        {
            public int Value;
            public List<int> Candidates;
            public bool Filled;

            public int i;
            public int j;
            public bool NewFound;

            public Field(int _i, int _j)
            {
                Candidates = new List<int>();
                Filled = false;
                i = _i;
                j = _j;
                NewFound = false;
            }

            public Field Copy()
            {
                Field Result = new Field(i, j);
                foreach (int ii in Candidates)
                    Result.Candidates.Add(ii);
                Result.Filled = Filled;
                Result.Value = Value;
                Result.NewFound = NewFound;
                return Result;
            }
        }

        public Field[][] Fields;
                    public int Difficulty;
            public int Rem1;
            public int Rem2;
            public int Rem3;
            public int NrSolutions;

        public Sudoku Copy()
        {
            Sudoku Result = new Sudoku(new List<int>());
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    Result.Fields[i][j] = Fields[i][j].Copy();
                }
            }
            Result.Difficulty = Difficulty;
            Result.Rem1 = Rem1;
            Result.Rem2 = Rem2;
            Result.Rem3 = Rem3;
            Result.NrSolutions = NrSolutions;

            return Result;
        }

        public Sudoku(List<int> values)
        {
            Difficulty = 1;
            Rem1 = -1;
            Rem2 = -1;
            Rem3 = -1;
            NrSolutions = 0;

            Fields = new Field[9][];
            for (int i = 0; i < 9; i++)
            {
                Fields[i] = new Field[9];
                for (int j = 0; j < 9; j++)
                {
                    Fields[i][j] = new Field(i, j);
                }
            }

            // fills the Sudoku with the given values
            int a = 0;
            int b = 0;
            for (int x = 0; x < values.Count; x++)
            {
                if (values[x] != 0)
                {
                    Fields[b][a].Value = values[x];
                    Fields[b][a].NewFound = true;
                    Fields[b][a++].Filled = true;
                }
                else
                    a++;
                if (a > 8)
                {
                    a = 0;
                    b++;
                }
            }
        }

        // returns all fields in a column
        public List<Field> GetColumn(int i, int j)
        {
            List<Field> Result = new List<Field>();
            for (int a = 0; a < 9; a++)
            {
                if (a != i)
                    Result.Add(Fields[a][j]);
            }
            return Result;
        }

        // returns all fields in a row
        public List<Field> GetRow(int i, int j)
        {
            List<Field> Result = new List<Field>();
            for (int a = 0; a < 9; a++)
            {
                if (a != j)
                    Result.Add(Fields[i][a]);
            }
            return Result;
        }

        // returns all fields in a box
        public List<Field> GetBox(int i, int j)
        {
            List<Field> Result = new List<Field>();
            int iStart = i - i % 3;
            int jStart = j - j % 3;

            for (int a = 0; a < 3; a++)
            {
                for (int b = 0; b < 3; b++)
                {
                    if (iStart + a != i || jStart + b != j)
                        Result.Add(Fields[iStart + a][jStart + b]);
                }

            }
            return Result;
        }

        // returns all fields in a group
        public List<Field> GetGroup(int i, int j)
        {
            List<Field> Row = GetRow(i, j);
            List<Field> Column = GetColumn(i, j);
            List<Field> Box = GetBox(i, j);
            List<Field> Result = new List<Field>();
            Result.AddRange(Row);
            Result.AddRange(Column);
            Result.AddRange(Box);
            return Result;
        }

        // returns all fields from either a row, column or box
        public List<Field> GetGroupPart(int i, int j, int part)
        {
            switch (part)
            {
                case 0:
                    return GetRow(i, j);
                case 1:
                    return GetColumn(i, j);
                case 2:
                    return GetBox(i, j);
                default:
                    return null;
            }
        }

        public string Debug(int Difficulty)
        {
            string Result = "";
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    Result += Fields[i][j].Value.ToString() + " ";
                }
                Result += Environment.NewLine;
            }
            Result += "  Difficulty: " + Difficulty.ToString();
            return Result;
        }

        public bool BelongsToBox(int i, int j, Field f)
        {
            int iStart = i - i % 3;
            int jStart = j - j % 3;
            if (f.i >= iStart && f.i <= iStart + 2 && f.j >= jStart && f.j <= jStart + 2)
                return true;
            else
                return false;
        }
    }

    public class SudokuSolver
    {
        Sudoku Input; // Workung Sudoku
        int SolCounter; // Solution counter
        int Remaining; // Fields yet to be found
        bool Finished; // true when done

        bool Changed;

        public Sudoku Solve(Sudoku suk, bool count, int maxDifficulty)
        {
            Remaining = 81;
            Input = suk;
            InitCandidates();
            SolCounter = 0;

            int Difficulty = 1;
            int HighestDifficulty = 1;

            Input.Rem1 = -1;
            Input.Rem2 = -1;
            Input.Rem3 = -1;

            while (Remaining > 0)
            {
                int oldRem = Remaining;

                Grade0();

                if (Grade1())
                    continue;

                if (Difficulty >= 2)
                {
                    if (Input.Rem1 == -1)
                        Input.Rem1 = Remaining;

                    if (GradeX(2))
                    {
                        continue;
                    }
                    if (CandidateLine())
                    {
                        continue;
                    }
                }

                if (Difficulty >= 3)
                {
                    if (Input.Rem2 == -1)
                        Input.Rem2 = Remaining;

                    if (GradeX(3))
                        continue;
                    if (XWing())
                    {
                        continue;
                    }
                }

                if (Difficulty >= 4)
                {   // this completes the sudoku in one step
                    if (Input.Rem3 == -1)
                        Input.Rem3 = Remaining;

                    NonLogic(count);
                }

                if (Remaining == oldRem)
                {
                    Difficulty++;
                    if (Difficulty > HighestDifficulty)
                        HighestDifficulty = Difficulty;

                    if (Difficulty > maxDifficulty)
                    {
                        Input.Difficulty = HighestDifficulty;
                        Input.NrSolutions = 0;
                        return null;
                    }
                    if (Difficulty > 4)
                        break;
                }
                else
                    Difficulty = 1;
            }

            // brute force counts the number of solutions
            Input.NrSolutions = SolCounter;
            if (Input.NrSolutions == 0)
                Input.NrSolutions = 1; // no brute force used
       
            Input.Difficulty = HighestDifficulty;
            return Input;
        }

        private void InitCandidates()
        {
            Remaining = 0;
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!Input.Fields[i][j].Filled)
                    {
                        for (int z = 1; z <= 9; z++)
                        {
                            Input.Fields[i][j].Candidates.Add(z);
                        }
                        Remaining++;
                        Input.Fields[i][j].NewFound = false;
                    }
                    else
                        Input.Fields[i][j].NewFound = true;
                }
            }
        }

        private bool Grade0()
        {
        bool Change = false;

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (Input.Fields[i][j].NewFound)
                    {
                        foreach (Sudoku.Field f in Input.GetGroup(i, j))
                        {
                            if (!f.Filled)
                            {   // remove all candidates which have already been placed in the group
                                if (f.Candidates.Remove(Input.Fields[i][j].Value))
                                    Change = true;
                            }
                        }
                     Input.Fields[i][j].NewFound = false;
                    }
                }
            }

            return Change;
        }

        private bool Grade1()
        {
            // Direct = Naked Single
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!Input.Fields[i][j].Filled && Input.Fields[i][j].Candidates.Count == 1)
                    {   // for fields with only one remaining candidate chose that
                        Input.Fields[i][j].Value = Input.Fields[i][j].Candidates[0];
                        Input.Fields[i][j].Filled = true;
                        Input.Fields[i][j].NewFound = true;
                        Remaining--;
                        return true;
                    }
                }
            }
            // Inverse = Hidden Single
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!Input.Fields[i][j].Filled)
                    {
                        for (int a = 0; a < Input.Fields[i][j].Candidates.Count; a++)
                        {
                            for (int part = 0; part < 3; part++)
                            {
                                bool Found = false;
                                foreach (Sudoku.Field f in Input.GetGroupPart(i, j, part))
                                {
                                    if (!f.Filled && f.Candidates.Contains(Input.Fields[i][j].Candidates[a]))
                                    {
                                        Found = true;
                                        break;
                                    }
                                }
                                if (!Found)
                                {   // if one candidate of field X never occurs in the candidate lists of the other fields in one part of the group of X, chose that
                                    Input.Fields[i][j].Value = Input.Fields[i][j].Candidates[a];
                                    Input.Fields[i][j].Filled = true;
                                    Input.Fields[i][j].NewFound = true;
                                    Remaining--;
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
            return false;
        }

        private bool GradeX(int x)
        {
            // Direct = Hidden Double, Triple etc.
            Changed = false;
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!Input.Fields[i][j].Filled && Input.Fields[i][j].Candidates.Count >= x)
                    {
                        for (int a = 0; a < Input.Fields[i][j].Candidates.Count; a++)
                        {
                            List<int> Temp = new List<int>();
                            Temp.Add(a);
                            RekGradeX(i, j, Temp, 1, x); // recursively try the direct version
                        }
                    }
                }
            }

            // Opposite = Naked Double, Triple etc.
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!Input.Fields[i][j].Filled && Input.Fields[i][j].Candidates.Count == x)
                    {
                        for (int part = 0; part < 3; part++)
                        {
                            int FoundCounter = 0;
                            List<int> FoundI = new List<int>();
                            List<int> FoundJ = new List<int>();
                            foreach (Sudoku.Field f in Input.GetGroupPart(i, j, part))
                            {
                                if (!f.Filled && f.Candidates.Count == x)
                                {
                                    bool Found = true;
                                    for (int z = 0; z < x; z++)
                                    {
                                        if (!f.Candidates.Contains(Input.Fields[i][j].Candidates[z]))
                                        {
                                            Found = false;
                                            break;
                                        }
                                    }
                                    if (Found)
                                    {
                                        FoundCounter++;
                                        FoundI.Add(f.i);
                                        FoundJ.Add(f.j);
                                    }
                                }

                            }
                            // now we know that all of the x candidates of field i, j appear in x - 1 other fields in that part of the group
                            if (FoundCounter == x - 1)
                            {   // they have to be filled to one of these x fields, delete the candidates in all other fields of the group part
                                bool ErasedSomething = false;
                                foreach (Sudoku.Field ff in Input.GetGroupPart(i, j, part))
                                {
                                    if (FoundI.Contains(ff.i) && FoundJ.Contains(ff.j))
                                        continue;
                                    for (int z = 0; z < x; z++)
                                    {
                                        if (ff.Candidates.Remove(Input.Fields[i][j].Candidates[z]))
                                            ErasedSomething = true;
                                    }
                                }
                                return ErasedSomething;
                            }
                        }
                    }
                }
            }
            if (Changed)
                return true;
            else
                return false;
        }

        private void RekGradeX(int i, int j, List<int> current, int depth, int x)
        {
            if (depth < x)
            {
                for (int a = 0; a < Input.Fields[i][j].Candidates.Count; a++)
                {
                    if (!current.Contains(a))
                    {
                        List<int> Copied = Copy(current);
                        Copied.Add(a);
                        RekGradeX(i, j, Copied, depth + 1, x);
                    }
                }
            }
            else
            {
                // when reached the bottom of the recursion, x candidates of field i, j have been selected
                for (int part = 0; part < 3; part++)
                {
                    int Found = 0;
                    List<int> FoundI = new List<int>();
                    List<int> FoundJ = new List<int>();

                    foreach (Sudoku.Field f in Input.GetGroupPart(i, j, part))
                    {
                        if (!f.Filled)
                        {
                            for (int z = 0; z < x; z++)
                            {
                                if (f.Candidates.Contains(Input.Fields[i][j].Candidates[current[z]]))
                                {
                                    Found++;
                                    FoundI.Add(f.i);
                                    FoundJ.Add(f.j);
                                    break;
                                }
                            }
                            if (Found > x - 1)
                                break;
                        }
                    }
                    if (Found == x - 1)
                    {
                        // now we know that the selected x candidates only occur in x - 1 fields in that part of the group
                        bool Match = true;
                        for (int a = 0; a < FoundI.Count; a++)
                        {
                            for (int z = 0; z < x; z++)
                            {   // now we check if those x - 1 fields contain all x candidates
                                if (!Input.Fields[FoundI[a]][FoundJ[a]].Candidates.Contains(Input.Fields[i][j].Candidates[current[z]]))
                                {
                                    Match = false;
                                    break;
                                }
                            }
                        }
                        if (Match)
                        {   // if yes, they have to be filled to one of these x fields, delete all other candidates
                            List<int> Candidates = new List<int>();

                            for (int z = 0; z < x; z++)
                            {
                                Candidates.Add(Input.Fields[i][j].Candidates[current[z]]);
                            }

                            if (Input.Fields[i][j].Candidates.Count() != Candidates.Count)
                                Changed = true;
                            Input.Fields[i][j].Candidates = new List<int>();
                            for (int z = 0; z < x; z++)
                            {
                                Input.Fields[i][j].Candidates.Add(Candidates[z]);
                            }
                            for (int a = 0; a < FoundI.Count; a++)
                            {
                                if (Input.Fields[FoundI[a]][FoundJ[a]].Candidates.Count() != Candidates.Count)
                                    Changed = true;
                                Input.Fields[FoundI[a]][FoundJ[a]].Candidates = new List<int>();
                                for (int z = 0; z < x; z++)
                                {
                                    Input.Fields[FoundI[a]][FoundJ[a]].Candidates.Add(Candidates[z]);
                                }
                            }
                            return;
                        }
                    }
                }
            }
        }

        private void NonLogic(bool count)
        {  
            // find all not yet solved fields
            List<Sudoku.Field> ToDo = new List<Sudoku.Field>();
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!Input.Fields[i][j].Filled)
                        ToDo.Add(Input.Fields[i][j]);
                }
            }
            Finished = false;
            // solve these by trying out all combinations
            BruteForce(ToDo, 0, Input, count);
        }

        private void BruteForce(List<Sudoku.Field> ToDo, int pos, Sudoku Temp, bool count)
        {
            if (Finished)
                return;
            for (int i = 0; i < ToDo[pos].Candidates.Count; i++)
            {
                Sudoku Copied = Temp.Copy();
                Copied.Fields[ToDo[pos].i][ToDo[pos].j].Filled = true;
                Copied.Fields[ToDo[pos].i][ToDo[pos].j].NewFound = false;
                // place a random value and ...
                Copied.Fields[ToDo[pos].i][ToDo[pos].j].Value = ToDo[pos].Candidates[i];
                bool Valid = true;
                // ... check if solution is still valid
                foreach (Sudoku.Field f in Copied.GetGroup(ToDo[pos].i, ToDo[pos].j))
                {
                    if (f.Filled && f.Value == Copied.Fields[ToDo[pos].i][ToDo[pos].j].Value)
                    {
                        Valid = false;
                        break;
                    }
                }
                if (Valid)
                {   // if yes, go to the next position
                    if (pos % 5 == 0)
                        Grade0();
                    if (pos < ToDo.Count - 1)
                        BruteForce(ToDo, pos + 1, Copied, count);
                    else
                    {   // or otherwise, we are done
                        if (!count)
                        {
                            Finished = true;
                            Input = Copied;
                            Remaining = 0;
                        }
                        else
                        {   // if we want to count the solutions, we do not stop after having found the first one
                            SolCounter++;
                            Remaining = 0;
                            if (SolCounter > 1)
                            {
                                Finished = true;
                            }
                        }
                    }
                }
            }
        }

        private bool CandidateLine()
        {
            bool Found = false;
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!Input.Fields[i][j].Filled)
                    {
                        for (int z = 0; z < Input.Fields[i][j].Candidates.Count; z++)
                        {
                            int Direction = 0; // 1 = Vertical, 2 = Horizontal
                            foreach (Sudoku.Field f in Input.GetBox(i, j))
                            {
                                if (!f.Filled && f.Candidates.Contains(Input.Fields[i][j].Candidates[z]))
                                {
                                    if (Direction == 0)
                                    {
                                        if (f.i == i)
                                            Direction = 2;
                                        else if (f.j == j)
                                            Direction = 1;
                                        else
                                            Direction = -1;
                                    }
                                    else
                                    {
                                        if (f.i == i && Direction == 2)
                                            Direction = 2;
                                        else
                                        {
                                            Direction = -1;
                                            break;
                                        }
                                        if (f.j == j && Direction == 1)
                                            Direction = 1;
                                        else
                                        {
                                            Direction = -1;
                                            break;
                                        }
                                    }
                                }
                            }

                            if (Direction == 1)
                            {
                                foreach (Sudoku.Field f in Input.GetColumn(i, j))
                                {
                                    if (!Input.BelongsToBox(i, j, f) && !f.Filled)
                                    {
                                        if (f.Candidates.Remove(Input.Fields[i][j].Candidates[z]))
                                            Found = true;
                                    }
                                }
                            }
                            if (Direction == 2)
                            {
                                foreach (Sudoku.Field f in Input.GetRow(i, j))
                                {
                                    if (!Input.BelongsToBox(i, j, f) && !f.Filled)
                                        if (f.Candidates.Remove(Input.Fields[i][j].Candidates[z]))
                                            Found = true;
                                }
                            }

                            if (Found)
                                return true;
                        }
                    }
                }
            }

            return Found;
        }

        private bool XWing()
        {
            bool Found = false;

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (!Input.Fields[i][j].Filled)
                    {
                        for (int z = 0; z < Input.Fields[i][j].Candidates.Count; z++)
                        {
                            bool RowPossible1 = true;
                            bool ColumnPossible1 = true;
                            bool RowPossible2 = true;
                            bool ColumnPossible2 = true;

                            int RowCounter1 = 1;
                            foreach (Sudoku.Field a in Input.GetColumn(i, j))
                            {
                                if (!a.Filled && a.Candidates.Contains(Input.Fields[i][j].Candidates[z]))
                                {
                                    RowCounter1++;
                                }
                            }
                            if (RowCounter1 != 2)
                                RowPossible1 = false;

                            int ColumnCounter1 = 1;
                            foreach (Sudoku.Field a in Input.GetRow(i, j))
                            {
                                if (!a.Filled && a.Candidates.Contains(Input.Fields[i][j].Candidates[z]))
                                {
                                    ColumnCounter1++;
                                }
                            }
                            if (ColumnCounter1 != 2)
                                ColumnPossible1 = false;


                            if (!RowPossible1 && !ColumnPossible1)
                                continue;

                            foreach (Sudoku.Field f in Input.GetRow(i, j))
                            {
                                if (!f.Filled && f.Candidates.Contains(Input.Fields[i][j].Candidates[z]) && !Input.BelongsToBox(i, j, f)) // 2nd point
                                {
                                    int RowCounter2 = 1;
                                    RowPossible2 = true;
                                    foreach (Sudoku.Field b in Input.GetColumn(f.i, f.j))
                                    {
                                        if (!b.Filled && b.Candidates.Contains(Input.Fields[i][j].Candidates[z]))
                                        {
                                            RowCounter2++;
                                        }
                                    }
                                    if (RowCounter2 != 2)
                                        RowPossible2 = false;

                                    foreach (Sudoku.Field ff in Input.GetColumn(i, j))
                                    {
                                        if (!ff.Filled && ff.Candidates.Contains(Input.Fields[i][j].Candidates[z]) && !Input.BelongsToBox(i, j, ff)) // 3rd point
                                        {
                                            int ColumnCounter2 = 1;
                                            ColumnPossible2 = true;
                                            foreach (Sudoku.Field c in Input.GetRow(ff.i, ff.j))
                                            {
                                                if (!c.Filled && c.Candidates.Contains(Input.Fields[i][j].Candidates[z]))
                                                {
                                                    ColumnCounter2++;
                                                }
                                            }
                                            if (ColumnCounter2 != 2)
                                                ColumnPossible2 = false;

                                            if ((!RowPossible1 || !RowPossible2) && (!ColumnPossible1 || !ColumnPossible2))
                                                continue;

                                            Sudoku.Field fff = Input.Fields[ff.i][f.j];
                                            {
                                                if (!fff.Filled && !Input.BelongsToBox(ff.i, ff.j, fff) && fff.Candidates.Contains(Input.Fields[i][j].Candidates[z])) // 4th point
                                                {
                                                    if (ColumnPossible1 && ColumnPossible2)
                                                    {
                                                        foreach (Sudoku.Field ffff in Input.GetColumn(i, j))
                                                        {
                                                            if (ffff.i == ff.i && ffff.j == ff.j)
                                                                continue;
                                                            if (ffff.Candidates.Remove(Input.Fields[i][j].Candidates[z]))
                                                                Found = true;
                                                        }
                                                        foreach (Sudoku.Field ffff in Input.GetColumn(f.i, f.j))
                                                        {
                                                            if (ffff.i == fff.i && ffff.j == fff.j)
                                                                continue;
                                                            if (ffff.Candidates.Remove(Input.Fields[i][j].Candidates[z]))
                                                                Found = true;
                                                        }
                                                    }

                                                    if (RowPossible1 && RowPossible2)
                                                    {
                                                        foreach (Sudoku.Field ffff in Input.GetRow(i, j))
                                                        {
                                                            if (ffff.i == f.i && ffff.j == f.j)
                                                                continue;
                                                            if (ffff.Candidates.Remove(Input.Fields[i][j].Candidates[z]))
                                                                Found = true;
                                                        }
                                                        foreach (Sudoku.Field ffff in Input.GetRow(ff.i, ff.j))
                                                        {
                                                            if (ffff.i == fff.i && ffff.j == fff.j)
                                                                continue;
                                                            if (ffff.Candidates.Remove(Input.Fields[i][j].Candidates[z]))
                                                                Found = true;
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                            if (Found)
                                return true;
                        }
         
                    }
                }
            }
            return Found;
        }

        private List<int> Copy(List<int> dummy)
        {
            List<int> Result = new List<int>();
            foreach (int i in dummy)
                Result.Add(i);
            return Result;
        }
    }