3. [Gelöst]Backtracking und Sudoku

[Gelöst]Backtracking und Sudoku

  • E

    Dein Why-Abschnitt lässt mich schmunzeln.

    0
  • V

    Bashar schrieb:

    Woran erkennst du denn, ob eine Lösung gefunden wurde oder nicht? Also insbesondere, woran erkennst du, dass du backtracken musst?

    Ich hab zwar noch keinen Sudoku-Löser implementiert, aber wenn ich es per Backtracking machen würde, würde ich searchSolution einen bool-Rückgabewert verpassen: true falls Lösung gefunden, false falls Sackgasse. Dann läuft der Algorithmus ungefähr so:

    if (aktuelles feld nicht frei)
  return false;
for (zahl = 1 bis 9) {
  if (kann zahl ins aktuelle Feld eintragen ohne Konflikte)
     trage zahl ein
     erfolg = searchSolution(nächstes Feld)
     if (erfolg)
       // cool!
       return true; // oder vielleicht versuchen ob es weitere Lösungen gibt?
     else
       mache das aktuelle Feld wieder frei
       // Schleife weiter laufen lassen
}
// Schleife erfolglos durchlaufen?
return false;

    Das wäre jedenfalls erstmal die Variante mit den wenigsten Abweichungen von deiner, man kann das natürlich alles auch ganz anders machen.

    Das sehe ich gar nicht so. Die erste oder alle Lösungen ausgeben geht sehr wohl mit void. Sogar besser, weil ich nicht glaube, daß man mit dem bool was sinnvolles macht.

    0
  • B

    Geht das ein bisschen ausführlicher?

    0
  • V

    eddi0815 schrieb:

    Quelltext:

    #include <iostream>
#include <array>

const std::size_t ROW = 9;
const std::size_t COL = 9;

class Field {
public:
	Field();
	void printField();
    void searchSolution(std::size_t y, std::size_t x);
	bool isColumnOk(std::size_t y, char number);
    bool isRowOk(std::size_t x, char number);
    bool isBlockOk(std::size_t y, std::size_t x, char number);
private:
    std::array<std::array<char, ROW>, COL> field;
};

Field::Field()
{
    field = {' ', ' ', ' ',/*|*/ ' ', '1', ' ',/*|*/ ' ', '6', ' ',
             '7', '3', '6',/*|*/ '2', '8', '5',/*|*/ ' ', '9', ' ',
             ' ', ' ', ' ',/*|*/ ' ', '4', '9',/*|*/ ' ', '3', ' ',
             /****************************************************/
             ' ', '1', '3',/*|*/ '8', ' ', '7',/*|*/ ' ', '4', ' ',
             '6', '7', '5',/*|*/ ' ', ' ', ' ',/*|*/ '9', '8', '3',
             ' ', '8', ' ',/*|*/ '5', ' ', '6',/*|*/ '1', '2', ' ',
             /****************************************************/
             ' ', '2', ' ',/*|*/ '9', '5', ' ',/*|*/ ' ', ' ', ' ',
             ' ', '6', ' ',/*|*/ '4', '7', '8',/*|*/ '3', '5', '2',
             ' ', '4', ' ',/*|*/ ' ', '6', ' ',/*|*/ ' ', ' ', ' '
            };
}

    Zeile 21 compiliert beri mir nicht. Es gäbe keinen passenden operator=.

    0
  • V

    Das geht hoffentlich:

    #include <iostream>
#include <array>

const std::size_t ROW = 9;
const std::size_t COL = 9;

class Field {
public:
    Field();
    void printField();
    void searchSolution(std::size_t y, std::size_t x);
    bool isColumnOk(std::size_t y, char number);
    bool isRowOk(std::size_t x, char number);
    bool isBlockOk(std::size_t y, std::size_t x, char number);
private:
    std::array<std::array<char, ROW>, COL> field;
};

Field::Field()
{
    field = std::array<std::array<char, ROW>, COL>
             {' ', ' ', ' ',/*|*/ ' ', '1', ' ',/*|*/ ' ', '6', ' ',
             '7', '3', '6',/*|*/ '2', '8', '5',/*|*/ ' ', '9', ' ',
             ' ', ' ', ' ',/*|*/ ' ', '4', '9',/*|*/ ' ', '3', ' ',
             /****************************************************/
             ' ', '1', '3',/*|*/ '8', ' ', '7',/*|*/ ' ', '4', ' ',
             '6', '7', '5',/*|*/ ' ', ' ', ' ',/*|*/ '9', '8', '3',
             ' ', '8', ' ',/*|*/ '5', ' ', '6',/*|*/ '1', '2', ' ',
             /****************************************************/
             ' ', '2', ' ',/*|*/ '9', '5', ' ',/*|*/ ' ', ' ', ' ',
             ' ', '6', ' ',/*|*/ '4', '7', '8',/*|*/ '3', '5', '2',
             ' ', '4', ' ',/*|*/ ' ', '6', ' ',/*|*/ ' ', ' ', ' '
            };
}

void Field::printField()
{
    for (std::size_t y = 0; y < COL; ++y) {
        if (y % 3 == 0) {
            std::cout << "+---+---+---+\n";
        }
        for (std::size_t x = 0; x < ROW; ++x) {
            if (x % 3 == 0) {
                std::cout << "|";
            }
            std::cout << field[y][x];
        }
        std::cout << "|\n";
    }
    std::cout << "+---+---+---+\n";
}

void Field::searchSolution(std::size_t y, std::size_t x)
{
    //Abbruchkriterium
    if (y >= COL) {//geändert
        printField();//neu
        std::cout<<'\n';//neu
        return;
    }
    //Nächste Zeile bestimmen
    std::size_t yNext, xNext;
    //Zeile noch nicht voll?
    if (x < ROW - 1) {
        yNext = y; //Zeile bleibt gleich
        xNext = x + 1; //Spalte ein weiter
    } else {
        //Wenn Zeile voll, in erste Spalte eine Zeile tiefer
        yNext = y + 1; //Zeile ein "tiefer"
        xNext = 0; //Spalte zurück auf 0
    }
    //Suchen
    if (field[y][x] != ' ') { //Feld ist Vorbelegt
        searchSolution(yNext, xNext); //Dann beim nächsten Index weitersuchen
    } else { //sonst alle Zahlen probieren
        for (char number = '1'; number <= '9'; ++number) {
            if (isColumnOk(y, number)
                    && isRowOk(x, number)
                    && isBlockOk(y, x, number)) {
                field[y][x] = number; //gefundene Zahl eintragen
                searchSolution(yNext, xNext); //weitersuchen
            }
        } //irgendwie das bisherige rückgängig machen, falls es eine Sackgasse ist. Nur wie?
        field[y][x] = ' ';//genau!
    }
}

bool Field::isColumnOk(std::size_t y, char number)
{
    for (std::size_t x = 0; x < COL; ++x) {
        if (field[y][x] == number) {
            return false;
        }
    }
    return true;
}

bool Field::isRowOk(std::size_t x, char number)
{
    for (std::size_t y = 0; y < ROW; ++y) {
        if (field[y][x] == number) {
            return false;
        }
    }
    return true;
}

bool Field::isBlockOk(std::size_t y, std::size_t x, char number)
{
    std::size_t col = (y / 3) * 3;
    std::size_t row = (x / 3) * 3;

    for (std::size_t i = col; i < col + 3; ++i) {
        for (std::size_t j = row; j < row + 3; ++j) {
            if (field[i][j] == number) {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    Field field;
    field.printField();
    field.searchSolution(0, 0); //beginne oben links
}
    0
  • V

    Bashar schrieb:

    Geht das ein bisschen ausführlicher?

    Hast recht. bool ist gut, um abzubrechen, um nur eine Lösung auszugeben. Hab in Letzter Zeit immer alle Lösungen grbraucht, sorry.

    Hab's ein wenig aufgemotzt, und gebe einen size_t zurück, die Anzahl der Lösungen.

    #include <iostream>
#include <array>
#include <cstdlib>
#include <ctime>

const std::size_t ROW = 9;
const std::size_t COL = 9;

class Field {
public:
    Field();
    void printField();
    std::size_t searchSolution(std::size_t y, std::size_t x,bool show);
    bool isColumnOk(std::size_t y, char number);
    bool isRowOk(std::size_t x, char number);
    bool isBlockOk(std::size_t y, std::size_t x, char number);
    void harden();
private:
    std::array<std::array<char, ROW>, COL> field;
};

Field::Field()
{
    field = std::array<std::array<char, ROW>, COL>
             {' ', ' ', ' ',/*|*/ ' ', '1', ' ',/*|*/ ' ', '6', ' ',
             '7', '3', '6',/*|*/ '2', '8', '5',/*|*/ ' ', '9', ' ',
             ' ', ' ', ' ',/*|*/ ' ', '4', '9',/*|*/ ' ', '3', ' ',
             /****************************************************/
             ' ', '1', '3',/*|*/ '8', ' ', '7',/*|*/ ' ', '4', ' ',
             '6', '7', '5',/*|*/ ' ', ' ', ' ',/*|*/ '9', '8', '3',
             ' ', '8', ' ',/*|*/ '5', ' ', '6',/*|*/ '1', '2', ' ',
             /****************************************************/
             ' ', '2', ' ',/*|*/ '9', '5', ' ',/*|*/ ' ', ' ', ' ',
             ' ', '6', ' ',/*|*/ '4', '7', '8',/*|*/ '3', '5', '2',
             ' ', '4', ' ',/*|*/ ' ', '6', ' ',/*|*/ ' ', ' ', ' '
            };
}

void Field::printField()
{
    for (std::size_t y = 0; y < COL; ++y) {
        if (y % 3 == 0) {
            std::cout << "+---+---+---+\n";
        }
        for (std::size_t x = 0; x < ROW; ++x) {
            if (x % 3 == 0) {
                std::cout << "|";
            }
            std::cout << field[y][x];
        }
        std::cout << "|\n";
    }
    std::cout << "+---+---+---+\n";
}

std::size_t Field::searchSolution(std::size_t y, std::size_t x,bool show)
{
    size_t result=0;
    //Abbruchkriterium
    if (y >= COL) {//geändert
        if(show)
        {
            printField();//neu
            std::cout<<'\n';//neu
        }
        return 1;
    }
    //Nächste Zeile bestimmen
    std::size_t yNext, xNext;
    //Zeile noch nicht voll?
    if (x < ROW - 1) {
        yNext = y; //Zeile bleibt gleich
        xNext = x + 1; //Spalte ein weiter
    } else {
        //Wenn Zeile voll, in erste Spalte eine Zeile tiefer
        yNext = y + 1; //Zeile ein "tiefer"
        xNext = 0; //Spalte zurück auf 0
    }
    //Suchen
    if (field[y][x] != ' ') { //Feld ist Vorbelegt
        result+=searchSolution(yNext, xNext,show); //Dann beim nächsten Index weitersuchen
    } else { //sonst alle Zahlen probieren
        for (char number = '1'; number <= '9'; ++number) {
            if (isColumnOk(y, number)
                    && isRowOk(x, number)
                    && isBlockOk(y, x, number)) {
                field[y][x] = number; //gefundene Zahl eintragen
                result+=searchSolution(yNext, xNext,show); //weitersuchen
            }
        } //irgendwie das bisherige rückgängig machen, falls es eine Sackgasse ist. Nur wie?
        field[y][x] = ' ';//genau!
    }
    return result;
}

bool Field::isColumnOk(std::size_t y, char number)
{
    for (std::size_t x = 0; x < COL; ++x) {
        if (field[y][x] == number) {
            return false;
        }
    }
    return true;
}

bool Field::isRowOk(std::size_t x, char number)
{
    for (std::size_t y = 0; y < ROW; ++y) {
        if (field[y][x] == number) {
            return false;
        }
    }
    return true;
}

bool Field::isBlockOk(std::size_t y, std::size_t x, char number)
{
    std::size_t col = (y / 3) * 3;
    std::size_t row = (x / 3) * 3;

    for (std::size_t i = col; i < col + 3; ++i) {
        for (std::size_t j = row; j < row + 3; ++j) {
            if (field[i][j] == number) {
                return false;
            }
        }
    }
    return true;
}
void Field::harden()
{
    size_t left=100;
    while(left!=0){
        std::cout<<left<<"   \r"<<std::flush;
        size_t x=rand()%ROW;
        size_t y=rand()%COL;
        if(field[y][x]!=' '){
            char save=field[y][x];
            field[y][x]=' ';
            left--;
            if(searchSolution(0,0,false)==1)
            {
                //printField();
                left=100;
            }
            else
            {
                field[y][x]=save;
            }
        }
    }
}

int main()
{
    srand(time(0));
    Field field;

    std::cout<<"The Field:\n";
    field.printField();

    std::cout<<"The Solutions:\n";
    std::size_t solutionsCount=field.searchSolution(0, 0, true);
    if(solutionsCount!=1){
        std::cout<<"Error: Invalid Field\n";
        return 1;
    }

    std::cout<<"A harder Field:\n";
    field.harden();
    field.printField();
}

    Ausgabe

    The Field:
+---+---+---+
|   | 1 | 6 |
|736|285| 9 |
|   | 49| 3 |
+---+---+---+
| 13|8 7| 4 |
|675|   |983|
| 8 |5 6|12 |
+---+---+---+
| 2 |95 |   |
| 6 |478|352|
| 4 | 6 |   |
+---+---+---+
The Solutions:
+---+---+---+
|894|713|265|
|736|285|491|
|152|649|738|
+---+---+---+
|213|897|546|
|675|124|983|
|489|536|127|
+---+---+---+
|328|951|674|
|961|478|352|
|547|362|819|
+---+---+---+

A harder Field:
+---+---+---+
|   | 1 | 6 |
|736|   | 9 |
|   | 4 | 3 |
+---+---+---+
|  3|  7| 4 |
|67 |   |98 |
| 8 |5  |1  |
+---+---+---+
|   |95 |   |
| 6 |  8|  2|
|   | 6 |   |
+---+---+---+
    0
  • B

    volkard schrieb:

    Bashar schrieb:

    Geht das ein bisschen ausführlicher?

    Hast recht. bool ist gut, um abzubrechen, um nur eine Lösung auszugeben. Hab in Letzter Zeit immer alle Lösungen grbraucht, sorry.

    Stimmt, wenn man den ganzen Baum abläuft und alle Blätter, die Lösungen sind, ausgibt, braucht man kein bool.

    0
  • E

    Vielen Dank an Alle für die Hilfe.

    0
  • E

    Es geht hier aber um Sudoku und da gibt es nur eine Lösung. Somit gilt die Ausrede für "alle Lösungen" nicht. 🤡

    0
  • B

    Eisflamme schrieb:

    Es geht hier aber um Sudoku und da gibt es nur eine Lösung.

    Das ist so offensichtlicher Unfug, dass es wahrscheinlich schon wieder richtig ist. Erklär doch mal, wie du das meinst.

    0
  • E

    Das ist in meinen Augen überhaupt kein Unfug und daher erst recht nicht offensichtlich. Leider sind die Quellen, die ich so fand, inkommensurabel, sodass ich Mal auf diese Zusammenfassung in einem Forum verweise:
    http://portableapps.com/node/20122#comment-124186 (nicht alle Quellen geprüft)

    Die meisten Bücher und andere Quellen sagen also Eindeutigkeit aus. Da es aber offensichtlich Ausnahmen (ob Sudoko oder dann nicht mehr) gibt, sollte eine Software wohl damit klarkommen.

    0
  • B

    Eisflamme schrieb:

    Das ist in meinen Augen überhaupt kein Unfug und daher erst recht nicht offensichtlich.

    Doch, das leere Sudoku-Feld hat beispielsweise mehr als eine Lösung.

    0
  • E

    Und wer sagt Dir, dass man so etwas als Sudoku bezeichnet? Das Sudoko-Feld mit Kreisen statt Rechtecken, 200 Feldern, bei dem jedes Sudoku-Feld binäre Werte enthält, hat auch mehrere Lösungen.

    Sudoku ist ein Puzzle. Ich werfe daher auch Mal eine Definition eines Puzzles in den Raum: http://en.wikipedia.org/wiki/Glossary_of_Sudoku#Puzzle_terms

    0
  • B

    Niemand sagt mir das. Wahrscheinlich hast du sogar Recht, und man nennt offiziell nur eindeutig lösbare sudokuartige Rätsel "Sudoku". Diese willkürliche Benennung ist aber im Zusammenhang mit einem Sudokulöser reichlich irrelevant, schließlich kann man einem eventuell nicht- oder mehrdeutig lösbaren sudokuartigen Rätsel nicht ohne weiteres ansehen, ob es ein Sudoku ist. Man kann aber versuchen, es zu lösen, und so herausfinden, ob es überhaupt eine oder wenn ja, mehrere Lösungen besitzt. Und damit man nicht einen Sudokulöser und einen eventuell-nicht-oder-mehrdeutig-lösbare-sudokuartige-Rätselspiele-Löser nebeneinander programmieren muss, löst man sich sinnvollerweise von willkürlichen Festlegungen und betrachtet das Problem so, wie das ein Mathematiker oder Informatiker tun würde.

    0
  • V

    Also Sudokus aus der Rätselzeitschrift haben nur eine Lösung. Da wäre bool gut zum abbrechen.
    Der Löser scheint aber so schnell zu sein, daß es von der Laufzeit her überhaupt nicht drauf ankommt, ob man abbricht oder alle Lösungen ausgibt. Ich bin daran interessiert, ob es zufällig doch mehr als eine Lösung gibt.

    0
  • E

    Diese willkürliche Benennung ist aber im Zusammenhang mit einem Sudokulöser reichlich irrelevant

    Und dafür schrieb ich ja in meinem Beitrag auch bereits (möglicherweise nicht deutlich genug):

    Da es aber offensichtlich Ausnahmen (ob Sudoko oder dann nicht mehr) gibt, sollte eine Software wohl damit klarkommen.

    🙂

    0
Anmelden zum Antworten