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

14

EDIT: I quickly completed the amateur proof that I started a few months ago and never finished. You can download it in PDF format on my blog ... nobody has checked it yet, so refutations, comments and suggestions are welcome. I don't know if there is an official proof, but a few months ago I built the gadgets to mimic a planar 3-CNF formula; for example ...

8

With m eggs and k measurements the most floors that can be checked is exactly $$n(m,k)={k \choose 0} + {k \choose 1} + \ldots + {k \choose m},$$ (maybe $\pm 1$ depending on the exact def). Proof is trivial by induction. This expression has no closed form inverse but gives good asymptotic.

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

6

I thought of this weird reduction (chances that it is wrong are high :-). Idea: reduction from Hamiltonian path on grid graphs with degree $\leq 3$; each node of the planar graph can be shifted in such a way that every "row" ($y$ value) and every "column" ($x$ value) contains at most one node. The graph can be scaled and each node can be replaced by a square ...

3

Just a partial self-answer: I think the problem is NP-complete. I found 3 gadgets (each one occupies $16 \times 16$ cells) that allows to build a Net game equivalent to a grid graph of degree $\leq 3$ and that should have a solution iif the original graph has an Hamiltonian cycle. The figure shows four different configurations of the gadget equivalent to a ...

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

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

This isn't really an answer to your questions, but I think it would help in understanding the problem (or the way to answer your questions is) to write out a formal statement and proof of the solution. The proof you've presented doesn't say what is being proven, and as written is certainly incorrect. It states (final bullet point) that the inductive ...

2

In my comment above I said perhaps $\Theta(\min_{k \le m} kn^{\frac{1}{k}})$ is a tight bound. I'm not sure about the lower bound, but since you just want an explanation for what $k$ means, I can explain the intuition using the upper bound. As you guessed, $k$ is the number of eggs actually used. That explains the $\min$ on the outside. Now once we've ...

1

This is to report an implementation of completed-sudoku compact encoding (similar to suggestion by Zurui Wang 9/14/11). The input is the top row and 1st 3 digits of the 2nd row. These are reduced to 1-9! and 1-120 and combined to <= 4.4x10^7. These are used as givens to count lexicographically all the partial sukokus of 30 digits up to the matching ...

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