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
Lösning av Sudoku med mänskliga strategier
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2013 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Sudoku is a puzzle that has become popular during the

last decade. A great number of algorithms have been implemented

to solve the problem but many use approaches

that do not correspond to how a human solves a sudoku

puzzle. The purpose of this project was to evaluate how

a strategy based algorithm which utilizes a more human

approach compares to a so called Dancing Links-algorithm

and an exhaustive search algorithm with respect to solving

time and correctness.

A qualitative study was conducted, with four respondents,

which together with a literature study lay the foundation

for the strategies in the implemented algorithm.

Furthermore, a comparison was performed with 725 sudoku

puzzles of which the strategy-based algorithm only

managed to solve sudoku puzzles of a limited difficulty

where the others solved all. The result showed though,

that the strategy based algorithm was the fastest for the

difficulties that it solved, but at the same time it showed

a trend hinting at increased solving time with increasing

difficulty.

Finally, it could be determined that Dancing Links is

a generally faster algorithm than the others. A strategy

based algorithm could however be a fast alternative when

solving sudoku puzzles of the difficulties that often appear

in daily papers.

Abstract [sv]

Sudoku är ett pussel som har blivit populärt det senaste

decenniet. Ett stort antal algoritmer har implementerats

för att lösa problemet men många använder angreppssätt

som inte motsvarar hur en människa går tillväga för att lösa

sudokupussel. Syftet med projektet var utvärdera hur en

strategibaserad algoritm som använder ett mer mänskligt

angreppsätt står sig mot en sk. Dancing Links-algoritm och

en totalsökningsalgoritm med avseende på tid och korrekthet.

I projektet genomfördes en kvalitativ undersökning, med

fyra respondenter, som tillsammans med en litteraturstudie

lade grunden för strategierna i den implementerade algoritmen.

Vidare gjordes en jämförelse med 725 sudokupussel av

vilka den strategibaserade algoritmen endast löste sudokupussel

av en begränsad svårighetsgrad medan de övriga

löste samtliga. Resultat visade däremot att den strategibaserade

algoritmen var snabbast för de svårighetgrader den

löste men samtidigt också en trend om förlängd lösningstid

vid ökande svårighetgrad.

Slutligen kunde det konstateras att Dancing Links är

en generellt snabbare algoritm än de övriga. En strategibaserad

algoritm kan dock vara ett snabbt alternativ vid

lösning av sudokupussel av de svårighetsgrader som ofta

förekommer i dagstidningar

Place, publisher, year, edition, pages
2013.
Series
Kandidatexjobb CSC, K13064
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-136683OAI: oai:DiVA.org:kth-136683DiVA: diva2:676654
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2013-12-13 Created: 2013-12-06 Last updated: 2013-12-13Bibliographically approved

Open Access in DiVA

Lösning av Sudoku med mänskliga strategier(683 kB)298 downloads
File information
File name FULLTEXT01.pdfFile size 683 kBChecksum SHA-512
1a18d3950fd2849aee07d7876513d18cf8d04db7f5add4d9da4c5c9bbe0f02aca585c71ebb254ac5ba0de2e0063843c76e5c205c1cabea768356b45ee1548156
Type fulltextMimetype application/pdf

Other links

http://www.csc.kth.se/utbildning/kth/kurser/DD143X/dkand13/Group10Pawel/report/j.brodin.j.pellby.finalreport.pdf
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 298 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: 146 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