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.