[kanemcgrath]

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.

[Scaevolus]

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.

[freakynit]

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/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..

[stabbles]

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/...

[sunrunner]

> 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]

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.

[johanvts]

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]

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

[Zobody]

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.

[dyigitpolat]

MILP solver: https://github.com/dyigitpolat/enclose-horse-solver/blob/mai...

try at: https://dyigitpolat.github.io/enclose-horse-solver/

[Macuyiko]

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/86299dc120478fdff529cab386f...

[emil-lp]

Someone asked about this very problem here:

https://cs.stackexchange.com/questions/176005/how-to-remove-...

[qwertyforce]

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

[emil-lp]

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