print(`This is Kakuro: a Maple package to generate and solve Kakuro puzzles.`):
print(`created by Dr. Z.'s Spring 2007 Math 640 class`):
print(``):
print(`type Help(); for a list of available functions.`):
print(`type HelpS(); for an explanation of syntax/puzzle conventions.`):

HelpS:=proc()
print(`We represent a Kakuro puzzle as a list of lists.`):
print(`each entry in a list has the form [n,L], where one of the following occurs:`):
print(`(1) n=-1, L=[] (black square)`):
print(`(2) n=0, L=[a,b] (information square with column sum a and row sum b)`):
print(`(3) n=1, L=[] (white unfilled square)`):
print(`(4) n=1, L=[c] (white square filled in with c (when puzzle is solved))`):
print(``):
print(`for example, a valid Kakuro puzzle is:`):
print(`K:=[`):
print(`[  [-1,[]], [0,[4,0]], [0,[3,0]]  ],`):
print(`[  [0,[0,3]], [1,[]], [1,[]]  ],`):
print(`[  [0,[0,4]], [1,[]], [1,[]]  ]`):
print(`]:`):
print(`which represents the Puzzle:`):
print(PrintNiceKakuro([[[-1,[]],[0,[4,0]],[0,[3,0]]],[[0,[0,3]],[1,[]],[1,[]]],[[0,[0,4]],[1,[]],[1,[]]]])):
print(`(Xs denote black squares, 0s denote unfilled white squares)`):
print(``):
print(`We assume that the entries of the puzzle solutions are only {1,2,3,4,5,6,7,8,9}`):
print(`and that the entries adding up to a particular clue are distinct.`):
end:

Help:=proc()
if nargs=0 then
print(`Available functions are:`):
print(`GeneratePuzzle(M,N,T), SolveKakuro(Puz), PrintNiceKakuro(Puz)`);
print(`For help with a specific function, type Help(function_name)`):

elif args[1]=GeneratePuzzle then
print(`GeneratePuzzle(M,N,T): Generates a (solved) M by N Kakuro Puzzle`):
print(`with T black and info squares, if possible.`):
print(`Throws an error if T is too large or too small to produce a valid puzzle.`):
print(``):
print(`(Note that T must be >=M+N-1 and <=M*N to produce a valid puzzle`):
print(`Also, note that if M,N>9 then T must be sufficiently large that there are no blocks of`):
print(`more than 9 consecutive white squares.)`):
print(``):
print(`For example, try:`):
print(`GeneratePuzzle(5,5,13);`):

elif args[1]=SolveKakuro then
print(`SolveKakuro(Puz): Inputs a Kakuro Puzzle (Puz) and outputs all its solutions.`):
print(`Warning: It is advisable not to try too big of puzzles: 7 by 6 puzzles can take up to 10 minutes or more,`):
print(`and larger puzzles have not yet been solved with this program`):
print(``):
print(`SolveKakuro can input an unsolved puzzle, or a solved puzzle.`):
print(`If it inputs a solved puzzle, it will erase all entries in white squares and then look for all solutions to the resulting unsolved puzzle.`):
print(``):
print(`For example, try:`):
print(`SolveKakuro(GeneratePuzzle(5,5,14));`):

elif args[1]=PrintNiceKakuro then
print(`PrintNiceKakuro(Puz): Inputs a Kakuro Puzzle (Puz) and prints it to the screen as a matrix`):
print(`This can be especially useful to look at the results of SolveKakuro(Puz) one at a time`):
print(``):
print(`For example try:`):
print(`S:=SolveKakuro(GeneratePuzzle(5,5,14));`):
print(`for i from 1 to nops(S) do`):
print(`print(PrintNiceKakuro(S[i]));`):
print(`od:`):

fi:
end:


with(combinat,randperm):
with(ListTools):

################################
#
# functions by Aek's team
#
################################

# Inputs : The number M of rows, the number N of columns of
# the puzzle and the total number T of black and information
# cells
# Outputs : The list [B,I,Puz] where B and I are the number of black
# cells and information cells, Puz is the Kukaro puzzle in the
# format.

GeneratePuzzle := proc(M,N,T)
    local L:
    L := [-1,-1,-1]:
    while(L[1] < 0) do
        L := SelectBlackAndInfoCells(M,N,T):
        # print(matrix(L[3])):
        L := LeftToRightIteration(M,N,L):
        # print(matrix(L[3])):
        L := TopToBottomIteration(M,N,L):
        # print(matrix(L[3])):
    od:
    L[3]:
end:


SelectBlackAndInfoCells:=proc(M,N,T)

# Inputs the number M of rows, the number N of columns of
#  the puzzle and the total number T of black and information
#  cells
# Outputs the list [B,I,A] where A is one valid configuration
#  of the black and information cells (in standard format). B
#  and I are the number of black cells and information cells,
#  respectively, in the configuration

local A,i,j,a,k,jihe,humberto,ke,count:

# Check for bad input
    if T<M+N-1 or T>M*N then
        ERROR(`Bad input`):
    fi:

    # Generate grid
    A:=[seq([seq([1,[]],j=1..N)],i=1..M)]:
    for i from 1 to M do
        A[i][1]:=[-1,[]]:
    od:
    for j from 2 to N do
        A[1][j]:=[-1,[]]:
    od:

# Randomly select black and information cells
    jihe:={seq(n,n=1..(M-1)*(N-1))}:
    for k from 1 to T-(M+N-1) do
        a:=rand(1..(M-1)*(N-1)-k+1):
        humberto:=a():
        ke:=jihe[humberto]:
        jihe:=jihe minus {ke}:
        i:=floor((ke-1)/(N-1))+1:
        j:=ke mod (N-1):
        if j=0 then
            j:=N-1:
        fi:
        i:=i+1:
        j:=j+1:
        A[i][j]:=[-1,[]]:
    od:
    A:

# Determine information cells
    count:=0:
    for i from 1 to M do
        for j from 1 to N do
            if A[i][j][1]=-1 then
                if j<N and A[i][j+1][1]=1 or
                i<M and A[i+1][j][1]=1 then
                    A[i][j]:=[0,[]]:
                    count:=count+1:
                fi:
            fi:
        od:
    od:

    return [T-count,count,A]:

end:



# Input : Two numbers n,k
# Output : A random permutation of k numbers from 1..n
randsub := proc(n,k)
    [op(randperm(n))[1..k]]:
end:

# Input : A list L, and a number k
# Output : A random permutation of k numbers from the list
permutelist := proc(L,k)
    [op(randperm(L))[1..k]]:
end:

# Fills in horizontal clues. IMPORTANT : This happens before the vertical #clues.
LeftToRightIteration := proc(M,N,T)
    local puz,BLACK,INFO,EMPTY,r,c,count,l,clue,fill:
    puz := T[3]:

    BLACK := -1:
    INFO := 0:
    EMPTY := 1:

    for r from 1 to M do
        for c from 1 to N do
            # Search for the pattern : An info cell followed by
            # empty cells followed by a black cell.
#             if(puz[r][c][1] = EMPTY) then
#                 print(puz):
#                 print(puz[r]):
#                 ERROR(`Empty Cell after a black cell`):
#             fi:

            # Info cell found
            if(puz[r][c][1] = INFO) then
                # If there are multiple INFO cells then pass over
                # to the last one.
                count := 0:
                while(c+count <= N and puz[r][c+count][1] = INFO) do
                    puz[r][c+count][2] := [0,0]:
                    count := count+1:
                od:
                c := c+count-1:
                count := 0:

                l := []:
                # Find the next black cell so that we can fill in a
                # clue
                count := count+1:
                while(c+count <= N and puz[r][c+count][1] = EMPTY) do
                    count := count+1:
                od:

# This should have been an error, but ....
#                 if(c+count <= N and puz[r][c+count][1] = INFO) then
#                     print(puz):
#                     print(puz[r]):
#                     ERROR(`Info Cell after another info cell`):
#                 fi:

                # Black Cell Found. count is the length of the clue.
                if(c+count > N or puz[r][c+count][1] = BLACK or puz[r][c+count][1] = INFO ) then
                    count := count-1:
                    if(count > 9) then
                        print(puz):
                        print(puz[r]):
                        ERROR(`Clue longer than length 9 found.`):
                    fi:
                    # Generate and fill in the clue
                    clue := randsub(9,count):
                    for fill from 1 to count do
                        puz[r][c+fill][2] := [clue[fill]]:
                    od:
                    puz[r][c][2] := [0,add(clue[i],i=1..count)]:

                    c := c+count:
                fi:
            fi:
        od:
    od:
    [T[1],T[2],puz]:
end:


# Fills in the vertical clues. This happens AFTER the horizontal
# clues are filled. Here we might detect that the process of
# randomly filling in horizontal clues didnt give a valid puzzle,
# in particular that there is a number repeated in a vertical
# clue. In such a case we return -1.
TopToBottomIteration := proc(M,N,T)
    local puz,BLACK,INFO,EMPTY,r,c,count,l,clue,fill,set,clueset,cluesum,cc:
    puz := T[3]:

    BLACK := -1:
    INFO := 0:
    EMPTY := 1:

    for c from 1 to N do
        for r from 1 to M do
            # Search for the pattern : An info cell followed by
            # empty cells followed by a black cell.
#             if(puz[r][c][1] = EMPTY) then
#                 print(puz):
#                 print(puz[r]):
#                 ERROR(`Empty Cell after a black cell`):
#             fi:

            # Info cell found
            if(puz[r][c][1] = INFO) then
                # If there are multiple INFO cells then pass over
                # to the last one.
                count := 0:
                while(r+count <= M and puz[r+count][c][1] = INFO) do
                    count := count+1:
                od:
                r := r+count-1:
                count := 0:

                l := []:
                # Find the next non-empty cell so that we can fill in a
                # clue
                count := count+1:
                set := {1,2,3,4,5,6,7,8,9}:
                clueset := []:
                cluesum := 0:
                while(r+count <= M and puz[r+count][c][1] = EMPTY) do
                    ### Here is a little trick. Remove those
                    # numbers which occur in the same column from 1..9
                    if not ({op(puz[r+count][c][2][1])} subset set) then
                       # print(`Busted :-( . I am too dumb to create a
                                 #nice matrix `):
                        return [-1,-1,-1]:
                    fi:
                        set := set minus {op(puz[r+count][c][2][1])}:
                        clueset :=[op(puz[r+count][c][2][1]),op(clueset)]:
                        count := count+1:
#                    else
                od:

#                 if(r+count <= M and puz[r+count][c][1] = INFO) then
#                     print(puz):
#                     print(puz[r]):
#                     ERROR(`Info Cell after another info cell`):
#                 fi:

                # Non-empty Cell Found/Hit end of matrix. count is the
#length of
#the clue.
                if(r+count > M or puz[r+count][c][1] = BLACK or puz[r+count][c][1] = INFO) then
                    count := count-1:
                    if(count > 9) then
                        print(puz):
                        print(puz[r]):
                        ERROR(`Clue longer than length 9 found.`):
                    fi:
                    # Generate and fill in the clue
                    clue := permutelist(set,count-nops(clueset)):
                    cc := 1:
                    for fill from 1 to count do
                        if(nops(puz[r+fill][c][2]) = 0) then
                            puz[r+fill][c][2] := [clue[cc]]:
                            cc := cc +1:
                        fi:
                    od:
                    puz[r][c][2][1] :=add(clue[i],i=1..nops(clue))+add(clueset[i],i=1..nops(clueset)):
                    #print(r,c,count,clue,cluesum,clueset):

                    r := r+count:
                fi:
            fi:
        od:
    od:
    [T[1],T[2],puz]:
end:

################################
#
# functions by Eric's team
#
################################

#Submodule GetEquations by Mike Neiman
#
#GetEquations(P,x) inputs a Kakuro puzzle P and an indeterminate symbol x.
#
#(The data structure for P is as follows: P is a list of lists of 2-element lists,where
#the entry P[i][j] is a 2-element list encoding the cell in the ith row and jth
#column of the puzzle; P[i][j]=[-1,[]] if the (i,j)th cell is black,
#P[i][j]=[1,[]]if the (i,j)th
#cell is white(blank), and P[i][j]=[0,[a,b]] if the (i,j)th cell is an
#informational cell, where a is `column sum below` and b is `row sum to right`.)
#
#GetEquations(P,x) outputs [eq,vars], where vars is the set of variables
#{x[i,j]: the (i,j)th cell is white} and eq is the set of equations corresponding
#to the row and column sum constraints given by the informational cells. 

GetEquations:=proc(P,x) local eq,vars,i,j,Inf,IC,a,b,ColVarList,k,RowVarList,l,y:

#initialize vars

vars:={}:

#compute vars by scanning through P for white cells and augmenting vars

for i from 1 to nops(P) do
  for j from 1 to nops(P[1]) do
    if P[i][j][1]=1 then
      vars:=vars union {x[i,j]}:
    fi:
  od:
od:

#Inf is a list recording the positions and values of the informational cells;
#if the (i,j)th cell is the informational cell a\b (i.e., P[i][j]=[0,[a,b]]),
#then there is an element [[i,j],[a,b]] in Inf.

#initialize Inf

Inf:=[]:

#compute Inf by scanning through P for informational cells and augmenting Inf


for i from 1 to nops(P) do
  for j from 1 to nops(P[1]) do
    if P[i][j][1]=0 then
      Inf:=[op(Inf),[[i,j],[P[i][j][2][1],P[i][j][2][2]]]]:
    fi:
  od:
od:

#initialize eq

eq:={}:

#compute equations by going through Inf and adding corresponding equations to eq

for IC in Inf do

#unpack IC as [[i,j],[a,b]]

  i:=IC[1][1]:
  j:=IC[1][2]:
  a:=IC[2][1]:
  b:=IC[2][2]:

#ColVarList is a list containing the variables appearing in column-sum constraint for (i,j)th cell

#initialize ColVarList

ColVarList:=[]:

#compute ColVarList by scanning down column from (i,j) until hit bottom of puzzle or a non-white cell

for k from i+1 to nops(P) while P[k][j][1]=1 do
  ColVarList:=[op(ColVarList),x[k,j]]:
od:

#augment eq with the column-sum constraint equation (unless null)

if nops(ColVarList)>0 then
  eq:=eq union {add(y, y in ColVarList)=a}:
fi:

#RowVarList is a list containing the variables appearing in row-sum constraint for (i,j)th cell

#initialize RowVarList

RowVarList:=[]:

#compute RowVarList by scanning across row from (i,j) until hit right side of puzzle or a non-white cell

for l from j+1 to nops(P[i]) while P[i][l][1]=1 do
  RowVarList:=[op(RowVarList),x[i,l]]:
od:

#augment eq with the row-sum constraint equation (unless null)

if nops(RowVarList)>0 then
  eq:=eq union {add(y, y in RowVarList)=b}:
fi:

od:

RETURN([eq,vars]):

end:



#Author: Emilie Hogan
#There are a total of 3 programs which call eachother.
#FindIneqKak(K,x) calls FindRowIneqKak(K,x) which calls 
#FindInfos(row).

#FindIneqKak(K,x): inputs a Kakuro puzzle and a variable x
#and finds all the sets {x[i1,j1],x[i2,j2],...,x[in,jn]} such that variables
#in the same set cannot equal eachother (rows and columns)

FindIneqKak := proc(K,x) local
rowIneq,Kt,prelimColIneq,colIneq,N,i,oneColIneq,k,j,IneqSet,l,rid;

#get the set of inequality sets for the rows of K
rowIneq := FindRowIneqKak(K,x);

Kt := Transpose(K);

#find the inequality sets for the columns of K
#except that if there is x[i,j] we really want
#x[j,i] since I transposed the matrix.
prelimColIneq := FindRowIneqKak(Kt,x);

#i'm going to run through prelimColIneq and transpose the x[i,j]
#and put the transposed element into colIneq.
colIneq := {};

#N is the number of inequality sets
N := nops(prelimColIneq);

for i from 1 to N do
        oneColIneq := {};
        #this double loop basically checks if x[k,j] is in prelimColIneq
        #for all x[k,j] in the matrix. i couldn't think of a better way to do that
        for k from 1 to nops(K[1]) do
                for j from 1 to nops(K) do
                        if nops({x[k,j]} intersect prelimColIneq[i])=1 then
                                oneColIneq := {op(oneColIneq),x[j,k]};        
                        fi;
                od;
        od;
        colIneq := {op(colIneq),oneColIneq};
od;

#merge the row inequalities and column inequalities
IneqSet := {op(rowIneq),op(colIneq)};

#get rid of inequality sets which have only one element
rid := {};
for l from 1 to nops(IneqSet) do
        if nops(IneqSet[l])=1 then
                rid := rid union {l};
        fi;
od;

IneqSet := IneqSet minus {seq(IneqSet[m],m in rid)};

RETURN(IneqSet);

end:

#-------------------------------------------------------------------

#FindRowIneqKak(K,x): Inputs a Kakuro puzzle and a variable x
#and finds all the sets {x[i1,j1],x[i2,j2],...,x[in,jn]} such that the variables
#in the same set cannot equal eachother (only looking at rows of K)

FindRowIneqKak := proc(K,x) local Ineq,R,row,rowIneq,Inf,i,neq,j;

#initialize Ineq, the list of inequality sets
Ineq := {};

#loop over each row to find inequalities by row
for R from 1 to nops(K) do
        row := K[R];

        #initialize rowIneq, the list of inequality
        #sets for a specific row.
        rowIneq := {};

        #gets a list of all info cells in the row
        Inf := FindInfos(row);

        if nops(Inf) = 0 then
                #don't do anymore in the loop
                #because there are no info cells in the row
        else
                #loop for each info cell 
                for i from 1 to nops(Inf) do
                        neq := {};

                        #crawl along the row from the info cell 
                        #while the next cell is white and you
                        #don't fall off the end of the row        
                
                        for j from Inf[i]+1 while j<= nops(row) and row[j][1]=1 do
                                #add x[R,j] to the set of inequalities
                                neq := {op(neq),x[R,j]};
                        od;
                        
                        #if there was nothing to add, then don't add an empty set to rowIneq
                        if nops(neq) <> 0 then
                                rowIneq := {op(rowIneq),neq};
                        fi;
                od;
        fi;
        
Ineq := {op(Ineq),op(rowIneq)};
od;

RETURN(Ineq);

end:

#-------------------------------------------------------------------

#FindInfos(row): inputs a Kakuro row and outputs a list
#[i1,i2,...,in] indicating where the info cells are.

FindInfos := proc(row) local Inf,r;

Inf := [];

for r from 1 to nops(row) do
        if row[r][1]=0 then
                Inf := [op(Inf),r];
        fi;
od;

RETURN(Inf);

end:



#Author: Justin Palumbo
#FindIndVars - gives a method to identify the independent variables in a set of equations
#Part of a software project to create and solve KAKARU puzzles

#FindIndVars
#INPUT: a set of equations, eqns, whose variables are taken from
#        the also inputted set vars.
#OUTPUT: set of solution equations, set of independent variables in those equations
#         and the set of dependent variables, in that order 
FindIndVars:=proc(eqns,vars)
        local answer,eq0,dep,ind:
        answer:=solve(eqns,vars):
        dep:={}:
        ind:={}:
        for eq0 in answer do
                if lhs(eq0)=rhs(eq0) then
                        ind:=ind union {lhs(eq0)}:
                else
                        dep:=dep union {lhs(eq0)}:
                fi:        
        od:
        return answer,ind,dep:
end:



#Author: Eric Rowland

#Inputs a Kakuro puzzle (as a list of lists) and a variable to be used in equations.
#Outputs the 4-tuple [independent variables, dependent variables, equations, sets of pairwise inequal variables].
AnalyzeKakuro:=proc(puzzle, var)
 local mike, eqns, vars, ineqs, justin, indvars, depvars;
 mike:=GetEquations(puzzle, var);
 eqns:=mike[1];
 vars:=mike[2];
 ineqs:=FindIneqKak(puzzle, var);
 justin:=FindIndVars(eqns, vars);
 eqns:=justin[1];
 indvars:=justin[2];
 depvars:=justin[3];
 [indvars, depvars, eqns, ineqs];
end proc:



################################
#
# functions by Baxter's team
#
################################

DioSystemMaker:=proc(eq::set,ineq::set) local S, s:
#ineq is a set of sets of variables which must be distinct
#For example, if a<>b but also c,d,e must be distinct, this would be encoded{{a,b},{c,d,e}}
#This program decodes the encoding
#Written by Baxter

eq union {seq(seq(s[1]<>s[2],s in combinat[choose](S,2)), S in ineq)}:

end:


#Deduce(part,vars, DioSystem) takes a set of (partial) assignments of the variablespart, 
#and the set of equations (and inequalities) eq in variables var that must besatisfied, 
#and returns either FAIL (if there is no solution given the partial assignment), 
#or another set of partial assignments (possibly extending part) 
#that are forced by the inputs.
#part        : set of partial assignments (e.g. {a=3, c=5, d=3})
#vars        : set of variables appearing in eq (e.g. {a,b,c,d,e,f})
#DioSystem   : set of equations and inequalities to be solved
#Then the program returns all assignments necessitated by eq, or returns FAIL if there is some inherent contradiction. (e.g. Deduce({a=3,c=5,d=3},{a=c-b,e=d+f},{a,b,c,d,e,f},{a=c-b,e=d+f,a<>b, d<>f}) would return {a=3,c=5,d=3, b=2})
#Notice that no check is made to ensure that all variables are in the range 1..9, although such a check could easily be added.
#Written by Justin Bush.

Deduce:=proc(part,vars, DioSystem)
local A, fin, vars2, s, t,class:


#"vars2" is the set of variables we have yet to assign.
vars2:=vars minus indets(part):

#First solve(in integers) for unassigned variables the equations we are given 
#with the assignments we are given.
A:=solve(subs(part,DioSystem),vars2):

#If there are no solutions, we fail.
if A=NULL then
  RETURN(FAIL):
fi:

#"fin" is the set we will return otherwise.  Initialize it to be the assignments wealready have.
fin:=part:

#Ranging over elements of vars2, we check if they have integral solution in A.  If so, we add them.
for s in vars2 do
  t:=subs(A,s):
  if type(t,integer) and t>0 then
   fin:=fin union {s=t}:
  fi:
od:


fin:

end:


# Looper(p,my,vars,sat,eq, ineq) is the recursive routine that searches for satisfying assignments
# to the Kakuro program that is at hand. 
# p          : set of partial assignments of the variables (i.e. {a=3,b=7,d=2})
# my         : the variables that is currently being considered (my must not be in p initially)
# vars       : the set of total variables
# sat        : the list of satisfying assignments to the Kakuro board
# DioSystem  : the list of Diophantine equations and inequalities (passed from Eric's part).  This is not needed for Looper itself, just needs to be passed to Deduce
# So, our initial call would be Looper({},a,{a,b,c,...},{}, eq, ineq)
#Written by Paul Raff

Looper:=proc(p,my,vars,sat,DioSystem)

local cur_var,p1,next_var,i,used_vars,new_sat,leftover_vars:

new_sat:=sat:

for i from 1 to 9 do
        p1:=Deduce(p union {my=i},vars,DioSystem):
        if p1<>FAIL then
                used_vars:=indets(p1):
                leftover_vars:=vars minus used_vars:
                if nops(leftover_vars)=0 then
                        new_sat:=[op(new_sat),p1]:
                else
                        next_var:=leftover_vars[1]:
                        new_sat:=Looper(p1,next_var,vars,new_sat,DioSystem):
                fi:
        fi:
od:

RETURN(new_sat):

end:


#Edited by Baxter

################################
#
# functions by Lara
#
################################

PrintNiceKakuro:=proc(Puz) local i, j, R, R2:
for i from 1 to nops(Puz) do
R:=Puz[i]:
R2[i]:=[]:
for j from 1 to nops(R) do
if R[j][1]=-1 then
	R2[i]:=[op(R2[i]),X]:
elif R[j][1]=0 then
	R2[i]:=[op(R2[i]),R[j][2]]:
elif R[j][2]=[] then
	R2[i]:=[op(R2[i]),0]:
else
	R2[i]:=[op(R2[i]),op(R[j][2])]:
 fi:
od:
od:
Matrix([seq(R2[i],i=1..nops(Puz))]);
end:

UnfillKakuro:=proc(Puz,a) local i,R,Puz2,R2,j:
Puz2:=[]:
for i from 1 to nops(Puz) do
R:=Puz[i]:
R2:=[]:
for j from 1 to nops(R) do
if R[j][1]=1 then 
R2:=[op(R2),[1,[a[i,j]]]]:
else
R2:=[op(R2),R[j]]:
fi:
od:
Puz2:=[op(Puz2),R2]:
od:
Puz2:
end:

SolveKakuro:=proc(Puz) local a,AK,Ind,Dep,eq,ineq,VARS,DioSystem,i,P2,M,M2:
P2:=UnfillKakuro(Puz,a):
AK:=AnalyzeKakuro(P2,a):

Ind:=AK[1]:
Dep:=AK[2]:
eq:=AK[3]:
ineq:=AK[4]:

VARS:=Ind union Dep:
DioSystem:=DioSystemMaker(eq, ineq):

M:=Looper({},VARS[1],VARS,{}, DioSystem):

M2:={}:
for i from 1 to nops(M) do
if CheckKakuroSolution(subs(M[i],P2)) then 
M2:=M2 union {subs(M[i],P2)}:
fi:
od:
M:=M2:


if nops(M)=0 then
print("Sorry, this Puzzle has no solution."):
elif nops(M)=1 then 
print("This puzzle has 1 solution.  Here it is:"):
else
print("This puzzle has ", nops(M), " solutions.  Here they are:"):
fi:
M:
end:

CheckKakuroSolution:=proc(Puz) local j,k,R, rowsum, tot, letters,countit:
#print(PrintNiceKakuro(Puz)):
#first check that all entries are in {1,...,9}
for j from 1 to nops(Puz) do
R:=Puz[j]:
for k from 1 to nops(R) do
if R[k][1]=1 and op(R[k][2])>9 then return false:
elif R[k][1]=1 and op(R[k][2])<1 then return false:
fi:
od:
od:

#print("survived 1-9 check"):

#check rowsums are correct and use no repeats
for j from 1 to nops(Puz) do
R:=Puz[j]:
for k from 1 to nops(R) do
countit:=false:
if R[k][1]=1 then
	tot:=tot+op(R[k][2]):
	if member(op(R[k][2]),letters) then 
	print("repeat letter"): return false: fi:
	letters:=letters union {op(R[k][2])}:
elif R[k][1]=0 and k>1 and R[k-1][1]=1 then
	if tot<>rowsum then print("bad sum in middle"): return false: fi:
	tot:=0: countit:=true:
	letters:={}:
	rowsum:=R[k][2][2]:
elif k=1 and R[1][1]=0 then
	tot:=0: countit:=true:
	letters:={}:
	rowsum:=R[k][2][2]:
elif R[k][1]=0 then
	tot:=0: countit:=true:
	letters:={}:
	rowsum:=R[k][2][2]:
elif k>1 and R[k-1][1]=1 then
	if tot<>rowsum then return false: print("bad sum at black square"): fi:
fi:
od:
if countit and rowsum<>tot then return false: fi:
od:

#print("survived rowcheck"):

#check columnsums are correct and use no repeats
for j from 1 to nops(Puz[1]) do
R:=[seq(Puz[i][j],i=1..nops(Puz))]:
tot:=0: rowsum:=0: letters:={}:
for k from 1 to nops(R) do
countit:=false:
if R[k][1]=1 then
	tot:=tot+op(R[k][2]):
	if member(op(R[k][2]),letters) then 
	return false: fi:
	letters:=letters union {op(R[k][2])}:
elif R[k][1]=0 and k>1 and R[k-1][1]=1 then
	if tot<>rowsum then return false: fi:
	tot:=0: countit:=true:
	letters:={}:
	rowsum:=R[k][2][1]:
elif k=1 and R[1][1]=0 then
	tot:=0: countit:=true:
	letters:={}:
	rowsum:=R[k][2][1]:
elif R[k][1]=0 then
	tot:=0: countit:=true:
	letters:={}:
	rowsum:=R[k][2][1]:
elif k>1 and R[k-1][1]=1 then
	if tot<>rowsum then  return false: fi:
fi:
od:
if countit and rowsum<>tot then return false: fi:
od:

#print("survived column check"):

true:
end: