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.

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.

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

Someone asked about this very problem here:

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

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

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

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