SudoPHASE: A Multithreaded Hybrid ACO-SA Sudoku Solver with Ring and Random Communication Topologies

Sudoku solving is a combinatorial constraint satisfaction problem that becomes increasingly difficult for large grids and low-clue puzzles. In this paper, SudoPHASE is introduced as a parallel hybrid Sudoku solver that combines constraint propagation, the Ant Colony System (ACS), and Simulated Annealing (SA) within a multithreaded architecture. This work integrates multithreaded hybrid ACO–SA with ring-based and randomized communication topologies for coordinated parallel search. Each thread executes an independent solver and communicates through ring-based exchanges of iteration-best solutions and randomized exchanges of best-so-far solutions. We propose a three-source pheromone update mechanism that integrates local and shared information while preserving search diversity. Experimental results on 9×9, 16×16, and 25×25 Sudoku instances demonstrate that the proposed approach improves robustness, convergence speed, and scalability compared to non-hybrid and non-parallel baselines, particularly for large, low-clue puzzles.