Integer programming easily encloses horse
SubscribeSign in
Integer programming easily encloses horse<br>Stop having fun without me<br>Jan 15, 2026
86
36
Share
enclose.horse is a game in which you enclose a horse. You start with a map like this with water, fields, and horse.
Then you enclose horse. You have a finite budget of walls. (For the above map, 13.) You need to place them so that the horse is enclosed in as large an area as possible. The horse cannot move diagonally and cannot move over water.<br>Here’s one (bad) solution:
This is a charming little game. But something about it disturbs me. It’s exploring a mathematical structure (good) but it’s a disorganized mathematical structure that stubbornly resists understanding. There are—I think—no broad theorems or abstractions that might allow you to “derive” or “explain” the best solution for a given problem. If you want to know why the best solution is best, the honest answer is: Because it’s better than all of the other solutions.<br>I guess that what really bothers me is living in such a disordered universe. Did you know that this is the most compact known way to pack 11 squares together into a larger square?
Really makes you think about the mindset of whoever made the universe, am I right?<br>Few people seem quite as bothered by this aspect of reality as I am. So, since I can’t enjoy this kind of game, I thought I’d try to ruin it for everyone by showing that it’s extremely easy for machines.<br>Integer programming
Integer programming is, I think, one of humanity’s most unsung achievements. If you’re not familiar with it, don’t be confused by the word “programming”. It’s not like C++ or whatever. It’s a type of mathematical optimization problem. You have some list of variables, and you want to minimize a linear function of those variables under linear (technically affine) constraints.<br>For example, you might want to minimize<br>3×a + 5×bwith respect to a and b under the constraints that<br>b ≥ 2,<br>3×a + b ≥ 10.If the variables are continuous, then this is just linear programming, which is theoretically pretty fast and in practice extremely fast.<br>However, if the variables are integers, then this is integer programming. Theoretically, this is NP-hard, meaning that it’s probably impossible to solve all integer programming problems in any reasonable amount of time.<br>But NP-hardness is not nearly as big a deal as people make it out to be. People have put a lot of effort into integer programming, because it’s useful for laying out chips, doing logistics and routing, managing supply chains, creating financial products and lots of other real-world problems that involve constraints and discrete choices.<br>After decades of effort, we have solvers that are extremely good. For most real-world problems of moderate size, these solvers can not just find the optimal solution, but also provide a proof that that it’s actually optimal.<br>OK, enough ranting. Let’s enclose some horse.<br>Maps
To start, I needed a representation of the map. I looked at the source code for the game page, but couldn’t easily figure out how to extract the map. So I started typing it into a spreadsheet:
I knew this would be slow and tedious, but the empirical slowness and tedium exceeded my expectations. After getting as far as shown above, I couldn’t take it anymore and decided to use image processing instead. I took a screenshot and then wrote a script that breaks up the image into tiles and then counts how many pixels in each chunk match the background color for water and for field. Then I manually added the horse. This gave me an array with 0 for water, 1 for field, and 2 for horse.
Enclosing the horse
Now, how to enclose the horse? How to formalize this as an instance of integer programming?<br>Thinking about this for a few minutes, I had the following thoughts:<br>Instead of thinking about if a given tile is enclosed, it’s easier to think about if it’s possible to escape from a given tile. Minimizing the number of tiles from which it is possible to escape is equivalent to maximizing the size of the horse’s enclosure.
So let’s have two binary variables for the solver to set each tile: (1) Is there a wall? (2) Is it possible to escape? The objective is to minimize the number of tiles from which you can escape. Say that W[i,j] indicates if there is a wall at row i and column j while E[i,j] indicates if it’s possible to escape from that tile.
Now all we need to do is add enough constraints to guarantee that the solution is valid.
There’s a maximum number of walls. So let’s constrain that the sum of W[i,j] over all i and j doesn’t exceed that.
It must not be possible for the horse to escape. So let’s constrain that E[i,j]=0 for that tile.
You can’t put a wall on top of the horse. So let’s constrain that W[i,j]=0 for that tile.
For water tiles, it’s never possible to escape. So let’s constrain that E[i,j]=0 for those tiles.
For field tiles on to boundary, it’s possible to escape unless there is a wall on the...