Hoexum, Eline (2020) Revisiting the proof of the complexity of the sudoku puzzle. Bachelor's Thesis, Mathematics.
|
Text
bMATH_2020_HoexumES.pdf.pdf Download (1MB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
toestemming.pdf Restricted to Registered users only Download (91kB) |
Abstract
In 2003 it was shown by Takayuki Yato that the sudoku puzzle is an NP-complete and ASP-complete problem. The proof provided in this paper involved a reduction from the Latin SquareCompletion problem, which is quite similar to a sudoku puzzle. However, as the paper was not solely focused on the sudoku puzzle, the formulation of the proof was short and not very intuitive. This paper will describe the method of proof in more detail and give more context, as to make it more understandable. Additionally, because there has not been much research done into other ways to prove the NP- and ASP-completeness of the sudoku puzzle, a different approach to the proof is explored. After this, the solving procedure is explained and the performances of different solving algorithms are compared to determine which is the most efficient method for solving a sudoku puzzle.
| Item Type: | Thesis (Bachelor's Thesis) |
|---|---|
| Supervisor name: | Verbrugge, L.C. and Top, J. |
| Degree programme: | Mathematics |
| Thesis type: | Bachelor's Thesis |
| Language: | English |
| Date Deposited: | 17 Jul 2020 09:19 |
| Last Modified: | 17 Jul 2020 09:19 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/22745 |
Actions (login required)
 |
View Item |