Portal de Periódicos da CAPES

Sequential and Parallel Scattered Variable Neighborhood Search for Solving Nurikabe

2021; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-030-69625-2_8

1611-3349

Paul Bass, Aişe Zülal Şevkli,

Multimedia Communication and Technology

Japanese pencil games have been the subjects of innumerable papers. However, some problems - like Sudoku - receive far more attention than others - like Nurikabe. In this paper we propose a novel algorithm to solve Nurikabe puzzles. We first introduce a sequential hybrid algorithm that we call Scattered Variable Neighborhood Search. We then propose a method of parallelizing this algorithm, examining the empirical benefits of parallelization. We conclude that our parallel implementation performs best in almost all scenarios.