Sudoku - jaki algorytm na rozwiązanie?

0

Witam,
poszukuję jakiegoś algorytmu pozwalającego rozwiązać sudoku. Jestem początkującym programistą, więc najlepszy byłby dla mnie pseudokod. Mimo to dziękuję za każdą formę pomocy.
Pozdrawiam

1
     Initialize 2D array with 81 empty grids(nx=9,ny=9)
     Fill in some empty grid with the known values
     Make an original copy of the array
     Start from top left grid(nx=0,ny=0), check if grid is empty
     if (grid is empty){
     assign the empty grid with values (i) 
       if (no numbers exists in same rows & same columns same as (i))
       fill in the number
       if (numbers exists in same rows & same columns same as (i))
       discard (i) and repick other values (i++)
     }else{
       while (nx<9){
         Proceed to next row grid(nx++,ny)
           if (nx equal 9){
           reset nx = 1
           proceed to next column grid(nx,ny++)
               if (ny equal 9){
               print solutions
               }
           }           
     }

http://en.wikipedia.org/wiki/Sudoku_solving_algorithms

0

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?

0

Moze jakis algo genetyczny?

2

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.n[...]ience/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;
}
0

Dziękuję wszystkim za pomoc :)

1

Jakby kogoś to bardziej kręciło to publikacja moich kolegów:
http://www.itl.waw.pl/czasopisma/JTIT/2013/2/49.pdf ;)

0

Jeszcze jedno pytanko. Chciałbym trochę podrasować program. Czy jest możliwość (w dosyć łatwy sposób) przemienić ten algorytm na taki, który rozwiąże sudoku z nieregularnymi kształtami, zamiast tych 9 kwadratów (3x3)?

0

Wystarczy że podmienisz bool can_insert(int x, int y, int value) {

0

Nie wiem czy się do końca zrozumieliśmy. Chodzi mi o sudoku z kształtami w takim stylu: http://penszko.blog.polityka.[...]nt/uploads/2012/10/Pesu_2.jpg

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