Hacker News Reader

Comment by kanemcgrath | Hacker News Reader

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.

View on HN

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.

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

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

Has to be my favourite comment, haha!

The pre-machine-learning formulations of AI focused on symbolic reasoning through the dual problems of search and logic. Many problems can be reduced to enumerating legal steps, and SAT/SMT/ASP and related systems can churn through those in a highly optimized and genetic manner.

Thanks... noted a few keywords to expand on further:

1. Symbolic reasoning

2. SAT/SMT/ASP

3. pre-machine-learning formulations of AI

"Logic programming"[0] is what I've always heard this stuff called. I was introduced to it with Prolog.

"Declarative programming"[1] is kind of a superset of logic programming, which may or may not be the aspect that piques your interest.

"Constraint programming"[2] and "Constraint logic programming"[3] are also a perspective on it.

[0] https://en.wikipedia.org/wiki/Logic_programming

[1] https://en.wikipedia.org/wiki/Declarative_programming

[2] https://en.wikipedia.org/wiki/Constraint_programming

[3] https://en.wikipedia.org/wiki/Constraint_logic_programming

Thanks a lot. These are what I was hoping to know.

The more recent Lifschitz book is the easiest to learn from IMO:

- https://www.cs.utexas.edu/~vl/teaching/378/ASP.pdf

It starts with basics of using ASP and gives examples in clingo, not math.

The Potassco book is more comprehensive and will help you understand better what is going on:

- https://potassco.org/book/

Things I don't like include that it's more dense, doesn't use clingo examples (mostly math-style examples so you kind of have to translate them in your head), and while the proofs of how grounding works are interesting, the explanations are kind of short and don't always have the intuition I want.

I still think this is the authoritative reference.

The "how to build your own ASP system" paper is a good breakdown of how to integrate ASP into other projects:

- https://arxiv.org/abs/2008.06692

The Potassco folks are doing amazing work maintaining these tools. I also wish more people knew about them.

EDIT: I forgot to mention that specifically for games stuff like enclose.horse, look at Adam Smith's Applied ASP Course from UCSC:

- https://canvas.ucsc.edu/courses/1338

Forgot to mention that one... we use clingo in Spack for dependency solving and other applications frequently slip my mind.

Thank you.. Have noted these down.

> 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?'

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.

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

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

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.

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.

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.

You transform it into the directed case and then you turn each vertex into an arc.

There is a standard construction for going between vertex and edge cuts.

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.

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

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.

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.

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?

It's not quite that easy. For the simplest example, look at 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.

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!

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

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

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.

Someone asked about this very problem here:

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

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

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

Reply on news.ycombinator.com