Analiza problema obilaska šahovske ploče skakačem

undergraduate thesis

• Title (english): Analysis of Knight's Tour Problem
• Author: Marko Palameta
• Mentor: Lana Horvat Dmitrović (mentor)
• Committee member: Lana Horvat Dmitrović (predsjednik povjerenstva)
• Committee member: Ana Žgaljić Keko (član povjerenstva)
• Committee member: Mate Puljiz (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-09-01, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem obilaska skakača na ploči je problem iz domene teorije grafova. Šahovska figura skakač, svojim potezima u obliku slova L, posjećuje polja šahovske ploče na način da ih posjeti samo jedanput. Općenito, riječ je o problemu pronalaska hamiltonovskog puta u neusmjerenom grafu. Za rješavanje problema koristi se Backtracking algoritam, uz primjenu Warnsdorffovog pravila za optimizaciju.

Abstract (english)

A knight's tour problem is a problem from the domain of graph theory. The knight chess piece, with its moves in the shape of a letter L, traverses the squares of the chessboard in a way that visits each square only once. In general, this is a problem of finding a hamiltonian path in an undirected graph. The problem is solved using Backtracking algorithm, with the application of Warnsdorff's rule for optimization.

• Keywords: Šah; Skakač; Graf; Hamiltonovski put; Warnsdorffovo pravilo; Pretraživanje prostora stanja; Algoritam DFS; Tremaux stablo; Backtracking
• Keywords (english): Chess; Knight; Graph; Hamiltonian path; Warnsdorff's rule; State space search; DFS algorithm; Tremaux tree; Backtracking
• Language: croatian
• URN:NBN: urn:nbn:hr:168:755399
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 09:37:56