The NP-completeness of pen and paper puzzles

dc.rights.license	CC-BY-NC-ND
dc.contributor.advisor	Rin, B.
dc.contributor.advisor	Klein, D.
dc.contributor.author	Donkers, M.T.
dc.date.accessioned	2021-09-02T18:00:33Z
dc.date.available	2021-09-02T18:00:33Z
dc.date.issued	2021
dc.identifier.uri	https://studenttheses.uu.nl/handle/20.500.12932/1383
dc.description.abstract	Pen and paper puzzles are often NP-complete. When a problem is NP-complete, it is commonly understood that (under the assumption that P is not equal to NP) the problem is too complex for computers to compute a solution in reasonable time. In this paper we use the Hamiltonian grid graph problem and Planar NOR CircuitSAT to prove that respectively Arukone3 and Bariasensa are NP-complete.
dc.description.sponsorship	Utrecht University
dc.format.extent	4711007
dc.format.mimetype	application/pdf
dc.language.iso	en
dc.title	The NP-completeness of pen and paper puzzles
dc.type.content	Bachelor Thesis
dc.rights.accessrights	Open Access
dc.subject.keywords	NP-completeness, computational complexity, puzzles
dc.subject.courseuu	Kunstmatige Intelligentie