This is still handwaving a little, since for horses you cut verticies and not edges and you have a different variant of optimization/decision problems, but these are the kind of issues that should be easy to workaround in your reduction.
I don't know if the planar version is still NP-complete.
Hmmm! I think there are a lot of graph problems that are polynomial when planar but non-polynomial when non-planer though. Good point that it's strongly related to min-cut though. (At first I thought it just WAS min-cut but I guess the size of the cut here is fixed and you're tying to maximize the number of enclosed nodes?)
Integer programming is great, especially when it's used as the backend for a nice language like MiniZinc. Personally I find integer programming about as natural as using assembly language to write code.
Fun little game and I really want to try out integer programming now!
I think I've found a bug with your formalization: Have a look at this little level: https://enclose.horse/play/XHZO8P. I'm pretty sure the maximum score is 3. But your script's solution has a score of 1. It tries to enclose the upper row, which doesn't count as horse cannot reach it.
Edit: Yair Halberstadt was quicker in figuring this out
Ah, you're absolutely right. This is indeed the problem that I'm not enforcing that there is only one contiguous enclosed area, it's found a solution that's (according to my definition) "better" than the optimal one, because it encloses a total of 10 squares, rather than just two. Thanks for pointing this out, I'll update the model to enforce that there's only one connected component.
It seems to me this would allow a solution where a large space is bounded, and the horse was bounded separately? Am I wrong that there's nothing in your constraints which says that the inescapable area has to be attached to the horse?
> Am I wrong that there's nothing in your constraints which says that the inescapable area has to be attached to the horse?
This thew me off at first. We do have the constraint that E[i,j]=0 if (i,j) is the horse. This means that the horse must be enclosed. However, I think it is theoretically possible that my solver could return a solution with two separate enclosed areas. In some sense this is OK in the spirit of integer programming, because if such a failure mode occurred, you wouldn't know it, it wouldn't be a quietly suboptimal solution. But I suspect it would be possible to reformulate and prevent this. I'll think about it.
Here's an adversarial level I designed: https://enclose.horse/play/ZxxGGo. I guess you can only get a score of 8, but the disconnected solver will think it can get a score of 13 by enclosing the other region.
I guess you'll need a third constraint to tell if a region is connected to the horse:
C[i,j] = 1 at the horse (C for Connected to horse)
I think you might like adventofcode.com (which thankfully needs no UI parsers to interact with mostly integer problems)
If linear programming is so great and factorio so bad, write a linear program to do factorio then I dare you
The NP-completeness of the non-planar version (so if you are allowed to place portals on the map, like some later levels) of the problem was proven in https://www.sciencedirect.com/science/article/pii/S0304397515009378
This is still handwaving a little, since for horses you cut verticies and not edges and you have a different variant of optimization/decision problems, but these are the kind of issues that should be easy to workaround in your reduction.
I don't know if the planar version is still NP-complete.
Hmmm! I think there are a lot of graph problems that are polynomial when planar but non-polynomial when non-planer though. Good point that it's strongly related to min-cut though. (At first I thought it just WAS min-cut but I guess the size of the cut here is fixed and you're tying to maximize the number of enclosed nodes?)
Integer programming is great, especially when it's used as the backend for a nice language like MiniZinc. Personally I find integer programming about as natural as using assembly language to write code.
...I mean, I already don't play factorio because it feels a bit too much like work, but am I missing the reference?
No, I think you basically got it.
How did you lose access to your website??
Certain tokens being stored on certain hard drives that are far away from where I currently am. :) No worries, I'll have it back soon.
Fun little game and I really want to try out integer programming now!
I think I've found a bug with your formalization: Have a look at this little level: https://enclose.horse/play/XHZO8P. I'm pretty sure the maximum score is 3. But your script's solution has a score of 1. It tries to enclose the upper row, which doesn't count as horse cannot reach it.
Edit: Yair Halberstadt was quicker in figuring this out
Huh? I just tried running it on that map myself and it seems to find the solution just fine.
$ uv run map.py
solve time: 0.03868913650512695
[[0 0 0 0 0 0 0 0 0 0 0]
[5 1 1 1 1 1 1 1 1 1 0]
[0 0 0 0 0 0 0 0 0 0 0]
[1 1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 0 0 0 1 1 1 1]
[1 1 1 1 0 2 0 0 1 1 1]
[1 1 1 1 0 1 1 0 1 1 1]
[1 1 1 1 1 5 5 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1 1]]
You called it with 3 walls, but the map only allows 2.
This is the solution I get:
[[0 0 0 0 0 0 0 0 0 0 0]
[5 1 1 1 1 1 1 1 1 1 0]
[0 0 0 0 0 0 0 0 0 0 0]
[1 1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 0 0 0 1 1 1 1]
[1 1 1 1 0 2 0 0 1 1 1]
[1 1 1 1 0 5 1 0 1 1 1]
[1 1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1 1]]
Ah, you're absolutely right. This is indeed the problem that I'm not enforcing that there is only one contiguous enclosed area, it's found a solution that's (according to my definition) "better" than the optimal one, because it encloses a total of 10 squares, rather than just two. Thanks for pointing this out, I'll update the model to enforce that there's only one connected component.
It seems to me this would allow a solution where a large space is bounded, and the horse was bounded separately? Am I wrong that there's nothing in your constraints which says that the inescapable area has to be attached to the horse?
> Am I wrong that there's nothing in your constraints which says that the inescapable area has to be attached to the horse?
This thew me off at first. We do have the constraint that E[i,j]=0 if (i,j) is the horse. This means that the horse must be enclosed. However, I think it is theoretically possible that my solver could return a solution with two separate enclosed areas. In some sense this is OK in the spirit of integer programming, because if such a failure mode occurred, you wouldn't know it, it wouldn't be a quietly suboptimal solution. But I suspect it would be possible to reformulate and prevent this. I'll think about it.
Here's an adversarial level I designed: https://enclose.horse/play/ZxxGGo. I guess you can only get a score of 8, but the disconnected solver will think it can get a score of 13 by enclosing the other region.
I guess you'll need a third constraint to tell if a region is connected to the horse:
C[i,j] = 1 at the horse (C for Connected to horse)
C[i,j] = Map_is_grass[i,j] * max(C[i-1,j], C[i+1,j], C[i,j-1], C[i,j+1])
redefine E'[i,j] = E[i,j] || not C[i,j]. I wrote that as Boolean logic but you can translate it to arithmetic.