Part 3's fast route cleans a furnished 40×40 room in 1,327 commands, and Part 3 could only prove that no route needs fewer than 1,037. Written as a linear program, the same question proves 1,122. The simplex method from …
Put five squares round every corner of the robot's floor instead of four and the floor can't lie flat: it ruffles like a lettuce leaf. Within ten steps there are 16,737 fields instead of 221, the 50,000-command budget …
Send the cleaning robot up the walls of a pool or over the outside of a box, and three left turns can bring it home. Every corner is ninety degrees short, no compass fits the whole surface, the checkerboard fails at each …
Glue the room's ends with a half twist, like a Möbius strip, and every lap swaps the robot's up and down. Part 1's commands walk it into walls, the blind robot's dock needs an arrow, and union-find with parity tells, one …
Glue the room's left edge to its right and its top to its bottom, as in Asteroids. The cleaning robot's walk still works, but the blind robot from Part 3 never stops and the checkerboard bound gives wrong answers. A …
The fewest commands, a robot with no map, a dock that empties the bag and a second robot that must not collide. Each new rule turns the cleaning robot puzzle into a different classic problem: a travelling-salesman path, …
Every floor field gets some dirt and the robot a bag that fills up, then a battery that runs out. The cleaning robot puzzle turns into subset sum, a connected knapsack and the orienteering problem, with exact solvers …
One robot, rooms full of furniture and a 50,000-command budget: a short depth-first search cleans it all. The first part explains it line by line, traces it by hand, proves it correct and checks it on 3,000 random rooms.
Algorithms