Author Topic: Most restrictions vs. most solutions  (Read 2304 times)

0 Members and 1 Guest are viewing this topic.

Offline mobius

  • Posts: 2747
  • relax.
    • View Profile
Most restrictions vs. most solutions
« on: October 31, 2019, 10:33:57 PM »
Math nerds; I have a problem for you to work on :P  I want to see if I can figure out how to do this or if it's even possible or not.

This was how I formed this idea:
At first I wanted to try to make a level that has a large number of solutions (but not infinite). I want a lemmings level that has a definitive finite number of solutions that are certainty different from each other*.
Then I got to thinking why not make the level as small and limited as you can and see how many solutions you can fit into one tiny level? Two extremes: smallest level; smallest skill set, (possibly) smallest time limit but largest number of solutions.


Obstacles:
*The first major obvious problem here is defining how solutions differ from each other. I'm not sure if this was discussed in the NP hard thread but it goes without saying that every level has a huge number of solutions if you consider e.g. placing a builder bridge 1 pixel differently to be different.
For this to even be worth considering I think we need to come up with a good definition of what constitutes a "different" solution. But this is not easy. Some important factors:
-Each objective of each skill might have to be factored into this consideration. For example; in the above example; this would not constitute different because if the object was to cross a gap and placing the bridge with a leeway of 5 or so pixels still reaches said objective; then only one of those count. Placing the bridge on any of those pixels is the same solution.
However; if the bridge crosses a gap in one example; then in another; is placed 1 pixel to the left and still crosses the gap but the builder doesn't turn from hitting something above (which he did if one pixel to the right) then this in turn allows him to do something else not possible otherwise etc etc.) this could allow for a 'certainty different' solution. Already it's gotten pretty complicated.

I'm not exactly sure how to even begin. I'm curious if there's a way to compute this or make some kind of educated estimate/ballpark/upper & lower bound on what a possible answer might be.

IMO the best way to start would be to make the smallest possible solvable level (which I believe namida did posted a while ago in discord); work out the number of possible solutions; then make the level slightly bigger; adding only 1 new element or possibility etc. and go from there?

I got the idea for this while watching a video about the Tree3 problem. Maybe we will be able to create another new huge number while doing this :D
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Offline namida

  • Administrator
  • Posts: 12398
    • View Profile
    • NeoLemmix Website
Re: Most restrictions vs. most solutions
« Reply #1 on: October 31, 2019, 11:48:55 PM »
I doubt it's possible to have a completely objective definition of what does or doesn't count as a "different solution". The only cases we could really count as "the same" solution that aren't literally identical, would be changes that have absolutely zero impact on physics whatsoever (eg. a release rate change after all lemmings are already out, or assigning a swimmer to a lemming that dies / exits without ever encountering water, etc).

Even this, some people might theoretically disagree on.

Beyond that, it's going to be very subject to interpretation, so I'd ultimately have to say "go with whatever you feel counts while designing the level".
My Lemmings projects
2D Lemmings: NeoLemmix (engine) | Lemmings Plus Series (level packs) | Doomsday Lemmings (level pack)
3D Lemmings: Loap (engine) | L3DEdit (level / graphics editor) | L3DUtils (replay / etc utility) | Lemmings Plus 3D (level pack)

Offline grams88

  • Posts: 557
  • Just one more thing.
    • View Profile
Re: Most restrictions vs. most solutions
« Reply #2 on: November 01, 2019, 12:59:08 AM »
(Smile if you love lemmings) that level I think has a lot of different solutions, I could be wrong. (Interesting topic Mobius)