Sudoku Solver Acceleration with CUDA

Abstract

The classic Sudoku is a puzzle with simple rules that can become complicated to solve automatically due to the exponential increase in possible solutions as the board size increases. This paper presents an algorithmic solution to solve any size Sudoku incorporating an implementation in CUDA C/C++ that, consequently, leverages parallel programming on a GPU. This involves using threads and processes with shared and distributed memory for various solution strategies. These solution strategies encompass backtracking, where multiple alternatives are tried until reaching a solution, and rule-based algorithms that rely on heuristics to solve Sudokus, among others. Regardless of the implementation approach, it is pertinent to conduct a comparison between the solution achieved with a parallel algorithm utilizing a GPU and a sequential algorithm processed on the CPU. This is done to quantify the performance of the solution. The proposed algorithm managed to accelerate the traditional backtracking approach by up to 7x on a typical 9x9 Sudoku. While getting 7x and 3x reduction on 16x16 and 25x25 boards respectively.