J-POP: Japanese Puzzles as Optimization Problems

Lloyd, Huw, Crossley, Matthew, Sinclair, Mark and Amos, Martyn (2021) J-POP: Japanese Puzzles as Optimization Problems. IEEE Transactions on Games. ISSN 2475-1502 (In Press)

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: 31 Jul 2021 10:50
URI: http://nrl.northumbria.ac.uk/id/eprint/46181

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics