Zadanie
Táto úloha sa dá nahradiť riešením sady arrays_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.
Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Andrejovi na
Výborne! Ani my nevieme skryť nadšenie z toho, koľkí z vás si poradili s našou výzvou – vyriešiť osemsmerovky a pomôcť tým Žabovej babke. Dokonca ste si tým vyslúžili aj jej rešpekt. Nastal však problém, ako to už býva, babka o osemsmerovky z tohto dôvodu stratila záujem a teraz nevie, čo robiť. Nádej prišla až včera ráno, keď zahliadla vo svojich obľúbených novinách nový typ hlavolamu s názvom sudoku. Zo začiatku si s ním nevedela dať rady, ale po chvíli v ňom už bola expertka.
Rozhodla sa, že si s vami tentokrát dá súťaž, keď už vám tie hlavolamy tak idú. Prebiehať to bude tak ako ste zvyknutí. Vy odovzdáte program a ona začne v tom istom čase riešiť. Ak to stihnete skôr ako ona, body sú vaše, ak nie, tak za daný pokus nič nedostanete. Babke trvá vyriešenie každej sudoku presne \(2\) sekundy. Vďaka súbojom s vami možno príde na lepšie metódy riešenia a tie vám po konci tejto série pošle, ako námet na riešenie.
Úloha
Sudoku je hra, v ktorej dostanete mriežku rozmerov \(9\times9\), v ktorej sú zo začiatku doplnené nejaké čísla a nejaké samozrejme chýbajú. Vašou úlohou je doplniť všetky prázdne políčka podľa nasledujúcich pravidiel:
1: do mriežky môžete doplniť iba čísla \(1\) až \(9\)
2: pre každý riadok musí platiť, že sa v ňom nachádza každé čislo práve raz
3: pre každý stĺpec musí platiť, že sa v ňom nachádza každé čislo práve raz
4: ak si rozdelíme túto mriežku \(9\) štvorčekov veľkosti \(3\times3\) tak ako na obrázku, musí platiť, že v každom sa nachádza každé čislo práve raz.
Čísla, ktoré sú na začiatku napísané vo vnútri mriežky samozrejme spĺňajú hore uvedené pravidlá.
Sudoku môže vyzerať napríklad nasledovne.
Na vstupe od nás dostanete jedno takéto sudoku s niekoľkými prázdnymi políčkami. Vašou úlohou je napísať program, ktorý dané sudoku vyrieši a vypíše na výstup.
Vstup
Na vstupe sa bude nachádzať presne \(9\) riadkov, pričom každý bude obsahovať \(9\) čísel. \(j\)-te číslo na \(i\)-tom riadku \(a_{i,j}\), reprezentuje číslo v \(i\)-tom riadku a \(j\)-tom stĺpci mriežky. Pre všetky \(a_{i,j}\) platí \(0 \leq a_{i,j} \leq 9\). Iste ste si všimli, že \(a_{i,j}\) je z rozsahu až \(10\) čísiel. Prázdne políčko budú reprezentované číslom \(0\). To znamená, že dopĺnať budete rovnako ako v pôvodnom sudoku iba čísla \(1\) až \(9\).
Výstup
Na výstup vypíšte správne doplnenú sudoku. Vašou úlohou je teda nahradiť všetky 0 zo vstupu tak, aby boli dodržané hore uvedené pravidlá. V prípade, že dané sudoku má viac riešení, vypíšte ľubovolné z nich. Môžete predpokladať, že každé zadané sudoku má aspoň jedno riešenie.
Sudoku vypisujte na výstup po riadkoch. Medzi jednotlivými číslami sa musia nachádzať medzery. To, či sa aj za posledným číslom v riadku bude nachádzať medzera alebo nie, je na vás, nespôsobí to chybu pri testovaní, avšak nezabudnite každý riadok oddeliť znakom konca riadku “\n”. Výstup má teda obsahovať \(9\) riadkov, pričom v každom sa bude nachádzať presne \(9\) čísel oddelených medzerou, reprezentujúcich jednotlivé políčka v sudoku, za ktorými bude nasledovať znak konca riadku.
Hodnotenie
Vaše riešenie bude ako obyčajne testované na rôznych sadách, ktoré sa budú líšiť obtiažnosťou ich riešenia.
Keďže riešiť menšie sudoku by bolo podvádzanie, sady sa líšia iba tým, koľko čísel v sudoku chýba.
- V prvej sade platí, že v každom riadku chýba práve jedno políčko.
- V druhej sade platí, že v každom stĺpci chýba práve jedno políčko.
- V tretej sade platí, že v každom bloku veľkosti 3x3 chýba práve jedno políčko.
- Vo štvrtej sade platí, že počas riešenia a dopĺňania vždy existuje aspoň jedno políčko, ktoré vieme jednoznačne doplniť z pohľadu na riadok, stĺpec a blok, v ktorom sa nachádza. Inak povedané, pre toto políčko iba jedno číslo spĺňa, že sa nenachádza v rovnakom stĺpci, riadku a bloku.
- V piatej sade neplatia žiadne obmedzenia.
Príklady
Input:
0 2 8 1 6 0 0 0 4
0 0 0 4 7 0 0 0 0
0 0 0 0 0 8 9 0 1
4 0 5 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0
0 3 0 0 0 0 4 0 6
6 0 3 9 0 0 0 0 0
0 0 0 0 8 7 0 0 0
9 0 0 0 4 5 8 3 0Output:
7 2 8 1 6 9 3 5 4
5 1 9 4 7 3 6 2 8
3 4 6 2 5 8 9 7 1
4 9 5 8 3 6 2 1 7
8 6 2 7 1 4 5 9 3
1 3 7 5 9 2 4 8 6
6 8 3 9 2 1 7 4 5
2 5 4 3 8 7 1 6 9
9 7 1 6 4 5 8 3 2 Vstup a výstup zodpovedá osemsmerovke zo zadania spolu s riešením.
Input:
0 7 2 3 9 5 6 4 1
4 0 6 7 2 1 8 9 5
9 5 0 6 8 4 2 3 7
7 1 3 0 4 2 9 5 6
2 8 5 9 0 6 1 7 4
6 4 9 1 5 0 3 2 8
5 2 8 4 6 3 0 1 9
1 6 4 2 7 9 5 0 3
3 9 7 5 1 8 4 6 0Output:
8 7 2 3 9 5 6 4 1
4 3 6 7 2 1 8 9 5
9 5 1 6 8 4 2 3 7
7 1 3 8 4 2 9 5 6
2 8 5 9 3 6 1 7 4
6 4 9 1 5 7 3 2 8
5 2 8 4 6 3 7 1 9
1 6 4 2 7 9 5 8 3
3 9 7 5 1 8 4 6 2Vstup, ktorý sa môže vyskytnúť aj v prvej aj v druhej sade.
Vzorové riešenie, ako aj väčšina vašich, sú založené na postupnom dopĺňaní jednotlivých políčok. Samotné sady sa líšia iba zložitosťou algoritmu, ktorý na dopĺňanie musíme použiť.
Prvá vec, ktorú musíme vyriešiť je, ako budeme sudoku reprezentovať v pamäti. Z dostupných možností, je najlepším riešením použiť dvojrozmerné pole. Takéto pole vieme indexovať a pristupovať na jeho jednotlivé políčka dvomi číslami \((a,b)\), kde \(a\) je číslo riadku a \(b\) číslo stĺpca daného políčka. Prvý riadok a stĺpec má poradové číslo \(0\) a teda hovoríme, že indexujeme od nuly. Z technických príčin budeme používať jeho inteligentnú implementáciu a to vector.
Sada 1, 2
Pustime sa teraz do prvých dvoch sád. Ako sa ukáže, ich riešenie je veľmi podobné. Sudoku budeme v oboch prípadoch prechádzať zľava doprava a zhora dole. Ak narazíme na prázdne políčko, musíme ho doplniť. V prvej sade je toto políčko jediné, ktoré v riadku chýba. Stačí sa nám teda pozrieť na to, ktoré čísla sú v danom riadku doplnené a zaznačiť si ich do pomocného poľa. Po prejdení celého riadku bude existovať iba jediné číslo medzi 1 a 9, ktoré sme nezaznačili ako nájdené. Je zrejmé, že to bude práve to hľadané číslo, ktoré chceme doplniť. Tento postup zopakujeme pre každé prázdne políčko a postupne vyplníme celé sudoku.
No a pri riešené druhej sady vieme robiť to isté, akurát pri zaznačovaní čísel budeme prechádzať stĺpec a nie riadok.
Predstavme si, že sa nachádzame na políčku \((a,b)\), ktoré ešte nie je doplnené, teda sa na ňom nachádza \(0\). Ktoré políčka sa nachádzajú v rovnakom riadku? Sú to všetky políčka s rovnakou prvou súradnicou označujúcou riadok, teda s rovnakým \(a\): \((a,0)\), \((a,1)\), \((a,2)\) … \((a,8)\). V našom programe potom prejdeme všetkými týmito políčkami a do pomocné poľa pouz[] si zaznačíme, ktoré čísla sú v riadku \(a\) doplnené. Z tohto poľa potom ľahko vyčítame, ktoré číslo v tomto riadku chýba.
#include<iostream>
#include<vector>//using kvoli vectoru
using namespace std;
int main()
{
vector<vector<int> > vstup(9, vector<int>(9));//vytvorime dvojrozmerny vektor
// v skutocnosti sa sprava velmi podobne ako pole a mohli by sme tuto deklarciu
// prepisat aj na : "int vstup[9][9];"
for(int i=0;i<9;++i)for(int j=0;j<9;++j)
{
cin >> vstup[i][j];//nacitame vstup
}
for(int i=0;i<9;++i)for(int j=0;j<9;++j)if(vstup[i][j] == 0)
{//narazili sme na prazdne policko na pozicii [i;j]
bool pouz[10] = {false};//tu si pamatame, ktore cisla uz sme pouzili/videli
//resp. su doplnene
//na zaciatku je pole plne false
for(int k=0;k<9;++k)pouz[vstup[i][k]] = true;
//for(int k=0;k<9;++k)pouz[vstup[k][j]] = true;//pouzijeme v pripade stlpca
for(int k=0;k<10;++k)if(pouz[k] == false)//ak je k nepouzite
{
vstup[i][j]=k;//doplnime ho a skoncime
break;
}
}
//a uz len doplnene sudoku cele vypiseme
for(int i=0;i<9;++i)
{
for(int j=0;j<9;++j)cout << vstup[i][j] << " ";
cout<<"\n";
}
return 0;
}Sada 3
Napriek tomu, že problém je skoro rovnaký ako v prvých dvoch sadách, implementácia je o niečo zložitejšia. Postup, ktorý môžeme zvoliť je, že budeme jednotlivé bloky vypĺňať postupne. Vždy vezmeme čísla v jednom bloku a zistíme, ktoré číslo v danom bloku chýba. Potom ho doplníme namiesto \(0\). Ako to však naimplementovať?
Predstavme si algoritmus, ktorý zrejme dokáže väčšina z vás bez problémov naprogramovať. Spočíva v tom, že doplní chýbajúce číslo v prvom bloku \(3\times 3\). Najskôr prejdeme menší štvorec \(3\times 3\) a zaznačíme si, tak ako v predchádzajúcich príkladoch, už doplnené čísla a tiež ktoré políčko v bloku nie je doplnené. Zo zadania vieme, že bude iba jedno. Na konci raz prejdeme zoznamom čísel a zistíme, ktoré z nich nebolo použité. Toto číslo doplníme na súradnice, na ktorých leží v danom bloku číslo 0. A keďže sa pozeráme iba na prvý blok \(3\times 3\), vieme, že prvý aj druhý index každého políčka v tomto bloku je menší ako 3. Implementácia preto môže vyzerať nasledovne:
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<vector<int> > vstup(9, vector<int>(9));//vytvorime dvojrozmerne pole
for(int i=0;i<9;++i)for(int j=0;j<9;++j)
{
cin >> vstup[i][j];//nacitame vstup
}
int a, b;//tu si pamatame indexy nedoplneneho policka
vector<bool>pouz(10, false);//tu ake cisla sme videli v nasom bloku
for(int k=0;k<3;++k)for(int l=0;l<3;++l)//riesime len prvy maly stvorcek 3x3
{
if(vstup[k][l] == 0)//ak je policko prazdne, zapametame si indexy do a, b
{
a = k;
b = l;
}
pouz[vstup[k][l]] = true;//kazdopadne si ho zaznacime
}
for(int f=0;f<10;++f)if(!pouz[f])//ak nie je pouzite, vieme, ze je jedine
{
vstup[a][b]=f;//doplnime ho
break;
}
for(int i=0;i<9;++i)//uz len vsetko vypiseme
{
for(int j=0;j<9;++j)cout << vstup[i][j] << " ";
cout<<"\n";
}
return 0;
}Ako nám to však pomôže pri dopĺňaní ostatných blokov? Pozrime sa na indexy políčok v ľavom hornom rohu každého bloku.
Rýchlo uvidíme istú zákonitosť. Ľavé horné políčko každého bloku má indexy v tvare \((0+3k,0+3l)\), kde \(k\) a \(l\) je menšie ako 3.
Všimnime si, čo sa stane ak k políčku v prvom bloku pripočítame indexy nejakého z týchto rohových políčok.
Uvidíme, že nás toto sčítanie posunulo na rovnaké políčko, akurát v inom bloku. Presnejšie v tom bloku, ktorého ľavé horné políčko bolo pri sčítavaní použité. V našom riešení teda vieme postupne prejsť týchto \(9\) políčok a v každom bloku sa budeme tváriť akoby sme pracovali s blokom prvým, akurát budeme o niečo posunutí.
V prvom bloku pracujeme s políčkami \((0,0)\), \((0,1)\), \((0,2)\), \((1,0)\) … až \((2,2)\). A napríklad v strednom bloku pracujeme s tými istými políčkami, avšak jednotlivé indexy sú posunuté o indexy ľavého horného políčka stredného bloku, teda robíme na indexoch \((0+3,0+3)\) až \((2+3,2+3)\).
Pomocou tejto úvahy sa vieme pohodlne presúvať po jednotlivých blokoch, čo vedie k nasledujúcej implementácii.
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<vector<int> > vstup(9, vector<int>(9));
for(int i=0;i<9;++i)for(int j=0;j<9;++j)
{
cin >> vstup[i][j];//nacitame vstup
}
for(int i=0;i<9;i+=3)for(int j=0;j<9;j+=3)
{
//cout<< i <<" "<< j <<endl;//vypise suradnice laveho horneho policka
int a, b;
vector<bool>pouz(10, false);
for(int k=0;k<3;++k)for(int l=0;l<3;++l)//tvarime sa, ze riesime prvy stvorcek
{
//v skutocnosti sa ale nachadzame na vstup[i+k][j+l] a nie na vstup[k][l]
if(vstup[i+k][j+l] == 0)//ak je policko prazdne, zapametame si indexy do a, b
{
a = i+k;//v a, b uz su skutocne suradnice policka, ktore nie je
b = j+l;//doplnene
}
pouz[vstup[i+k][j+l]] = true;//kazdopadne si ho zaznacime
}
for(int f=0;f<10;++f)if(!pouz[f])
{
vstup[a][b]=f;
break;
}
}
for(int i=0;i<9;++i)
{
for(int j=0;j<9;++j)cout << vstup[i][j] << " ";
cout<<"\n";
}
return 0;
}Sada 4
Riešenie štvrtej sady je zhrnutím toho, čo sme sa v tomto vzorovom riešení zatiaľ naučili. Sudoku budeme prechádzať tak ako doteraz, až pokým nebude úplne doplnená, avšak samotné dopĺňanie bude o čosi zložitejšie. Zadanie jasne hovorí, že niektoré z políčok je ľahko doplniteľné, ale nehovorí ktoré. Toto je problém, na ktorý si napíšeme pomocnú funkciu je_jednoznacne(a,b). Táto funkcia na vstupe dostane naše sudoku a pozíciu jedného prázdneho políčka \((a,b)\). Pre toto políčko vráti true, ak je práve toto políčko jednoznačne doplniteľné a false ak nie je.
Táto funkcia bude robiť to, že si vytvorí pole doplnených čísel a toto pole použije pri prejdení riadku, stĺpca aj bloku, v ktorom leží zadané políčko. Tým vlastne zistí, ktoré čísla nemôžu byť doplnené na pozíciu, ktorej jednoznačnosť overuje. Ak nám na doplnenie ostane viacero možností, nevieme políčko jednoznačne doplniť tak ako hovorí zadanie. Ak nám však ostala jediná možnosť, vieme políčko jednoznačne doplniť. Hodnotu, ktorú na toto políčko vieme vložiť vieme zistiť pomocou našeho poľa, my si však vytvoríme ešte jednu funkciu – je_mozne(a,b,k).
Táto funkcia slúži ako pomocná a jej existenciu naplno doceníme pri piatej sade. Funkcia na vstupe dostane naše sudoku, súradnice políčka \((a,b)\) a jedno číslo \(k\). Na výstupe nám vráti true, ak môžeme číslo \(k\) doplniť na políčko s indexami \((a,b)\) a v opačnom prípade vráti false. Pozor, táto funkcia nám nehovorí, či je správne doplniť číslo \(k\) na túto pozíciu. Hovorí iba to, či ho tam môžeme doplniť vzhľadom na aktuálny stav sudoku tak, aby sme neporušili žiadne pravidlo. Hodnotu true teda vráti, ak sa číslo \(k\) nenechádza ani v riadku \(a\), ani v stĺpci \(b\) a ani v bloku, v ktorom leží \((a,b)\).
Problém nastáva, keď chceme zistiť, v ktorom bloku sa nachádza políčko so súradnicami \((a,b)\). Možností ako toto riešiť je viac, my použijeme asi tú najjednoduchšiu. Uvedomme si, že blok vieme jednoznačne určiť podľa rozsahu hodnôt, v ktorom sa nachádza \(a\) a \(b\). Keďže vieme, aký je blok veľký, na jeho prejdenie nám stačí už len vedieť, kde máme začať.
Už dávnejšie sme prišli na to, že ľavé horné políčka v každom bloku majú zaujímavé súradnice, ktoré sú deliteľné trojkou. Pokúsme sa to nejak využiť. Ak sa pozrieme napríklad na stĺpec, tak sa v ňom nachádza \(9\) políčok, ktoré sú rovnomerne rozložené do \(3\) blokov. Ako zo súradnice zistíme, v ktorom bloku sa nachádza? Predsa ju vydelíme trojkou. Poďme si to overiť. Čísla \(0\), \(1\), \(2\) po delení \(3\) naozaj vrátia \(0\). Čo to znamená je, že sú v jednom z prvých blokov. Čísla \(3\), \(4\), \(5\) vrátia \(1\), čo o nich hovorí, že sú v jednom zo stredných blokov. Ak toto urobíme aj pre druhú súradnicu, vieme jednoducho určiť v ktorom bloku sa nachádza. Tak napríklad políčko \((5,7)\) sa nachádza v \(5/3=1\) bloku v rámci riadku a v \(7/3=2\) v rámci stĺpca, pričom indexujeme od nuly. Ak sa teraz pozrieme, kde sa naozaj políčko nachádza, zistíme, že presne tam, kde sme určili.
Ako toto využiť? Pri celočíselnom delení sa zahadzuje zvyšok po delení, čo znamená, že napríklad výraz \((x/3)\cdot 3 \neq x\). Tento výraz sa nebude zakaždým rovnať pôvodnému číslu, ale prvému menšiemu alebo rovnému násobku \(3\). Čo sa teraz stane, keď index “bloku” vynásobíme opäť \(3\)? Stane sa to, že sa číslo bloku zase zmení na číslo nejakého políčka a to práve ľavého horného prislúchajúceho bloku. Na získanie ľavého horného rohu bloku, v ktorom sa nachádza políčko \((a,b)\) potrebujeme teda obe súradnice \(a\) aj \(b\) vydeliť a potom opäť prenásobiť 3.
Keď máme tieto dve funkcie napísané, vieme už túto sadu riešiť pomerne jednoducho. Sudoku prechádzame stále odznova, pokým nie je doplnená. V prípade, že narazíme na políčko, ktoré je prázdne, skontrolujeme, či ho môžeme jednoznačne doplniť. Ak áno, prejdeme cez všetky možné čísla, pričom vieme, že pre to jediné, ktoré môžeme na toto miesto doplniť, nám funkcia je_mozne() vráti true.
#include<iostream>
#include<vector>
using namespace std;
bool je_mozne(const vector<vector<int> >&sudoku, int a, int b, const int &k)
{
for(int i=0;i<9;++i)if(sudoku[a][i] == k)return false;//prejdeme riadok
for(int i=0;i<9;++i)if(sudoku[i][b] == k)return false;//prejdeme stlpec
//prejdeme blok
int m=(a/3)*3, n=(b/3)*3;
for(int i=m;i<m+3;++i)for(int j=n;j<n+3;++j)if(sudoku[i][j] == k)return false;
return true;
}
bool je_jednoznacne(const vector<vector<int> >&sudoku, int a, int b)
{
int pom=0;
vector<bool>nachadza(10, false);
for(int i=0;i<9;++i)nachadza[sudoku[a][i]]=true;
for(int i=0;i<9;++i)nachadza[sudoku[i][b]]=true;
int m=(a/3)*3, n=(b/3)*3;
for(int i=m;i<m+3;++i)for(int j=n;j<n+3;++j)nachadza[sudoku[i][j]]=true;
for(int i=1;i<10;++i)if(nachadza[i] == false)pom++;
if(pom == 1)return true;
return false;
}
int main()
{
vector<vector<int> >sudoku(9, vector<int>(9));
int nedoplnene = 0;
for(int i=0;i<9;++i)for(int j=0;j<9;++j)
{
cin >> sudoku[i][j];
if(sudoku[i][j] == 0)nedoplnene++;
}
for(int f=0;f<nedoplnene;++f)
{
for(int i=0;i<9;++i)for(int j=0;j<9;++j)if(sudoku[i][j] == 0)
{
if(je_jednoznacne(sudoku, i, j))
{
for(int k=1;k<10;++k)if( je_mozne(sudoku, i, j, k) == true)
{
sudoku[i][j]=k;
break;
}
}
}
}
for(int i=0;i<9;++i)
{
for(int j=0;j<9;++j)cout << sudoku[i][j] << " ";
cout<<"\n";
}
return 0;
}Pokiaľ vás v tejto implementácii mätie, prečo sme funkcii nedali parametre takto vector<vector<int> > sudoku, ale takto const vector<vector<int> > &sudoku, čítajte ďalej. Pokiaľ by sme použili prvý spôsob, C++ by predpokladalo, že pôvodné pole nechceme meniť a preto by vytvorilo jeho kópiu, všetky zmeny čo sme vykonali vo funkcii by sa teda po konci funkcie zahodili, pretože toto skopírované pole by prestalo existovať. Ak však použijeme operátor &, hovoríme tým počítaču, že chceme aby pole poslalo ako referenciu, teda poslalo do funkcie pôvodné pole a my sme mohli zmeny vykonávať priamo v ňom. Toto je ešte dôležitejšie pri veľkých poliach, pri ktorých kopírovanie zaberá dlhý čas, čo by mohlo spôsobiť problémy.
Nakoniec už len vysvetliť kľučové slovo const. Ak ho použijeme pred nejakou premennou alebo poľom, hovoríme počítaču, že túto premennú/pole/ vector nechceme meniť. Chceme z nej iba načítavať alebo sa na ňu pozerať. Používať túto konvenciu vrelo odporúčam, pretože počítač nás pri nechcenej zmene takejto premennej upozorní a nespustí, resp. neskompiluje náš program.
Sada 5
Zatiaľ sme v podstate neskúsili poriadny bruteforce. Ten by nás však veľmi nepomohol, keďže možných sudoku je vzhľadom na naše pomery takmer nekonečne veľa. Avšak práve táto myšlienka nás teraz privedie k vzorovému riešeniu.
Predstavme si takýto algoritmus. Máme funkciu vyries(), ktorá na vstupe dostane sudoku a vráti nám true ak ju vedela vyplniť. Ako by takáto funkcia asi vyzerala? Použijeme rekurziu.
Prvý prípad je, že funkcia sa pozrela na zadané sudoku a nenašla v nej žiadne voľné políčka. Vtedy je sudoku zjavne vyriešené a funkcia vráti true a skončí. Druhý prípad je, že aspoň jedno políčko je nevyplnené. Čo táto funkcia urobí je, že prejde všetky možnosti, čo doplniť na toto voľné miesto a pri prvom čísle, ktoré nebude porušovať pravidlá sudoku, ho skúsi doplniť.
Takýmto splsobom dostane sudoku, ktoré má o jedno voľné políčko menej a môže opäť skúsiť zavolať funkciu vyries(). Predstavme si, že je táto funkcia ďalej úspešná a vráti true. Doplnilnili sme teda jedno číslo a rekurzívna funkcia ďalej zistila, že takúto sudoku vieme riešiť a toto číslo tam naozaj patrilo. V takom prípade dostaneme vyriešené sudoku.
Samozrejme, môže nastať aj druhý prípad, keď po doplnení čísla vráti rekurzívna funkcia vyries() hodnotu false. To znamená, že číslo, ktoré sme doplnili, priviedlo sudoku do nevyriešiteľného stavu. Toto číslo tam teda nepatrilo. Musíme preto na danú pozíciu skúsiť doplniť iné číslo a rekurzívnym volaním opäť overiť, či takto upravenú sudoku vieme vyriešiť.
No a v momente, keď sme pre voľné políčko vyskúšali všetky možnosti a zakaždým sme sa dostali do nevyriešiteľného stavu vieme, že táto sudoku nemôže byť správna, lebo sa nedá žiadnym spôsobom vyriešiť. Vrátime preto hodnotu false.
Tento postup, ktorý sme použili sa v skutočnosti vyskytuje v programovaní dosť často. Nazýva sa backtracking a používa sa v situáciách, keď prechádzame postupne všetky možnosti, pričom dúfame, že zlé možnosti si všimneme dostatočne skoro a nebudeme sa ich kontrolovaním vôbec zaťažovať.
Backtracking prebieha v niekoľkých fázach. Máme nejakú rekurzívnu funkciu, ktorá najprv dostane reprezentáciu problému, v našom prípade pole s uloženým sudoku. Pokúsi sa v riešení problému postúpiť daľej tým, že niečo v poli doplní, čím zmenší pôvodný problém a zavolá sama seba na toto nové pole. Ak sa jej nepodarí nájsť riešenie, vráti pole do stavu v akom ho dostala a vráti false. V opačnom prípade, ak sa niektorej z vetiev podarilo nájsť riešenie, teda táto vetva vrátila true, aj naša funkcia vráti true a ďalšie možnosti už neskúša.
#include<iostream>
#include<vector>
using namespace std;
bool je_mozne(const vector<vector<int> >&sudoku, int a, int b, const int &k)
{
for(int i=0;i<9;++i)if(sudoku[a][i] == k)return false;
for(int i=0;i<9;++i)if(sudoku[i][b] == k)return false;
int m=(a/3)*3, n=(b/3)*3;
for(int i=m;i<m+3;++i)for(int j=n;j<n+3;++j)if(sudoku[i][j] == k)return false;
return true;
}
bool vyries(vector<vector<int> >&sudoku)//rekurzivna funkcia riesiaca sudoku
{
for(int i=0;i<9;++i)for(int j=0;j<9;++j)if(sudoku[i][j] == 0)
{
for(int k=1;k<=9;++k)if( je_mozne(sudoku, i, j, k) )//mozme na toto policko dat k?
{
sudoku[i][j] = k;//skusime ho doplnit
if( vyries(sudoku) )return true;//ak tam patrilo vratime sa
sudoku[i][j] = 0;//inak tam zas dame nulu
}
if(sudoku[i][j] == 0)return false;//ak sme ho nevedeli vyplnit nijak, vratime sa
}
}
int main()
{
vector<vector<int> >vstup(9, vector<int>(9));
for(int i=0;i<9;++i)for(int j=0;j<9;++j)cin >> vstup[i][j];
vyries(vstup);
for(int i=0;i<9;++i)
{
for(int j=0;j<9;++j)cout << vstup[i][j] << " ";
cout<<"\n";
}
return 0;
}Časová zložitosť tohto prístupu nie je nijak oslnivá. Uvedomme si, že sa tu dosť spoliehame na to, že nedôjde k najhoršiemu možnému scenáru, teda vyskúšaniu všetkých možností. To sa totiž naozaj môže stať. Nevieme prečo, ale ukazuje sa, že k takejto situácii prichádza málokedy, skoro až nikdy. Všeobecnejšia verzia tohto problému, kde riešime sudoku rozmerov \(n\times n\), sa ukazuje byť tažká, presnejšie NP-úplná.
Čo to znamená, že je problém NP-úplný? Detailami a teóriou vás nudiť nebudeme, stačí nám vedieť, že NP-úplné problémy sú tie, na ktoré ešte neboli vyvinuté efektívne algoritmy. V preklade to znamená, že najlepší algoritmus, ktorý sme zatiaľ vymysleli stále negarantuje, že nevyskúša všetky možnosti. V priemernom prípade si môže tento algortimus počínať výborne, avšak v najhoršom stále len vyskúša všetky možnosti, čo je práve prípad aj našeho algoritmu.
Napriek tomu, ak sa vám podarí vytvoriť algoritmus, ktorý bude takýto problém riešiť a zároveň garantovať, že nevyskúša v najhoršom prípade všetky možnosti, neváhajte nám ho poslať! Získate prvé miesto v PRASKU a aj odmenu \(1\,000\,000\) dolárov, ktorá na vyriešenie tohto problému bola vypísaná. Platí totiž, že ak sa nájde algoritmus riešiaci len jeden z NP-úplných problémov, bude sa s miernymi zmenami dať použiť na vyriešenie všetkých týchto problémov.
V prípade, že ste niečomu vo vzoráku nepochopili alebo vás inšpiroval k vyriešeniu NP-úplného problému, neváhajte ma kontaktovať na [email protected]. S výhrou aj vašimi nejasnosťami sa rád podelím.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.