The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
120 views

Partially filled jigsaw puzzle with six types of tiles

This is a slight variation of the question Are 'zero-one' jigsaw puzzles NP-complete? asked on cs.stackexchange.com. What is the complexity of the following problem? Input: an $n\times n$ Jigsaw ...
6
votes
1answer
828 views

How hard is binary Sudoku puzzle?

Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers $0$ and $1$. The rules are as follows. Each row and each column must contain an equal ...
3
votes
1answer
267 views

How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

The following question was first presented in MATHEMATICS of StackExchange. With a simple description at first sight, it has far-reaching consequences on plenty of recent and advanced theories, such ...
8
votes
2answers
478 views

Is there some mathematical closed form (or somewhat tight asymptotic one) for “Google Eggs Puzzle”?

The following brief description of the known "Google Eggs Puzzle" comes mainly from the web site Google Eggs: Google Eggs Puzzle: Given n floors and m eggs, what is the approach to find the ...
8
votes
1answer
242 views

The complexity of the puzzle game Net

Net (known also as FreeNet, or as NetWalk) is a puzzle game played on a $n \times n$ grid with the following objects: there are $m$ computers ; each computer occupies one cell and has one link ...
5
votes
0answers
99 views

Reduction from planar bounded NCL to a static puzzle game

I call Fill3 the following simple game: the input is a $n \times n$ grid; every cell of the grid has a type: OR, AND, CHOICE, FANOUT and FIXED and can be rotated ...
4
votes
1answer
976 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 ...
5
votes
1answer
247 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. ...
27
votes
8answers
2k views

What is the minimum number of bits required to store a sudoku puzzle?

Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support solved, legal puzzles. So a solution doesn't need to support empty cells and can rely on the properties of a solved ...
4
votes
2answers
344 views

Can we infer the next player in chess from the current board configuration?

Presume that a program memory only includes the current state for instance of a chess board. Does it need the variable which player, black or white, has the next turn to move or is it redundant ...
3
votes
1answer
429 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...
18
votes
2answers
476 views

Solving a Number-Hopper Maze

My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this: The idea is to start from x and reach o via the normal rules. Additionally, you ...
9
votes
1answer
220 views

Bounding the number of edges between star graphs such that graph is planar

I have a graph $G$ which consists only of star graphs. A star graph consists of one central node having edges to every other node in it. Let $H_1, H_2, \ldots, H_n$ be different star graphs of ...
11
votes
1answer
420 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
vote
0answers
204 views

constraints placement question

Suppose I have a set of squares. I get them in iterative way – one after another. I would like to place the squares in some structure according to set of rules: When a new square arrives all ...
1
vote
1answer
197 views

Naming the Boxes

Here is a puzzle (which I am sure somebody must have studied in TCS): Suppose I have $x$ balls, each having a unique $O(\log x)$ bit name (the names have no structure). These balls are distributed ...
11
votes
2answers
1k 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: ...
5
votes
1answer
589 views

An Interactive Proof of God's Number?

I've been learning about interactive proofs lately and I've been wondering if the whole thing was nothing more than a theoretical curiosity, or if it had any practical applications. I thought I'd ...
10
votes
2answers
449 views

Complexity of hidden polygon puzzle on square grids?

Hiroimono is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle. The problem is: Input: Given a set of points on on a $n$x$n$ square grid and ...
22
votes
2answers
612 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 ...
28
votes
2answers
590 views

Bounded-input bijections of infinite sequences

Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution. It is possible to define a bijection $ 3^\mathbb{N} \cong 5^\mathbb{N} $ ...
35
votes
6answers
2k 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? ...
33
votes
2answers
3k 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 ...
16
votes
1answer
545 views

Construction of graphs where every pair of vertices have an unique common neighbor

Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise ...
15
votes
1answer
788 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? ...