# Backtracking vs. Clickbait

In social media you often find the worst advertisements. One that I saw recently is the following one. It was a video of a field with red and blue dots, and a toy figure going through the blue dot and removing them. The idea was that it should go through the grid of dots and remove all the blue dots in one go. One must not step back and go through a grid field where the blue dot was already removed. It showed a video with the figure failing to clear them all, leaving one.

It also says that “Only people with high IQ cann [sic] clear the blue dots,” which makes it sound like a challenge. Just click here, and you can play the game. You can show that you are not a dumb person and solve the riddle.

Thing is that it isn't solvable due to the layout of the problem. Of course this is intential to keep the people playing it over and over again, and likely to consume advertisements from others. It's a clever idea, buy advertisements to lure people into pages where they are shown more advertisements for which you get the money. A pyramid scheme of attention, so to speak.

We can try to use the backtracking algorithm here to show that there is no solution to this problem. We start by representing the state as a two dimensional grid of characters, really primitive. It looks like this:

```##...
####.
...#.
.....
.....
```

Now I have the following Python code:

```import string

def print_state(state):
for line in state:
print(''.join(line))
print()

state = [
list('##...'),
list('####.'),
list('...#.'),
list('.....'),
list('.....'),
]

blue_total = sum(c == 'o' for line in state for c in line)
blue_removed = 0

steps = 0

states = []

def backtrack(row, col):
global steps
global blue_removed

if steps > 10000:
return

steps += 1

next_state_str = '\n'.join(''.join(x) for x in state)
if not states or next_state_str != states[-1][0]:
states.append((next_state_str, blue_removed))

can_move_there = 0 <= row < 5 and 0 <= col < 5 and state[row][col] == '.'
if can_move_there:
state[row][col] = string.ascii_uppercase[blue_removed]
blue_removed += 1

if blue_removed == blue_total:
print_state(state)
return

backtrack(row + 1, col)
backtrack(row - 1, col)
backtrack(row, col + 1)
backtrack(row, col - 1)

state[row][col] = '.'
blue_removed -= 1

backtrack(0, 2)
```

The main part is the backtracking. There is some book-keeping to visualize the progress. It works by tentatively going a step into any direction and leaving breadcrumbs. This way we know that we cannot go onto the same spot twice. We just go as long as we can, until we cannot move any more. Then we pick up the last breakcrumb, and go back one step. The call stack remembers which positions we have visited before.

Visualized with capital letters as breadcrumbs, these are the first four steps that the algorithm makes:

```##A..
####.
...#.
.....
.....

##AB.
####.
...#.
.....
.....

##ABC
####.
...#.
.....
.....

##ABC
####D
...#.
.....
.....
```

Eventually it has filled way more, but it did not have to backtrack yet. This changes when it places the “O” after the “N”. It cannot continue, but it is not done either. So it picks the “O” back up from the right, and tries it to the left. It then finishes until it has run out of options.

```##ABC
####D
.N.#E
.MJIF
.LKHG

##ABC
####D
.NO#E
.MJIF
.LKHG

##ABC
####D
.N.#E
.MJIF
.LKHG

##ABC
####D
ON.#E
.MJIF
.LKHG

##ABC
####D
ON.#E
PMJIF
.LKHG

##ABC
####D
ON.#E
PMJIF
QLKHG
```

But there is a spot missing! So it is not the final solution yet. It now has to bo back to the “N” and also pick that up, because there are no other options to set the “O” in this setup. So it will pick up the “N” and try to set the “N” to the left of the “M”:

```##ABC
####D
ON.#E
PMJIF
.LKHG

##ABC
####D
ON.#E
.MJIF
.LKHG

##ABC
####D
...#E
.MJIF
.LKHG

##ABC
####D
...#E
NMJIF
.LKHG
```

From there it will try again, but it will also end up leaving a spot. In the end it will have tried 592 different versions to go through this problem, but none will clear all 18 dots. Only 17 will be cleared at the maximum. These solutions look like this:

```##ABC
####D
ON.#E
PMJIF
QLKHG

##ABC
####D
OPQ#E
NMJIF
.LKHG

##ABC
####D
OP.#E
NQJIF
MLKHG

##ABC
####D
OPQ#E
N.JIF
MLKHG

##ABC
####D
.PQ#E
NOJIF
MLKHG

##ABC
####D
QP.#E
NOJIF
MLKHG
```

So matter what one does, the “Q” always end up somewhere such that one cannot remove the last dot. It is just something that cannot be solved.

One could also frame this problem in a graph theoretical way. Then one would have the following connectivity graph:

The solution to be found is a longest simple path which covers all the nodes. And the way that this graph is structured, this path simply doesn't exist. I am not sure how to show that without trying all ways (like I did above). So if somebody know it, I'd be happy to hear about that!

I wonder how many people feel challenged to prove their intelligence, only to spend quite some time on some advertisement infested website only to realize that they cannot make it. They might assume that it can be solved, just that they are not clever enough. And then they might have a hit to their self-esteem, give up, and become even more suseptible for the next clickbait riddle of this kind.

## Proof found

In the meantime a reader has sent me a proof, see the follow-up article.