9
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ I know for sure there is 2 lol $\endgroup$ – warspyking Oct 5 '14 at 14:27
  • $\begingroup$ If you mean paths in opposite directions, no they're counted as one. $\endgroup$ – kevin Oct 5 '14 at 14:37
  • $\begingroup$ It's the same thing but reversed XD $\endgroup$ – warspyking Oct 5 '14 at 14:43
  • 5
    $\begingroup$ This asks: "Where every white box is a vertex and white boxes which touch are connected by an undirected edge, how many Hamiltonian Cycles are there?" ALOT $\endgroup$ – d'alar'cop Oct 5 '14 at 17:53
  • 1
    $\begingroup$ Since they must all contain every square... starting place doesn't matter. $\endgroup$ – d'alar'cop Oct 5 '14 at 19:21
6
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So a good programmer would have to use the room is symmetric, and program the robot to alternatively start at B1 and V11... $\endgroup$ – Alexander Oct 6 '14 at 14:10
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Both of you are correct. I think you explained a bit better than Joe. Still, I'm not giving credit yet - there's another simpler (in my opinion) explanation that does not involve using checkerboard tiles. $\endgroup$ – kevin Oct 7 '14 at 1:32
  • $\begingroup$ @kevin: What is your (subjectively) simpler explanation then? $\endgroup$ – Chris Nov 4 '14 at 14:28
  • $\begingroup$ @IanF1's answer: there's an odd number of tiles, which makes a path impossible. $\endgroup$ – kevin Nov 4 '14 at 14:46
  • $\begingroup$ @kevin Hmm... I thought the question was for any path, not just cyclical, but now that I look at it again, I see you only asked for a cyclical path. $\endgroup$ – Trenin Nov 4 '14 at 14:54
  • $\begingroup$ @Trenin yup that was what I was looking for; although I do appreciate your effort for trying to solve for any path as well (I did not try this myself until I saw the answers). $\endgroup$ – kevin Nov 4 '14 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.