Advertisement
jordancurve

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!
text 1.99 KB | None | 0 0
  1. % Solution to Ostomachion puzzle (Riddler Classic, 2018-01-26)
  2. % https://twitter.com/jordancurve/status/957743754143784960
  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.  
  38. adj(1,(2;6)).
  39. adj(2,3).
  40. adj(3,7).
  41. adj(4,(5;8;9)).
  42. adj(5,(6;10)).
  43. adj(6,(7;11)).
  44. adj(7,12).
  45. adj(8,9).
  46. adj(9,(10;13;14)).
  47. adj(10,(11;13)).
  48. adj(11,12).
  49. adj(13,14).
  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.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement