Efficient array for solving sudoku problem
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...
Main Author: | |
---|---|
Format: | Bachelor Thesis |
Language: | English |
Published: |
Umeå universitet, Institutionen för datavetenskap
2018
|
Subjects: | |
Online Access: | http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-155407 |
id |
ftumeauniv:oai:DiVA.org:umu-155407 |
---|---|
record_format |
openpolar |
spelling |
ftumeauniv:oai:DiVA.org:umu-155407 2023-10-09T21:56:15+02:00 Efficient array for solving sudoku problem Effektiv array för att lösa sudoku problem Spara grannar i Dancing Links utan pekare Foroutan Rad, Aria 2018 application/pdf http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-155407 eng eng Umeå universitet, Institutionen för datavetenskap UMNAD 1173 http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-155407 info:eu-repo/semantics/openAccess Engineering and Technology Teknik och teknologier Student thesis info:eu-repo/semantics/bachelorThesis text 2018 ftumeauniv 2023-09-22T13:50:59Z 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. 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. Bachelor Thesis The Pointers Umeå University: Publications (DiVA) |
institution |
Open Polar |
collection |
Umeå University: Publications (DiVA) |
op_collection_id |
ftumeauniv |
language |
English |
topic |
Engineering and Technology Teknik och teknologier |
spellingShingle |
Engineering and Technology Teknik och teknologier Foroutan Rad, Aria Efficient array for solving sudoku problem |
topic_facet |
Engineering and Technology Teknik och teknologier |
description |
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. 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. |
format |
Bachelor Thesis |
author |
Foroutan Rad, Aria |
author_facet |
Foroutan Rad, Aria |
author_sort |
Foroutan Rad, Aria |
title |
Efficient array for solving sudoku problem |
title_short |
Efficient array for solving sudoku problem |
title_full |
Efficient array for solving sudoku problem |
title_fullStr |
Efficient array for solving sudoku problem |
title_full_unstemmed |
Efficient array for solving sudoku problem |
title_sort |
efficient array for solving sudoku problem |
publisher |
Umeå universitet, Institutionen för datavetenskap |
publishDate |
2018 |
url |
http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-155407 |
genre |
The Pointers |
genre_facet |
The Pointers |
op_relation |
UMNAD 1173 http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-155407 |
op_rights |
info:eu-repo/semantics/openAccess |
_version_ |
1779320866233909248 |