program be possible?
Yes, possible.
NL doesn't expose an API to control execution. Either let the robot brute-force replays based on the level file and feed them into the NL replay checker, or fork NL and hack the robot into the game itself.
you'd need to do some culling, but try to define some good rules for this that don't cause backroutes to be missed.
Yeah, brute-force is infeasible. The solution space explodes according to the size of the skillset.
For brute force, the solution space is all replays that assign the finitely-many skills to the finitely-many lems over time. Since time is unlimited, it seems absurd to allow the maximum possible time before a looping sequence of physics repeats, and instead impose artificial restrictions à la maximum of 5 minutes of doing nothing, or 10 minutes of absolute time.
In Lix, we already encourage level authors to let levels be solved within 5 minutes after the final assignment, so a skill every 5 minutes seems reasonable. 5 minutes is 5*60*15 Lix physics updates or 5*60*17 NL physics updates of doing nothing.
Lix replay checker runs single-threaded. On an Intel i5-6600 at 3.30GHz with 4 cores (3 unused), it checks 22 replays/second. Even though this doesn't generate any imagery unlike the interactive mode, some time is still spent constructing the physics matrix in the beginning. For solving single levels, you would construct this phymap once, cache that, and revert.
The problem runs purely on RAM, and two solutions never interact, thus this parallelizes perfectly across CPU cores.
We still cannot conclude that, without rendering the phymap every time, an AI could test replays faster than this per core. Wrong replays can run for a while before they're cut under the 5-minute-idling rule.
Ballpark guess: A typical level may have 20 lix, 10 skills, and guarantees that a solution under 10 minutes = 9000 Phyus exists. To brute-force without reading physics along the way, each skill assignment may go in 9000*20 positions, and you must test all spreads of the 10 different skills across these positions, that is (9000*20)^10 = 3.57 * 10^53 replays. At 20 replays-per-core-per-second * 4 cores = 80 replays-per-second, we need 4.4 * 10^51 seconds = 1.4 * 10^44 years.
essentially finds all possible solutions in a level
You'd have to define "essential". Levels with infinite time can allow infinitely many solutions. The human considers two solutions practically identical based on intuition, this seems hard to capture in rules.
-- Simon