Might you know any simple puzzles similar to $n$ queens? Anything parametrized worth running to a constraint solver?

Question

In the $n$ queens puzzle, we have to put $n$ queens on an $n \times n$ chessboard, without any $2$ queens being able to attack each other. Finding a single feasible solution is not NP-complete.

It's a useful example nonetheless, because:

• it is simple to understand
• it has a visual solution
• it has exactly $1$ parameter (the $n$) to generate a dataset
• it doesn't have an immediately obvious solution
• it is a single-player game

Are there any other similar puzzles/games, you might think of?

Answer 1

I adressed part of that in

Puzzles : having fun and useful mathematics

where I mention the IBM Ponder This Challenge, a monthly puzzle that is 20+ years old now.

Let me also mention the Decision Management Community challenge

Without much effort many of those challenges can be turn into generic puzzles you can scale with a simple parameter.

Within the IBM CPLEX product, some examples comply 100% with your requirement:

• Lifegame
• Euler
• linear_peg_solitaire.py in CPLEX_Studio129\python\examples\cp\basic

NB:

I work for IBM

Answer 2

In my book The Opex Analytics Weekly Puzzle, there are several puzzles that can be solved as MIPs. Part of the fun (in my opinion) is that some people will want to solve them this way, but others will prefer to solve them in other ways.

Examples include:

• A prize-collecting TSP-type puzzle
• A "clueless" sudoku-type puzzle
• A graph connectivity puzzle
• An attacking-queen-type puzzle
• A poker-hand puzzle

(I don't mean to self-promote with this answer. I hope it doesn't come across this way.)

Answer 3

The book Puzzles and Games: A Mathematical Modeling Approach by Tony Hurlimann, is a comprehensive guide to mathematical modeling of games and puzzles. It uses about 100 puzzles as "case studies" and represents them as a mathematical model. All the games have already coded using LPL language. The website included all the codes and interactive solving environment.

Edit: the book even has a chapter for chessboard placement puzzles. Below I added a sample of the puzzles in the reference.

---

---

Answer 4

I've never tried it, but the knight's tour is certainly a conceptually simple problem which meets your constraints. I'm curious whether there exists an efficient CP formulation for this problem.

Answer 5

I just ran across two papers by Sönke Hartmann in INFORMS Transactions on Education (Hartman 2017 and Hartmann 2019) that present IP formulations for logic puzzles that are available as smartphone apps. I'm not sure if these can be formulated as CPs, but it might be worth a look.

Actually, on closer look, there are a lot of puzzle-related articles in that journal; here's a search query.

Answer 6

dkmGames has a bunch of online logic puzzles that would be amenable to constraint programming. Nonograms in particular would be easy to explain and (I think) easy to code.

Answer 7

The variant here has been suggested by Donald Knuth