CFP last date
22 April 2024
Reseach Article

A Hybrid Backtracking and Pencil and Paper Sudoku Solver

by Onokpasa Eva, Bisandu Desmond, Bakwa Dunka
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 181 - Number 47
Year of Publication: 2019
Authors: Onokpasa Eva, Bisandu Desmond, Bakwa Dunka
10.5120/ijca2019918642

Onokpasa Eva, Bisandu Desmond, Bakwa Dunka . A Hybrid Backtracking and Pencil and Paper Sudoku Solver. International Journal of Computer Applications. 181, 47 ( Apr 2019), 39-43. DOI=10.5120/ijca2019918642

@article{ 10.5120/ijca2019918642,
author = { Onokpasa Eva, Bisandu Desmond, Bakwa Dunka },
title = { A Hybrid Backtracking and Pencil and Paper Sudoku Solver },
journal = { International Journal of Computer Applications },
issue_date = { Apr 2019 },
volume = { 181 },
number = { 47 },
month = { Apr },
year = { 2019 },
issn = { 0975-8887 },
pages = { 39-43 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume181/number47/30472-2019918642/ },
doi = { 10.5120/ijca2019918642 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T01:09:23.409093+05:30
%A Onokpasa Eva
%A Bisandu Desmond
%A Bakwa Dunka
%T A Hybrid Backtracking and Pencil and Paper Sudoku Solver
%J International Journal of Computer Applications
%@ 0975-8887
%V 181
%N 47
%P 39-43
%D 2019
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In an earlier research [1] it was found that based on the number of iterations taken to solve puzzles from [2] the pencil and paper (PnP) was the most efficient method for solving Sudoku puzzles rated easy and medium by [2]. However for more difficult puzzles this method p*roved ineffective. Next, the method of alternating projections proved more efficient at solving all test puzzles compared to the backtracking (BT) algorithm. In this research work, a hybrid solver is created using the pencil and paper method and backtracking methods. This method solves all sample puzzles in finite seconds. The execution time outperforms the BT method for most of the sample puzzles.

References
  1. Onokpasa, E. & Bakwa, D. (2019)A Comparison of Three Sudoku Solving Methods. International Journal of Computer Applications. 10.5120/ijca2019918439
  2. www.sudoku.org.uk (2018)http://www.sudoku.org.uk/Daily.aspAccessed:20/11/2018
  3. Learn-Sudoku.com(2008)https://www.learn-sudoku.com/ [Accessed 20/09/18]
  4. Perez, M. and Marwala, T., (2011)Stochastic optimization approaches for solving Sudoku, Proc. IEEE Congress on Evolutionary Computing, pp 256–279, Vancouver: Piscataway.
  5. Chi E. & Lange K. (2012)Techniques for Solving Sudoku Puzzles, pp 2,3 arXiv:1203.2295 [math.OC]
  6. Cantú-Paz, E. & Goldberg, D.E. (2000). Efficient parallel genetic algorithms: theory and practice. Computer Methods in Applied Mechanics and Engineering, 186 ( 2-4), 221-238.
  7. Kirkpatrick, S., Gelatt, C.D. & Vecchi, M. P. (1983).Optimization by Simulated Annealing. Science, 220(4598), 671-680.
  8. Van Laarhoven, P. & Aarts, E. (1987). Simulated Annealing: Theory and Application. D Reidel Publishing Company, the Netherlands.
  9. www.aisudoku.com(2006)http://www.aisudoku.com/index_en.htmlAccessed:20/11/2018
  10. Schaad J. (2010)Modeling the 8-Queens Problem and Sudoku using an Algorithm based on Projections onto Nonconvex Sets, Master’s thesis, The University of British Columbia. Pages 23, 93-95
  11. Google(2019)https://drive.google.com/open?id=1C9ym99n7IXsQASwmZcLVDo57SGpxIX-E.
  12. Kock, N. (2015)One-tailed or two-tailed P values in PLS-SEM? International Journal of e-collaboration, 11(2), 1-7.
Index Terms

Computer Science
Information Sciences

Keywords

Hybrid backtracking pencil and paper Sudoku algorithms