Linear ProgrammingThe Cleaning Robot Puzzle: A Lower Bound from a Linear Program
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 …