Randomised Analysis of Backtracking-based Search Algorithms in Elucidating Sudoku Puzzles Using a Dual Serial/Parallel Approach

Abstract

Sudoku is a 9 x 9 grid-based puzzle. It is a game where each row, column, and 3 x 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%.

Key Findings

• Parallelized search algorithms outperformed serial approaches by 28% to 56% in solving complex Sudoku puzzles.
• Depth-First Search (DFS) demonstrated a 15-21% performance improvement over Breadth-First Search (BFS) in serial configurations.
• Developed a hybrid DFS-BFS parallelization strategy for sub-tree processing to optimize time and space complexity.
• Analyzed performance across varying puzzle complexities, establishing best practices for backtracking-based search algorithms.