5 ms·

I am curious on how you would algorithmically find the optimal solution for this kind of problem for much bigger grids. I wanted to do some seed finding in Fact

I am curious on how you would algorithmically find the optimal solution for this kind of problem for much bigger grids. I wanted to do some seed finding in Factorio for the same exact problem using the generated map images, but never found a good solution that was fast enough.

deleted 8mo ago
[deleted]
Zobody 8mo ago
Constraint programming seems to be a fitting approach. Input would be number of walls, and the location of lakes. The decision variables would be the positions of walls. In order to encode the horse being enclosed, additional variables for whether horse can reach a given square can be given. Finally, constraints for reachability and that edges cannot be reached should ensure correctness.
- Macuyiko 8mo ago
  Yes. CP SAT crunches through it in no time, but of course larger grids would quickly make it take much longer. See https://gist.github.com/Macuyiko/86299dc120478fdff529cab386ffd14a https://gist.github.com/Macuyiko/86299dc120478fdff529cab386f...
  - ooopdddddd 8mo ago
    I don't believe this works in general. If you have a set of tiles that connect to neither the horse nor to an exit, they can still keep each other reachable in this formulation.
    - Scaevolus 8mo ago
      Yes, this is the major challenge with solving them with SAT. You can make your solver check and reject these horseless pockets (incrementally rejecting solutions with new clauses), which might be the easiest method, since you might need iteration for maximizing anyways (bare SAT doesn't do "maximize"). To correctly track the flood-fill flow from the horse, you generally need a constraint like reachable(x,y,t) = reachable(nx,ny,t-1) ^ walkable(x,y), and reachable(x,y,0)=is_horse_cell, which adds N^2 additional variables to each cell. You can more precisely track flows and do maximization with ILP, but that often loses conflict-driven clause learning advantages.
    - Macuyiko 8mo ago
      Good point. I don't think the puzzles do this and if they would, I would run a pre-solve pass over the puzzle first to flood fill such horseless pockets up with water, no?
      - ooopdddddd 8mo ago
        It's not quite that easy. For the simplest example, look at https://enclose.horse/play/dlctud https://enclose.horse/play/dlctud, where the naive solution will waste two walls to fence in the large area. Obviously, you can construct puzzles that have lots of these "bait" areas. Like the other comment suggested, running a loop where you keep adding constraints that eliminate invalid solutions will probably work for any puzzle that a human would want to solve.
        Macuyiko 8mo ago
        Oh I see what you mean now, indeed: Score: 7 ~~~~~~ ~····~ ~·~~·~ .#..#. ...... ..#... .#H#.. ..#... However, I think that you do not need 'time' based variables in the form of reachable(x,y,t) = reachable(nx,ny,t-1) Enforcing connectivity through single-commodity flows is IMO better to enforce flood fill (also introduces additional variables but is typically easier to solve with CP heuristics): Score: 2 ~~~~~~ ~....~ ~.~~.~ ...... ...... ..##.. .#H·#. ..##.. Cool puzzle!
- dyigitpolat 8mo ago
  MILP solver: https://github.com/dyigitpolat/enclose-horse-solver/blob/main/src/solver/milpWorker.js https://github.com/dyigitpolat/enclose-horse-solver/blob/mai... try at: https://dyigitpolat.github.io/enclose-horse-solver/ https://dyigitpolat.github.io/enclose-horse-solver/
  - dyigitpolat 8mo ago
    it was very easy to support the portal mechanism when the entire problem is mapped as a network flow optimization. i could just simply add the portal coordinates together with the neighbors.
Scaevolus 8mo ago
The site uses Answer Set Programming with the Clingo engine to compute the optimal solutions for smaller grids. Maximizing grids like this is probably NP-hard. Note that traditional SAT and SMT solvers are quite inefficient at computing flood-fills. The ASP specifications it uses to compute optimal solutions are surprisingly short and readable, and look like: #const budget=11. horse(4,4). cell(0,0). boundary(0,0). cell(0,1). boundary(0,1). % ...truncated for brevity... cell(3,1). water(3,1). % ... % Adjacent cells (4-way connectivity) adj(R,C, R+1,C) :- cell(R,C), cell(R+1,C). adj(R,C, R-1,C) :- cell(R,C), cell(R-1,C). adj(R,C, R,C+1) :- cell(R,C), cell(R,C+1). adj(R,C, R,C-1) :- cell(R,C), cell(R,C-1). % Walkable = not water walkable(R,C) :- cell(R,C), not water(R,C). % Choice: place wall on any walkable cell except horse and cherries { wall(R,C) } :- walkable(R,C), not horse(R,C), not cherry(R,C). % Budget constraint (native counting - no bit-blasting!) :- #count { R,C : wall(R,C) } > budget. % Reachability from horse (z = enclosed/reachable cells) z(R,C) :- horse(R,C). z(R2,C2) :- z(R1,C1), adj(R1,C1, R2,C2), walkable(R2,C2), not wall( R2,C2). % Horse cannot reach boundary (would escape) :- z(R,C), boundary(R,C). % Maximize enclosed area (cherries worth +3 bonus = 4 total) #maximize { 4,R,C : z(R,C), cherry(R,C) ; 1,R,C : z(R,C), not cherry( R,C) }. % Only output wall positions #show wall/2.
- stabbles 8mo ago
  Nice, you don't see clingo mentioned often. We use it in the Spack package manager for resolving dependencies [1] [1] https://github.com/spack/spack/blob/develop/lib/spack/spack/solver/concretize.lp https://github.com/spack/spack/blob/develop/lib/spack/spack/...
- freakynit 8mo ago
  Im over 35 years of age. I have 15+ years of programming experience. And I generally consider myself as someone who has good breadth of tech in general. Yet, this is the first time in my life I've heard of ASP. And gosh. I was completely blown away by this as I read more about it and went through some examples (https://github.com/domoritz/clingo-wasm/blob/main/examples/examples/traveling-salesperson.lp https://github.com/domoritz/clingo-wasm/blob/main/examples/e...) Therefore, like a good little llm bitch that I have become recently, I straight away went to chatgpt/sonnet/gemini and asked them to compile me a list of more such "whatever this is known as". And holy cow!! This is a whole new world. My ask to HN community: any good book recommendations related to "such stuff"? Not those research kinds as I don't have enough brain cells for it. But, a little easier and practical ones? Thanks..
johanvts 8mo ago
I think it's NP hard, maybe from Sparsest Cut. But you could probably find the min-cut and then iterate by adding capacity on edges in the min cut until you find a cut of the right size. (if the desired cut-size is close to the min cut size at least).
- emil-lp 8mo ago
  It's NP-hard from Minimum s–t Cut with at least k Vertices. That's the edge version, but since the grid graph is 4-regular(-ish), the problem is trivially convertible to the vertex version. Edit: apex-4-regular
  - sltkr 8mo ago
    That conclusion may be too hasty. If min cut with k vertices is NP-hard on arbitrary graphs, that doesn't automatically mean that that applies to a 2D grid too. Is NP hardness proven for just planar graphs? Those are closer to the 2D grid, but still slightly more general. All I could find was a reduction to densest k subgraphs, but Wikipedia tells me that whether that problem is NP hard for planar graphs is an open question. To be clear, I would be very surprised if the problem turns out to be _not_ NP hard, but there is no trivial equivalence to min cut in general graphs to show that it is.
    - emil-lp 8mo ago
      I agree, that is a good point. Although it is (induced) subgraphs of 2D grids, which gets you a bit closer to the planar case (albeit with bounded degree). It might be polytime on planar graphs, but that would be surprising.
  - sltkr 8mo ago
    Also I don't think the equivalence between edge/vertex versions is trivial at all (though maybe we just have different standards of triviality). For example, in a grid like this: ..#### .....# #.#..# #...H# ###### A single wall placed (i.e. vertex removed) can block two edges, and it's not obvious what graph transformation can turn that into a single edge.
deleted 8mo ago
[deleted]
qwertyforce 8mo ago
I think there should be some graph algorithm for this, to find a bottleneck in a graph
sunrunner 8mo ago
> algorithmically find the optimal solution for this kind of problem for much bigger grids. Great, now I've been double nerd-sniped - once for the thing itself and another for 'What would an optimiser for this look like? Graph cuts? SAT/SMT? [AC]SP?'
- qsort 8mo ago
  I'd bet it's NP-hard. The standard reduction to a flow problem only tells you if a cut exists (by min-cut max-flow duality), but here we want the cut of size at most N that maximizes enclosed area. The Leetcode version of this is "find articulation points", which is just a DFS, but it's less general than what is presented here.
emil-lp 8mo ago
There's probably an FPT algorithm using important separators (4^k).
emil-lp 8mo ago
Someone asked about this very problem here: https://cs.stackexchange.com/questions/176005/how-to-remove-vertices-from-a-graph-to-leave-behind-the-largest-connected-compon https://cs.stackexchange.com/questions/176005/how-to-remove-...

deleted 8mo ago

[deleted]

Zobody 8mo ago

Constraint programming seems to be a fitting approach. Input would be number of walls, and the location of lakes. The decision variables would be the positions of walls. In order to encode the horse being enclosed, additional variables for whether horse can reach a given square can be given. Finally, constraints for reachability and that edges cannot be reached should ensure correctness.

Macuyiko 8mo ago
Yes. CP SAT crunches through it in no time, but of course larger grids would quickly make it take much longer. See https://gist.github.com/Macuyiko/86299dc120478fdff529cab386ffd14a https://gist.github.com/Macuyiko/86299dc120478fdff529cab386f...
- ooopdddddd 8mo ago
  I don't believe this works in general. If you have a set of tiles that connect to neither the horse nor to an exit, they can still keep each other reachable in this formulation.
  - Scaevolus 8mo ago
    Yes, this is the major challenge with solving them with SAT. You can make your solver check and reject these horseless pockets (incrementally rejecting solutions with new clauses), which might be the easiest method, since you might need iteration for maximizing anyways (bare SAT doesn't do "maximize"). To correctly track the flood-fill flow from the horse, you generally need a constraint like reachable(x,y,t) = reachable(nx,ny,t-1) ^ walkable(x,y), and reachable(x,y,0)=is_horse_cell, which adds N^2 additional variables to each cell. You can more precisely track flows and do maximization with ILP, but that often loses conflict-driven clause learning advantages.
  - Macuyiko 8mo ago
    Good point. I don't think the puzzles do this and if they would, I would run a pre-solve pass over the puzzle first to flood fill such horseless pockets up with water, no?
    - ooopdddddd 8mo ago
      It's not quite that easy. For the simplest example, look at https://enclose.horse/play/dlctud https://enclose.horse/play/dlctud, where the naive solution will waste two walls to fence in the large area. Obviously, you can construct puzzles that have lots of these "bait" areas. Like the other comment suggested, running a loop where you keep adding constraints that eliminate invalid solutions will probably work for any puzzle that a human would want to solve.
      - Macuyiko 8mo ago
        Oh I see what you mean now, indeed: Score: 7 ~~~~~~ ~····~ ~·~~·~ .#..#. ...... ..#... .#H#.. ..#... However, I think that you do not need 'time' based variables in the form of reachable(x,y,t) = reachable(nx,ny,t-1) Enforcing connectivity through single-commodity flows is IMO better to enforce flood fill (also introduces additional variables but is typically easier to solve with CP heuristics): Score: 2 ~~~~~~ ~....~ ~.~~.~ ...... ...... ..##.. .#H·#. ..##.. Cool puzzle!
dyigitpolat 8mo ago
MILP solver: https://github.com/dyigitpolat/enclose-horse-solver/blob/main/src/solver/milpWorker.js https://github.com/dyigitpolat/enclose-horse-solver/blob/mai... try at: https://dyigitpolat.github.io/enclose-horse-solver/ https://dyigitpolat.github.io/enclose-horse-solver/
- dyigitpolat 8mo ago
  it was very easy to support the portal mechanism when the entire problem is mapped as a network flow optimization. i could just simply add the portal coordinates together with the neighbors.

Scaevolus 8mo ago

The site uses Answer Set Programming with the Clingo engine to compute the optimal solutions for smaller grids. Maximizing grids like this is probably NP-hard. Note that traditional SAT and SMT solvers are quite inefficient at computing flood-fills. The ASP specifications it uses to compute optimal solutions are surprisingly short and readable, and look like: #const budget=11. horse(4,4). cell(0,0). boundary(0,0). cell(0,1). boundary(0,1). % ...truncated for brevity... cell(3,1). water(3,1). % ... % Adjacent cells (4-way connectivity) adj(R,C, R+1,C) :- cell(R,C), cell(R+1,C). adj(R,C, R-1,C) :- cell(R,C), cell(R-1,C). adj(R,C, R,C+1) :- cell(R,C), cell(R,C+1). adj(R,C, R,C-1) :- cell(R,C), cell(R,C-1). % Walkable = not water walkable(R,C) :- cell(R,C), not water(R,C). % Choice: place wall on any walkable cell except horse and cherries { wall(R,C) } :- walkable(R,C), not horse(R,C), not cherry(R,C). % Budget constraint (native counting - no bit-blasting!) :- #count { R,C : wall(R,C) } > budget. % Reachability from horse (z = enclosed/reachable cells) z(R,C) :- horse(R,C). z(R2,C2) :- z(R1,C1), adj(R1,C1, R2,C2), walkable(R2,C2), not wall( R2,C2). % Horse cannot reach boundary (would escape) :- z(R,C), boundary(R,C). % Maximize enclosed area (cherries worth +3 bonus = 4 total) #maximize { 4,R,C : z(R,C), cherry(R,C) ; 1,R,C : z(R,C), not cherry( R,C) }. % Only output wall positions #show wall/2.

stabbles 8mo ago
Nice, you don't see clingo mentioned often. We use it in the Spack package manager for resolving dependencies [1] [1] https://github.com/spack/spack/blob/develop/lib/spack/spack/solver/concretize.lp https://github.com/spack/spack/blob/develop/lib/spack/spack/...
freakynit 8mo ago
Im over 35 years of age. I have 15+ years of programming experience. And I generally consider myself as someone who has good breadth of tech in general. Yet, this is the first time in my life I've heard of ASP. And gosh. I was completely blown away by this as I read more about it and went through some examples (https://github.com/domoritz/clingo-wasm/blob/main/examples/examples/traveling-salesperson.lp https://github.com/domoritz/clingo-wasm/blob/main/examples/e...) Therefore, like a good little llm bitch that I have become recently, I straight away went to chatgpt/sonnet/gemini and asked them to compile me a list of more such "whatever this is known as". And holy cow!! This is a whole new world. My ask to HN community: any good book recommendations related to "such stuff"? Not those research kinds as I don't have enough brain cells for it. But, a little easier and practical ones? Thanks..

johanvts 8mo ago

I think it's NP hard, maybe from Sparsest Cut. But you could probably find the min-cut and then iterate by adding capacity on edges in the min cut until you find a cut of the right size. (if the desired cut-size is close to the min cut size at least).

emil-lp 8mo ago
It's NP-hard from Minimum s–t Cut with at least k Vertices. That's the edge version, but since the grid graph is 4-regular(-ish), the problem is trivially convertible to the vertex version. Edit: apex-4-regular
- sltkr 8mo ago
  That conclusion may be too hasty. If min cut with k vertices is NP-hard on arbitrary graphs, that doesn't automatically mean that that applies to a 2D grid too. Is NP hardness proven for just planar graphs? Those are closer to the 2D grid, but still slightly more general. All I could find was a reduction to densest k subgraphs, but Wikipedia tells me that whether that problem is NP hard for planar graphs is an open question. To be clear, I would be very surprised if the problem turns out to be _not_ NP hard, but there is no trivial equivalence to min cut in general graphs to show that it is.
  - emil-lp 8mo ago
    I agree, that is a good point. Although it is (induced) subgraphs of 2D grids, which gets you a bit closer to the planar case (albeit with bounded degree). It might be polytime on planar graphs, but that would be surprising.
- sltkr 8mo ago
  Also I don't think the equivalence between edge/vertex versions is trivial at all (though maybe we just have different standards of triviality). For example, in a grid like this: ..#### .....# #.#..# #...H# ###### A single wall placed (i.e. vertex removed) can block two edges, and it's not obvious what graph transformation can turn that into a single edge.

deleted 8mo ago

[deleted]

qwertyforce 8mo ago

I think there should be some graph algorithm for this, to find a bottleneck in a graph

sunrunner 8mo ago

> algorithmically find the optimal solution for this kind of problem for much bigger grids. Great, now I've been double nerd-sniped - once for the thing itself and another for 'What would an optimiser for this look like? Graph cuts? SAT/SMT? [AC]SP?'

qsort 8mo ago
I'd bet it's NP-hard. The standard reduction to a flow problem only tells you if a cut exists (by min-cut max-flow duality), but here we want the cut of size at most N that maximizes enclosed area. The Leetcode version of this is "find articulation points", which is just a DFS, but it's less general than what is presented here.

emil-lp 8mo ago

There's probably an FPT algorithm using important separators (4^k).

emil-lp 8mo ago

Someone asked about this very problem here: https://cs.stackexchange.com/questions/176005/how-to-remove-vertices-from-a-graph-to-leave-behind-the-largest-connected-compon https://cs.stackexchange.com/questions/176005/how-to-remove-...