15
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I think some sudoku or things like this, might be useful. $\endgroup$
    – A.Omidi
    Sep 11, 2019 at 19:23

7 Answers 7

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
10
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Feel free. I do it all the time. :-) $\endgroup$
    – prubin ♦
    Sep 12, 2019 at 19:41
9
$\begingroup$

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.

Description of the puzzle

Model

Solution

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ "Queen placement" is a definitely a good candidate, thanks. $\endgroup$
    – Geoffrey De Smet
    Sep 12, 2019 at 6:59
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

The variant here has been suggested by Donald Knuth

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.