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:
- Što je rješenje zagarantirantirano (barem dok je slagalica valjana – ako se u nekom trenutku ispostavi da nije, moguće je odbaciti sva prethodna valjano rješena polja)
- Vrijeme rješavanja ne ovisi o težini
- Jednostavniji je od ostalih algoritama
Nedostatak:
- Potrebno mu je puno vremena da dođe do rješenja
Stohastička potraga / metode optimizacije
Stohastički ili nasumilni algoritmi rješevaju se ovako:
- Nasumično dodijelimo brojeve praznim poljima
- Izračunamo broj pogrešaka
- 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.