Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Solving Heyawake puzzles using Answer Set Programming
KTH, School of Computer Science and Communication (CSC).
2014 (English)Independent thesis Advanced level (professional degree), 10 credits / 15 HE creditsStudent thesis
Abstract [sv]

Den här rapporten undersöker automatisk lösning av Heyawakepussel genom att använda Answer Set Programming. Heyawake är på många sätt likt det mer välkända Sudoku men har inte blivit lika efterforskat vilket gör spelet väldigt intressant att undersöka.Spelet är bevisat NP-fullständigt så fokus har legat på att implementera lösaren istället för att göra den så snabb som möjligt men endel optimeringar har ändå gjorts.Answer Set Programming ha länge använts för att lösa NP-fullständiga problem och för Heyawake är det möjligt att lösa normalstora pussel väldigt snabbt. För att optimera lösaren krävs djupgående kunskaper om Answer Set Programming-lösaren som används.

Abstract [en]

This report exmamines automatic solving of Heyawake puzzles usingAnswer Set Programming. Heyawake is somewhat similar to the morewell known Sudoku but has not been as extensively researched whichmakes the game very interesting to examine.The game has previously been proven to be NP-complete so the focushas been on implementing the solver instead of making it fast althoughsome optimizations has been made.Answer Set Programming has long been used to solve NP-completeproblems and for Heyawake it is possible to solve normal sized puzzlesvery fast. Optimizing the solver proved to be hard unless you have extensiveknowledge of the Answer Set Programming solver that is used.

Place, publisher, year, edition, pages
2014.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-157344OAI: oai:DiVA.org:kth-157344DiVA: diva2:769770
Examiners
Available from: 2014-12-09 Created: 2014-12-09 Last updated: 2015-08-27Bibliographically approved

Open Access in DiVA

fulltext(627 kB)435 downloads
File information
File name FULLTEXT01.pdfFile size 627 kBChecksum SHA-512
1897b1c6959613a94867691832ee67b6037591827d77648a9d0541329a4778650eb535082aa1cc55a5c55ceab29b82e717462f355441191840d5b45602b40e2a
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 435 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 158 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf