/* 

  Kakuro solver in Picat.

  This program reads an input file of the form
  """
# from   http://en.wikipedia.org/wiki/File:Kakuro_black_box.svg
x,23\,30\,x,x,27\,12\,16\
\16,0,0,x,17\24,0,0,0
\17,0,0,15\29,0,0,0,0
\35,0,0,0,0,0,12\,x
x,\7,0,0,7\8,0,0,7\
x,11\,10\16,0,0,0,0,0
\21,0,0,0,0,\5,0,0
\6,0,0,0,x,\3,0,0
"""
        
  And then solves the Kakuro instance.

  Here is the full output of the program given the file kakuro1.txt

Kakuro:
     x   23\   30\     x     x   27\   12\   16\
   \16     0     0     x 17\24     0     0     0
   \17     0     0 15\29     0     0     0     0
   \35     0     0     0     0     0   12\     x
     x    \7     0     0   7\8     0     0    7\
     x   11\ 10\16     0     0     0     0     0
   \21     0     0     0     0    \5     0     0
    \6     0     0     0     x    \3     0     0

Hints:
         0    [23,x]    [30,x]         0         0    [27,x]    [12,x]    [16,x]
    [x,16]     _46d0     _46d8         0   [17,24]     _46f0     _46f8     _4700
    [x,17]     _4688     _4690   [15,29]     _46a0     _46a8     _46b0     _46b8
    [x,35]     _4640     _4648     _4650     _4658     _4660    [12,x]         0
         0     [x,7]     _4600     _4608     [7,8]     _4618     _4620     [7,x]
         0    [11,x]   [10,16]     _45c0     _45c8     _45d0     _45d8     _45e0
    [x,21]     _4568     _4570     _4578     _4580     [x,5]     _4590     _4598
     [x,6]     _4520     _4528     _4530         0     [x,3]     _4548     _4550

Solution:
      _    23\    30\      _      _    27\    12\    16\
    \16      9      7      _  17\24      8      7      9
    \17      8      9  15\29      8      9      5      7
    \35      6      8      5      9      7    12\      _
      _     \7      6      1    7\8      2      6     7\
      _    11\  10\16      4      6      1      3      2
    \21      8      9      3      1     \5      1      4
     \6      3      1      2      _     \3      2      1



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

*/

import util.
import cp.

main => go.

go ?=>
  File = "kakuro1.txt", % http://hakank.org/picat/kakuro1.txt solve time: 0.001s
  % File := "kakuro_hard.txt", % solve time: 0.002s
  % File := "kakuro_hard2.txt", % solve time: 0.33s
  
  [Rows,Cols,Hints,Hs] = read_hints(File),
  X = new_array(Rows,Cols),
  X :: 0..9,
  foreach(I in 1..Rows, J in 1..Cols)
    if nonvar(Hints[I,J])  then
      X[I,J] #= 0
    else
      X[I,J] #> 0      
    end    
  end,
  foreach(AB=Sum in Hs)
    Xs = [X[A,B] : [A,B] in AB],
    all_different(Xs),    
    sum(Xs) #= Sum
  end,

  solve($[ff],X),

  println("\nSolution:"),
  print_sol(X,Hints),
  
  fail,
  nl.
go => true.

/*
  Read the instance file and return
  - Rows
  - Cols
  - Hints matrix
  - Hs: list of indices=Sum

*/
read_hints(File) = [Rows,Cols,Hints,Hs] =>

  Kakuro = [ Line.split(",") : Line in read_file_lines(File), Line[1] != '#'],
  Rows = Kakuro.len,
  Cols = Kakuro[1].len,
  Hints = new_array(Rows,Cols),
  println("Kakuro:"),  
  foreach(I in 1..Rows)
    foreach(J in 1..Cols)
      KIJ = Kakuro[I,J],
      printf("%6w",KIJ),
      if KIJ == "0" then
        % To be filled in
        true
      elseif find(KIJ,"\\",_,_) then
        % Hints
        HIJ = split(KIJ,"\\"),
        if HIJ.len == 2 then
          T = HIJ.map(to_int)
        else      
          T = new_list(2)
        end,
        if KIJ.last == '\\' then
          T[1] = HIJ.last.to_int,
          T[2] = 'x'
        elseif KIJ.first == '\\' then
          T[1] = 'x',
          T[2] = HIJ.first.to_int
        end,
        Hints[I,J] = T
      elseif KIJ == "x" then
        % Unused cell
        Hints[I,J] = 0
      else
        println("What?"=KIJ),
        halt
      end
    end,
    nl
  end,
  nl,
  println("Hints:"),
  foreach(I in 1..Rows)
    foreach(J in 1..Cols)
      printf("%10w",Hints[I,J])
    end,
    nl
  end,
  % Get the indices and the sum
  Hs = [],
  foreach(I in 1..Rows)
    foreach(J in 1..Cols)
      HIJ = Hints[I,J],
      if nonvar(HIJ), HIJ != 0 then
        [ColSum,RowSum] = HIJ ,
        if RowSum != 'x' then
          HR = [Hints[I,K] : K in J+1..Cols],
          R = check(HR,X,row,I,J),
          Hs := Hs ++ [R=RowSum]
        end,
        if ColSum != 'x' then
          HC = [Hints[A,J] : A in I+1..Rows],
          C = check(HC,X,col,I,J),
          Hs := Hs ++ [C=ColSum]
        end
      end
    end
  end.

/*
  Extract the indices for this slice
*/
check(L,X,Type,Row,Col) = T =>
  Len = L.len,  
  T = [],
  OK = true,
  foreach(K in 1..Len, break(OK == false))
    if var(L[K]) then
      if Type == row then
        T := T ++ [[Row,Col+K]]
      else
        T := T ++ [[Row+K,Col]]
      end
    else 
      OK := false
    end
  end.
  
/*
  Pretty print the solution
*/
print_sol(X,Hints) =>
  Rows = X.len,
  Cols = X[1].len,
  foreach(I in 1..Rows)
    foreach(J in 1..Cols)
      if var(Hints[I,J]) then
        T = X[I,J]
      elseif list(Hints[I,J]) then
        [H1,H2] = Hints[I,J].map(to_string),
        T = cond(H1=="x","",H1) ++ "\\" ++ cond(H2=="x","",H2)
      else
        T = "_"
      end,
      printf("%7w",T)
    end,
    nl
  end,
  nl.