Algoritmi za rešavanje sudokua

S Vikipedije, slobodne enciklopedije
A typical Sudoku puzzle, a 9x9 grid with several numbers missing
Tipična Sudoku slagalica

Sudoku slagalica se sastoji iz 81 ćelije i one se nalaze u mreži 9x9 koja je podeljena u 9 zona, gde se u svakoj zoni nalazi po 9 ćelija. Svaka ćelija može da sadrži broj od jedan do devet, svaki broj se može naći samo jednom u svakoj zoni. Na samom početku rešavanja slagalice neke od ćelija će biti popunjene sa brojevima. Cilj je da se i sve ostale ćelije popune brojevima. Igrači mogu da koriste širok spektar strategija za rešavanje Sudokua, i ovaj članak prekriva niz metoda za rešavanje.

Tehnike[uredi | uredi izvor]

Bektreking[uredi | uredi izvor]

Algoritmi bektrekinga koji su prilagođeni za rešavanje Sudokua isprobavaju sva moguća rešenja za dati Sudoku. Ako dodeljena rešenja ne predstavljaju rešenje celokupnog Sudokua algoritam odbacuje dodeljeno rešenje i vraća se na prvobitna rešenja, a onda pokušava ponovo i zbog toga se zove bektreking.[1]

Ispod je ispisan generalni pseudokod bektreking algoritma za standardni Sudoku primer (9x9).[2] 

 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) & 3x3 square (i) is currently in)
     fill in the number
   if (numbers exists in same rows & same columns same as (i) & 3x3 square (i) is currently in)
     discard (i) and repick other values (i++)
 }
 else {
   while (nx < 9) {
     Proceed to next row grid(nx++, ny)
     if (nx equals 9) {
       reset nx = 1
       proceed to next column grid(nx,ny++)
       if (ny equals 9) {
         print solution
       }
     }
   }
 }
Animirani gif pokazuje kako se Sudoku rešava pomoću bektrekinga. Crveni broj je “fiksiran” broj, dok algoritam neprestano pokušava da pronađe rešenje da popuni prazne ćelije Sudokua. Primetite kako algoritam odbacuje sva prethodna rešenja ako trenutno rešenje ne ispunjava uslov.

Tačna odluka[uredi | uredi izvor]

Sudoku može biti opisan kao primer “problema tačne odluke”. Ovo dovodi i do elegantnog opisa problema i efikasnog rešenja korišćenjem bektrekinga. Dok tačna odluka ne garantuje brzo rešavanje zona, popunjavanje Sudokua koristeći algoritam za tačnu odluku, kao što je Igrajuće veze, tipično rešava 9x9 Sudoku za nekoliko sekundi.

Iscrpna pretraga (gruba sila)[uredi | uredi izvor]

Programeri su napravili kompjuterske programe koji vrše iscrpne pretrage, tj. koriste grubu silu. Iako je utvrđeno da postoji približno 6.67 x 1021 finalnih rešenja, koristeći iscrpnu pretragu kompjuterski algoritam može da bude praktična metoda rešavanja slagalica, ukoliko je kod dobro dizajniran.

Prednosti ove metode su:

  • Rešenje je zagarantovano (dok god je slagalica ispravna)
  • Vreme rešavanja uglavnom nije povezano sa težinom slagalice

Mane ove metode su da je poprilčno spora kad se uporedi sa kompjuterskim metodama rešavanja koje su osmišljene prema deduktivnim metodama.

Algoritam “grube sile” dolazi do praznih ćelija po nekom redu, redom ih popunjava brojevima koji odgovaraju, ili bektrekingom (uklanjanjem neodgovarajućih izbora) dok ne dođe do kraja. Na primer, program iscrpne pretrage će rešiti slagalicu umetanjem cifre “1” u prvu ćeliju i proveravanjem da li je dozvoljeno da se ona tu nađe. Pri proveravanju da li ima prestupa, saznaje se da “1” nije dozvoljeno, pa se zato vrednost povećava na ”2”. Ako se pronađe ćelija gde nijedna od 9 cifara nije dzvoljena, algoritam ostavlja tu ćeliju praznu i vraća se na prethodnu ćeliju. Tada se vrednost u toj ćeliji povećava za 1. Algoritam se ponavlja sve dok ne nađe odgovarajuće rešenje za svu 81 ćeliju.[3][4]

Nasumična pretraga/metoda optimizacije[uredi | uredi izvor]

Sudoku se može rešiti koristeći nasumične metode pretrage.[5][6] Primer ovog pristupa je da:

  1. Nasumično odredi brojeve praznim ćelijaama u mreži
  2. Izračuna broj grešaka
  3. “Promeša” ove unete brojeve po mreži dok se broj grešaka ne svede na nulu

Rešenje slagalice će tada biti pronađeno. Pristupi mešanju brojeva uključuju simulaciono prekaljivanje, genetički algoritam i tabu pretraživanje. Nasumično zasnovani optimizovani algoritmi znaju da budu veoma brzi, iako možda nisu brzi kao neke logički zasnovane tehnike. Za razliku od drugih, optimizacioni algoritmi ne zahtevaju da problemi budu obavezno logički rešivi, tako im davajući potencijal da reše širi raspon problemskih slučajeva. Algoritmi dizajnirani za grafičko bojenje isto znaju da rade veoma dobro sa Sudoku slagalicama.[7]

Takođe je moguće da Sudoku prikažemo kao problem celobrojnoh linearnog programiranja. Izgleda da su takvi pristupi bliži brzom pronalaženju rešenja i onda mogu da koriste račvanje pred kraj. Simpleks algoritam deluje kao da može da podnese veoma dobro situacije bez rešenja ili sa višestrukim rešenjima.

Ograničeno programiranje[uredi | uredi izvor]

Sudoku je ograničen problem. Sudoku kao ograničen problem[8] opisuje mnoge razumne algoritme pristupačne u formi ograničenja koji se mogu primeniti na modelu i rešiti problem. Neki moderatori ograničenja obuhvataju primer kako podesiti i rešiti Sudoku probleme.[9][10] Program ograničenja podešavanjem i rešavanjem će kod većine slučajeva imati manje od 100 redova koda. Ako kod koristi jak razuman algoritam, uključivanje pretrage je potrebno samo za najteže slagalice.

Vreme računanja[uredi | uredi izvor]

Kompjuterski algoritmi izvršavaju sve više ciklusa kada pretražuju Sudoku sa 20 ili manje tragova. Zaista, slagalice sa 17 tragova je izuzetno teško rešiti. Kada se ograničenje simetrije primeni, očekivano vreme pretrage će se dramatično povećati još više.[11]

Prazne Sudoku mreže[uredi | uredi izvor]

Iako Sudoku mreže koje dolaze sa nekim od ćelija koje su unapred popunjene, rešavanje može biti veoma izazovno, prazne Sudoku ćelije se zapravo mogu veoma brzo rešiti. Možda je najlakši način da se to sprovede je da se proizvede korensko rešenje, koje se može dostići korišćenjem sledećeg jednostavnog polinomijalnog vremenskog algoritma.

Za standardnu n2 x n2 (9 x 9) mrežu, ovaj algoritam (ekvivalentna implementacija u Javi i Haskelu) je sledeći: 

final int n = 3;
final int[][] field = new int[n*n][n*n];
for (int i = 0; i < n*n; i++)
	for (int j = 0; j < n*n; j++)
		field[i][j] = (i*n + i/n + j) % (n*n) + 1;

sol :: [[Int]]
sol = [ [ witness (build i j) | j <- [0..heightGame] ]
                              | i <- [0..heightGame] ]
  where
    build i j     = (i * heightRegion) + (i `div` heightRegion) + j
    witness       = (`mod` heightGame) . (+ 1)
    heightRegion  = 3
    heightGame    = heightRegion^2

Navedeni postupak daje sledeći 9x9 Sudoku: 

+-----------------------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |
|-------+-------+-------|
| 2 3 4 | 5 6 7 | 8 9 1 |
| 5 6 7 | 8 9 1 | 2 3 4 |
| 8 9 1 | 2 3 4 | 5 6 7 |
|-------+-------+-------|
| 3 4 5 | 6 7 8 | 9 1 2 |
| 6 7 8 | 9 1 2 | 3 4 5 |
| 9 1 2 | 3 4 5 | 6 7 8 |
+-----------------------+

Reference[uredi | uredi izvor]

  1. ^ Zelenski, Julie. Lecture 11 | Programming Abstractions (Stanford). Stanford Computer Science Department. 
  2. ^ „YasSS - Yet Another (Simple”. Arhivirano iz originala 30. 06. 2014. g. Pristupljeno 19. 05. 2016.  Tekst „Stupid) Sudoku Solver - Moritz Lenz ” ignorisan (pomoć)
  3. ^ „Geeks For Geeks Back Tracking Sudoku Algorithm”. Arhivirano iz originala 28. 08. 2016. g. Pristupljeno 19. 05. 2016. 
  4. ^ Solving Every Sudoku Puzzle
  5. ^ Lewis, R (2007) Metaheuristics Can Solve Sudoku Puzzles Journal of Heuristics, vol. 13 (4). str. 387-401.
  6. ^ Perez, Meir and Marwala, Tshilidzi (2008) Stochastic Optimization Approaches for Solving Sudoku arXiv:0805.0697.
  7. ^ Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.
  8. ^ „"Sudoku kao ograničen problem"” (PDF). Arhivirano iz originala (PDF) 07. 10. 2009. g. Pristupljeno 19. 05. 2016. 
  9. ^ "JaCoP"
  10. ^ "Sudokusolver"
  11. ^ "17 Clue Sudoku with Diagonal Symmetry"

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Алгоритми_за_решавање_судокуа&oldid=26807445”