Questions tagged [algorithm]

A puzzle related to algorithmics (a main concept in computer science).

Filter by
Sorted by
Tagged with
87
votes
7answers
21k views

Why does this solution guarantee that the prince knocks on the right door to find the princess?

I found this puzzle online: On the top floor of a castle lives a princess. The floor has 17 bedrooms arranged in a row. Each bedroom has doors connecting to the adjoining bedrooms as well as to the ...
34
votes
9answers
4k views

Wolves and sheep

All the sheep were living peacefully in the Land of Shewo. But suddenly they were struck by a danger. A few wolves dressed up as sheep entered the territory of Shewo and started killing the sheep one ...
31
votes
5answers
4k views

Switch The Knights

On a small $ 4 \times 3$ chessboard, the top row is filled with black knights and the bottom row with white knights. On each move, you may move one knight (as it moves in chess) to an unoccupied ...
28
votes
7answers
2k views

23 Clones and Two Lightbulbs

Rise and shine, Mister Bond. James awoke to find himself yet again imprisoned by an evil genius. At least, that's what he presumed. He was alone in a room with a strange device: it consisted of a ...
24
votes
7answers
6k views

Hacking an electronic keypad

You are a spy trying to break into an enemy facility. The back door is protected by an electronic keypad lock. You know that this particular lock is opened by a four digit code. Any stream of button ...
22
votes
5answers
949 views

Confused Soldiers

A squad has $n$ soldiers. Their impatient commander yells at them to form a line going East to West, with everyone facing East. They quickly manage to form an East/West line, but some soldiers are ...
22
votes
2answers
1k views

Desegregate the Knights

You are given a 3 by 3 chessboard with a knight on each corner, where the knights in the top row are black and in the bottom row are white. On each turn, you may move a knight of either color (the ...
22
votes
1answer
2k views

Is there an algorithm to decide that the nonogram puzzle is unique

A good nonogram puzzle has a unique solution. However, some nonograms do not. For example, this puzzle: ...
21
votes
4answers
1k views

Checkerboard Infection: The Aftermath

As in this previous puzzle, we are again playing with our favorite bacteria, C. Coli, whose natural habitat is an 8x8 checkers board. These are very nasty bacteria - once they are in a cell of a ...
19
votes
4answers
3k views

Checkerboard Infection

There is a dangerous bacteria, Checkerichia Coli, (or C. Coli for short) which lives in the squares of checkerboards. Squares with this bacteria living in their digestive systems are said to have "C-...
19
votes
1answer
1k views

Mystery operation

In a future not so far way, Earth archaeologists find on a far away planet a fragment from a long lost civilization. This fragment involves an unknown operation *|*...
19
votes
2answers
8k views

A general solution to the decanting problem? (aka jug-pouring, water-pouring)

Take a look at these two questions: - A Set of Water Jug Challenges - Pouring problem Now I'm asking for a generalised solution to that problem. I define the problem as follows: You are required ...
18
votes
5answers
4k views

Maze Solving Robot

Archie the archeologist has discovered an Egyptian temple, and plans to send in a robot to explore it. He uncovered the ancient engineers' papyruses which explain almost everything about the temple's ...
18
votes
5answers
1k views

Blindfold Bingo

Congratulations, you have been selected from among the audience to compete in the fabulous Blindfold Bingo challenge! (cue annoying, yet catchy theme music.) Here you see our perfectly ordinary Bingo ...
18
votes
4answers
2k views

Consecutive Towers of Hanoi

Consider the following variant of the Towers of Hanoi puzzle. There are six pegs. One of the pegs has a stack of $n$ differently sized disks, sorted by size so the smallest disk is at the top. All ...
16
votes
5answers
4k views

Can you recreate this fractal I randomly made?

This fractal looks relatively simple, but how would you generate it? On a smaller scale: I made it using a 1D cellular automaton with a four cell neighborhood: ...
16
votes
8answers
2k views

Rigged casino that prevents pairs

This question is still active as the answer from @Sleafar has just arrived. Not yet solved. Scenario The heads of 3 top terrorist organisations are planning to play an extremely high-stake poker ...
14
votes
6answers
2k views

Radioactive Rods

You have 8 identical looking rods, 2 of which are radioactive, though you don't know which. You also have a box which can test for radioactivity, which can hold any number of rods. After the test, the ...
14
votes
4answers
2k views

Emoji primes - what's the smallest positive integer this doesn't work for?

Driven by a silly conversation at work, here's the puzzle. Slack allows users to send emoji as a reaction to a message. Emoji are listed left to right in chronological order of reaction, and 'stacks' ...
13
votes
12answers
2k views

2 Person Same Number Verification

Alice and Beth both receive a random integer from 1 through 10, inclusive. They only know the number that they are given. The two of them want to come up with an algorithm to check that their ...
13
votes
1answer
497 views

GameDev: stuck with first puzzle design, would love resources to study from or algorithm suggestions!

First time posting here and I'm really, really hoping this is the community I've been looking for. I'm developing a game, right now I'm in the middle of designing levels as the core mechanics have ...
13
votes
4answers
387 views

20-Questions on a grid

Posted this on /r/puzzles too, none have given the right strategy as of now :) There is a square grid of width and height $m$. Three facts about the grid: Each cell has a value, and no two cells ...
13
votes
1answer
1k views

What is the optimal first move in Mastermind?

For a given number of positions/holes and a given number of colors, which initial guess eliminates the most possibilities for the solution at a minimum? For 4 positions, it's AABB. What is it for 5, ...
12
votes
2answers
398 views

Cubical Infection

You may remember the C. Coli bacteria, which infects checkerboard squares. There is a similar disease which plagues cubes, known as cubic lice. Once a cube gets infested with cubic lice, it will be ...
12
votes
1answer
351 views

Infection (Information Dissemination) Puzzle

There are 2020 people in a room. One person has COVID. After each minute, each person $\mathrm{P}$ is paired with some other person $\mathrm{Q}$ who was never paired with $\mathrm{P}$ before, and they ...
11
votes
2answers
2k views

Two Cannons - A Beginner's Physics Puzzle

Standoff Let's say we have two cannons aimed directly at one another ( as my horrible attempt shown in the image ). The Angles The cannon on top is aiming down towards the one on bottom right, and ...
11
votes
4answers
290 views

Rank the Fencers

There are five fencers. Each has a particular skill level, all of which are different. When two fencers duel, the one with the higher skill level always wins. How many duels do the fencers need to ...
11
votes
2answers
2k views

Three knights searching for a princess in a castle

There is a castle with rooms arranged in a 4x4 square grid. The princess living in the castle sleeps in a different room each night, but always one adjacent to the one in which she slept on the ...
11
votes
1answer
2k views

Worst way to solve Rubik's in one algorithm

If you apply the same algorithm over and over again the cube will be solved. I want to know what algorithm is the worst one (the one with the longest cycle) I have found RU (cycle of 60 times) I have ...
11
votes
7answers
3k views

Fastest way to collect an arbitrary army

I am looking for solution of this puzzle: There is a kingdom with a square shape with sides of length 1. The castle is located at the center of the square. At the castle the king lives under the ...
11
votes
3answers
1k views

The Generous Taco stand

There are a group of people standing in line for a taco stand. This taco stand is special in that it's slogan is "The older you are, the more you get!". To make sure though that there isn't any funny ...
11
votes
3answers
38k views

What is the Official notation on rubik's revenge(4x4)?

When solving a 4x4 cube you have specific notation to inner and outer lines, like R = Clockwise outer right and r = Clockwise ...
11
votes
2answers
1k views

Let's deal with “Names in Boxes” Safely

I met a puzzle, which is basically well known 100 Prisoners' Names in Boxes , but... it has an algorithm, which gives prisoners 100% chance to survive! This is achieved by a small change in the ...
10
votes
1answer
508 views

Half-reverse operation on binary strings

Is there an algorithm that you can apply twice to an input string of $0$s and $1$s in order to reverse it? In other words, is there a function $f : \mathrm B \to \mathrm B$ on the set of binary ...
10
votes
3answers
5k views

How do I memorize parity algorithms for higher-order Rubik's cubes?

I know how to solve a Rubik $4\times4\times4$ or $5\times5\times5$ or bigger, but I have problem with a specific algorithm: the parity error. What's the shortest parity algorithm for $n\times n\times ...
10
votes
2answers
2k views

3x3x3 Rubik's Cube Illegal State

After I learned how to solve a 3x3 Rubik's Cube and a 4x4 Rubik's Revenge, I began challenging myself to solve the cubes to different states rather than the normal solid sides. For instance, I'd solve ...
10
votes
2answers
528 views

Maze Solving Robot, More Difficult Variant

You are trying to design a maze solving robot, capable of solving "valid" mazes. A valid maze is an 8 by 8 checkerboard, surrounded by walls, where Between each pair of orthogonally adjacent squares, ...
9
votes
5answers
239 views

An $n$-sided polygon with area $n$

Here is a $10$-sided polygon which area is $23$ (i.e. it contains exactly 23 unit squares). Can you draw a polygon with: $6$ sides and area $6$? $8$ sides and area $8$? $12$ sides and area $12$? ...
9
votes
3answers
377 views

A problem of inequalities

The puzzle Given a set of numbers $\{1,2,\ldots,n\}$ and an expression of inequalities, e.g., $ x_1 > x_2 < \cdots > x_n$. Prove that there always exists a solution such that $x_i \in \{1,2,\...
9
votes
1answer
470 views

Puzzles like Sokoban?

I am looking for some puzzles like Sokoban or 15-puzzle but more difficult to solve and satisfy the following requirements: The number of possible moves at each step should be limited, let's say < ...
9
votes
1answer
265 views

Scoring Oracle: Bob easily wins, but how much?

Bob meets a magician with two bags and a chest on a bridge. The magician challenges him with the following enigma: Here is a bag A, holding 5080 pebbles. Here is another bag B. Most of the pebbles ...
8
votes
2answers
1k views

Stacking pancakes for your wife

You are cooking pancakes for your lovely wife. You want to sort the pancakes such that they increase in diameter as you move from the top to the bottom of the stack. The only operation you can perform ...
8
votes
4answers
2k views

Is there a simple algorithm for solving Kami 2 puzzles?

I'm finding my life has been consumed by Kami 2, partly because I seem to have achieved some "insight" and am able to solve the puzzles reliably, almost always on the first try. The rules are simple: ...
8
votes
1answer
466 views

Cube Scrambling

Take a normal 3x3 rubiks cube (the Classic unmodded cube). I know the WCA method for scrambling is to pick a random (valid) cube state and calculate a sequence of moves to go from solved to that state,...
8
votes
2answers
224 views

How to beat “Strata”?

Recently I purchased a bunch of mobile puzzle games for my iPhone and one of them was the famous top-rated app "Strata" by Graveck. The rules are simple - you begin with an $n \times n$ board, some ...
8
votes
4answers
461 views

Ten users, three lights but it's a chatroom

This is a variant of the classic problem of m prisoners n lights. (Example may be found here but note that the requirements are not exactly the same) The goal for you, however, is different. You want ...
8
votes
5answers
2k views

Minimum cells to fill grid without consecutive neighbours

Imagine you have a m x n grid which is initially colored white. you can fill in a cell with black color if and only if there are no immediately neighboring black cells (no black cells to the left/...
8
votes
3answers
176 views

Creating a maze that is traversed by a pair of compasses

Normal mazes require you to move a point-like object from the entrance of the maze to the exit. I am wondering whether a different kind of maze would work as a puzzle: Imagine a maze printed on a ...
7
votes
3answers
446 views

Find Local Maximum in an Integer Sequence

An element of an integer sequence is called a local maximum if it is not smaller than all its neighbors. E.g., all local maximums of the following sequence are highlighted. Consider an integer ...
7
votes
2answers
561 views

Numbers on a Blackboard

You are given an empty blackboard. Once a minute, you are allowed to do one of the following: Write two $1$'s on the blackboard Erase two copies of a number, $n$, and replace them with $n-1$ and $n+...