Primjena algoritama za bojanje grafova na Sudoku

završni rad

• Naslov (engleski): Graph coloring algorithms applied on Sudoku
• Autor: Marko Đukin
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Josip Žubrinić (član povjerenstva)
• Član povjerenstva: Vlatko Crnković (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-07-05, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu istražuje se primjena egzaktnih algoritama za bojanje grafova u kontekstu rješavanja Sudoku problema. Fokus je stavljen na Lawlerov algoritam i Brownov
algoritam, koji su se pokazali uspješnim u rješavanju slicnih problema. Lawlerov al- ˇ
goritam koristi tehniku grananja i ogranicavanja za sistematsko pretraživanje prostora ˇ
mogucih rješenja, dok Brownov algoritam koristi tehniku dinami ´ ckog programiranja.

Sažetak (engleski)

This paper explores the application of exact graph coloring algorithms in the context of solving Sudoku puzzles. The focus is on Lawler’s algorithm and Brown’s algorithm, which have shown success in solving similar problems. Lawler’s algorithm utilizes a branch-and-bound technique for systematic search of the solution space, while
Brown’s algorithm uses dynamic programming.

• Ključne riječi: bojanje grafova; sudoku; Lawlerov algoritam; Brownov algoritam; dinamicko programiranje; Grananje i ograni ˇ cavanje
• Ključne riječi (engleski): Graph coloring; Sudoku; Lawler’s algorithm; Brown’s algorithm; Dynamic programming; Branch and bound
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:710105
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-10-11 08:47:42