Skip to main content

Questions tagged [puzzles]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
40 votes
3 answers
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 ...
Jeffε's user avatar
  • 23.2k
38 votes
6 answers
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? ;...
Daniel Apon's user avatar
  • 6,011
18 votes
1 answer
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? ...
Jagadish's user avatar
  • 1,955
23 votes
2 answers
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 ...
Joe Fitzsimons's user avatar
13 votes
1 answer
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 ...
Steven Stadnicki's user avatar
13 votes
2 answers
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: ...
levanovd's user avatar
  • 231
8 votes
1 answer
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 ...
Neal Young's user avatar
  • 10.8k
7 votes
0 answers
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$-...
user avatar
5 votes
1 answer
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. ...
Lucas Cook's user avatar
5 votes
1 answer
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'...
Lucas Cook's user avatar
4 votes
1 answer
667 views

Synchronizing sequences for rubik's cube?

Are there any results on the existence of synchronizing sequences for a standard 3x3 rubik's cube? Like a proof that there are none? My google-skills failed me...
Mike's user avatar
  • 41