3. [Gelöst]Backtracking und Sudoku

[Gelöst]Backtracking und Sudoku

  • 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