13
$\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?

$\endgroup$
  • 2
    $\begingroup$ I think some sudoku or things like this, might be useful. $\endgroup$ – abbas omidi Sep 11 at 19:23
10
$\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

$\endgroup$
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

$\endgroup$
  • 2
    $\begingroup$ "Queen placement" is a definitely a good candidate, thanks. $\endgroup$ – Geoffrey De Smet Sep 12 at 6:59
9
$\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.)

$\endgroup$
  • 2
    $\begingroup$ Feel free. I do it all the time. :-) $\endgroup$ – prubin Sep 12 at 19:41
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.

$\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.

$\endgroup$
2
$\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.

$\endgroup$
1
$\begingroup$

The variant here has been suggested by Donald Knuth

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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