J-POP: Japanese Puzzles as Optimization Problems

Lloyd, Huw, Crossley, Matthew, Sinclair, Mark and Amos, Martyn (2022) J-POP: Japanese Puzzles as Optimization Problems. IEEE Transactions on Games, 14 (3). pp. 391-402. ISSN 2475-1502

Japanese_Puzzle_Games_for_Combinatorial_Black_Box_Optimization.pdf - Accepted Version

Download (1MB) | Preview
Official URL: https://doi.org/10.1109/tg.2021.3081817


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.

Item Type: Article
Uncontrolled Keywords: Games, Optimization, Bridges, Portfolios, Constraint handling, Benchmark testing, Artificial intelligence
Subjects: G400 Computer Science
G600 Software Engineering
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: John Coen
Date Deposited: 17 May 2021 09:38
Last Modified: 26 Sep 2022 13:45
URI: https://nrl.northumbria.ac.uk/id/eprint/46181

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics