With a battery of five moves, Part 2's robot collects 14 units of dirt and the best route collects 16. A price of 3¼ units of dirt per move proves that no route collects more than 17, and a concave hull shows why no …
Part 3's fast plan empties the bag on a furnished 12×12 room in 178 moves; the best plan takes 170, and this part proves it. A plan as a choice among trips, column generation with the dual prices of the fields, pricing …
Part 3's fast route cleans a furnished 20×20 room in 243 commands. The shortest route takes 221, and this part proves nothing shorter exists: parity and whole numbers put back into Part 8's linear program, branch and …
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.
A solver test failed in February and a hard-coded relaxation factor of 1.5 took the blame. Measured on every grid, 1.5 was within a sweep of the best on exactly one of them, February's failure had another cause, and the …
Part 1 of this saga shipped a compare-and-swap loop that gave up after 100 tries. It can fail at most 64 times. What really loses an Add is Union, with no retry involved and nothing the race detector can see. With …
Testing