Računalna igra zasnovana na potrazi za hamiltonovskim ciklusom u neusmjerenom grafu

završni rad

• Naslov (engleski): Computer Game Based on Hamiltonian Cycle Search in an Undirected Graph
• Autor: Toma Petrač
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Domagoj Kovačević (č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: 2019-07-12, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Lewis in a Maze jednostavna je računalna logička igra napisana u programskom jeziku
Python. Cilj igre je u zadanom vremenu riješiti što više slučajno nacrtanih grafova, na
način da se, za svaki od njih, pronađe jedan Hamiltonov put. Ako takav put ne postoji u
grafu, potrebno je pritisnuti gumb za nerješivost grafa. Postoje tri različite razine koje igrač
može odabrati. O tim razinama ovisi broj vrhova grafova koje treba riješiti, kao i
koeficijent kojim se na kraju igre množi ukupan broj bodova. Rezultati se mogu spremiti u
tablicu s rezultatima (bazu podataka, highscores).
Grafičko sučelje igre realizirano je Pythonovom standardnom bibliotekom tkinter, a
tablica s rezultatima standardnom bibliotekom sqlite3. Što se tiče crtanja grafova,
iskorištena je i modificirana vanjska biblioteka netgraph: open-source projekt s github
repozitorija za upravljanje, stvaranje i prikazivanje grafova.
Glavni algoritam koji se koristi za pronalazak svih Hamiltonovih putova u grafu je
iscrpna pretraga s backtrackingom.

Sažetak (engleski)

Lewis in a Maze is a simple computer puzzle game written in a programming language
called Python. Goal of the game is to solve as many graphs as possible, in the given time.
To solve a graph means to find a Hamiltonian path in it. If such a path doesn't exist, it is
possible to state so by pressing the „Unsolvable“ button. There are three difficulties to
choose. Depending on those difficulties, the number of nodes in a graph varies, as well as
the factor which multiplies total collected points at the end of the game. Results can be
saved to table with the highscores (database file).
Graphic user interface (GUI) is implemented with the Python's standard module,
tkinter, while the highscores are implemented with sqlite3. As for graph plotting,
an external library called netgraph is used and modified. It is an open-source
project from the github repository for managing, creating and plotting (displaying)
graphs.
The main algorithm used for finding all the Hamiltonian paths in the graph is the bruteforce algorithm with backtracking.

• Ključne riječi: računalna igra; logička igra; teorija grafova; neusmjereni grafovi; bestežinski grafovi; hamiltonovost; Hamiltonov ciklus; Hamiltonov put; iscrpna pretraga; backtracking; Python; tkinter; matplotlib; numpy; sqlite3
• Ključne riječi (engleski): computer game; puzzle game; graph theory; undirected graphs; weightless graphs; Hamiltonian cycle; Hamiltonian path; brute-force search algorithm; backtracking; Python; tkinter; matplotlib; numpy; sqlite3
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:310018
• 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: 2020-01-07 21:16:58