General variable neighborhood search for solving Sudoku puzzles: unfiltered and filtered models

摘要

In this paper, two novel models based on the Variable Neighborhood Search (VNS) algorithm are proposed to solve Sudoku puzzles. For the first model (Unfiltered-VNS), four neighborhood structures are proposed. The Filtered-VNS, which is the second model, uses filtering to reduce the number of partial infeasible solutions in the search area. Local search is performed by a novel mutation-based neighborhood structure. In both models, the neighborhood structures are implemented by using different local search improvement strategies. Two proposed models with the best configurations are tested on 57 well-known Sudoku benchmarks. The experimental results indicate that our models can solve all benchmarks. For easy-, medium-, and hard-level puzzles, Filtered-VNS shows better solution quality than Unfiltered-VNS. For very hard instances, performance of Unfiltered-VNS is better than Filtered-VNS. Except for two of the 57 benchmarks, Filtered-VNS improves the solution qualities of the previous studies.