/* 

  Star battle and Star battle reloaded in Picat.

  From Adrian Groza "Modelling Puzzles in First Order Logic"
  """
  Puzzle 93. Star battle

  Each puzzle is divided into a fixed number of cages. Place stars in an n × n grid so
  that:
  1. Each cage, row, and column must contain the same number of stars (1 or 2 stars,
     depending on the puzzle variety).
  2. Stars may not reside in adjacent cells (not even diagonally).
     The 5 × 5 puzzle in Fig. 9.7 has one star in each cage. (taken from Kleber 2013)
  """

  The cage where the number indicates the cage id
    1 1 2 2 2
    3 3 2 2 2
    3 3 4 4 4
    4 4 4 5 5
    5 5 5 5 5

  Here is the unique solution:

   1 * 2 2 2
   3 3 2 * 2
   * 3 4 4 4
   4 4 * 5 5
   5 5 5 5 *


  """
  Puzzle 94. Star battle reloaded

  Enter exactly one star in each row, each column, and each area of the grid. Cells with
  stars must not touch each other orthogonally or diagonally. (taken from Kleber 2013).
  """

  puzzle = 94
  Cages:
  [1,1,2,2,2]
  [1,1,1,2,3]
  [4,1,1,2,3]
  [4,5,5,2,2]
  [5,5,5,5,5]

  Solution:
   1 1 2 * 2
   1 * 1 2 3
   4 1 1 2 *
   * 5 5 2 2
   5 5 * 5 5


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

*/

import cp.

main => go.

go =>
  member(Puzzle,[93,94,krazydad]),
  println(puzzle=Puzzle),
  puzzle(Puzzle,N,NumCages,Cages),

  println("Cages:"),
  foreach(Row in Cages)
    println(Row),
  end,
  nl,
  
  star_puzzle(N,NumCages,Cages,X,NumStars),
  
  println("Solution:"),
  foreach(I in 1..N)
    foreach(J in 1..N)
      if X[I,J] == 1 then
        printf("%2s","*")
      else
        printf("%2s", Cages[I,J].to_string),
      end
    end,
    nl
  end,
  nl,
  println(num_stars=NumStars),
  nl,
  fail,
  nl.


star_puzzle(N,NumCages,Cages,X,NumStars) :-
  X = new_array(N,N),
  X :: 0..1, % 1: star

  % The number of stars in each cage
  NumStars :: 1..2,

  % Ensure that there are NumStars in each cage.
  foreach(C in 1..NumCages)
    Cs = [X[I,J] : I in 1..N, J in 1..N, Cages[I,J] == C],
    sum(Cs) #= NumStars
  end,

  % Same number of stars in rows and columns
  foreach(I in 1..N)
    sum([X[I,J] : J in 1..N]) #= NumStars,
    sum([X[J,I] : J in 1..N]) #= NumStars
  end,

  % Not 2 stars in the neighbourhood (including diaginals)
  foreach(I in 1..N, J in 1..N)
    Ns = [X[I+A,J+B] : A in -1..1, B in -1..1, not (A == 0, B == 0),
                       I+A >= 1, I+A <= N, J+B >= 1, J+B <= N],
    X[I,J] #= 1 #=> sum(Ns) #= 0                   
                       
  end,

  Vars = X.vars ++ [NumStars],
  solve(Vars).



puzzle(93,N,NumCages,Cages) :-
  N = 5,
  NumCages = 5,
  % The Cage ids
  Cages = [[1,1,2,2,2],
           [3,3,2,2,2],
           [3,3,4,4,4],
           [4,4,4,5,5],
           [5,5,5,5,5]].


puzzle(94,N,NumCages,Cages) :-
  N = 5,
  NumCages = 5,
  % The Cage ids
  Cages = [[1,1,2,2,2],
           [1,1,1,2,3],
           [4,1,1,2,3],
           [4,5,5,2,2],
           [5,5,5,5,5]].

% 
% https://krazydad.com/starbattle/tutorial/
% 
puzzle(krazydad,N,NumCages,Cages) :-
  N = 8,
  NumCages = 8,
  % The Cage ids
  Cages = [[1,1,1,1,1,2,2,2],
           [1,1,1,1,2,2,2,2],    
           [1,1,1,2,2,3,3,3],
           [4,4,1,2,2,3,5,5],
           [4,4,1,1,3,3,3,3],
           [6,4,4,7,3,3,3,3],
           [6,4,4,4,8,8,8,3],
           [4,4,4,4,8,8,3,3]].