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.