C# :: Aufgabe #222 :: Lösung #3

3 Lösungen Lösungen öffentlich
#222

Generierung eines SUDOKU

Anfänger - C# von hollst - 13.08.2018 um 16:23 Uhr
Für alle, denen es nicht bekannt sein sollte: Ein SUDOKU ist ein 9 × 9 - Gitter,
das mit den Ziffern 1 bis 9 so ausgefüllt ist, dass jede Ziffer in jeder Spalte,
in jeder Zeile und in jedem 3 x 3 - Unterblock genau ein einziges Mal vorkommt (Bild 1).

Insgesamt sind fast 6.7 Trilliarden (10 hoch 21) unterschiedliche SUDOKUS konstruierbar
(genau 6.670.903.752.021.072.936.960).

Die Programmieraufgabe bestehe darin, mittels Zufallsgenerator SUDOKUS zu erzeugen
und anzuzeigen.

Durch Ausblendung einiger Felder entsteht aus einem SUDOKU ein SUDOKU-Rätsel. Dabei
müssen allerdings mindestens 17 Felder unausgeblendet sein, um eine eindeutige Lösung
zu erhalten (Beweis siehe McGuire, Gary; Tugemann, Bastian; Civario, Gilles:
There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem.
2012arXiv1201.0749M, Sep 2013). Die Erzeugung eines solchen SUDOKU-Rätsels sei
Fortgeschrittenen vorbehalten, da hierbei auch die Eindeutigkeit einer Lösung nachgewiesen
werden sollte. Der Gipfel wäre anschließend, einen computergestützten SUDOKU-Löser zu entwickeln;
aber, wir wollen es hier noch nicht übertreiben, eines nach dem anderen und nur, wer die
Herausforderung nich scheut.

Viel Spaß!
Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.
Frage stellen
Bitte melden Sie sich an um eine Lösung einzureichen.
Lösung einreichen
pic_2.png Votes: 0 Admin: 0
#3
vote_ok
von RevTreb (860 Punkte) - 29.11.2018 um 15:59 Uhr
Hier mein Lösungsvorschlag.
Ich bin mir ziemlich sicher, daß ich das viel zu kompliziert angegangen bin :/

Program.cs
Quellcode ausblenden C#-Code
using System;

namespace SudokuGenerator
{
    class Program
    {
        static void Main(string[] args)
        {
            SudokuField field = new SudokuField();

            field.Calc();

            Console.WriteLine(field);

            Console.WriteLine("nötige Versuche: " + Sudoku.stack);
            Console.ReadLine();
        }
    }
}


Sudoku.cs
Quellcode ausblenden C#-Code
using System;
using System.Collections.Generic;

namespace SudokuGenerator
{
    static class Sudoku
    {
        public static int stack = 1;
        public static Random rnd = new Random();

        // Liefert die Differenzmenge aus Source - Used 
        public static List<int> Remaining(List<int> Used = null, List<int> Source = null)
        {
            if (Source==null)
                Source = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

            List<int> temp = new List<int>();
            foreach (int i in Source)
                if (!Used.Contains(i))
                    temp.Add(i);
            return temp;
        }

        //Liefert zufällige Elemente aus der Menge <Source>
        //... die Anzahl der Elemente kann mit <Count> begrenzt werden
        public static List<int> Shuffle(List<int> Source = null, int Count=-1)
        {
            List<int> temp = new List<int>();
            List<int> source = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            if (Source != null)
                source = Source;
            while (source.Count > 0)
            {
                int i = rnd.Next(1, source.Count + 1);
                int nr = source[i - 1];
                temp.Add(nr);
                source.Remove(source.Find(o => o == nr));
            }
            while (Count>0 && temp.Count>Count)
                temp.RemoveAt(0);
            return temp;
        }

        // Liefert die Summe der zwei Mengen list1 und list2
        public static List<int> Merge(List<int> list1, List<int> list2)
        {
            List<int> temp = new List<int>();
            foreach (int i in list1)
                temp.Add(i);
            foreach (int i in list2)
                if (!temp.Contains(i))
                    temp.Add(i);
            return temp;
        }

        // Liefert die Summe der Elemente der drei Mengen list1, list2 und list3
        public static List<int> Merge(List<int> list1, List<int> list2, List<int> list3)
        {
            return Merge(Merge(list1, list2),list3);
        }
    }
}


SudokuBlock3x3.cs
Quellcode ausblenden C#-Code
using System.Collections.Generic;
using System.Text;

namespace SudokuGenerator
{
    class SudokuBlock3x3
    {
        #region Felder
        SudokuCell[,] cells;
        #endregion

        #region Eigenschaft(en)
        internal SudokuCell[,] Cells { get => cells; set => cells = value; }
       
        #endregion

        #region Konstruktor(en)
        public SudokuBlock3x3()
        {
            cells = new SudokuCell[3, 3];
            Init();
        }
        #endregion

        internal void Init()
        {
            //In alle Zellen den Wert 0 eintragen
            for (int y = 0; y < 3; y++)
                for (int x = 0; x < 3; x++)
                    cells[x, y] = new SudokuCell(0);
            //Zeilen und Spalten verlinken
            for (int y = 0; y < 3; y++)
                for (int x = 0; x < 3; x++)
                {
                    if (y < 2)
                        cells[x, y].NextCellInColumn = cells[x, y + 1];
                    if (x < 2)
                        cells[x, y].NextCellInRow = cells[x + 1, y];
                }
        }

        public static implicit operator List<int>(SudokuBlock3x3 block)
        {
            List<int> temp = new List<int>();
            int content = 0;
            for (int y = 0; y < 3; y++)
                for (int x = 0; x < 3; x++)
                {
                    content = block.cells[x, y].Content;
                    if (content != 0)
                        temp.Add(content);
                }
            return temp;
        }

        internal void Clear()
        {
            foreach (SudokuCell cell in cells)
                cell.Clear();
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int y = 0; y < 3; y++)
                for (int x = 0; x < 3; x++)
                    sb.AppendLine(cells[x,y] + " ");
            return sb.ToString();
        }
    }
}


SudokuCell.cs
Quellcode ausblenden C#-Code
namespace SudokuGenerator
{
    class SudokuCell
    {
        #region Felder
        private int content;
        private SudokuCell nextCellInRow;
        private SudokuCell nextCellInColumn;    
        #endregion

        #region Eigenschaft(en)
        public int Content { get => content; set => content = value; }
        internal SudokuCell NextCellInRow { get => nextCellInRow; set => nextCellInRow = value; }
        internal SudokuCell NextCellInColumn { get => nextCellInColumn; set => nextCellInColumn = value; }
        #endregion

        #region Konstruktor(en)
        public SudokuCell(int content)
        {
            this.content = content;
        }
        #endregion

        internal void Clear()
        {
            content = 0;
        }

        public override string ToString()
        {
            return content.ToString();
        }
    }
}


SudokuRow.cs
Quellcode ausblenden C#-Code
using System.Collections.Generic;

namespace SudokuGenerator
{
    class SudokuRow : List<SudokuCell>
    {
        public static implicit operator List<int>(SudokuRow Row)
        {
            List<int> temp = new List<int>();
            foreach (SudokuCell cell in Row)
            {
                temp.Add(cell.Content);
            }
            return temp;
        }
    }
}


SudokuField.cs
Quellcode ausblenden C#-Code
using System;
using System.Collections.Generic;
using System.Text;
using static SudokuGenerator.Sudoku;


namespace SudokuGenerator
{
    class SudokuField
    {
        #region Felder
        private SudokuBlock3x3[,] blocks;
        private SudokuRow[] rows;
        private SudokuRow[] columns;
        #endregion

        #region Eigenschaft(en)       
        internal SudokuBlock3x3[,] Blocks { get => blocks; set => blocks = value; }
        internal SudokuRow[] Rows { get => rows; set => rows = value; }
        internal SudokuRow[] Columns { get => columns; set => columns = value; }

        #endregion

        #region Konstruktor(en)
        public SudokuField()
        {
            blocks = new SudokuBlock3x3[3, 3];
            for (int y = 0; y < 3; y++)
                for (int x = 0; x < 3; x++)
                    blocks[x, y] = new SudokuBlock3x3();
            Init();
        }
        #endregion

        internal void Calc()
        {
            Clear(); // Wert jeder Zelle auf 0 setzen
            try
            {
                FillField(); 
            }
            catch (ArgumentOutOfRangeException)
            {
                Sudoku.stack++;
                if (Sudoku.stack%100==0)
                    Console.WriteLine(Sudoku.stack);
                Calc();
            }
        }

        private void Init()
        {
            //Blockübergänge verlinken
            for (int i1 = 0; i1 < 2; i1++)
            {
                for (int i2 = 0; i2 < 3; i2++)
                {
                    for (int t = 0; t < 3; t++)
                    {
                        blocks[i1, t].Cells[2, i2].NextCellInRow = blocks[i1 + 1, t].Cells[0, i2];
                        blocks[t, i1].Cells[i2, 2].NextCellInColumn = blocks[t, i1 + 1].Cells[i2, 0];
                    }
                }
            }

            //verlinkte Zellen für besseres Handling in rows[] bzw. columns[] ablegen
            rows = new SudokuRow[9];
            columns = new SudokuRow[9];
            for (int y = 0; y < 3; y++)
            {
                for (int x = 0; x < 3; x++)
                {
                    rows[3 * y + x] = new SudokuRow();
                    columns[3 * x + y] = new SudokuRow();

                    SudokuCell cell = blocks[0, y].Cells[0, x];
                    while (cell != null)
                    {
                        rows[3 * y + x].Add(cell);
                        cell = cell.NextCellInRow;
                    }
                    cell = blocks[x, 0].Cells[y, 0];
                    while (cell != null)
                    {
                        columns[3 * x + y].Add(cell);
                        cell = cell.NextCellInColumn;
                    }
                }
            }
        }

        private void FillField()
        {
            //Ab hier wird mit Zahlen befüllt
            List<int> used; //... sind im aktuellen Kontext bereits in Benutzung 
            List<int> remaining;    //... dürfen im aktuellen Kontext verwendet werden
            for (int by = 0; by < 3; by++)  // ...für alle drei Blockzeilen
                for (int bx = 0; bx < 3; bx++)  //... und alle drei Blockspalten
                    for (int y = 0; y < 3; y++)     //  ... und allen Spalten im Block
                        for (int x = 0; x < 3; x++)     // ... , sowie allen drei Zeilen im Block
                        {   // => also sprich für jede einzelne Sudokuzelle im aktuellen SudokuField
                            // links oben beginnend:

                            // Ermittle die Zahlenmenge <used>, die für die zu untersuchende Zelle nicht mehr in Frage kommen
                            // , weil sie in der Zeile, oder der Spalte, oder im eigenen Block bereits vorkommen.
                            used = Merge(columns[y + 3 * bx], rows[x + 3 * by], blocks[bx, by]);
                            // Ermittle aus der Restmenge eine zufällige Ziffer
                            remaining = Shuffle(Remaining(used), 1);
                            // Und trage sie in die aktuelle Zelle ein.
                            blocks[bx, by].Cells[y, x].Content = remaining[0];
                        }
        }

        //Überschreibt den Inhalt aller Zellen mit '0'
        //Die Verlinkung bleibt jedoch bestehen
        internal void Clear()
        {
            foreach (SudokuBlock3x3 block in blocks)
                block.Clear();
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.AppendLine("┌───────┬───────┬───────┐");
            for (int yb = 0; yb < 3; yb++)
            {           
                for (int yc = 0; yc < 3; yc++)
                {
                    for (int xb = 0; xb < 3; xb++)
                    {
                        sb.Append("│ ");
                        for (int xc = 0; xc < 3; xc++)
                            sb.Append(blocks[xb, yb].Cells[xc,yc] + " ");
                    }
                    sb.AppendLine("│ ");                    
                }
                if (yb<2)
                    sb.AppendLine("├───────┼───────┼───────┤");
            }
            sb.AppendLine("└───────┴───────┴───────┘");
            return sb.ToString();
        }
    }
}
Admin: 0

Kommentare:

Für diese Lösung gibt es noch keinen Kommentar

Bitte melden Sie sich an um eine Kommentar zu schreiben.
Kommentar schreiben
Seite 1 von 0 1
2107537

Du scheinst einen AdBlocker zu nutzen. Ich würde mich freuen, wenn du ihn auf dieser Seite deaktivierst und dich davon überzeugst, dass die Werbung hier nicht störend ist.