The robotic vacuum cleaner

Question

An engineer has invented a robotic vacuum cleaner to sweep the floor of his house. The floor plan, shown below, is made up of many square tiles, with walls at certain places, represented by black cells.

The robot cleans one tile at a time, then moves either N, E, S, or W to the next tile. Being a prototype, it cannot detect if a tile is already clean nor skip a tile. After it moves to a new tile, the robot always clean it. Obviously, it cannot go through walls.

The robot is parked at a certain place. Ideally, the engineer wishes to program a route such that the robot visits each tile exactly once and terminate exactly at where it started, so it's ready for the next clean.

How many such paths are there? Symmetrical paths are counted separately, but different starting points along the same path are counted as one.

Answer 1

There's an odd number of tiles (11 × 23, minus an even number of wall spaces).

Any cyclical route must have the same number of North moves as South, and the same number of East moves as West.

Therefore the cyclical path has an even length and visits an even number of tiles.

Therefore there is no cyclical path visiting each tile once.

Answer 2

Assume square A1 is black, and that the floor is covered in a checkerboard pattern. Then, the entire grid contains 253 squares, 127 black and 126 white. A total of 42 squares are removed, leaving 211 squares.

Since the tiles alternate colour whenever the robot moves to a new tile, any path that ends up back on itself must be of even length. But there are an odd number of tiles on the grid, so no cycle is possible.

---

Now, can we do slightly worse and have there at least be a path where the robot can clean each tile?

From columns A and W, four black and four white tiles each are removed, for a total of eight black and eight white tiles.

From columns G and Q, each of the three-tile pillars contains two white tiles and one black, so a total of eight white and four black tiles are removed.

Finally, from columns I to O, each of the seven-tile blocks contains four black tiles and three white tiles, so a total of eight black tiles and six white tiles are removed.

In total, 20 black tiles and 22 white tiles are removed, leaving 107 black tiles and 104 white tiles. Any path cannot have a difference of more than one tile between the number of black and white, but there are three more black than white tiles. Thus, not even a path is possible.

Answer 3

Joe has the right answer, but it is a little hard to follow, so I will try to reproduce it here.

To start with, note that the entire room (including the walls) is 11x23=253 squares. Lets apply a checker board pattern to this rectangle. If you start with A1 black, then you will have 127 black squares and 126 white squares.

Now lets remove the walls.

The walls in the A and W columns include 2 black and 2 white squares each, and there are four such walls in total. Thus, you are left with 119 black and 118 white squares.

Since A1 is black, G1, G11, Q1, and Q11 are also black. That means that the walls in columns G and Q each contain 2 white and one black square. There are 4 of them again, so after removing these, you are left with 115 black and 110 white squares.

Lastly, there are two horizontal walls between columns I and O. Notice that I3 and I9 are black, so these two walls each contain 4 black and 3 white tiles. Thus, we are left with 107 black and 104 white tiles in the room.

Note that the robot always moves up, down, left, or right. This means that whenever it is on a white tile, its next move will be on a black tile, and vise versa.

So even if the robot starts from a black tile, it can only move to a white tile and return to a black tile 104 times before it will run out of white tiles to move to. But there will still be 2 black tiles left unvisited.

Thus, there is no path (directional, or cyclical) through the room without revisiting tiles.