# NP-Complete Static Square Puzzles

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.

• 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. – Mark Oct 18 '18 at 6:56
• 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. – Mateus de Oliveira Oliveira Oct 18 '18 at 9:27
• @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. – Peter Shor Oct 18 '18 at 9:42
• 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). – Marzio De Biasi Oct 18 '18 at 10:16
• @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. – Mateus de Oliveira Oliveira Oct 21 '18 at 20:38

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.
• Thank you for the links. This is the type of homepage I'm looking for. – Mateus de Oliveira Oliveira Oct 21 '18 at 20:41

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.