# Solution to Ostomachion puzzle (Riddler Classic, 2018-01-26)

Jan 28th, 2018
207
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. % Solution to Ostomachion puzzle (Riddler Classic, 2018-01-26)
3. % https://fivethirtyeight.com/features/how-often-does-the-senate-vote-in-palindromes/
4.
5. % 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.)
6. % Regions are numbered as shown in https://imgur.com/a/vjaVs.
7.
8. % 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).
9. % 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.
10.
11. % regionarea(R, N) :- the area of region R is N.
12.
13. regionarea(1, 24).
14. regionarea(2, 3).
15. regionarea(3, 9).
16. regionarea(4, 12).
17. regionarea(5, 6).
18. regionarea(6, 12).
19. regionarea(7, 6).
20. regionarea(8, 12).
21. regionarea(9, 12).
22. regionarea(10, 21).
23. regionarea(11, 6).
24. regionarea(12, 12).
25. regionarea(13, 3).
26. regionarea(14, 6).
27.
28. % region(R) :- R is a region.
29.
30. region(1..14).
31.
32. % color(C) :- C is a color.
33.
34. color(1..4).
35.
36. % adj(R, S) :- region R and region S are adjacent.
37.
50.
51. % WLOG, assign colors to region 4, 8, and 9.
52.
53. % regioncolor(R, C) :- region R has color C.
54.
55. regioncolor(4, 1).
56. regioncolor(8, 2).
57. regioncolor(9, 3).
58.
59. % Pick a color for each other region.
60.
61. 1 { regioncolor(R, C) : color(C) } 1 :- region(R).
62.
63. % No two adjacent regions can have the same color.
64.
65. :- adj(R, S), regioncolor(R, C), regioncolor(S, C).
66.
67. % No color's area can be more than 36.
68.
69. :- 36 < #sum { X, R : regionarea(R, X), regioncolor(R, C) }, color(C).
70.
71. #show regioncolor/2.