Sudoku is an NP-complete-based mathematical puzzle, which has enormous applications in the domains of steganography, visual cryptography, DNA computing, and so on. Therefore, solving Sudoku effectively can bring revolution in various fields. Several heuristics are there to solve this interesting structure. One of the heuristics, genetic algorithm, is used by many researchers to solve Sudoku successfully, but they face various problems. Genetic algorithm has so many lacunas, and to overcome these, we have hybridised it in a novel way. In this paper, we have developed a hybrid genetic algorithm-based firefly mating algorithm, which can solve Sudoku instances with a greater success rate for easy, medium, and hard difficulty level puzzles. Our proposed method has controlled “getting stuck in local optima”, considering a smaller population and lesser generation. © 2021, The Author(s), under exclusive licence to Springer-Verlag London Ltd., part of Springer Nature.