# Questions tagged [puzzles]

The tag has no usage guidance.

30 questions
Filter by
Sorted by
Tagged with
385 views

### NP-Complete Static Square Puzzles

In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to ...
86 views

### Construction of binary puzzle

Does there always exists a $n \times n$ grid with $0$s and $1$s that satisfy the following conditions: there is an equal number of 1s and 0s in each row and column no more than two identical ...
215 views

### How hard is PromiseFlowFree?

Playing more Flow Free, I think I've realized why I'm so amazingly brilliant at this game: The objective is to connect all pairs while covering the entire board, but in every puzzle there is always ...
421 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$-...
125 views

Most puzzles that you can buy are in P, NP-complete (like Sudoku) or PSPACE-complete (like Sokoban), at least if you scale them up. Are there any natural puzzles that are PPAD-complete? What about ...
274 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 ...
3k 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 number ...
346 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 ...
851 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 highest ...
325 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 cable; ...
191 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 0,...
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'...
300 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. ...
4k 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 ...
402 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 ...
625 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...
644 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 can "...
257 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 ...
536 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 ...
217 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 ...
203 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 ...
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: ...
907 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 ...
502 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 ...
669 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 ...
628 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}$ ...
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? ;...
8k 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 ...
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 ...
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? ...