Abstract
Sudoku is a 9\(\,\times \,\)9 grid-based puzzle. It is a game where each row, column, and 3\(\,\times \,\)3 box must have one instance of a number from 1 to 9. In present paper, we shall evaluate three different algorithmic approaches both in serial and parallel configurations that can be utilised to solve a puzzle of Sudoku to assess their comparative performance metrics for differential randomly generated Sudoku datasets. We shall utilise Breadth-first search, Depth-first search, Depth-first search with Breadth-first search parallelisation for sub-tress, for evaluating a large number of randomly generated Sudoku puzzles with a varying number of clues to find the best algorithm based on time and space complexity as well as clue complexity. With this, we shall analyse and develop a best practice algorithm that can be ideally used to solve a large number of puzzles in any given situation in the most time-efficient manner. Our analysis has found that there was a significant improvement in utilising the parallel algorithm over both the Breadth-first and Depth-first search approaches from 28% to over 56%. Even moving from Breadth-first to Depth-first search, we have gauged quite a moderate improvement in performance from 15 to 21%.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
H. Garns, Number Place (Dell Pencil Puzzles & Word Games, 1979)
J.P. Delahaye, The science behind Sudoku. Sci. Am. 294(6), 80–87 (2006)
R. Lewis, Metaheuristics can solve sudoku puzzles. J. Heuristics 13(4), 387–401 (2007)
B. Crawford, M. Aranda, C. Castro, E. Monfroy, Using constraint programming to solve sudoku puzzles, in 2008 Third International Conference on Convergence and Hybrid Information Technology, vol. 2 (IEEE, 2008), pp. 926–931
H. Simonis, Sudoku as a constraint problem, in CP Workshop on Modeling and Reformulating Constraint Satisfaction Problems, vol. 12 (Citeseer, 2005)
M. Eremic, R. Adamov, N. Bilinac, V. Ognjenovic, V. Brtka, I. Berkovic, Comparison of state space search algorithms-sudoku puzzle game. Chief Responsible Editor 154 (2013)
P. Van Beek, Backtracking search algorithms. Found. Artif. Intell. 2, 85–134 (2006)
P. Berggren, D. Nilsson, A Study of Sudoku Solving Algorithms (Royal Institute of Technology, Stockholm, 2012)
M.J. Pathak, R.L. Patel, S.P. Rami, Comparative analysis of search algorithms. Int. J. Comput. Appl. 179(50), 40–43 (2018)
T. Yato, T. Seta, Complexity and completeness of finding another solution and its application to puzzles. IEICE Trans. Fund. Electron. Commun. Comput. Sci. 86(5), 1052–1060 (2003)
A study of Sudoku solving algorithms. https://cutt.ly/zb2GfyN. Last accessed 18 May 2021
A. Bundy, L. Wallen, Breadth-first search, in Catalogue of Artificial Intelligence Tools (Springer, Berlin, Heidelberg, 1984), p. 13
L. Chen, Y. Guo, S. Wang, S. Xiao, K. Kask, Sudoku Solver (2016)
H.S. Stone, P. Sipala, The average complexity of depth-first search with backtracking and cutoff. IBM J. Res. Dev. 30(3), 242–258 (1986)
Multi-threaded algorithm for solving Sudoku. https://stackoverflow.com/a/850892. Last accessed 18 May 2021
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Garg, P., Jha, A., Shukla, K.A. (2022). Randomised Analysis of Backtracking-based Search Algorithms in Elucidating Sudoku Puzzles Using a Dual Serial/Parallel Approach. In: Smys, S., Balas, V.E., Palanisamy, R. (eds) Inventive Computation and Information Technologies. Lecture Notes in Networks and Systems, vol 336. Springer, Singapore. https://doi.org/10.1007/978-981-16-6723-7_21
Download citation
DOI: https://doi.org/10.1007/978-981-16-6723-7_21
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-16-6722-0
Online ISBN: 978-981-16-6723-7
eBook Packages: EngineeringEngineering (R0)