9
$\begingroup$

In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to each entry of the board, in such a way that the rules of the games are satisfied.

For instance, slitherlink,numberlink, sudoku, filomino, kakuro etc, are the types of puzzles I'm looking for.

Preferentially, the puzzles should satisfy the following conditions:

  1. Scalability: The puzzle can be defined for $n\times n$ boards for each $n$. Or if this is not possible, for each $f(n)$ where $f:{\bf N}\rightarrow {\bf N}$ is some easy looking function.
  2. An online library of instances for the puzzle should be available.

What would be online databases for such puzzles? For instance, the section Games and Puzzles of this wikipedia page has many square games satisfying condition 1. So what I'm really looking for is a of puzzles that also satisfy condition 2.

Please feel free to suggest more than one puzzle in one answer.

Improve this question
$\endgroup$
6
  • $\begingroup$ Can you not just start with a solution, and then "throw out" entries until you have a "base puzzle"? For a game like sudoku, this seems like it should allow you to efficiently generate instance-solution pairs. $\endgroup$
    – Mark Schultz-Wu
    Commented Oct 18, 2018 at 6:56
  • $\begingroup$ Hi Mark, thanks for the suggestion. The ideal would be to have a list of websites containing sets of instances, together with a way of comparing implementations. For instance, competition websites, etc. Your idea works of course, but I would prefer to compare the algorithms with more "standard" sets of instances. $\endgroup$
    – Mateus de Oliveira Oliveira
    Commented Oct 18, 2018 at 9:27
  • $\begingroup$ @Mark: "real" sudoku have a unique solution. The sudoku you generate in this way will not. I don't know whether the OP cares about the difference. $\endgroup$
    – Peter Shor
    Commented Oct 18, 2018 at 9:42
  • 1
    $\begingroup$ Why don't you use standard CSP benchmarks or CSP competition databases (for example take a look at http://xcsp.org/competition )? BTW for popular puzzle games (sudoku, kakuro,...) you can find many (open source) generators, most of them have a "difficulty" parameter, too (I used some of them in the past). $\endgroup$
    – Marzio De Biasi
    Commented Oct 18, 2018 at 10:16
  • $\begingroup$ @PeterShor Thanks for the remark. For the applications I'm interested in, uniqueness of solution is not relevant. Even though of course it would be much better to test algorithms against real sudoku instances. $\endgroup$
    – Mateus de Oliveira Oliveira
    Commented Oct 21, 2018 at 20:38

2 Answers 2

Reset to default
8
$\begingroup$

Two such puzzles that I know about are:

  • Unruly. This website has an online library of puzzles and solutions and a generator for puzzles of arbitrary size.
  • Masyu. This website has a library of puzzles and solutions. It also links to several variants of the puzzle.

Actually, the page where the Unruly puzzle is found lists more such puzzles, some of which satisfy your conditions, while others don't.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the links. This is the type of homepage I'm looking for. $\endgroup$
    – Mateus de Oliveira Oliveira
    Commented Oct 21, 2018 at 20:41
2
$\begingroup$

For my PhD (wow! that was long ago... i'm getting old..). I worked on a few different problems (and CSP or SAT modelled them). Of the kind you are interested in:

  • sudokus
  • edge matching puzzles

The phd is at: https://www.tdx.cat/handle/10803/8122

And I should have code (generators) lying around somewhere.

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.