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

[dyigitpolat]

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.

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

[ooopdddddd]

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.