Call for Paper - October 2019 Edition
IJCA solicits original research papers for the October 2019 Edition. Last date of manuscript submission is September 20, 2019. Read More

A Hybrid Backtracking and Pencil and Paper Sudoku Solver

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2019
Authors:
Onokpasa Eva, Bisandu Desmond, Bakwa Dunka
10.5120/ijca2019918642

Onokpasa Eva, Bisandu Desmond and Bakwa Dunka. A Hybrid Backtracking and Pencil and Paper Sudoku Solver. International Journal of Computer Applications 181(47):39-43, April 2019. BibTeX

@article{10.5120/ijca2019918642,
	author = {Onokpasa Eva and Bisandu Desmond and Bakwa Dunka},
	title = {A Hybrid Backtracking and Pencil and Paper Sudoku Solver},
	journal = {International Journal of Computer Applications},
	issue_date = {April 2019},
	volume = {181},
	number = {47},
	month = {Apr},
	year = {2019},
	issn = {0975-8887},
	pages = {39-43},
	numpages = {5},
	url = {http://www.ijcaonline.org/archives/volume181/number47/30472-2019918642},
	doi = {10.5120/ijca2019918642},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, 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.

Keywords

Hybrid, backtracking, pencil and paper, Sudoku, algorithms