Sudoku solver nie działa

Sudoku solver nie działa
K1
  • Rejestracja:prawie 7 lat
  • Ostatnio:ponad 5 lat
  • Postów:32
0

Nie wiem czemu ale mam gdzieś błąd w algorytmie, który rozwiązuje zadane sudoku i nie umiem go znaleźć. O to mój algorytm:

Kopiuj
#include <iostream>  
using namespace std;

bool mozliwe(int tab[9][9], int i, int j, int k){
    for(int a = 0; a < 9; a++){
        if(k == tab[i][a] || k == tab[a][j]) return false;
    }
    i /= 3;
    j /= 3;
    i *= 3;
    j *= 3;
    for(int m = i; m < i + 3; m++)
        for(int n = j; n < j + 3; n++)
            if(tab[i][j] == k) return false;
    return true;
}

void solver(int tab[9][9], int k, int l){
    if(k == 8 && l == 8) return;
    else{
        for(k; k < 9; k++){
            l %= 9;
            for(l; l < 9; l++){
                if(tab[k][l] != 0) continue;
                for(int m = 1; m < 10; m++){
                    if(mozliwe(tab, k, l, m)){
                        tab[k][l] = m;
                        solver(tab, k, (l + 1) % 9);
                        tab[k][l] = 0;
                    }
                }
            }
        }
    }
}

int main(){
    int sudoku[9][9] = {{0,6,0,7,5,0,0,0,3},
                        {0,0,0,0,3,8,0,0,2},
                        {9,0,0,0,0,6,0,0,0},
                        {6,0,0,5,0,7,0,0,0},
                        {8,0,0,0,0,0,0,1,0},
                        {3,0,0,1,0,0,2,0,7},
                        {0,0,0,0,0,0,0,0,5},
                        {0,0,7,9,0,0,0,6,0},
                        {0,9,0,6,0,0,0,0,0}};
    solver(sudoku, 0, 0);
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++)
            cout << sudoku[i][j];
        cout << endl;}
}

Bartosz36
  • Rejestracja:ponad 10 lat
  • Ostatnio:prawie 4 lata
  • Postów:348
0

Na czym polega błąd?


ExtendedVector czyli std::vector<T> z wygodą List<T> z .NET (ForEach, FindAll, itd...)
K1
  • Rejestracja:prawie 7 lat
  • Ostatnio:ponad 5 lat
  • Postów:32
0

Program w ogóle nie zwraca wyniku a jak zwraca to zwraca wynik początkowy

MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:9 minut
1

To nie wygląda nawet na połowę algorytmu rozwiązującego.
Twój algorytm jest brutal forcem, więc ma za duża złożoność.
Dla podanego przykładowego problemu, nie skończy się w rozsądnym czasie nawet jeśli użyjesz mocnej maszynki.
Testujesz mniej więcej 9^54 przypadków (przeszacowane, ale zrobiłeś to w taki sposób, że wychodzi taka skala problemu).

I jeszcze na dodatek jak już znajdziesz rozwiązanie, to nie robisz nic by je "zatwierdzić/zapamiętać", tylko cofasz wszystkie znalezione wartości.
W rekurencji brakuje wartości zwracanej bool określającej czy w danym przypadku rozwiązanie istnieje.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 7x, ostatnio: MarekR22
NO
Akurat to nie do końca bruteforce i z tego co szybki google pokazuje to taki backtracking jest rozsądnym sposobem rozwiązywania standardowego sudoku, natomiast to co piszesz w drugim akapicie zdecydowanie sprawia że ten program nigdy nie zwróci oczekiwanego wyniku :-)
MarekR22
jak "nie do końca bruteforce"? Przeszukuje wszystkie możliwe wypadki dla każdego nieznanego pola.
NO
No backtracking to niby jest typ bruteforce, ale to nadal lepsze niż bruteforce w stylu wypełnienia wszystkich pól i sprawdzenia dopiero wtedy czy to poprawne rozwiązanie.
MarekR22
sortować za pomocą bogosort też można :)
enedil
  • Rejestracja:prawie 12 lat
  • Ostatnio:16 dni
  • Postów:1027
1

Masz znaczący błąd w linijce 14.

K1
Jaki błąd? Wszystko jest okej

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.