Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Due to Python’s global interpreter lock, which limits the number of actual threads running at a given time to 1, we used processes instead of threads in our parallel implementation. Since processes are consume more memory than threads, and data had to be duplicated across processes, this may have caused some slowdown due to high memory, and thus high swap, usage.
- 2.
More than five minutes elapsed before a solution was found.
- 3.
As of the time of writing.
References
Das, K.N., Bhatia, S., Puri, S.: A retrievable GA for solving sudoku puzzles (2011)
Sevkli, A.Z., Hamza, K.A.: General variable neighborhood search for solving sudoku puzzles: unfiltered and filtered models. Soft Comput. 23(15), 6585–6601 (2019). https://doi.org/10.1007/s00500-018-3307-6
Amos, M., Crossley, M., Loyd, H.: Solving nurikabe with ant colony optimization (extended version) *, June 2019. https://doi.org/10.13140/RG.2.2.23813.19685
Holzer, M., Klein, A., Kutrib, M.: On the NP-completeness of the nurikabe pencil puzzle and variants thereof (2008)
Cayli, M., Kavlak, E., Kaynar, H., Türe, F., Erdem, E.: Solving challenging grid puzzles with answer set programming. In: Proceedings of ASP, pp. 175–190, December 2007
Glover, F., Laguna, M., Marti, R.: Fundamentals of scatter search and path relinking. Control Cybern. 29, 653–684 (2000)
Moreno Pérez, J.A., Hansen, P., Mladenovi’c, N.: Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175(01), 367–407 (2010)
Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8, 156–166 (1977). https://doi.org/10.1111/j.1540-5915.1977.tb01074.x
Janko, O.: Home. https://www.janko.at/Raetsel/Nurikabe/
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Bass, P., Sevkli, A.Z. (2021). Sequential and Parallel Scattered Variable Neighborhood Search for Solving Nurikabe. In: Mladenovic, N., Sleptchenko, A., Sifaleras, A., Omar, M. (eds) Variable Neighborhood Search. ICVNS 2021. Lecture Notes in Computer Science(), vol 12559. Springer, Cham. https://doi.org/10.1007/978-3-030-69625-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-69625-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-69624-5
Online ISBN: 978-3-030-69625-2
eBook Packages: Computer ScienceComputer Science (R0)