Sudoku-Enträtseler arbeitet nicht ordentlich (probiert ihn mal aus)-riesen Problem

CStoll

*g* drei Jahre ist aber eine seh optimistische Schätzung. Und ehe ich versuche, dieses Programm zu "tunen", bastel' ich mir lieber ein intelligenteres Verfahren, um einen Sudoku zu lösen (am günstigsten ist es, iterativ nach "sicheren" Positionen zu suchen).

Leon++

na dann mach mal!

Leon++

ich bin übrigens C++-Einsteiger, gerade mal 14 Jahre alt und habe deshalb nicht Zeit 20 Zeilen Code am Tag zu schreiben. Außerdem kotzt mich die scheiß Konsole an (deshalb die mangelnde Motivation). Ich habe versucht auf die WINAPI umzusteigen (zu schwer) und scheiterte ausserdem auch an wxWidgets (krieg ich nicht installed). Mein Vater erlaubt mir zudem auch nur 10 Std. Internet im Monat(obwohl ich die Kosten trage) und DSL (und Flatrate) ist bei mir nicht verfügbar(Glasfaser). Dies führt dazu, dass ich nicht wie andere Programmers stundenlang in der MSDN herumsurfen kann.

Ende, mfg, ****.

Jochen Kalmbach

Ich empfehle Dir fang mit C# Express an, da kannst Du graphische Oberflächen sehr einfach und schön machen...

Leon++

C# Express? Was ist das für ein Buch? C# ist doch was anderes als C++.

f.-th. schrieb:

nicht 51 sondern 9 x 9 = 81 felder!
nach 5 soduko brauch ich für leichte per graue zellen keine 1/4 stunde:
für meiner ansicht nach nicht brauchbaren ansatz willst du prozente -
dann biet ihn bei ebay an - da gibts vielleicht noch mehr.

mfg f.-th.

p.s. wer so schnell aufgibt für den ist programmieren eh nicht der
richtige sport.
faustzahl für profis (nach höhrensagen) 20 brauchbare codezeilen pro tag.

Falls du es nicht bemerkt haben solltest, 30 Zahlen stehen da schon drin...

und das berücksichigt sein programm ja nicht oder?

mfg f.-th.

Leon++

f.-th. schrieb:

und das berücksichigt sein programm ja nicht oder?

mfg f.-th.

doch das tut es es werden nur zufallszahlen bei feldern mit dem wert 0 generiet.

ich glaube die linux-spezies haben quelltexte zu dem thema. ich weis
allerdings nicht in welche programmiersprache, hab da irgendwas mit
gnome und kde in erinnerung.

mfg f.-th.

Leon++

hab jetzt nach ner langen weile mal wieder vorbeigeschaut. Was ist nun draus geworden. Hat irgendeiner hier mal einen anderen sudokuenträtseler gebaut?

hab jetzt übrigens flatrate, welche ich mir per wlan von einem freifunknetz in berlin hole. Und das beste: mein Vater kriegt nichts davon ab. Haha. Ausserdem bin ich jetzt 15!

nman

Ein Studienkollege hat das hier produziert:
http://twoday.tuwien.ac.at/alias/stories/8519/
http://twoday.tuwien.ac.at/alias/stories/8545/

Leon++

is leider python. da kenn ich mich nicht aus.

C++ Forumbot

Dieser Thread wurde von Moderator/in SideWinder aus dem Forum DOS und Win32-Konsole in das Forum C++ verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Phoemuex

Ich habe um Weihnachten/Silvester rum mal an einem "Sudoku-SOlver" gearbeitet. Der klappt auch ganz gut, allerdings kann er nicht ALLE Rätsel lösen, sondern nur die, die nicht ganz abnormal schwer sind. Ich habe zu Weihnachten so eine Sudoku-Sammlung mit 100 Rätseln gekriegt und bis ca. 70 konnte er sie noch lösen. Ich habe mal im Internet nach anderen Online-Lösern gesucht und die haben bei denen, die ich nicht lösen konnte Backtracking, d.h. systematisches Ausprobieren angewendet.

Die Idee von meinem Sudoku: Jedes Feld innerhalb des Spielfeldes ist eine Menge von möglichen Zahlen. Je nach Position der anderen Zahlen werden dann Möglichkeiten ausgeschlossen (Zahl schon in der horizontalen oder vertikalen Reihe oder in kleinen Quadrat vorhanden) und wenn es innerhalb eines Quadrates oder einer vertikalen bzw. horizontalen Reihe nur noch eine Möglichkeit gibt die Zahl zu setzen, oder für ein Feld nur noch ein Element möglich ist, wird es gesetzt und das Ganze geht wieder von vorne los...

Hier der Code, der allerdings wahrscheinlich nicht GANZ sauber ist:

Feld.h:

#ifndef __FELD_H__
#define __FELD_H__

class Feld
{
    public:
    static const int MaxNumber = 9;
    Feld(void);
    ~Feld(void);
    bool Exclude(int Nummer);
    bool Assign(int Nummer);
    int Number(void);
    const bool operator[] (int Index);
    private:
    bool Zustaende[MaxNumber];
    int NumberOfPossibilities (void);
};
#endif

Feld.cpp:

#include "Feld.h"

Feld::Feld(void)
{
    for(int i = 0; i < MaxNumber; ++i)
    {
        Zustaende[i] = true;
    }
}

Feld::~Feld(void)
{
}

bool Feld::Exclude (int Nummer)
{
    if((Nummer <= 0) || (Nummer > MaxNumber))
    {
        return false;
    }
    if(Nummer-1 < MaxNumber)
    {
        if(Zustaende[Nummer-1])
        {
            Zustaende[Nummer-1] = false;
            return true;
        }
    }
    return false;
}

bool Feld::Assign(int Nummer)
{
    bool ReturnValue = false;
    if((Nummer <= 0) || (Nummer > MaxNumber))
    {
        return false;
    }
    for(int i = 0; i < MaxNumber; ++i)
    {
        if(i != Nummer-1)
        {
            if(Zustaende[i])
            {
                ReturnValue = true;
                Zustaende[i] = false;
            }
        }
        else
        {
            if(!(Zustaende[i]))
            {
                ReturnValue = true;
                Zustaende[i] = true;
            }
        }
    }
    return ReturnValue;
}

int Feld::NumberOfPossibilities(void)
{
    int ReturnValue = 0;
    for(int i = 0; i < MaxNumber; ++i)
    {
        ReturnValue += Zustaende[i];
    }
    return ReturnValue;
}

int Feld::Number(void)
{
    if(NumberOfPossibilities() != 1)
    {
        return 0;
    }
    for(int i = 0; i < MaxNumber; ++i)
    {
        if(Zustaende[i])
        {
            return i+1;
        }
    }
    return 0;
}

const bool Feld::operator[] (int Index)
{
    if(Index <= 0)
    {
        return false;
    }
    if(Index-1 < MaxNumber)
    {
        return Zustaende[Index-1];
    }
    return false;
}

SpielFeld.h:

#ifndef __SPIELFELD_H__
#define __SPIELFELD_H__
#include "Feld.h"
#include <string>

class SpielFeld
{
    private:
    static const int XDimension = 9, YDimension = 9;
    Feld Felder[XDimension][YDimension];
    bool RefreshPossibilities(void);
    bool CeckUniqueness(void);
    public:
    SpielFeld(const std::string &Dateiname);
    ~SpielFeld(void);
    bool Loesen(void);
    bool Geloest(void);
    void Ausgeben(void);
};
#endif

SpielFeld.cpp:

#include "SpielFeld.h"
#include <fstream>
#include <iostream>

SpielFeld::SpielFeld (const std::string &Dateiname)
{
    std::ifstream Datei(Dateiname.c_str());
    int Number = 0;
    for(int i = 0; i < YDimension; ++i)
    {
        for(int j = 0; (j < XDimension) && !(Datei.eof()); ++j)
        {
            Datei >> Number;
            if((Number > 0) && (Number <= Feld::MaxNumber))
            {
                Felder[j][i].Assign(Number);
            }
        }
    }
    Datei.close();
}

SpielFeld::~SpielFeld(void)
{
}

bool SpielFeld::Loesen(void)
{
    bool Aenderung = true;
    while((Aenderung) && (!Geloest()))
    {
        Aenderung = RefreshPossibilities();
        Aenderung = Aenderung || CeckUniqueness();
    }
    return Geloest();
}

void SpielFeld::Ausgeben(void)
{
    for(int i = 0; i < YDimension; ++i)
    {
        if(!(i%3) && i)
        {
            for(int k = 0; k < 2*XDimension-1; ++k)
            {
                if(((k+1)%6) || (!k))
                {
                    std::cout << "-";
                }
                else
                {
                    std::cout << "+";
                }
            }
            std::cout << std::endl;
        }
        for(int j = 0; j < XDimension; ++j)
        {
            if(Felder[j][i].Number())
            {
                std::cout << Felder[j][i].Number();
            }
            else
            {
                std::cout << ' ';
            }
            if(!((j%3)-2) && (j) && (j<XDimension-1))
            {
                std::cout << "|";
            }
            else
            {
                std::cout << ' ';
            }
        }
        std::cout << '\n';
    }
}

bool SpielFeld::Geloest(void)
{
    for(int i = 0; i < YDimension; ++i)
    {
        for(int j = 0; j < XDimension; ++j)
        {
            if(!(Felder[j][i].Number()))
            {
                return false;
            }
        }
    }
    return true;
}

bool SpielFeld::RefreshPossibilities(void)
{
    bool Aenderung = false;
    for(int i = 0; i < XDimension; ++i)
    {
        for(int j = 0; j < YDimension; ++j)
        {
            if(Felder[i][j].Number())
            {
                //Horizontal ausschließen
                for(int k = 0; k < XDimension; ++k)
                {
                    if(k != i)
                    {
                        Aenderung = Felder[k][j].Exclude(Felder[i][j].Number()) || Aenderung;
                    }
                }
                //Vertikal ausschließen
                for(int k = 0; k < YDimension; ++k)
                {
                    if(k != j)
                    {
                        Aenderung = Felder[i][k].Exclude(Felder[i][j].Number()) || Aenderung;
                    }
                }
                //Im kleinen Rechteck ausschließen
                for(int k = i-(i%3); k < (i-(i%3))+3; ++k)
                {
                    for(int l = j-(j%3); l < j-(j%3)+3; ++l)
                    {
                        if(!((k == i) && (l == j)))
                        {
                            Aenderung = Felder[k][l].Exclude(Felder[i][j].Number()) || Aenderung;
                        }
                    }
                }
            }
        }
    }
    return Aenderung;
}

bool SpielFeld::CeckUniqueness(void)
{
    bool ReturnValue = false;
    for(int i = 0; i < XDimension; ++i)
    {
        for(int j = 0; j < YDimension; ++j)
        {
            //War: !Felder[i][j].Number()
            if(Felder[i][j].Number())
            {
                continue;
            }
            for(int Number = 1; Number <= Feld::MaxNumber; ++Number)
            {
                if(Felder[i][j][Number])
                {
                    bool OtherOccurence = false;
                    //Horizontal überprüfen
                    for(int k = 0; k < XDimension; ++k)
                    {
                        if((Felder[k][j][Number]) && (k!=i))
                        {
                            OtherOccurence = true;
                        }
                    }
                    if(!OtherOccurence)
                    {
                        ReturnValue = Felder[i][j].Assign(Number) || ReturnValue;
                        break;
                    }
                    OtherOccurence = false;
                    //Vertikal überprüfen
                    for(int k = 0; k < YDimension; ++k)
                    {
                        if((Felder[i][k][Number]) && (k!=j))
                        {
                            OtherOccurence = true;
                        }
                    }
                    if(!OtherOccurence)
                    {
                        ReturnValue = Felder[i][j].Assign(Number) || ReturnValue;
                        break;
                    }
                    //Im kleinen Rechteck überprüfen
                    OtherOccurence = false;
                    for(int k = i-(i%3); k < (i-(i%3))+3; ++k)
                    {
                        for(int l = j-(j%3); l < (j-(j%3))+3; ++l)
                        {
                            if((Felder[k][l][Number]) && !((k == i) && (l == j)))
                            {
                                OtherOccurence = true;
                            }
                        }
                    }
                    if(!OtherOccurence)
                    {
                        ReturnValue = Felder[i][j].Assign(Number) || ReturnValue;
                        break;
                    }
                }
            }
        }
    }
    return ReturnValue;
}

main.cpp

#include "Feld.h"
#include "SpielFeld.h"
#include <iostream>
#include <string>
using namespace std;

int main(void)
{
    cout << "Bitte Dateinamen eingeben!\n";
    string Dateiname;
    cin >> Dateiname;
    cout << endl << endl;
    SpielFeld Sudoku(Dateiname);
    Sudoku.Ausgeben();
    cout << endl << endl;
    Sudoku.Loesen();
    Sudoku.Ausgeben();
    cin.get();
    cin.get();
    return 0;
}

Also ich hab das Programm bei mir in Visual Studio zusammengefügt und es läuft auch. Allerdings weis ich nicht so richtig wie es funktioniert.

Ich soll nen Sudoku-Löser als Projekt im Studium jetzt Programmieren, hab aber nich wirklich Ahnung davon. Wär schön wenn mir das nochmal kurz jemand erklären könnte. Bei mir gibt er am ende nämlich nur 2 leere Sudokus aus.

Hier ist noch mehr zum Thema:

http://c-plusplus.net/forum/viewtopic-var-t-is-158943.html
Auf der ersten Seite, vorletzter Beitrag ist ein Solver der auch nach einem systematischen verfahren funktioniert.