# Tag Info

15

One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.

7

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

7

To meet condition 1, $n$ must be even, so let's assume that it is. Then we can automatically achieve both conditions 1 and 2 by making an $n/2\times n/2$ matrix whose entries are $2\times 2$ submatrices in one of the two patterns  \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right),\quad \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{...

6

Even without the hash function, this is basically just 1-dimensional Weisfeiler-Leman with individualization of a single vertex. Neuen & Schweitzer (STOC '18, arXiv) gave examples with an exponential $2^{\Omega(n)}$ lower bound for a much stronger family of algorithms, namely those for which one can iteratively individualize & refine, and even use $k$...

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.

2

In the most authoritative reference on PPAD-complete problems, there is no PPAD-complete puzzle mentioned.

2

Determining that $20$ is the diameter (God's number) of the Rubik's Cube Group $G$ under the half-turn metric with Singmaster generating set $s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$ was a wonderful result. I'm curious about follow-up questions, such as determining how many half-turn twists $m$ it would take to get the cube fully "mixed" to $\epsilon$...

Only top voted, non community-wiki answers of a minimum length are eligible