Sudoku - wersja prostsza

Witam, znalazłem kod pewnego użytkownika na tym forum:

msm napisał(a):

Mam wrażenie, że to nie jest tak krotkie na jakie wygląda... Tam nie ma tylko kilka pętli i ifow, trzeba dodatkowe metody dorobić. Prawda?

może coś takiego: http://www.thelearningpoint.ne[...]cience/c-program-sudoku-solver w porównaniu z innymi, które widziałam w C w internecie wydaje się prosty. - karolinaa dzisiaj, 15:24

Gotowiec rozwiązujący sudoku który niedawno dla kogoś innego na forum napisałem:

bool solve(int x, int y);

int sudoku[9][9] = { /* tu zadane sudoku... */ };
int curr[9][9];
bool can_insert(int x, int y, int value) {
    for(int i = 0; i < 9; i++) {
        if (value == curr[x][i] || value == curr[i][y] ||
            value == curr[x/3*3+i%3][y/3*3+i/3]) return false;
    } return true;
}

bool next(int x, int y) {
    if (x == 8 && y == 8) return true;
    else if (x == 8) return solve(0, y + 1);
    else return solve(x + 1, y);
}
 
bool solve(int x, int y) {
    if (sudoku[x][y] == 0) {
        for(int i = 1; i <= 9; i++) {
            if (can_insert(x, y, i)) {
                curr[x][y] = i;
                if (next(x, y)) return true;
            }
        } curr[x][y] = 0; return false;
    } return next(x, y);
}

Prosty? Prosty ;].
Zasadniczo dokładnie ten sam algorytm co na wikipedii.

Można poprawić trochę wydajność algorytmu (tzn. stałą w czasie wykonania), np. eliminując dzielenie w can_insert itd, ale starałem się jak najprostszy kod podać (zresztą jeśli przyjdzie tu Dragon to i tak mi to wypomni).

Żeby uruchomić algorytm z jakimiś testowymi danymi:

int sudoku[9][9]= {
    {0,1,0,0,5,6,2,7,0},
    {0,0,0,0,8,0,0,0,9},
    {0,7,8,0,0,3,6,0,5},
    {0,0,0,0,0,4,5,0,1},
    {8,5,2,0,0,0,7,3,4},
    {6,0,1,7,0,0,0,0,0},
    {1,0,6,4,0,0,9,5,0},
    {3,0,0,0,6,0,0,0,0},
    {0,2,7,3,9,0,0,8,0}
};

/* podany wyżej kod tutaj */

int main() {
    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++)
            curr[i][j] = sudoku[i][j];
    if (solve(0,0)) {
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                cout<<curr[i][j];
            } cout<<endl;
        }
    } else {
        cout<<"impossible\n";
    }
    return 0;
}

Jednak nie rozumiem zbytnio jego działania.. Czy ktoś mógłby go wytłumaczyć? A może znalazłaby się jakaś dobra dusza, która chciałaby napisać ten program w prostszy sposób? Nie rozumiem na przykład: bool solve(int x, int y);...

Z góry dziękuję za pomoc.

Nie możesz zrozumieć bo kod jest źle sformatowany.

bool solve(int x, int y);

int sudoku[9][9] = { /* tu zadane sudoku... */ };
int curr[9][9];

bool can_insert(int x, int y, int value) {
    for(int i = 0; i < 9; i++) {
        if (value == curr[x][i]
            || value == curr[i][y]
            || value == curr[x/3*3+i%3][y/3*3+i/3])
            return false;
    }
    return true;
}

bool next(int x, int y) {
    if (x == 8 && y == 8)
        return true;
    else if (x == 8)
        return solve(0, y + 1);
    else 
        return solve(x + 1, y);
}
 
bool solve(int x, int y) {
    if (sudoku[x][y] == 0) {
        for(int i = 1; i <= 9; i++) {
            if (can_insert(x, y, i)) {
                curr[x][y] = i;
                if (next(x, y))
                    return true;
            }
        }
        curr[x][y] = 0;
        return false;
    }
    return next(x, y);
}

Nie rozumiem na przykład:

bool solve(int x, int y);

No tak, bo to własnie funkcja rozwiązująca całe sudoku.

Chyba że chodzi Ci o pierwszą linijką kodu, jeśli tak to to po prostu deklaracja tej funkcji - czyli informacja dla kompilatora, że gdzieś później zostanie podana treść funkcji solve(x, y).
Jest to potrzebne, bo funkcja musi być zadeklarowana przed pierwszym użyciem, a funkcje next() i solve() odwołują się do siebie wzajemnie.

A może znalazłaby się jakaś dobra dusza, która chciałaby napisać ten program w prostszy sposób?

Prościej? Przecież to w zasadzie 20 linijek kodu, wiele uprościć się nie da.

Jednak nie rozumiem zbytnio jego działania.. Czy ktoś mógłby go wytłumaczyć?

Każdej linijki po kolei nie będę omawiał, ale może co robi każda funkcja osobno (później powinno Ci być prosto zweryfikować że faktycznie kod w funkcji robi to co powinien):

int sudoku[9][9] = { /* tu zadane sudoku... */ };

Zadane sudoku. Ta tablica nie jest modyfikowana podczas działania programu. Zera w niej oznaczają puste miejsca do wypełnienia.

int curr[9][9];

A to jest tablica którą wypełniamy - pod koniec działania algorytmu w niej będzie rozwiązane sudoku (jeśli wszystko pójdzie ok).

bool can_insert(int x, int y, int value) {
    for(int i = 0; i < 9; i++) {
        if (value == curr[x][i] || value == curr[i][y] ||
            value == curr[x/3*3+i%3][y/3*3+i/3]) return false;
    } return true;
}

Sprawdzanie czy do sudoku można wstawić wartość value na miejsce (x, y).
W szczególności, nie można wstawić wartości na pole jeśli:

• w wierszu y jest już taka wartość
• w kolumnie x jest już taka wartośc
• w tym kwadracie 3x3 jest już taka wartość

Te wszystkie 3 rzeczy są w tej funkcji sprawdzane.

bool solve(int x, int y) {
    if (sudoku[x][y] == 0) {
        for(int i = 1; i <= 9; i++) {
            if (can_insert(x, y, i)) {
                curr[x][y] = i;
                if (next(x, y)) return true;
            }
        } curr[x][y] = 0; return false;
    } return next(x, y);
}

Funkcja rozwiązująca całe sudoku.
A dokładniej, przyjmuje współrzędne (x, y), i zakłada że wszystko przed tymi współrzędnymi jest już poprawnie wypełnione - i próbuje wypełniać dalej.
Po kolei próbuje wstawić w pole (x, y) wszystkie wartości (od 1 do 9), i jeśli jakaś pasuje (can_insert), próbuje wypełniać sudoku dalej.

bool next(int x, int y) {
    if (x == 8 && y == 8) return true;
    else if (x == 8) return solve(0, y + 1);
    else return solve(x + 1, y);
}

I ostatnia funkcja. To bardziej funkcja pomocnicza, wskazuje które następne pole sudoku zgadywać (trzeba jakoś ustalić kolejność rozwiązywanych pól).
Czyli dla współrzędnych (0, 0) próbuje (1, 0), dla (1, 0) próbuje (2, 0), dla (3, 0) próbuje (4, 0) itd.
Dało się to rozwiązać inaczej, ale takie rozwiązanie wydawało mi się najprostsze.

Ogólnie cały ten algorytm to klasyczny przykład rekurencji z powrotami (możesz googlować jeśli Cię temat interesuje).

msm napisał(a):

bool can_insert(int x, int y, int value) {
    for(int i = 0; i < 9; i++) {
        if (value == curr[x][i] || value == curr[i][y] ||
            value == curr[x/3*3+i%3][y/3*3+i/3]) return false;
    } return true;
}

Sprawdzanie czy do sudoku można wstawić wartość value na miejsce (x, y).
W szczególności, nie można wstawić wartości na pole jeśli:

• w wierszu y jest już taka wartość
• w kolumnie x jest już taka wartośc
  • w tym kwadracie 3x3 jest już taka wartość**

Hej, nie rozumiem tego:
value == curr[x/33+i%3][y/33+i/3])
Skąd się wzięły te wartości? :O

x/3*3 to zaokrąglenie w dół do 3 (czyli dla x=0 to będzie 0, dla x=1 to będzie 0, dla x=2 to będzie 0, dla x=3 to będzie 1, itd).
Czyli curr[x/3*3][y/3*3] to współrzędne lewego górnego rogu mniejszego kwadratu w sudoku, zawierającego pole x, y.

curr[x/3*3+i%3][y/3*3+i/3] przechodzi po kolei przez wszystkie współrzędne w tym kwadracie.

Inaczej mówiąc, to wyrażenie sprawdza po kolei wszystkie wartości w mniejszym kwadracie 3x3 w sudoku (żeby mieć pewność że sie nie powtarzają).