Laden...

Sudoku-Solver trägt falsche Lösungszahlen ein

Erstellt von mrunkreativ vor 8 Jahren Letzter Beitrag vor 8 Jahren 1.414 Views
M
mrunkreativ Themenstarter:in
3 Beiträge seit 2015
vor 8 Jahren
Sudoku-Solver trägt falsche Lösungszahlen ein

Hallo Ihr Lieben,

ich stehe momentan ein wenig auf dem Schlauch 🤔

Ich versuche seit einigen Tagen ein Programm zu schreiben, dass Sudokus löst.
Für den Anfang hab ich mein "Spielfeld" in ein zweidimensionelles Array geladen, das nach und nach durchgegangen und die erstbeste Zahl in die leeren Felder eingetragen werden soll.
Später sollen dann, wenn im aktuellen Feld keine Zahl eingesetzt werden kann, solange mögliche Varianten für die vorherigen Felder durchgegangen werden, bis sich für das aktuelle Feld wieder eine Lösung ergibt.
Leider funktionieren scheinbar eine oder mehrere Funktionen nicht, die in der jeweiligen Zeile/Spalte/Block überprüfen, ob die einzusetzende Zahl schon vorhanden ist.
Ich finde den Fehler einfach nicht X(


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sudoku
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] map = new int[9, 9] {
                {9,0,5,0,8,2,6,3,0 }, {7,0,0,0,0,0,1,0,0}, {0,0,2,5,0,0,0,0,0},
                {0,0,6,1,0,0,0,0,0 }, {0,0,3,0,0,0,9,6,4}, {0,0,0,0,5,0,8,0,0},
                {4,0,0,8,0,7,0,5,0 }, {0,0,0,2,0,3,7,0,0}, {6,3,0,0,0,5,2,4,0}
            };

            print(map);
            solve(ref map);

            Console.Clear();
            print(map);
            Console.ReadKey();
        }

        private static void print(int[,] map)
        {
            for (int i = 0; i < 9; i++)
            {
                if (i == 3 || i == 6)
                {
                    Console.WriteLine("=========================");
                }

                for (int j = 0; j < 9; j++)
                {
                    if (j == 3 || j == 6)
                    {
                        Console.Write("||  ");
                    }

                    Console.Write(map[i, j].ToString() + " ");
                }

                Console.WriteLine();
            }
        }

        private static void solve(ref int[,] map)
        {
            for (int zeile= 0; zeile < 9; zeile++)
            {
                for (int spalte = 0; spalte < 9; spalte++)
                {
                    if (map[zeile, spalte] == 0)
                    {
                        for (int value = 1; value < 10; value++)
                        {
                            if (check(zeile,spalte,map, value))
                            {
                                map[zeile, spalte] = value;
                            }
                        }
                    }
                }
            }
        }

        private static bool check(int zeile, int spalte, int[,] map, int value)
        {
            if ((whichBlock(zeile, spalte, map, value)) && (chkSpalte(spalte, map, value) && (chkZeile(zeile, map, value))))
            {
                return true;
            }

            else
            {
                return false;
            }
        }

        private static bool chkZeile(int zeile, int[,] map, int value)
        {
            for (int spalte = 0; spalte < 9; spalte++)
            {
                if (map[zeile, spalte] == value)
                {
                    return false;
                }
            }

            return true;
        }

        private static bool chkSpalte(int spalte, int[,] map, int value)
        {
            for (int zeile = 0; zeile < 9; zeile++)
            {
                if (map[zeile, spalte] == value)
                {
                    return false;
                }
            }

            return true;
        }

        private static bool whichBlock(int zeile, int spalte, int[,] map, int value)
        {
            if ((zeile < 3) && (spalte < 3)) //1.Block 1.Zeile
            {
                return chkBlock(0, 3, 0, 3, value, map);
            }

            else if ((zeile < 3) && (spalte > 2) && (spalte < 6)) //2.Block 1.Zeile
            {
                return chkBlock(0, 3, 3, 6, value, map);
            }

            else if ((zeile < 3) && (spalte > 5)) //3.Block 1.Zeile
            {
                return chkBlock(0, 3, 6, 9, value, map);
            }

            else if ((zeile > 2) && (zeile < 6) && (spalte < 3)) //1.Block 2.Zeile
            {
                return chkBlock(3, 6, 0, 3, value, map);
            }

            else if ((zeile > 2) && (zeile < 6) && (spalte > 2) && (spalte < 6)) //2.Block 2.Zeile
            {
                return chkBlock(3, 6, 3, 6, value, map);
            }

            else if ((zeile > 2) &&  (zeile < 6) && (spalte > 5)) //3.Block 2.Zeile 
            {
                return chkBlock(3, 6, 6, 9, value, map);
            }

            else if ((zeile > 5) && (spalte < 3)) //1.Block 3.Zeile 
            {
                return chkBlock(6, 9, 0, 3, value, map);
            }

            else if ((zeile > 5) && (spalte > 2) && (spalte < 6)) //2.Block 3.Zeile
            {
                return chkBlock(6, 9, 3, 6, value, map);
            }

            else if ((zeile > 5) && (spalte > 5)) //3.Block 3.Zeile
            {
                return chkBlock(6, 9, 6, 9, value, map);
            }
        
                return false;
        }

        private static bool chkBlock(int zeilenStart, int zeilenEnd, int spaltenStart, int spaltenEnd, int value, int[,] map)
        {
            for (int i = zeilenStart; i < zeilenEnd; i++)
            {
                for (int j = spaltenStart; j < spaltenEnd; j++)
                {
                    if (value == map[i, j])
                    {
                        return false;
                    }
                }
            } 
            return true;
        }
    }
}

Eigentlich müsste im ersten freien Feld eine 1 eingetragen werden, stattdessen wird eine 4 eingetragen...

Ich hoffe Ihr könnt mir weiterhelfen und bedanke mich schonmal für eure Mühen.

MrUnkreativ

W
955 Beiträge seit 2010
vor 8 Jahren

Hallo,

du kannst mit dem Debugger prüfen wo der Fehler liegt.

BTW in der deutschsprachigen Wikipedia gibt es eine Menge Algorithmen zum Sudoku, das könnte dir vllt helfen. Wenn du raten musst, also kein weiteres Feld mehr durch das constraint restriced problem-Lösungsverfahren abhaken kannst dann nimm eine Tiefensuche mit most restricted value first (also beim Raten mit dem Feld anfangen welches die kleinste Zahl an Kandidaten besitzt)

5.657 Beiträge seit 2006
vor 8 Jahren

Hi mrunkreativ,

das Forum ist nicht dazu da, dir deinen Code zu debuggen, dafür gibt es den [Artikel] Debugger: Wie verwende ich den von Visual Studio?.

Bitte beachte zukünftig [Hinweis] Wie poste ich richtig? Punkt 4.2 und 5.

Christian

Weeks of programming can save you hours of planning

M
mrunkreativ Themenstarter:in
3 Beiträge seit 2015
vor 8 Jahren

Okay ich entschuldige mich 😄

Dass das mit dem Debugger funktioniert wusste ich nicht.

Danke für die Antworten! 😃

3.170 Beiträge seit 2006
vor 8 Jahren

Hallo,

Das hatten wir hier mal im Programmierspiel. Dort sind zwei verschiedene Lösungen, wie man ein Sudoku mit Backtracking lösen kann. Vielleicht möchtest Du Dir noch Anregungen holen:

Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch (Lösung von Campac68)
Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch (Lösung von mir)

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca