/* 

  Colouring Dracula's land in red in Picat.

  From Adrian Groza: "Modelling Puzzles in First Order Logic" and
  https://www.researchgate.net/publication/374588335_Measuring_reasoning_capabilities_of_ChatGPT
  """
  Puzzle 29. Colouring Dracula’s land in red
  The map of Romania contains the following regions: Transylvania, Maramures, Bucov-
  ina, Moldova, Muntenia, Oltenia, Banat, Crisana and Dobrogea. Transylvania is connected
  with all other regions excepting Dobrogea. Dobrogea is connected only with Moldova and
  Munteania. The connection relation is symmetric. Can the following map of Romania be
  coloured with only 3 distinct colours? What about 4 colours? Find a solution in which
  Transylvania, the birth place of Dracula, is coloured red. How many solutions exist?
  """

  3 colors does not suffice. There must be 4 colors. 

  Here is one solution (of 252 different solutions).
  colors = [transylvania = red,maramures = blue,bucovina = green,moldova = blue,muntenia = green,
            oltenia = blue,banat = green,crisana = yellow,dobrogea = red]



  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.

main => go.

go =>
  Regions = findall([R1,R2],n(R1,R2)).flatten.remove_dups,
  RegionMap = new_map([R=I : {R,I} in zip(Regions,1..Regions.len)]),
  Neibs = findall([C1,C2],n(C1,C2)),

  % Does 3 colors be enough, or must there be 4 colors?
  member(MaxColor,3..4),
  println(maxColor=MaxColor),

  color_map(Regions,RegionMap,Neibs,MaxColor, Colors),
  println(colors=[R=C : {R,C} in zip(Regions,Colors)]), % Print a solution
  
  All = findall(Colors2,color_map(Regions,RegionMap,Neibs,MaxColor,Colors2)),
  println(num_solutions=All.len),
  
  % Print all solutions
  % foreach(A in All)
  %   println([R=C : {R,C} in zip(Regions,A)])
  % end,
  nl.

colors([red,blue,green,yellow]).

color_map(Regions,RegionMap,Neibs,MaxColor, Colors) =>
  N = Regions.len,
  colors(Cs),
  Colors = new_list(N),
  foreach(R in 1..N)
    member(Colors[R],Cs[1..MaxColor])    
  end,
  Colors[RegionMap.get(transylvania)] = red, % Transylvania is red 
  foreach([C1,C2] in Neibs)
    Colors[RegionMap.get(C1)] != Colors[RegionMap.get(C2)]
  end.

n(transylvania,crisana).
n(transylvania,maramures).
n(transylvania,bucovina).   
n(transylvania,moldova).
n(transylvania,muntenia).
n(transylvania,oltenia).
n(transylvania,banat).
n(crisana,maramures).
n(crisana,banat).
n(oltenia,banat).
n(oltenia,muntenia).
n(maramures,bucovina).
n(bucovina,moldova).
n(moldova,dobrogea).
n(moldova,muntenia). 
n(dobrogea,muntenia).