<p>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:</p>

<ul>
<li>sudokus</li>
<li>edge matching puzzles</li>
</ul>

<p>The phd is at:
<a href="https://www.tdx.cat/handle/10803/8122" rel="nofollow noreferrer">https://www.tdx.cat/handle/10803/8122</a></p>

<p>And I should have code (generators) lying around somewhere.</p>

CC BY-SA 4.0
2018-11-13T15:50:40.097Z
2018-11-13T15:50:40.097Z
carlesm
<p>Two such puzzles that I know about are:</p>
<ul>
<li>Unruly. <a href="https://www.chiark.greenend.org.uk/%7Esgtatham/puzzles/js/unruly.html" rel="nofollow noreferrer">This website</a> has an online library of puzzles and solutions and a generator for puzzles of arbitrary size.</li>
<li>Masyu. <a href="https://www.janko.at/Raetsel/Masyu/index.htm" rel="nofollow noreferrer">This website</a> has a library of puzzles and solutions. It also links to several variants of the puzzle.</li>
</ul>
<p>Actually, the <a href="https://www.chiark.greenend.org.uk/%7Esgtatham/puzzles/" rel="nofollow noreferrer">page</a> where the Unruly puzzle is found lists more such puzzles, some of which satisfy your conditions, while others don't.</p>

CC BY-SA 4.0
2018-10-21T20:41:57.380Z
Thank you for the links. This is the type of homepage I'm looking for.
Mateus de Oliveira Oliveira
CC BY-SA 4.0
2018-10-19T07:42:55.110Z
2020-10-13T14:12:25.097Z
2020-10-13T14:12:25.097Z
Jan Johannsen
<p>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. </p>

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

<p>Preferentially, the puzzles should satisfy the following conditions: </p>

<ol>
<li>Scalability: The puzzle can be defined for <span class="math-container">$n\times n$</span> boards for each
<span class="math-container">$n$</span>. Or if this is not possible, for each <span class="math-container">$f(n)$</span> where <span class="math-container">$f:{\bf N}\rightarrow {\bf N}$</span> is some 
easy looking function. </li>
<li>An online library of instances for the puzzle should be available.  </li>
</ol>

<p>What would be online databases for such puzzles? For instance, the section Games and Puzzles of <a href="https://en.wikipedia.org/wiki/List_of_NP-complete_problems" rel="noreferrer">this wikipedia page</a> has many square games satisfying condition 1. So what I'm really looking for is a of puzzles that also satisfy condition 2. </p>

<p>Please feel free to suggest more than one puzzle in one answer. </p>

CC BY-SA 4.0
2018-10-18T06:56:23.157Z
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 Schultz-Wu
CC BY-SA 4.0
2018-10-18T09:27:57.050Z
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
CC BY-SA 4.0
2018-10-18T09:42:53.640Z
@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 
CC BY-SA 4.0
2018-10-18T10:16:00.463Z
Why don't you use standard CSP benchmarks or CSP competition databases (for example take a look at [http://xcsp.org/competition](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
CC BY-SA 4.0
2018-10-21T20:38:24.640Z
@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
CC BY-SA 4.0
2018-10-21T20:39:54.217Z
@MarzioDeBiasi The link you mentioned is very useful. But in this particular context, the CSP solvers are specialized to square puzzles. So answers in the line of the one given by Jan Johannsen below are the ideal ones.
Mateus de Oliveira Oliveira
<np-complete><puzzles>
NP-Complete Static Square Puzzles
Mateus de Oliveira Oliveira
# NP-Complete Static Square Puzzles

(Asked by: username_0 on 2018-10-17)

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](https://en.wikipedia.org/wiki/List_of_NP-complete_problems) 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.

**Tags:** np-complete, puzzles
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: @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.  
> **username_3**: Why don't you use standard CSP benchmarks or CSP competition databases (for example take a look at [http://xcsp.org/competition](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).  
> **username_0**: @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.  
> **username_0**: @MarzioDeBiasi The link you mentioned is very useful. But in this particular context, the CSP solvers are specialized to square puzzles. So answers in the line of the one given by Jan Johannsen below are the ideal ones.  

---

## 2 answers

### Answer by username_5 on 2018-10-19. Score: 8 | Accepted answer

Two such puzzles that I know about are:

* Unruly. [This website](https://www.chiark.greenend.org.uk/%7Esgtatham/puzzles/js/unruly.html) has an online library of puzzles and solutions and a generator for puzzles of arbitrary size.
* Masyu. [This website](https://www.janko.at/Raetsel/Masyu/index.htm) has a library of puzzles and solutions. It also links to several variants of the puzzle.

Actually, the [page](https://www.chiark.greenend.org.uk/%7Esgtatham/puzzles/) where the Unruly puzzle is found lists more such puzzles, some of which satisfy your conditions, while others don't.

> **Comments:**
> **username_0**: Thank you for the links. This is the type of homepage I'm looking for.  

---

### Answer by username_4 on 2018-11-13. Score: 2

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.


---

