/*
  Kakuro solver based on constraint programming.
	
  Problem Input implemented as 2D matrix containing local horizontal/
  vertical constraint sums in sub lists

  Model created by Lorenz Schiffmann, lorenz.schiffmann@gmail.com
  [with some small additions by Hakan Kjellerstrand, hakank@gmail.com]

*/

import cp.

main => go.

go => 
  time2($kakuro(1)),
  time2($kakuro(2)).

free(X) => not number(X), not list(X).
stop(X,Y) => free(X), list(Y).

kakuro(Id) =>
   printf("\nSolving problem %w\n", Id),
   problem(Id,A),  
   NC := length(A[1]), NR := length(A),
   IJ := 0,   
   foreach(Row in 2..NR, Col in reverse(2..NC))  % prepare all horizontal constraints from right to left for each row
     ( free(A[Row,Col]) -> member(A[Row,Col], 1..9); true),
     ((free(A[Row,Col]), IJ=0) -> IJ:=Col; true),     
     ( stop(A[Row,Col],A[Row,Col-1]) -> (A[Row,Col-1,2] #= sum([A[Row,J] : J in Col..IJ]), all_different([A[Row,J] : J in Col..IJ]), IJ:=0); true)                   
   end,  
   IJ := 0,
   foreach(Col in 2..NC, Row in reverse(2..NR))  % prepare all vertical constraints from bottom to top for each col
     ( free(A[Row,Col]) -> member(A[Row,Col],1..9); true),
     ((free(A[Row,Col]), IJ=0) -> IJ:=Row; true),     
     ( stop(A[Row,Col],A[Row-1,Col]) -> (A[Row-1,Col,1] #= sum([A[I,Col] : I in Row..IJ]), all_different([A[I,Col] : I in Row..IJ]), IJ:=0); true)                   
   end,      
   solve(A),   
   foreach(Row in 1..NR, Col in 1..NC) 
     printf("%8w", A[Row,Col]),
     if Col=NC then printf("%n") end 
   end,
   nl.
   
problem(1, A) => 
  % http://krazydad.com/kakuro/books/KD_Kakuro_6x6_s0_b100.pdf   (7)
    A={{0      , [13,0], [6,0]    ,  0     , [27,0] , [16,0] , 0    },
      {[0,10]  , _     ,  _       ,  [16,4], _      , _      , 0    },
      {[0,17]  , _     ,  _       ,  _     , _      , _      , 0    },
      { 0      , 0     ,  [11,19] ,  _     , _      , _      , 0    },
      { 0      ,[0,10] , _        ,  _     , _      , [14,0] , [8,0]},
      { 0      ,[0,27] , _        ,  _     , _      , _      , _    },
      { 0      ,[0,8]  , _        ,  _     , [0,16] , _      , _    }}.
      
problem(2, A) => 
 % http://www.kakuros.org/?s=9x8   (randomly generated)
   A={{0      ,  0    ,   0      ,   [16,0], [7,0]  , 0       , 0     , 0      },
      {0      ,  0    ,   [0,8]  ,   _     , _      , [15,0]  , 0     , 0      },
      {0      ,  0    ,   [24,20],   _     , _      , _       , [29,0], [13,0] },
      {0      , [0,5] ,   _      ,   _     , [0,21] , _       , _     , _      },
      {0      , [5,10],   _      ,   _     , 0      , [18,15] , _     , _      },
      {[0,4]  , _     ,   _      ,  [13,0] , [0,13] , _       , _     , 0      },
      {[0,21] , _     ,   _      ,   _     , [14,8] , _       , _     , 0      },
      {0      ,  0    ,   [0,14] ,   _     , _      , _       , 0     , 0      },
      {0      ,  0    ,   0      ,  [0,15] , _      , _       , 0     , 0      }}.