/* 

  Hitori in Picat.

  See https://en.wikipedia.org/wiki/Hitori
  """
  Hitori is played with a grid of squares or cells, with each cell initially containing a number. 
  The game is played by eliminating squares/numbers and this is done by blacking them out. 
  The objective is to transform the grid to a state wherein all three following rules are true:

  - no row or column can have more than one occurrence of any given number
  - black cells cannot be horizontally or vertically adjacent, although they can be diagonal 
    to one another.
  - the remaining numbered cells must be all connected to each other, horizontally or vertically.
  """

  Here's the instance from the Wikipedia page:
   4 8 1 6 3 2 5 7 
   3 6 7 2 1 6 5 4 
   2 3 4 8 2 8 6 1 
   4 1 6 5 7 7 3 5 
   7 2 3 1 8 5 1 2 
   3 5 6 7 3 1 8 4 
   6 4 2 3 5 4 7 8 
   8 7 1 4 2 3 5 6


  The (unique) solution:
   X 8 X 6 3 2 X 7 
   3 6 7 2 1 X 5 4 
   X 3 4 X 2 8 6 1 
   4 1 X 5 7 X 3 X 
   7 X 3 X 8 5 1 2 
   X 5 6 7 X 1 8 X 
   6 X 2 3 5 4 7 8 
   8 7 1 4 X 3 X 6 


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

*/

import util.
import sat. % must use sat fpr scc/1

main => go.

go ?=>
  nolog,
  % member(Puzzle,1..4),
  data(Puzzle,Data),
  println(puzzle=Puzzle),  
  time(hitori(Data,Y)),
  print_solution(Data,Y),
  nl,
  fail.
go => true.  

print_solution(Data,Y) =>  
  foreach(I in 1..Data.len)
    foreach(J in 1..Data[1].len)
      if Y[I,J] == 1 then
        printf("%3d",Data[I,J])
      else
        printf("  X")
      end
    end,
    nl
  end,
  nl.
  
hitori(Data,Y) =>
  Rows = Data.len,
  Cols = Data[1].len,

  Y = new_array(Rows,Cols),
  Y :: 0..1, % 0: blocked, 1: not blocked

  % * no row or column can have more than one occurrence of any given number
  foreach(I in 1..Rows)
    all_different_except_0([T : J in 1..Cols, T #= Data[I,J]*Y[I,J]])    
  end,
  foreach(J in 1..Cols)
    all_different_except_0([T : I in 1..Rows, T #= Data[I,J]*Y[I,J]])
  end,

  % * black cells cannot be horizontally or vertically adjacent, although
  %   they can be diagonal to one another.
  foreach(I in 1..Rows)
    foreach(J in 2..Cols-1)
      Y[I,J] #= 0 #=> (Y[I,J-1] #!= 0 #/\ Y[I,J+1] #!= 0)
    end
  end,

  foreach(J in 1..Cols)
    foreach(I in 2..Rows-1)
      Y[I,J] #= 0 #=> (Y[I-1,J] #!= 0 #/\ Y[I+1,J] #!= 0)
    end
  end,

  % the remaining numbered cells must be all connected to each other,
  % horizontally or vertically.  
  scc_grid(Y),

  solve(Y).

% From https://en.wikipedia.org/wiki/Hitori
data(1,Data) :-
  Data = chunks_of([
4,8,1,6,3,2,5,7,
3,6,7,2,1,6,5,4,
2,3,4,8,2,8,6,1,
4,1,6,5,7,7,3,5,
7,2,3,1,8,5,1,2,
3,5,6,7,3,1,8,4,
6,4,2,3,5,4,7,8,
8,7,1,4,2,3,5,6
  ], 8).


% https://www.brainbashers.com/showhitori.asp?date=1102&size=5&diff=2
% Solution:
% 5 2 3 1 X 
% 3 X 2 5 1 
% 4 3 X 2 X 
% 2 1 5 X 3 
% X 5 4 3 2 
%
data(2,Data) :-
  Data = chunks_of([
5,2,3,1,3,
3,5,2,5,1,
4,3,3,2,2,
2,1,5,3,3,
2,5,4,3,2
  ], 5).


%
% https://www.brainbashers.com/showhitori.asp?date=1102&size=9&diff=2
% Solution
% 2 X 1 X 6 4 8 X 9 
% 4 7 8 6 2 1 X 3 5 
% 5 X 9 X 3 X 6 X 2 
% X 1 6 3 X 9 2 5 4 
% 1 X 3 2 9 X 4 6 X 
% 9 5 X 1 4 3 X 8 6 
% 3 X 5 4 X 6 1 X 8 
% 8 6 7 X 1 2 X 4 3 
% X 9 X 8 5 7 3 2 X 
%
data(3,Data) :-
  Data = chunks_of([
2,9,1,2,6,4,8,4,9,
4,7,8,6,2,1,6,3,5,
5,6,9,3,3,2,6,5,2,
9,1,6,3,4,9,2,5,4,
1,1,3,2,9,3,4,6,4,
9,5,3,1,4,3,8,8,6,
3,5,5,4,1,6,1,6,8,
8,6,7,4,1,2,1,4,3,
2,9,9,8,5,7,3,2,5
  ],9).


% https://www.brainbashers.com/showhitori.asp?date=1102&size=8&diff=2
% data(3,Data) =>
%  Data = chunks_of([
%  ],9).

% https://github.com/SmilingWayne/PuzzleSolver/blob/main/Puzzles/Hitori.ipynb
% https://github.com/SmilingWayne/PuzzleSolver/blob/main/assets/data/hitori/problems/131_17x17.txt
data(4,Data) :-
  Data = chunks_of([
17,1,7,5,11,6,11,10,2,10,13,17,16,17,8,14,13,
14,15,10,10,3,13,9,7,15,12,12,11,17,16,15,15,4,
2,13,6,7,9,5,16,4,15,3,16,11,1,11,9,10,9,
8,9,13,3,1,11,4,12,16,5,10,16,9,11,14,2,7,
12,9,3,3,2,7,13,13,4,17,10,15,11,15,1,17,17,
10,9,8,3,14,12,12,15,3,13,10,7,12,5,4,17,9,
13,5,11,10,4,6,16,8,17,1,15,14,3,7,6,13,12,
13,7,2,17,16,10,3,6,4,14,9,5,12,15,4,4,9,
13,3,2,15,7,8,15,9,6,8,9,1,7,8,10,17,5,
3,15,2,1,7,17,10,5,12,6,9,13,14,2,13,11,16,
3,16,15,2,10,11,17,11,11,11,3,6,13,12,13,17,1,
7,11,16,2,9,1,2,2,10,4,2,14,6,3,13,5,17,
11,4,16,9,15,17,11,7,16,12,2,10,8,7,5,7,3,
5,14,4,3,17,3,12,11,13,8,6,17,10,9,2,7,15,
11,17,1,13,12,14,4,9,15,10,4,2,5,8,7,7,6,
11,2,1,14,12,15,6,17,7,16,4,4,5,10,15,8,13,
11,10,1,8,12,16,5,13,9,11,5,9,2,6,3,13,14
  ],17).


% https://github.com/SmilingWayne/PuzzleSolver/blob/main/assets/data/hitori/problems/37_17x17.txt
data(5,Data) :-
  Data = chunks_of([
16,2,9,5,17,1,4,6,13,17,3,12,11,8,11,15,10,
3,3,15,2,7,6,6,8,6,1,5,16,4,4,11,10,7,
4,15,5,1,12,13,3,6,8,11,3,9,13,10,11,14,7,
8,1,11,1,13,7,7,6,12,9,2,12,10,14,17,5,7,
6,15,10,10,10,2,6,13,6,8,17,16,1,11,7,3,12,
14,13,4,2,10,11,12,9,9,5,5,3,15,14,7,8,16,
8,17,13,2,2,8,7,3,10,7,6,4,14,5,7,12,16,
10,16,17,17,17,12,5,14,1,7,9,4,3,9,2,11,16,
3,1,14,8,6,3,10,11,16,7,15,4,5,7,8,9,2,
15,7,15,12,3,3,11,17,14,2,16,10,16,9,16,6,7,
7,13,6,13,5,16,12,2,1,3,1,11,12,14,8,13,9,
14,10,9,9,9,15,1,12,7,8,8,8,16,2,17,13,6,
13,14,1,2,16,9,9,6,17,12,14,5,2,15,4,13,8,
12,9,14,11,8,7,8,15,8,6,14,2,12,13,9,1,5,
9,12,10,6,8,4,15,11,1,16,16,8,9,17,14,17,13,
11,8,8,14,4,14,2,7,9,9,12,1,17,6,13,17,3,
1,4,8,16,12,17,13,8,3,4,13,14,7,11,9,17,15
],17).