# Tag Info

Accepted

### Is optimally solving the n×n×n Rubik's Cube NP-hard?

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

### NP-Complete Static Square Puzzles

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 ...
• 4,630
Accepted

### Construction of binary puzzle

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$ ...
• 51.1k
Accepted

### Can you find a counter-example for this proposed Graph Isomorphism algorithm?

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 ...
• 37.4k
Accepted

### Does Rush-Hour (or Klotski) admit a search-to-decision reduction?

Yes! As long as we can give the oracle a limit on the number of steps in a path, I think we can do it this way: Set $k\leftarrow n^3$ and set $B\leftarrow B_0$, where $B_0$ is the initial ...
• 96
Accepted

### Name and complexity of a stone placement puzzle

The phrase you are looking for is "system of distinct representatives". A stone placement represents its set of candidate locations, and all sets must have distinct placements. It is more or ...
• 51.1k
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 ...