J-POP: Japanese Puzzles as Optimization Problems

Lloyd, H ORCID: https://orcid.org/0000-0001-6537-4036, Crossley, M ORCID: https://orcid.org/0000-0001-5965-8147, Sinclair, M and Amos, M (2022) J-POP: Japanese Puzzles as Optimization Problems. IEEE Transactions on Games, 14 (3). pp. 391-402. ISSN 2475-1502

Preview

Accepted Version Available under License In Copyright. Download (1MB) | Preview

Abstract

Japanese puzzle games such as Sudoku and Futoshiki are familiar recreational pursuits, but they also present an interesting computational challenge. A number of algorithms exist for the automated solution of such puzzles, but, until now, these have not been compared in a unified way. Here we present an integrated framework for the study of combinatorial black-box optimisation, using Japanese puzzles as the test-bed. Importantly, our platform is extendable, allowing for the easy addition of both puzzles and solvers. We compare the performance of a number of optimization algorithms on six different puzzle games, and identify a subset of puzzle instances that could provide a challenging benchmark set for future algorithms.