hey there, I managed to add cherries and apples! (note: i did use AI for this and I ditched the visual recognition code for text input but hey, it works!)
Wonder whether changing E[i,j] ≥ (1-W[i,j]) E[i_n, j_n] (as in your post) to E[i,j] ≥ E[i_n, j_n]-W[i,j] (as in your code) is always ok
Sure, the inequality will stay true, but why won't it introduce new spurios solutions (it seems that dropping W[i,j] instead of E[i_n, j_n] will do so, as we'd get E[i,j] ≥ E[i_n, j_n]-E[i_n, j_n] = 0 )?
Very interesting! Though, I think the level on the 14th breaks the solver. I figured out how to directly extract the daily from the API and parse it directly into the solver. It found a solution with a score of 110; meanwhile, the true optimal is 112. I was considering a brute-force approach, but that seems like it might be... inconvenient, to say the least. Do you think a graph-based approach could optimize this better?
Woah, that's surprising. I think the solver could give a solution that's "too good" (because it has two connected areas) but I don't see how it could give a suboptimal one. You're sure there's no error with the map?
(Also, any chance you could show your way of getting the daily?)
The "Zip" game of LinkedIn Games is a (simplified) Hamiltonian path game! (Also, yes, LinkedIn has daily puzzle games and I have an unspeakably long streak on them)
Regarding turning optimisation problems into games, the resolution of my R&D on that (especially regarding the NP ones) is that they're inherently difficult to make good because the score difference between the obvious solution and the optimal solution is usually pretty small, so it's hard to make players care.
Small score differences would matter in a competitive game I guess, but many don't enjoy those including me, so I didn't continue.
Also, you'll only be able to tell players whether they've found the optimal solution either as a result of of the fact that a machine found it or because another player found it before them, acknowledging either of these things is demoralising.
Various possible mitigations though:
I guess you could maybe address both of those things by (as usual) immersing the player in a natural-seeming environment where finding optimal solutions is necessary to progress, I'm imagining for instance a basin that tends to drain into groundwater at a particular rate, so you can only overflow into the canal if you can make a pump with a very specific minimum efficiency. I wouldn't want to put fluid dynamics in a game but that illustrates the design principle. Basins and overflows.
Another situation where small optimizations count is one where many people are using the optimised design. Massively multiplayer collaborations do feel pretty good. Reframe the competitive "someone else has optimised this further than you so you're useless" to "someone else has optimised this further than you and you get to benefit from that, and also you can go and optimise something else instead". Though the "go and optimise something else instead" does rely on the absence of exactly the kind of botting this post is about :p
It was easy enough to grab the map out of __LEVEL__.map in console. Gemini 3 Pro one-shotted all of "figure out the rules from the javascript, parse the map, write a program that calls `scipy.optimize.milp`, run the program, and pretty print the final board and score. No image processing needed. I only tested it on today's puzzle.
Yes, but the math notation isn't cut-and-pastable or sharable --- I did it on an internal work account. At first glance it looks reasonable to me (I have a PhD in Operations Research, but it's been awhile): it defines binary reachability variables, wall variables, and flow variables (on the edges between nodes) to avoid the problem showing up in the comments involving enclosing an area without the horse. (I didn't have to prompt it for that, it did it on its own.) Each reachable node (except the horse) consumes exactly one unit of flow, flow can only flow out of a node if that node is reachable, and if a node is reachable, arbitrary amount of flow can flow out (implemented via a "large enough" constant).
OK, thanks. That answers the main question I had, which is if thinks you need to add some set of edge variables in order to enforce a single connected component. (Apparently yes.) I feel like just building a spanning tree would be more bulletproof, but this might well be valid too. Maybe you could test it one some of the adversarial examples people have suggested?
"I think you should be able to mostly solve the problem using System 1 but need to engage System 2 enough to keep things interesting."
That's a very good corollary to "A Game is a Series of Interesting Choices"
Put together, one gets:
"A FUN game is a series of interesting choices that initially mainly engage System 1 (Fast/Intuitive) but then make increasing demands on System 2 (Slow/Deliberative/Logical/Empirical)"
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.
Good evening! I found your blog by way of a link from Adam Mastroianni's newsletter.
I happen to have spent some time figuring out how to encode various puzzles into Z3 code. If you've heard of Hitori, it has a requirement that all cells in the final solution (not masked off) must be in a single connected component. (Go to www.puzzle-hitori.com and read the rules and noodle around, then come back.)
This is from memory, as I don't want to dig out my toy laptop and reread my now-old Python code...
I picked a cell to be the starting seed (more on that later). I assign a BFS distance metric to each cell that's not masked off, and assert that:
- the starting cell's distance is 0, and
- all non-starting distances are 1 + min(distance[n] for n in neighbors if not masked[n])
The real trick turned out to be picking the seed. Using the puzzle's rules I was able to ensure that either:
- the upper left corner (WLOG) was unmasked, and could be used as the seed, or
- if the corner was masked, its neighbor to the east (WLOG) was unmasked and could be used as the seed
From there it's basically a flood fill through all of the neighbors in turn to the rest of the connected region.
If you have a disconnected component, it won't have a path of consecutive distance numbers back to the seed, so there would always be one cell in the island that doesn't have any neighbor with distance one less than its own.
This proved to be tractable for the sizes of puzzles that I've been tinkering with, on the order of dozens of tiles per dimension, but naturally I can't vouch for it working well when you get to hundreds or thousands or millions.
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 would 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 tried (basically) this same extra set of variables and constraints, but it still seems to allow separate connected components. The problem is that you can have a whole region of C==1 with no actual horse. I'm starting to suspect that you might need something like a set of variables that build a spanning tree over the entire enclosed area. Then you can enforce that the tree can only start at the horse.
Yeah, having thought about this a bunch more and used Gemini to make an implementation (see other thread), you need some sort of flow-based formulation or similar (which will involve decision variables on edges, not merely nodes) to enforce that you're only scoring cells that are actually reachable from the horse. I believe any node-variable-only solution is vulnerable to enclosing multiple disconnected components.
Gemini 3 was easily able to (and in fact, one-shotted it without prompting about this issue) make a version that did the right thing and solves these nice examples.
hey there, I managed to add cherries and apples! (note: i did use AI for this and I ditched the visual recognition code for text input but hey, it works!)
https://drive.google.com/drive/folders/1PsyUiSEP5LoyGcAeYC2-N2ij3LJdig2E?usp=sharing
Wonder whether changing E[i,j] ≥ (1-W[i,j]) E[i_n, j_n] (as in your post) to E[i,j] ≥ E[i_n, j_n]-W[i,j] (as in your code) is always ok
Sure, the inequality will stay true, but why won't it introduce new spurios solutions (it seems that dropping W[i,j] instead of E[i_n, j_n] will do so, as we'd get E[i,j] ≥ E[i_n, j_n]-E[i_n, j_n] = 0 )?
Very interesting! Though, I think the level on the 14th breaks the solver. I figured out how to directly extract the daily from the API and parse it directly into the solver. It found a solution with a score of 110; meanwhile, the true optimal is 112. I was considering a brute-force approach, but that seems like it might be... inconvenient, to say the least. Do you think a graph-based approach could optimize this better?
Woah, that's surprising. I think the solver could give a solution that's "too good" (because it has two connected areas) but I don't see how it could give a suboptimal one. You're sure there's no error with the map?
(Also, any chance you could show your way of getting the daily?)
The "Zip" game of LinkedIn Games is a (simplified) Hamiltonian path game! (Also, yes, LinkedIn has daily puzzle games and I have an unspeakably long streak on them)
Can confirm, is fun: https://www.linkedin.com/games/zip
Regarding turning optimisation problems into games, the resolution of my R&D on that (especially regarding the NP ones) is that they're inherently difficult to make good because the score difference between the obvious solution and the optimal solution is usually pretty small, so it's hard to make players care.
Small score differences would matter in a competitive game I guess, but many don't enjoy those including me, so I didn't continue.
Also, you'll only be able to tell players whether they've found the optimal solution either as a result of of the fact that a machine found it or because another player found it before them, acknowledging either of these things is demoralising.
Various possible mitigations though:
I guess you could maybe address both of those things by (as usual) immersing the player in a natural-seeming environment where finding optimal solutions is necessary to progress, I'm imagining for instance a basin that tends to drain into groundwater at a particular rate, so you can only overflow into the canal if you can make a pump with a very specific minimum efficiency. I wouldn't want to put fluid dynamics in a game but that illustrates the design principle. Basins and overflows.
Another situation where small optimizations count is one where many people are using the optimised design. Massively multiplayer collaborations do feel pretty good. Reframe the competitive "someone else has optimised this further than you so you're useless" to "someone else has optimised this further than you and you get to benefit from that, and also you can go and optimise something else instead". Though the "go and optimise something else instead" does rely on the absence of exactly the kind of botting this post is about :p
It was easy enough to grab the map out of __LEVEL__.map in console. Gemini 3 Pro one-shotted all of "figure out the rules from the javascript, parse the map, write a program that calls `scipy.optimize.milp`, run the program, and pretty print the final board and score. No image processing needed. I only tested it on today's puzzle.
Can you translate the model it built into math? (Or ask it to do that itself?)
Yes, but the math notation isn't cut-and-pastable or sharable --- I did it on an internal work account. At first glance it looks reasonable to me (I have a PhD in Operations Research, but it's been awhile): it defines binary reachability variables, wall variables, and flow variables (on the edges between nodes) to avoid the problem showing up in the comments involving enclosing an area without the horse. (I didn't have to prompt it for that, it did it on its own.) Each reachable node (except the horse) consumes exactly one unit of flow, flow can only flow out of a node if that node is reachable, and if a node is reachable, arbitrary amount of flow can flow out (implemented via a "large enough" constant).
OK, thanks. That answers the main question I had, which is if thinks you need to add some set of edge variables in order to enforce a single connected component. (Apparently yes.) I feel like just building a spanning tree would be more bulletproof, but this might well be valid too. Maybe you could test it one some of the adversarial examples people have suggested?
I think its necessary because reachability cant be expressed in first order logic, only <n-step-reachability.
Done. It scores 8 on https://enclose.horse/play/ZxxGGo and 3 on https://enclose.horse/play/XHZO8P, in both cases enclosing only the area that includes the horse.
Nice, thanks!
Also REALLY don't play Satisfactory, which is 3D First Person Factorio with progression towards building up the supply chain for jet packs and tanks.
"I think you should be able to mostly solve the problem using System 1 but need to engage System 2 enough to keep things interesting."
That's a very good corollary to "A Game is a Series of Interesting Choices"
Put together, one gets:
"A FUN game is a series of interesting choices that initially mainly engage System 1 (Fast/Intuitive) but then make increasing demands on System 2 (Slow/Deliberative/Logical/Empirical)"
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.
Update: Almost a day later, I'm still thinking about the easiest way to enforce a single connected component...
Good evening! I found your blog by way of a link from Adam Mastroianni's newsletter.
I happen to have spent some time figuring out how to encode various puzzles into Z3 code. If you've heard of Hitori, it has a requirement that all cells in the final solution (not masked off) must be in a single connected component. (Go to www.puzzle-hitori.com and read the rules and noodle around, then come back.)
This is from memory, as I don't want to dig out my toy laptop and reread my now-old Python code...
I picked a cell to be the starting seed (more on that later). I assign a BFS distance metric to each cell that's not masked off, and assert that:
- the starting cell's distance is 0, and
- all non-starting distances are 1 + min(distance[n] for n in neighbors if not masked[n])
The real trick turned out to be picking the seed. Using the puzzle's rules I was able to ensure that either:
- the upper left corner (WLOG) was unmasked, and could be used as the seed, or
- if the corner was masked, its neighbor to the east (WLOG) was unmasked and could be used as the seed
From there it's basically a flood fill through all of the neighbors in turn to the rest of the connected region.
If you have a disconnected component, it won't have a path of consecutive distance numbers back to the seed, so there would always be one cell in the island that doesn't have any neighbor with distance one less than its own.
This proved to be tractable for the sizes of puzzles that I've been tinkering with, on the order of dozens of tiles per dimension, but naturally I can't vouch for it working well when you get to hundreds or thousands or millions.
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 would 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.
I tried (basically) this same extra set of variables and constraints, but it still seems to allow separate connected components. The problem is that you can have a whole region of C==1 with no actual horse. I'm starting to suspect that you might need something like a set of variables that build a spanning tree over the entire enclosed area. Then you can enforce that the tree can only start at the horse.
Yeah, having thought about this a bunch more and used Gemini to make an implementation (see other thread), you need some sort of flow-based formulation or similar (which will involve decision variables on edges, not merely nodes) to enforce that you're only scoring cells that are actually reachable from the horse. I believe any node-variable-only solution is vulnerable to enclosing multiple disconnected components.
Gemini 3 was easily able to (and in fact, one-shotted it without prompting about this issue) make a version that did the right thing and solves these nice examples.