4. Sudoku Solver mit C++ Builder 5

Sudoku Solver mit C++ Builder 5

  • ?

    Kann mir jemand erklären, wie ich am besten vorgehen soll, wenn ich
    ein Sudoku Solver programmieren möchte ??

    [Ich habe Erfahrung mit Arrays, Funktionen und verschiendenen Bedingungen und
    auch ein bisschen mit Klassen]

    0
  • D

    diesen Beitrag hier bitte löschen

    0
  • ?

    Deforation schrieb:

    diesen Beitrag hier bitte löschen

    warum? bist du eigentlich unfähig meine frage zu verstehen ?

    sudoku solver ist ein project woran ich arbeite und ich wollte hier keine Lösung,
    sonder nur in Sätzen wie ich vorgehen sollte. da hätten doch ein paar
    punkte gerreicht. aber anscheinend hast du wohl keine Ahnung....

    0
  • A

    Bitte Thread schließen. Unregistrierte Fragesteller mit wahllosen Aggressionen können dieselbigen bitte andernorts ausleben.

    Edit: Typographie

    0
  • ?

    audacia schrieb:

    Bitte Thread schließen. Unregistrierte Fragesteller mit wahllosen Aggressionen können dieselbigen bitte andernorts ausleben.

    Edit: Typographie

    wahllose aggression ? kaum ein smiley benutzt und schon kommt es als aggression
    rüber 😃 😃

    so klingt es witzig
    "Bitte Thread schließen. Unregistrierte Fragesteller mit wahllosen Aggressionen können dieselbigen bitte andernorts ausleben. :D"

    so klingt es ängstlich
    "Bitte Thread schließen. Unregistrierte Fragesteller mit wahllosen Aggressionen können dieselbigen bitte andernorts ausleben. 😮 "

    und so nervig
    "Bitte Thread schließen. Unregistrierte Fragesteller mit wahllosen Aggressionen können dieselbigen bitte andernorts ausleben. 🙄 "

    und jetzt wütend
    "Bitte Thread schließen. Unregistrierte Fragesteller mit wahllosen Aggressionen können dieselbigen bitte andernorts ausleben. 😡 "

    tja was smileys alles können. 🕶

    0
  • ?

    man man du lässt auch niht lock oder?^^

    hier ist eine schöne Lösung:
    du musst es nur noch auf C++ Builder umschreiben.
    beschäftige dich auch mal mit Brute Force!! sehr wichtig!!

    #include <iostream>
#include <fstream>

using namespace std;

class SudokuBoard;
void printB(SudokuBoard sb);

typedef unsigned int uint;

const uint MAXVAL = 9;
const uint L = 9;
const uint C = 9;
const uint S = L * C;
const uint ZONEL = 3;
const uint ZONEC = 3;
const uint ZONES = ZONEL * ZONEC;

const uint lineElements[L][C] = {
    { 0,  1,  2,  3,  4,  5,  6,  7,  8},
    { 9, 10, 11, 12, 13, 14, 15, 16, 17},
    {18, 19, 20, 21, 22, 23, 24, 25, 26},
    {27, 28, 29, 30, 31, 32, 33, 34, 35},
    {36, 37, 38, 39, 40, 41, 42, 43, 44},
    {45, 46, 47, 48, 49, 50, 51, 52, 53},
    {54, 55, 56, 57, 58, 59, 60, 61, 62},
    {63, 64, 65, 66, 67, 68, 68, 70, 71},
    {72, 73, 74, 75, 76, 77, 78, 79, 80}
};

const uint columnElements[C][L] = {
    { 0,  9, 18, 27, 36, 45, 54, 63, 72},
    { 1, 10, 19, 28, 37, 46, 55, 64, 73},
    { 2, 11, 20, 29, 38, 47, 56, 65, 74},
    { 3, 12, 21, 30, 39, 48, 57, 66, 75},
    { 4, 13, 22, 31, 40, 49, 58, 67, 76},
    { 5, 14, 23, 32, 41, 50, 59, 68, 77},
    { 6, 15, 24, 33, 42, 51, 60, 69, 78},
    { 7, 16, 25, 34, 43, 52, 61, 70, 79},
    { 8, 17, 26, 35, 44, 53, 62, 71, 80}
};

const uint zoneElements[S / ZONES][ZONES] = {
    { 0,  1,  2,  9, 10, 11, 18, 19, 20},
    { 3,  4,  5, 12, 13, 14, 21, 22, 23},
    { 6,  7,  8, 15, 16, 17, 24, 25, 26},
    {27, 28, 29, 36, 37, 38, 45, 46, 47},
    {30, 31, 32, 39, 40, 41, 48, 49, 50},
    {33, 34, 35, 42, 43, 44, 51, 52, 53},
    {54, 55, 56, 63, 64, 65, 72, 73, 74},
    {57, 58, 59, 66, 67, 68, 75, 76, 77},
    {60, 61, 62, 68, 70, 71, 78, 79, 80}
};

class SudokuBoard {
public:
    SudokuBoard() :
        filledIn(0)
    {
        for (uint i(0); i < S; ++i)
            table[i] = usedDigits[i] = 0;
    }

    virtual ~SudokuBoard() {
    }

    int const at(uint l, uint c) { // Returns the value at line l and row c
        if (isValidPos(l, c))
            return table[l * L + c];
        else
            return -1;
    }

    void set(uint l, uint c, uint val) { // Sets the cell at line l and row c to hold the value val
        if (isValidPos(l, c) && ((0 < val) && (val <= MAXVAL))) {
            if (table[l * C + c] == 0)
                ++filledIn;
            table[l * C + c] = val;
            for (uint i = 0; i < C; ++i) // Update lines
                usedDigits[lineElements[l][i]] |= 1<<val;
            for (uint i = 0; i < L; ++i) // Update columns
                usedDigits[columnElements[c][i]] |= 1<<val;
            int z = findZone(l * C + c);
            for (uint i = 0; i < ZONES; ++i) // Update columns
                usedDigits[zoneElements[z][i]] |= 1<<val;
        }
    }

    void solve() {
        try { // This is just a speed boost
            scanAndSet(); // Logic approach
            goBruteForce(); // Brute force approach
        } catch (int e) { // This is just a speed boost
        }
    }

    void scanAndSet() {
        int b;
        bool changed(true);
        while (changed) {
            changed = false;
            for (uint i(0); i < S; ++i)
                if (0 == table[i]) // Is there a digit already written?
                    if ((b = bitcount(usedDigits[i])) == MAXVAL - 1) { // If there's only one digit I can place in this cell, do
                        int d(1); // Find the digit
                        while ((usedDigits[i] & 1<<d) > 0)
                            ++d;
                        set(i / C, i % C, d); // Fill it in
                        changed = true; // The board has been changed so this step must be rerun
                    } else if (bitcount(usedDigits[i]) == MAXVAL)
                        throw 666; // Speed boost
        }
    }

    void goBruteForce() {
        int max(-1); // Find the cell with the _minimum_ number of posibilities (i.e. the one with the largest number of /used/ digits)
        for (uint i(0); i < S; ++i)
            if (table[i] == 0) // Is there a digit already written?
                if ((max == -1) || (bitcount(usedDigits[i]) > bitcount(usedDigits[max])))
                    max = i;

        if (max != -1) {
            for (uint i(1); i <= MAXVAL; ++i) // Go through each possible digit
                if ((usedDigits[max] & 1<<i) == 0) { // If it can be placed in this cell, do
                    SudokuBoard temp(*this); // Create a new board
                    temp.set(max / C, max % C, i); // Complete the attempt
                    temp.solve(); // Solve it
                    if (temp.getFilledIn() == S) { // If the board was completely solved (i.e. the number of filled in cells is S)
                        for (uint j(0); j < S; ++j) // Copy the board into this one
                            set(j / C, j % C, temp.at(j / C, j % C));
                        return; // Break the recursive cascade
                    }
                }
        }
    }

    uint getFilledIn() {
        return filledIn;
    }

private:
    uint table[S];
    uint usedDigits[S];
    uint filledIn;

    bool const inline isValidPos(int l, int c) {
        return ((0 <= l) && (l < (int)L) && (0 <= c) && (c < (int)C));
    }

    uint const inline findZone(uint off) {
        return ((off / C / ZONEL) * (C / ZONEC) + (off % C / ZONEC));
    }

    uint const inline bitcount(uint x) {
        uint count(0);
        for (; x; ++count, x &= (x - 1));
        return count;
    }
};

void printB(SudokuBoard sb) {
    cout << "  |  -------------------------------  |" << endl;
    for (uint i(0); i < S; ++i) {
        if (i % 3 == 0)
            cout << "  |";
        cout << "  " << sb.at(i / L, i % L);
        if (i % C == C - 1) {
            if (i / C % 3 == 2)
                cout << "  |" << endl << "  |  -------------------------------";
            cout << "  |" << endl;
        }
    }
    cout << endl;
}

int main(int argc, char *argv[]) {
    SudokuBoard sb;

    ifstream fin("sudoku4.in");
    int aux;
    for (uint i(0); i < S; ++i) {
        fin >> aux;
        sb.set(i / L, i % L, aux);
    }
    fin.close(); //Quelle:http://snippets.dzone.com

    printB(sb);
    sb.solve();
    printB(sb);

    return 0;
}
    0
  • ?

    super vielen dank 🙂

    0
  • V

    Toll, ein quengelndes Kind das evtl. nicht verstehen kann das Deforation zB im falschen Thread gepostet hat und den dafür anmacht, das er seine Nachricht gelöscht haben möchte, nun mit einen Copy&Past Code zu belohnen....

    0
  • ?

    VergissEs schrieb:

    Toll, ein quengelndes Kind das evtl. nicht verstehen kann das Deforation zB im falschen Thread gepostet hat und den dafür anmacht, das er seine Nachricht gelöscht haben möchte, nun mit einen Copy&Past Code zu belohnen....

    wieder mal ein besserwisser, der jetzt versucht zu provozieren. na ja, wenn
    man die Frage nicht verstanden hat, dann kann man auch nicht mehr helfen. oh man 😃

    0
Log in to reply