Skip to main content
17 votes
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.
Mikhail Rudoy's user avatar
8 votes
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 ...
Jan Johannsen's user avatar
7 votes
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$ ...
David Eppstein's user avatar
7 votes
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 ...
Joshua Grochow's user avatar
4 votes
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 ...
wobtax's user avatar
  • 96
3 votes
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 ...
David Eppstein's user avatar
2 votes

NP-Complete Static Square Puzzles

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 ...
carlesm's user avatar
  • 29
2 votes

An Interactive Proof of God's Number?

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 ...
Mark S's user avatar
  • 1,124

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