Algoritmi → Rekurzija i bektreking → Sudoku rešavač (bektreking)

Sudoku rešavač (bektreking)

Lekcija 7 od 7 · Rekurzija i bektreking

Sudoku je odličan primer bektrekinga: prazna polja popunjavamo jedno po jedno, a čim neki broj izazove sukob, vraćamo se i probamo sledeći. Na kraju lekcije je i poboljšanje koje rešavač ubrzava više stotina puta.

Pre nego što počneš: potrebno predznanje – Bektreking.
Kako da učiš: svaki primer prekucaj i pokreni, a zadatke na kraju prvo reši sam/a; uputstvo i rešenje otvori tek posle toga. Svi programi su u C++-u.

Pravila i predstavljanje table

Tabla je 9 × 9, podeljena na devet kvadrata 3 × 3. U svaku vrstu, kolonu i kvadrat treba upisati brojeve od 1 do 9, svaki tačno jednom. Tablu čuvamo kao matricu int t[9][9], a prazno polje kao 0. Ulaz je 9 redova po 9 cifara.

Kvadrat kome pripada polje (r, k) ima redni broj (r / 3) * 3 + k / 3 (od 0 do 8).

Rešavač

Za brzu proveru vodimo tri tabele zauzetosti: uVrsti[r][b], uKoloni[k][b] i uKvadratu[q][b] – da li je broj b već upotrebljen. Funkcija resi(p) popunjava polja redom (p = 0 … 80) i vraća true čim je tabla popunjena.

#include <iostream>
#include <string>
using namespace std;

int t[9][9];
bool uVrsti[9][10], uKoloni[9][10], uKvadratu[9][10];

int kvadrat(int r, int k) { return (r / 3) * 3 + k / 3; }

void postavi(int r, int k, int b, bool vrednost) {
    uVrsti[r][b] = uKoloni[k][b] = uKvadratu[kvadrat(r, k)][b] = vrednost;
}

bool resi(int p) {
    if (p == 81) return true;                   // sva polja su popunjena
    int r = p / 9, k = p % 9;
    if (t[r][k] != 0) return resi(p + 1);       // polje je zadato
    for (int b = 1; b <= 9; b++) {
        if (uVrsti[r][b] || uKoloni[k][b] || uKvadratu[kvadrat(r, k)][b]) continue;
        t[r][k] = b; postavi(r, k, b, true);    // izaberi
        if (resi(p + 1)) return true;           // istraži – rešenje nađeno
        t[r][k] = 0; postavi(r, k, b, false);   // poništi
    }
    return false;                               // nijedan broj ne odgovara
}

int main() {
    for (int r = 0; r < 9; r++) {
        string red;
        cin >> red;
        for (int k = 0; k < 9; k++) {
            t[r][k] = red[k] - '0';
            if (t[r][k] != 0) postavi(r, k, t[r][k], true);
        }
    }
    if (!resi(0)) {
        cout << "Nema resenja" << endl;
        return 0;
    }
    for (int r = 0; r < 9; r++) {
        for (int k = 0; k < 9; k++) cout << t[r][k];
        cout << "\n";
    }
    return 0;
}

Primer

Ulaz

530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079

Izlaz

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

Ubrzanje: prvo polje sa najmanje mogućnosti

Rešavač iznad popunjava polja redom. Kod teških sudokua mnogo je brže da se u svakom koraku izabere prazno polje sa najmanje dozvoljenih brojeva: ako polje ima samo jednu mogućnost, nema grananja, a ako ima nula – odmah se vraćamo. Ova heuristika (u literaturi „MRV – minimum remaining values“) smanjuje stablo pretrage za nekoliko redova veličine.

// Umesto "sledeće polje redom", u funkciji resi() biramo najbolje polje:
int najboljeR = -1, najboljeK = -1, najmanje = 10;
for (int r = 0; r < 9; r++)
    for (int k = 0; k < 9; k++) {
        if (t[r][k] != 0) continue;
        int moguce = 0;
        for (int b = 1; b <= 9; b++)
            if (!uVrsti[r][b] && !uKoloni[k][b] && !uKvadratu[kvadrat(r, k)][b]) moguce++;
        if (moguce < najmanje) { najmanje = moguce; najboljeR = r; najboljeK = k; }
    }
if (najboljeR == -1) return true;   // nema praznih polja – rešeno
if (najmanje == 0) return false;    // ćorsokak
// ... dalje isto kao ranije, ali za polje (najboljeR, najboljeK)
Česte greške i saveti
  • Pre rekurzivnog poziva ažuriraj i tablu i tabele zauzetosti, a posle neuspešnog poziva vrati obe.
  • Funkcija koja vraća bool i odmah izlazi kad nađe rešenje mnogo je brža od one koja traži sva rešenja.
  • Za kvadrat 3 × 3 koristi celobrojno deljenje: r / 3 i k / 3.
  • Uvek proveri i ulaz bez rešenja – program treba to da prijavi, a ne da se vrti bez kraja.

Proveri znanje

Otvori kviz

Mini kviz: Sudoku

1. Koji redni broj kvadrata ima polje (4, 7) (indeksi od 0)?




2. Šta funkcija resi() treba da uradi kada nijedan broj ne odgovara polju?