A Novel Evolutionary Algorithm with Column and Sub-Block Local Search for Sudoku Puzzles

Wang, Chuan, Sun, Bing, Du, Ke-Jing, Li, Jian-Yu ORCID: 0000-0002-6143-9207, Zhan, Zhi-Hui ORCID: 0000-0003-0862-0514, Jeon, Sang-Woon ORCID: 0000-0002-0199-2254, Wang, Hua ORCID: 0000-0002-8465-0996 and Zhang, Jun ORCID: 0000-0001-7835-9871 (2023) A Novel Evolutionary Algorithm with Column and Sub-Block Local Search for Sudoku Puzzles. IEEE Transactions on Games. ISSN 2475-1502 (In Press)


Sudoku puzzles are not only popular intellectual games but also NP-hard combinatorial problems related to various real-world applications, which have attracted much attention worldwide. Although many efficient tools, such as evolutionary computation (EC) algorithms, have been proposed for solving Sudoku puzzles, they still face great challenges with regard to hard and large instances of Sudoku puzzles. Therefore, to efficiently solve Sudoku puzzles, this paper proposes a genetic algorithm (GA)-based method with a novel local search technology called local search-based GA (LSGA). The LSGA includes three novel design aspects. First, it adopts a matrix coding scheme to represent individuals and designs the corresponding crossover and mutation operations. Second, a novel local search strategy based on column search and sub-block search is proposed to increase the convergence speed of the GA. Third, an elite population learning mechanism is proposed to let the population evolve by learning the historical optimal solution. Based on the above technologies, LSGA can greatly improve the search ability for solving complex Sudoku puzzles. LSGA is compared with some state-of-the-art algorithms at Sudoku puzzles of different difficulty levels and the results show that LSGA performs well in terms of both convergence speed and success rates on the tested Sudoku puzzle instances.

Dimensions Badge

Altmetric Badge

Item type Article
URI https://vuir.vu.edu.au/id/eprint/47124
DOI 10.1109/TG.2023.3236490
Official URL https://ieeexplore.ieee.org/document/10015696
Subjects Current > FOR (2020) Classification > 4602 Artificial intelligence
Current > Division/Research > Institute for Sustainable Industries and Liveable Cities
Keywords algorithms, sudoku, artificial intelligence, genetic algorithm
Download/View statistics View download statistics for this item

Search Google Scholar

Repository staff login