umu.sePublications
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
Efficient array for solving sudoku problem
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Effektiv array för att lösa sudoku problem Spara grannar i Dancing Links utan pekare (Swedish)
Abstract [en]

In Knuth’s example of Dancing Links and Algorithm X (DLX), pointers were used to connect the neighbors with each other. This has caused problems when DLX is used for parallelisation and to solve this some workaround is needed. One solution is to store the pointers as indicesin an array instead. The purpose of this thesis is therefore answer how a solution based on indices compares time wise to a solution with pointers. A comparison was made by implementing two versions of DLX, one with pointers and one with indices. Each version was then used to solve sudoku puzzles and the time taken was measured. The result of this was that the representations had similar complexity but the representation with indices fell behind since each recursion took longer time compared to the representation with pointers. Therefore parallelisation is needed to put the representation with indices up to par with the represnetation with pointers.

Abstract [sv]

I Knuths exempel av Dancing Links och Algorithm X (DLX) användes pekare för att koppla ihop grannar med varandra. Problemet med denna lösning är att när DLX ska parallelliseras är det inte möjligt att använda sig av samma pekare. Istället måste en alternativ lösning hittas för detta problem och en lösning är att använda index i en array. Denna rapport kommer därmed ge ett svar på hur snabb en lösning med index är jämförtmed en representation med pekare genom att implementera två versioner av DLX, en med pekare och den andra med index. Resultatet av detta var att representationerna hade liknande komplexitet men array representationen tog längre tid än representationen med pekare eftersom att varje rekursion tog längre tid. Parallellisering behövs därav för att göra array representationen lika snabb som representationen med pekare.

Place, publisher, year, edition, pages
2018. , p. 24
Series
UMNAD ; 1173
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:umu:diva-155407OAI: oai:DiVA.org:umu-155407DiVA, id: diva2:1278842
Educational program
Bachelor of Science Programme in Computing Science
Supervisors
Examiners
Available from: 2019-01-15 Created: 2019-01-15 Last updated: 2019-01-15Bibliographically approved

Open Access in DiVA

fulltext(327 kB)49 downloads
File information
File name FULLTEXT01.pdfFile size 327 kBChecksum SHA-512
d52e14ae70ceb81ad1380597fa4744224ea7383189ebb6f42f03f596b25ef583ebdd883a324c2c5c58d852e584706b34c7675c6bff182675d29fea4b71fb1d44
Type fulltextMimetype application/pdf

By organisation
Department of Computing Science
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 49 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: 130 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