View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        The NP-completeness of some lesser known logic puzzles

        Thumbnail
        View/Open
        Scriptie_Mieke_Maarse_5750032.pdf (633.2Kb)
        Publication date
        2019
        Author
        Maarse, A.H.
        Metadata
        Show full item record
        Summary
        Logic puzzles have been gaining popularity and many puzzles have been proved to be NP-complete. When a puzzle is NP-complete, it is not feasible to try to compute a solution. In this case algorithms that approximate the solution, or programs that are limited in input size can be used. In this paper we use the Hamiltonian path and cycle problems in grid graphs, and the Latin square completion problem to show that the puzzles unequal and adjacent, towers, chains and linesweeper are NP-complete.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/33867
        Collections
        • Theses
        Utrecht university logo