% Solution to Ostomachion puzzle (Riddler Classic, 2018-01-26)
% https://twitter.com/jordancurve/status/957743754143784960
% https://fivethirtyeight.com/features/how-often-does-the-senate-vote-in-palindromes/

% Color in the regions of the Ostomachion square with four colors such that [no two adjacent regions share the same color and] each color shades an equal area. (That is, each color needs to shade 36 square units.)
% Regions are numbered as shown in https://imgur.com/a/vjaVs.

% Solution: Fix the colors of the three regions in the upper-left corner, then let the Clingo answer set solver color the rest of the regions. It finds 9 distinct solutions (https://twitter.com/jordancurve/status/957838324156305408).
% To see it find them, paste the contents of this file into https://potassco.org/clingo/run/, set the mode to "Enumerate all", and click Run.

% regionarea(R, N) :- the area of region R is N.

regionarea(1, 24).
regionarea(2, 3).
regionarea(3, 9).
regionarea(4, 12).
regionarea(5, 6).
regionarea(6, 12).
regionarea(7, 6). 
regionarea(8, 12).
regionarea(9, 12).
regionarea(10, 21).
regionarea(11, 6). 
regionarea(12, 12).
regionarea(13, 3). 
regionarea(14, 6). 

% region(R) :- R is a region.

region(1..14).

% color(C) :- C is a color.

color(1..4).

% adj(R, S) :- region R and region S are adjacent.

adj(1,(2;6)).
adj(2,3).
adj(3,7).
adj(4,(5;8;9)).
adj(5,(6;10)).
adj(6,(7;11)).
adj(7,12).
adj(8,9).
adj(9,(10;13;14)).
adj(10,(11;13)).
adj(11,12).
adj(13,14).

% WLOG, assign colors to region 4, 8, and 9.

% regioncolor(R, C) :- region R has color C.

regioncolor(4, 1).
regioncolor(8, 2).
regioncolor(9, 3).

% Pick a color for each other region.

1 { regioncolor(R, C) : color(C) } 1 :- region(R).

% No two adjacent regions can have the same color.

:- adj(R, S), regioncolor(R, C), regioncolor(S, C).

% No color's area can be more than 36.

:- 36 < #sum { X, R : regionarea(R, X), regioncolor(R, C) }, color(C).

#show regioncolor/2.