⇦ Početna stranica

Algoritmi u rješavanju sudoka

Igrači koriste različite kompjuterske algoritme za rješavanje sudoka, a istraživači su tu da proučavaju njihova svojstva i stvaraju nove igre, uključujući sudoku.

Postoji nekoliko algoritama koji se mogu koristiti kako bi došli do rješenja.

Backtracking

Uključuje isprobavaje mogućih elemenata u jednome polju u potrazi za rješenjem, te zatim prelazak na iduće polje - i tako redom. Zapravo, pokušavamo pogoditi rezultat u svakome polju isprobavajući redom sve opcije, a ako tijekom igre ustanovimo da neki element nije valjan, vraćamo se natrag te ga ispravljamo – otuda naziv backtracking.

Prednosti:

Nedostatak:

Stohastička potraga / metode optimizacije

Stohastički ili nasumilni algoritmi rješevaju se ovako:

  1. Nasumično dodijelimo brojeve praznim poljima
  2. Izračunamo broj pogrešaka
  3. Mijenjamo brojeve sve dok broj pogrešaka nije 0

Ovaj način rješavanja puno je brži od backtrackinga.

Programiranje ograničenja

Sudoku može biti postavljen kao constraint satisfaction problem – matematičko pitanje definirano kao skup objekata čije stanje mora zadovoljiti broj ograničenja (pravila). Ovdje se koriste algoritmi zaključivanja bazirani na tim ograničenjima te se primjenjuju u traženju rješenja.

Ovo je najbrža metoda rješavanja, a kombinirana s backtrackingom rješava svaki sudoku.