Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Utvärdering av sudokulösare baserade på mänskliga lösningstekniker: En jämförelse med Dancing links som referensalgoritm
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2014 (Swedish)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [sv]

Syftet med den här rapporten var att undersöka under vilka förutsättningar en regelbaserad algoritm eventuellt skulle kunna vara effektivare för att lösa sudokupussel än Donald Knuths totalsökningsalgoritm Dancing links. Förutsättningarna som testades var pusselstorlek och pusselsvårighetsgrad. Den regelbaserade lösarens regler implementerades utifrån ett antal vanliga lösningstekniker som människor brukar använda sig av och referenslösaren baserades på Knuths egna pseudokod för algoritmen Dancing links. De två lösarna implementerades i Java och deras respektive körtider för varje pussel plus övrig information om körningen och de testade pusslen sparades. Resultatet visade att den regelbaserade lösaren klarade av att lösa de flesta pusslen testade i rimlig tid, och de största pusslen med högre svårighetsgrad snabbare än Dancing links. Slutsatsen som kunde dras var att även om det fanns fall då den regelbaserade lösaren var bättre så var den dels besvärligare att implementera och dels sämre för den vanligaste pusselstorleken 9x9, vilket begränsade dess användningsområden.

Place, publisher, year, edition, pages
2014. , 46 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-146014OAI: oai:DiVA.org:kth-146014DiVA: diva2:721639
Subject / course
Computer Science
Educational program
Bachelor of Science in Engineering - Computer Engineering
Supervisors
Examiners
Available from: 2014-11-25 Created: 2014-06-04 Last updated: 2014-11-25Bibliographically approved

Open Access in DiVA

fulltext(604 kB)117 downloads
File information
File name FULLTEXT01.pdfFile size 604 kBChecksum SHA-512
d49e327dc3713ce3cad35a4e0eddfeb892d96014875b742faaf97afc145962a47a8cdb0b007e67c335959263fd7bdb157a6761109acbe6944ca353097675a65a
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Bronge, EricaSundh, Jakob
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 117 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: 221 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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