# Questions tagged [puzzles]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
10k views

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

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
• 23.2k
3k views

### Grid $k$-coloring without monochromatic rectangles

Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known. Anyone feel up to trying 5-colorings? ;...
• 6,011
1k views

### Cutting-sticks puzzle

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time? ...
• 1,955
741 views

### Are there local maxima in the number of moves required to solve a Rubik's Cube?

Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive ...
• 13.7k
755 views

### What is the complexity of (possibly succinct) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid which is to be filled with on/off values for each cell, with each number ...
• 1,396
2k views

### Is the half-filled magic square problem NP-complete?

Here is the problem: We have a square with some numbers from 1..N in some cells. It's needed to determine if it can be completed to a magic square. Examples: ...
• 231
497 views

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

As D. Eppstein pointed out here regarding proposed poly-time algorithms for Graph Isomorphism: ... it is easy to define algorithms for graph isomorphism that attempt to amplify some sort of subtle ...
• 10.8k
624 views

### complexity of Sokoban with a small number of boxes

(I asked a very concise version of this one month ago on cs.stackexchange, and although it got edited, it was not (otherwise) responded to.) In this post, for positive integer values $k$, "$k$-...
332 views

### Scrambling a Rubik's cube by an adversarial noob

My friend dislikes Rubik's cubes, and he asked me how to frustrate amateur solvers by adversarially scrambling the cube. I expect that the answer depends highly on the particular solving algorithm. ...
• 255
3k views

### Shortest paths when randomly scrambling a Rubik's cube

I saw a previous question about local maxima for the number of moves in a Rubik's cube solution, and I wondered what is known about the distribution of shortest paths when randomly scrambling a Rubik'...
• 255