{"id":2201,"date":"2018-01-28T13:07:11","date_gmt":"2018-01-28T19:07:11","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=2201"},"modified":"2018-10-29T01:37:18","modified_gmt":"2018-10-29T06:37:18","slug":"ostomachion-coloring","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/ostomachion-coloring\/","title":{"rendered":"Ostomachion coloring"},"content":{"rendered":"

The following problems appeared in The Riddler<\/a>. And it features an interesting combination of an ancient game with the four-color theorem.<\/p>\n

\nThe famous four-color theorem states, essentially, that you can color in the regions of any map using at most four colors in such a way that no neighboring regions share a color. A computer-based proof of the theorem was offered in 1976.<\/p>\n

Some 2,200 years earlier, the legendary Greek mathematician Archimedes described something called an Ostomachion<\/a> (shown below). It\u2019s a group of pieces, similar to tangrams<\/a>, that divides a 12-by-12 square into 14 regions. The object is to rearrange the pieces into interesting shapes, such as a Tyrannosaurus rex. It\u2019s often called the oldest known mathematical puzzle.<\/p>\n

Your challenge today: Color in the regions of the Ostomachion square with four colors such that each color shades an equal area. (That is, each color needs to shade 36 square units.) The coloring must also satisfy the constraint that no adjacent regions are the same color.<\/p>\n

Extra credit: How many solutions to this challenge are there?\n<\/p><\/blockquote>\n

\"Ostomachion\"<\/p>\n

Here are the details of how I solved the problem:
\n[Show Solution]<\/a><\/p>\n

\n

I’d like to start by pointing out that Hector Pefo also posted a nice solution<\/a> to this problem. There were also diagrams of solutions posted on Twitter, such as those from @DimEarly<\/a> and from @chattinthehatt<\/a>. The solution I’ll describe here is similar to Hector’s, but I’ll explain how to model it as an integer linear program and solve it that way. Of course both solutions produce the same answers (because they’re both correct!) but it’s nice to see different approaches. So without further ado…<\/p>\n

Integer linear program<\/h3>\n

Let’s suppose there are $N$ shapes and we’d like to use $C$ colors. Define:
\n\\[
\nx_{ij} = \\begin{cases}1&\\text{if shape }i\\text{ is colored using color }j\\\\0&\\text{otherwise}\\end{cases}
\n\\]The first constraint is that each shape must be assigned to exactly one color. We can express this algebraically as follows:
\n\\[
\n\\sum_{j=1}^C x_{ij} = 1\\qquad\\text{for }i=1,\\dots,N
\n\\]Now suppose that shape $j$ has area $a_j$. The constraint that each color has an equal share of the area means that the sum of the areas of the shapes of each color must be $A_\\text{tot}\/C$, where $A_\\text{tot}$ is the total area of the Ostomachion. Algebraically, we can write this as:
\n\\[
\n\\sum_{i=1}^N a_i x_{ij} = A_\\text{tot}\/C\\qquad\\text{for }j=1,\\dots,C
\n\\]Finally, we must deal with the edge constraints. We say that $(p,q)$ is an “edge” if shape $p$ shares an edge with shape $q$. Shapes that share an edge must be different colors. We can encode this algebraically as:
\n\\[
\nx_{pj} + x_{qj} \\le 1\\qquad\\text{for all edges }(p,q)\\text{ and for }j=1,\\dots,C
\n\\]And that’s it! We described the feasible set of solutions as the set of matrices $x \\in \\{0,1\\}^{N\\times C}$ that satisfy the three sets of linear constraints above. This sort of optimization model is a modified version of a Knapsack problem<\/a>. More generally, it’s an Integer Linear Program<\/a> (ILP). Such problems are known to be NP-hard<\/a>, which roughly means that in the worst-case, there is no efficient way to solve them short of trying all possible colorings. However, modern ILP solvers are quite sophisticated and can usually solve these types of problems very efficiently.<\/p>\n

Finding all solutions<\/h3>\n

When using an ILP model, most commercial solvers are designed to find a single solution. For this problem, we are interested in finding all<\/em> solutions. One way to get around the limitation is to use Barvinok’s algorithm<\/a>. One can also use variants of branch-and-cut<\/a>. Yet another way, which is not as systematic but much easier to explain and implement, is to use a randomized approach.<\/p>\n

Since all our variables are binary (0 or 1), the convex hull of the feasible set cannot contain any interior solution points. All solutions will be on the boundary. This means that any solution can be found by specifying the right objective function for the optimization. As stated, our optimization is just a feasibility problem and there is no objective specified. For this problem, we start by letting $r_{ij}$ be random numbers (we can draw them i.i.d.<\/a> from a standard normal distribution<\/a>, for example). Then, we simply add the objective function:
\n\\[
\n\\text{Minimize}\\qquad \\sum_{i=1}^N\\sum_{j=1}^C r_{ij} x_{ij}
\n\\]and solve the problem. If we do this repeatedly with different realizations of the $\\{r_{ij}\\}$, we will eventually enumerate all possible solutions of the optimization problem.<\/p>\n<\/div>\n

To jump straight to the solution (and pretty pictures!) see below.
\n[Show Solution]<\/a><\/p>\n

\n

Solutions<\/h3>\n

I implemented the ILP described earlier using Julia<\/a> and JuMP<\/a> and I solved everything using the Gurobi<\/a> solver. Although the randomized approach for finding all solutions works well, Gurobi has built-in functionality that allows one to directly find all solutions. In addition to doing this, I also included logic that removes duplicate solutions arising from different re-colorings of the same solution. e.g. if you take a solution and just swap red for green, I counted that as the same solution. Here are the solutions I found. I included the time it took Gurobi (on my laptop) to find all solutions for each case:<\/p>\n

For $C=3$ colors, there are $2$ distinct solutions (took 1.6 ms to solve)
\n\"\"<\/a><\/p>\n

For $C=4$ colors, there are $9$ distinct solutions (took 32 ms to solve):
\n\"\"<\/a><\/p>\n

For $C=6$ colors, there are $33$ distinct solutions (took 700 ms to solve):
\n\"\"<\/a><\/p>\n

Interestingly, using fewer colors makes it easier to satisfy the equal-area constraint, but it makes it harder to satisfy the edge constraints. Ultimately, there are only solutions for the cases above ($C=3,4,6$). There are no solutions for any other values of $C$.<\/p>\n

If you are interested in seeing my code, here is my IJulia notebook<\/a>.\n<\/div>\n","protected":false},"excerpt":{"rendered":"

The following problems appeared in The Riddler. And it features an interesting combination of an ancient game with the four-color theorem. The famous four-color theorem states, essentially, that you can color in the regions of any map using at most four colors in such a way that no neighboring regions share a color. A computer-based … Continue reading “Ostomachion coloring”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2209,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[30,27,31,26,2],"class_list":["post-2201","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-integer-programming","tag-linear-programming","tag-modeling","tag-optimization","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2201","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2201"}],"version-history":[{"count":15,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2201\/revisions"}],"predecessor-version":[{"id":2523,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2201\/revisions\/2523"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2209"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2201"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2201"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2201"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}