Sudoku solver nie działa

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:

#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;}
}

0

Na czym polega błąd?

0

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

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.

1

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1