Sudoku solver

Sveiki, gavau užduotį padaryti sudoku solverį, tačiau reikia šiokios tokios konsultacijos. Mano sugalvotas algoritmas:

1) Surandu tusčias vietas ('0')

2) Turiu konstantinį masyvą su 1,2,...,9 skaičiais

3) Susirandu eilutes ar stulpelius, kur mažiausiai '0', t.y. kur didžiausia tikimybė įrašyti skaičių iš masyvo kažkurį

4) Tada pasiemu iš tos eilutės visus skaičius duotus ir įsidedu į masyvą

5) Tada pasižiūriu kokius skaičius įsidėjau ir kokių trūksta iš konstantinio masyvo (nelabai žinau kaip šitą realizuoti dar)

6) Bandau įrašinėti ir žiūriu ar nesikartoja nei stulpely, nei eilutėje.

Neesu įsitikinęs dėl šito algoritmo efektyvumo, tad teiraujuos jūsų, koks būtų pats efektyviausias ir realizuojamas sudoku solver'is? Gal kokių įdėjų pametėsit?

Čia backtrackingo uždavinys, man atrodo.

Use google. KTU mokė grafų teoremų, tai va, čia gali rasti tai ko Tau reikia. Čia turbūt vienas iš optimaliausių variantų.

Easy implementacijos variantas:

1. Turi 9x9 masyvą

2. Susirandi kurie masyvo nariai yra tušti ir kiek jų yra (pvz randi kad trūksta bendrai 5 skaičių)

3. Suki ciklą nuo 11111 iki 99999, įstatai skaičius eilės tvarka į tuščias vietas ir tikrini ar visas 9x9 masyvas yra validus sprendimas.

Šitas sprendimas ilgiau ieškos varianto, bet labai nesunku pagaminti

Sudėtingesnis:

1. Susikuri klasę block, kuri yra 3x3 masyvas

2. Susikuri block masyvą 3x3 (sumoje gausis kaip ir aukščiau 9x9)

3. Susirandi trūkstamus skaičius block'e, kad jis būtų validus (nėra pasikartojančių skaičių)

4. Viską vykdai while cikle ir kai esi prabėgęs pro visus 9 blokus, tikrini eilučių/stulpelių validumą

5. Randi atsakymą

Šitas sprendimas sudėtingiau padaromas, bet truputi efektyvesnis

Šiaip abiems atvejais bus daug if'ų, tai nenusigąsk

Dėkui!

Sudėtingesnis:

1. Susikuri klasę block, kuri yra 3x3 masyvas

2. Susikuri block masyvą 3x3 (sumoje gausis kaip ir aukščiau 9x9)

3. Susirandi trūkstamus skaičius block'e, kad jis būtų validus (nėra pasikartojančių skaičių)

4. Viską vykdai while cikle ir kai esi prabėgęs pro visus 9 blokus, tikrini eilučių/stulpelių validumą

5. Randi atsakymą

Šitas sprendimas sudėtingiau padaromas, bet truputi efektyvesnis

 

Šiaip abiems atvejais bus daug if'ų, tai nenusigąsk

Dar truputį paklausiu: aš jau turiu apsirašęs sudoku 9x9, tai man jį reikia išsiskaidyt į 3x3 taip išeina?

pilna sprendimų yra jau, https://www.geeksforgeeks.org/backtracking-set-7-suduku/ va su visais komentarais net, išsinagrinėk ir apsiginsi lengvai.