Portal de Periódicos da CAPES

J-POP: Japanese Puzzles as Optimization Problems

2021; Institute of Electrical and Electronics Engineers; Volume: 14; Issue: 3 Linguagem: Inglês

10.1109/tg.2021.3081817

2475-1510

Huw Lloyd, Matthew Crossley, M.C. Sinclair, Martyn Amos,

Video Analysis and Summarization

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 blackbox 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 five different puzzle games, and identify a subset of puzzle instances that could provide a challenging benchmark set for future algorithms.