Set Puzzles are created with a deck of cards from the Set Game™. The object of the puzzle is to find sets of 3 cards in a rectangle of cards that have been dealt face up. 


There are 81 cards in a deck.
Each card contains a unique variation of the following four features: color, symbol, number and shading.

 there are three colors:
    red, green, purple

 there are three symbols:
    oval, squiggle, diamond

 there is a number of symbols on the card:
    one, two, three

 there are three shadings:
    solid, open, striped

Three cards form a set if each feature is either the same on each card, or is different on each card. For instance: all 3 cards are red, all 3 cards have a different symbol, all 3 cards have a different number of symbols, all 3 cards are striped.

There are two degrees of difficulty: basic and advanced. The basic mode deals 9 cards, that contain exactly 4 sets; the advanced mode deals 12 cards that contain exactly 6 sets.

When creating sets you may use the same card more than once.




Task
Write code that deals the cards (9 or 12, depending on selected mode) from a shuffled deck in which the total number of sets that could be found is 4 (or 6, respectively); and print the contents of the cards and the sets.

For instance:



DEALT 9 CARDS:

green, one, oval, striped
green, one, diamond, open
green, one, diamond, striped
green, one, diamond, solid
purple, one, diamond, open
purple, two, squiggle, open
purple, three, oval, open
red, three, oval, open
red, three, diamond, solid

CONTAINING 4 SETS:

green, one, oval, striped
purple, two, squiggle, open
red, three, diamond, solid


green, one, diamond, open
green, one, diamond, striped
green, one, diamond, solid


green, one, diamond, open
purple, two, squiggle, open
red, three, oval, open


purple, one, diamond, open
purple, two, squiggle, open
purple, three, oval, open


import util.
import cp.
 
%
% Solve the task in the description.
%
go ?=>
  sets(1,Sets,SetLen,NumSets),
  print_cards(Sets),
  set_puzzle(Sets,SetLen,NumSets,X),
  print_sol(Sets,X),
  nl,
  fail, % check for other solutions
  nl.
go => true.
 
%
% Generate and solve a random instance with NumCards cards,
% giving exactly NumSets sets.
%
go2 =>
  _ = random2(),
  NumCards = 9, NumSets = 4, SetLen = 3,
  generate_and_solve(NumCards,NumSets,SetLen),
  fail, % prove unicity
  nl.
 
go3 =>
  _ = random2(),
  NumCards = 12, NumSets = 6, SetLen = 3,
  generate_and_solve(NumCards,NumSets,SetLen),  
  fail, % prove unicity)
  nl.
 
%
% Solve a Set Puzzle.
%
set_puzzle(Cards,SetLen,NumWanted, X) =>
  Len = Cards.length,
  NumFeatures = Cards[1].length,
 
  X = new_list(NumWanted),
  foreach(I in 1..NumWanted)
    Y = new_array(SetLen), 
    foreach(J in 1..SetLen)
      member(Y[J], 1..Len)
    end,
    % unicity and symmetry breaking of Y
    increasing2(Y), 
    % ensure unicity of the selected cards in X
    if I > 1 then
      foreach(J in 1..I-1) X[J] @< Y  end
    end,
    foreach(F in 1..NumFeatures)
       Z = [Cards[Y[J],F] : J in 1..SetLen],
       (allequal(Z) ; alldiff(Z))
    end,
    X[I] = Y
  end.
 
% (Strictly) increasing
increasing2(List) => 
  foreach(I in 1..List.length-1)
    List[I] @< List[I+1]
  end.
 
% All elements must be equal
allequal(List) => 
  foreach(I in 1..List.length-1)
    List[I] = List[I+1]
  end.
 
% All elements must be different
alldiff(List) => 
  Len = List.length,
  foreach(I in 1..Len, J in 1..I-1)
    List[I] != List[J]
  end.
 
% Print a solution
print_sol(Sets,X) =>
  println("Solution:"),
  println(x=X),
  foreach(R in X)
    println([Sets[R[I]] : I in 1..3])
  end,
  nl.
 
% Print the cards
print_cards(Cards) =>
  println("Cards:"),
  foreach({Card,I} in zip(Cards,1..Cards.len))
     println([I,Card])
  end,  
  nl.
 
%
% Generate a problem instance with NumSets sets (a unique solution).
%
% Note: not all random combinations of cards give a unique solution so
%       it might generate a number of deals.
%
generate_instance(NumCards,NumSets,SetLen, Cards) =>
  println([numCards=NumCards,numWantedSets=NumSets,setLen=SetLen]),
  Found = false,
  % Check that this instance has a unique solution.
  while(Found = false) 
    if Cards = random_deal(NumCards), 
      count_all(set_puzzle(Cards,SetLen,NumSets,_X)) = 1
    then
      Found := true
    end
  end.
 
%
% Generate a random problem instance of N cards.
%
random_deal(N) = Deal.sort() =>
  all_combinations(Combinations),
  Deal = [], 
  foreach(_I in 1..N)
    Len = Combinations.len,
    Rand = random(1,Len),
    Comb = Combinations[Rand],
    Deal := Deal ++ [Comb],
    Combinations := delete_all(Combinations, Comb)
  end.
 
%
% Generate a random instance and solve it.
%
generate_and_solve(NumCards,NumSets,SetLen) => 
  generate_instance(NumCards,NumSets,SetLen, Cards),
  print_cards(Cards),  
  set_puzzle(Cards,SetLen,NumSets,X), % solve it
  print_sol(Cards,X),
  nl.
 
 
%
% All the 81 possible combinations (cards)
%
table
all_combinations(All) =>
   Colors = [red, green, purple],
   Symbols = [oval, squiggle, diamond],
   Numbers = [one, two, three],
   Shadings = [solid, open, striped],
   All = findall([Color,Symbol,Number,Shading],
                  (member(Color,Colors),
                   member(Symbol,Symbols),
                   member(Number,Numbers),
                   member(Shading,Shadings))).
 
%
% From the task description.
%
% Solution: [[1,6,9],[2,3,4],[2,6,8],[5,6,7]]
%
sets(1,Sets,SetLen,Wanted) => 
  Sets = 
  [
    [green, one, oval, striped], % 1 
    [green, one, diamond, open], % 2 
    [green, one, diamond, striped], % 3
    [green, one, diamond, solid], % 4
    [purple, one, diamond, open], % 5
    [purple, two, squiggle, open], % 6
    [purple, three, oval, open], % 7
    [red, three, oval, open], % 8
    [red, three, diamond, solid] % 9
 ],
 SetLen = 3,
 Wanted = 4.