#!/usr/bin/python -utt
# vim:sw=4:et
"""Try to solve kakuro puzzle.
Input could be like this:

x   x    5\13  -  -  -  -  
x   3\24  -    -  -  -  -

that sort of thing.

'x' is gray, no numbers go here.  Can also be 'X'
3\24 means "squares down sum to 3; squares across (to the right) sum to 24"
'\' can also be spelled '.'

'-' (also spelled '_') means a digit goes here"""

import sys
import time
from Cell import * 

# OK, so here's what we have to do:
# step1: read in the matrix
# step2: group cells according to totals
# step3: eliminate what values can't be; assign values where possible
# step4: eliminate combos that can't be
# step5: if any changes and any unassigned then goto step3
# step6: print answer


def main(infile):
    the_puzzle = parse_input(infile)         # step1
    group_totals(the_puzzle)                    # step2
    # After totals are grouped, basically what
    # I care about is the SUMS cells.
    scells = [x for x in reduce(lambda a,b:a+b, the_puzzle) if x.type == SUMS]
    more_to_do = 1
    passno = 1
    while more_to_do:
        more_to_do = 0
        print "starting pass", passno, "-- cpu time", time.clock(), "<br>"
        passno += 1
        # step3: eliminate what values can't be; assign values where possible
        for acell in scells:
            more_to_do += cut_possibles(acell.dtotal)   # any changes?
            more_to_do += cut_possibles(acell.atotal)   # any changes?
        #print "%%% after cut_possibles: more_to_do =", more_to_do 
        # step4: eliminate combos that can't be
        for acell in scells:
            more_to_do += cut_combos(acell.dtotal)      # any changes?
            more_to_do += cut_combos(acell.atotal)      # any changes?
        #print "%%% after cut_combos: more_to_do =", more_to_do 
    unknown_cells = print_puzzle(the_puzzle)       # done with this part
    # Up to this point doesn't take very long.
    if unknown_cells > 0:
        # Find totals that have undecided cells
        utotals = list()
        for acell in scells:
            for atot in acell.dtotal, acell.atotal:
                if atot and atot.has_undecided():
                    utotals.append(atot)
        print "about to calculate permutations -- cpu time", time.clock()
        # Calculate permutations.
        for atot in utotals:
            stime = time.clock()
            print "get perms", atot.cell.name() + \
                  "<sub>" + atot.kind + "</sub>", \
                  "(" + `len(atot.combos)`, "combos):",
            permutes = list()
            for acombo in atot.combos:
                if len(permutes) == 0:
                    permutes = permute(acombo)
                else:
                    # "x=x+y" creates new list but "x+=y" updates x in-place
                    # We need the former here:
                    permutes = permutes + permute(acombo)
            print len(permutes), "permutations; CPU cost", 
            print time.clock()-stime, "<br>"
            atot.permutes = permutes

        # Now we can trim permutations and possible values in cells.
        more_to_do = 1
        passno = 1
        while more_to_do:
            more_to_do = 0
            print "starting pass", passno, "-- cpu time", time.clock(), "<br>"
            passno += 1
            for atot in utotals:
                more_to_do += cut_permutes(atot)
            print "%%%", more_to_do, "permutations removed<br>"

            for acell in [x for x in reduce(lambda a,b:a+b, the_puzzle) 
                          if x.type == 0 and len(x.possibles) == 2]:
                # For now try it only on cells having exactly 2 possibles
                for aval in acell.possibles:
                    achange = cut_contradictory_possibles(acell, aval)
                    more_to_do += achange
                    if achange:
                        print "###", acell.name(), "can't be", aval, "<br>"
                        if len(acell.possibles) == 1:
                            acell.type = acell.possibles[0]
                            handle_decided_cells(acell)
                            break
                    
            if more_to_do > 0:
                for atot in utotals:
                    cut_possibles_with_permutes(atot)
        unknown_cells = print_puzzle(the_puzzle)   # done with this part

def parse_input(infile):
    """step1: read in the matrix"""
    row_list = list()
    row_num = -1                                # first row is row 0
    row_len = 0                                 # not yet known
    for aline in infile:
        arow = aline.split('#')[0].strip()      # delete comments
        if len(arow) == 0:                      # skip blank lines
            continue
        arow = arow.replace('\\', '.')          # I hate escaping
        awords = arow.split()
        if row_len == 0:
            row_len = len(awords)
        elif row_len != len(awords):
            print "Inconsistent length!  was", row_len,
            print "but this doesn't match:"
            print aline.rstrip()
            sys.exit(1)
        # We have a good one, so bump the row #
        row_num += 1
        row_of_cells = list()
        for cnum,ctext in enumerate(awords):
            if ctext in 'xX':
                row_of_cells.append(Cell(row_num, cnum, GRAY))
            elif ctext in '_-':
                row_of_cells.append(Cell(row_num, cnum, 0))
            else:
                # Better have a '.' -- Just one, too.
                dtotal = 0
                atotal = 0
                try:
                    dsum,asum = ctext.split('.')
                    if dsum != '':
                        dtotal = int(dsum)
                    if asum != '':
                        atotal = int(asum)
                except:
                    print "Ouch! Unknown cell info:", ctext
                    print "in this row:"
                    print aline.rstrip()
                    sys.exit(1)
                row_of_cells.append(Cell(row_num, cnum, SUMS,
                                         dtotal, atotal))
        row_list.append(row_of_cells)
    for rnum,arow in enumerate(row_list):
        for cnum,acell in enumerate(arow):
            if rnum > 0:
                acell.above = row_list[rnum-1][cnum]
            if rnum < len(row_list)-1:
                acell.below = row_list[rnum+1][cnum]
            if cnum > 0:
                acell.left = arow[cnum-1]
            if cnum < row_len-1:
                acell.right = arow[cnum+1]
    return row_list

def group_totals(the_puzzle):
    """For each cell of type SUMS, gather the cells that are included in each
    total.  Adjust pointers accordingly."""
    nrows = len(the_puzzle)
    ncols = len(the_puzzle[0])
    sum_lists = sums()
    for arow in the_puzzle:
        #print "starting row", arow[0].row
        for acell in [x for x in arow if x.type == SUMS]:
            if acell.dtotal:
                t = acell.dtotal
                t.cells = blanks_down(the_puzzle, acell.row, acell.col)
                t.combos = list(sum_lists[(len(t.cells), t.sum)])
            if acell.atotal:
                t = acell.atotal
                t.cells = blanks_across(arow, acell.col)
                t.combos = list(sum_lists[(len(t.cells), t.sum)])

    # Now, look for 2x2 boxes with one appendage, which may be above or
    # below either column, or to the left or right of either row.  Example:
    #      A     B     C     D     E     F   ...
    #   +-----+-----+-----+-----+-----+-----+...
    #  0|XXXXX|XXXXX|XXXXX|17\  |15\  |XXXXX|...
    #   +-----+-----+-----+-----+-----+-----+...
    #  1|XXXXX|XXXXX|  \10| ___ | ___ |XXXXX|...
    #   +-----+-----+-----+-----+-----+-----+...
    #  2|XXXXX|XXXXX|  \15| ___ | ___ |18\14|...
    #   +-----+-----+-----+-----+-----+-----+...
    #  3|XXXXX| 9\  |16\  |  \11| ___ | ___ |...
    #   +-----+-----+-----+-----+-----+-----+...
    #  4|  \10| ___ | ___ |15\  |  \ 9| ___ |...
    #
    # Based on 0D and 0E, 1D+2D+1E+2E+2F = 32.
    # Based on 1C and 2C, 1D+1E+2D+2E    = 25.
    #  Subtracting yields             2F =  7
    #
    # How to find these?  When see len=3, see if there's len=2 nearby in
    # the right places.
    for arow in the_puzzle:
        for acell in [x for x in arow if x.type == SUMS]:
            if acell.dtotal and len(acell.dtotal.cells) == 3:
                try_box(acell.dtotal, DOWN)
            if acell.atotal and len(acell.atotal.cells) == 3:
                try_box(acell.atotal, ACROSS)

def try_box(tot, dir):
    """Helper function: Look for an adjacent column(row) either in same
    row(column) or one above(left) or below(right) of the first one,
    with length=2.  Then see if there are two crosswise totals to the
    left (above) the lower-numbered column(row), starting at 1+the
    higher-numbered column(row).  If one is found, then bob's yer uncle;
    you can fill in the 3rd element with the determined value.  If you
    do that, be sure to call handle_decided_cells()."""
    mycell = tot.cell
    if dir == DOWN:
        prev_rank = lambda x: x.left
        next_rank = lambda x: x.right
        t_same = lambda x:x.dtotal
        ahead1 = lambda x:x.below
        t_other = lambda x:x.atotal
    else:       # ACROSS
        prev_rank = lambda x:x.above
        next_rank = lambda x:x.below
        t_same = lambda x:x.atotal
        ahead1 = lambda x:x.right
        t_other = lambda x:x.dtotal
    p = prev_rank(mycell)
    n = next_rank(mycell)
    if p and p.type == SUMS:
        x = prev_rank(p)
        tail = ahead1(ahead1(ahead1(mycell))) 
        if x and tail.type == 0:
            box_helper(tot, p, tail, x, ahead1, t_same, t_other)
    elif p and ahead1(p).type == SUMS:
        p = ahead1(p)
        x = prev_rank(p)
        tail = ahead1(mycell) 
        if x and tail.type == 0:
            box_helper(tot, p, tail, x, ahead1, t_same, t_other)
    elif n and n.type == SUMS:
        x = prev_rank(mycell)
        tail = ahead1(ahead1(ahead1(mycell))) 
        if x and tail.type == 0:
            box_helper(tot, n, tail, x, ahead1, t_same, t_other)
    elif n and ahead1(n).type == SUMS:
        n = ahead1(n)
        tail = ahead1(mycell) 
        x = prev_rank(tail)
        if x and tail.type == 0:
            box_helper(tot, n, tail, x, ahead1, t_same, t_other)
        
def box_helper(tot, adj, tail, x, ahead1, t_same, t_other):
    """Helper function for try_box: bad medicine to type the same thing 4x.
    tot is the 'total' struct in the cell we're looking at (len=3)
    adj is a cell adjacent or diagonal with len=2
    tail is the cell that's sticking out (to be fixed, if all goes well)
    x is the cell one behind the two cross(thus 'x')ing totals
    ahead1 is a function to move us one ahead (direction of tot)
    t_same maps a cell to the same kind of total as 'tot' is
    t_other maps a cell to the OTHER (d'oh!)..."""
    x1 = ahead1(x)
    x2 = ahead1(x1)
    if t_same(adj) and len(t_same(adj).cells) == 2 and \
       x1.type == SUMS and t_other(x1) and \
                           len(t_other(x1).cells) == 2 and \
       x2.type == SUMS and t_other(x2) and \
                           len(t_other(x2).cells) == 2:
        # Got a box.
        big_total = tot.sum + t_same(adj).sum
        other_total = t_other(x1).sum + t_other(x2).sum
        tail.type = big_total - other_total
        if tail.type not in tail.possibles:
            print "???", tail.name(), "<-", tail.type, "but!", tail.possibles
        handle_decided_cells(tail)

def cut_possibles(tot):
    """Using the combos in "tot" (atotal or dtotal from a Cell instance),
    go through each cell included in that total and remove any value
    that isn't possible for that cell.  Return a positive value if any cells
    have had their list of possible values modified based upon the totals.
    Example: If there are 2 cells which must add up to 17, then eliminate
    every value other than 8 and 9.
    If only one value remains, then assign that value to the cell's
    "type" and eliminate that value from "possibles" of other cells
    in the same total (across or down)."""

    
    # might be None; caller doesn't check
    if not tot:
        return 0        # Nothing changed

    # work queue for later
    cells_decided = list()


    # First, construct list of possible values
    #print "%%%", tot.cell.name(), "combos", tot.combos
    tposs = list(tot.combos[0])
    for acombo in tot.combos[1:]:       # if there /are/ any more
        for aval in acombo:
            if aval not in tposs:
                tposs.append(aval)

    cells_changed = 0
    # Now for each cell...
    for acell in [x for x in tot.cells if x.type == 0]:
        # There's probably a better way to do this...
        this_cell_changed = False
        for aval in range(1,10):
            if aval in acell.possibles and aval not in tposs:
                this_cell_changed = True
                acell.possibles.remove(aval)
        if this_cell_changed:
            cells_changed += 1
            if len(acell.possibles) == 1:
                acell.type = acell.possibles[0]
                cells_decided.append(acell)
                #print "%%%", acell.name(), "=", acell.type,
                #print "because", tot.cell.name(), "total is", tot.sum

    # NEW! (yeah right) Look for n cells with same combo [x1,x2...xn].
    # If any other cell has any of (x1...xn) then remove xi from said cell.
    # This only useful if we have n+1 or more cells in the list.
    undec_cells = [x for x in tot.cells if x.type == 0]
    if len(undec_cells) >= 3:
        for listlen in range(2, len(undec_cells)):
            # Find at least "listlen" lists of length "listlen"
            lenmatching = [x.possibles for x in undec_cells \
                            if len(x.possibles) == listlen]
            if len(lenmatching) < listlen:
                continue                        # no joy here
            if len(lenmatching) > listlen:
                # Possibilities...
                lenmatching.sort()
            # Suppose len(lenmatching)=3, listlen=2 (three 2-element lists)
            # We want startidx to be 0,1 -- i.e., range(3-2+1)
            for startidx in range(len(lenmatching) - listlen + 1):
                # compare-val, the first in the set.
                cval = lenmatching[startidx]
                for idx in range(startidx+1, startidx+listlen):
                    if cval != lenmatching[idx]:
                        break
                else:
                    # All of them (maybe just 2) match!
                    break       # out of enclosing loop
            else:
                break           # try next value of listlen
            # If I understand loops correctly, getting here means we
            # have a set of 'listlen' cells, all matching.
            for acell in undec_cells:
                decided_cells = list()
                acell_changed = False
                if acell.possibles != cval:
                    for aval in cval:
                        if aval in acell.possibles:
                            acell_changed = True
                            decided_cells += forbid(acell, aval)
                if acell_changed:
                    cells_changed += 1
                    if decided_cells:
                        handle_decided_cells(decided_cells)
                        


    # Did we decide upon any cells?
    handle_decided_cells(cells_decided)

    # Is there any value which is required by all viable combos?
    req_by_all = list(tot.combos[0])
    for acombo in tot.combos[1:]:       # if there /are/ any more
        for aval in list(req_by_all):
            if aval not in acombo:
                req_by_all.remove(aval)
    for aval in req_by_all:
        can_be = [x for x in tot.cells if x.type == 0 and aval in x.possibles]
        if len(can_be) == 1:
            # Then there is only one cell which could be this value
            # Hence it must be this value.
            can_be[0].type = aval
            cells_changed += 1
            cells_decided.append(can_be[0])
            handle_decided_cells(cells_decided)
            #print "%%% Only", can_be[0].name(), "can/must be", aval

    return cells_changed
                
def compare_posslists(x,y):
    """Compare list of possibles for cut_possibles: to sort first by
    length then by values"""
    lencmp = cmp(len(x.possibles), len(y.possibles))
    if lencmp == 0:
        return cmp(x.possibles,y.possibles)
    else:
        return lencmp
    
def handle_decided_cells(cell_or_cells):
    if isinstance(cell_or_cells,(list,tuple)):
        # Better be a list.
        cells_decided = cell_or_cells
    else:
        cells_decided = [cell_or_cells]
    while len(cells_decided):
        acell = cells_decided.pop()
        acell.possibles = [acell.type]
        if acell.atotal:
            cells_decided += forbid(acell.atotal.cells, acell.type)
        if acell.dtotal:
            cells_decided += forbid(acell.dtotal.cells, acell.type)

def cut_combos(tot):
    """Given the values that exist in the cells constituting the total,
    eliminate combinations that lack values the cells must be.  Should it 
    also eliminate combos that require values the cells can't have?  Yes.
    Return a nonzero value if any combos have been thus eliminated."""
    if not tot:
        return 0
    ret = 0     
    decided_values = []
    for acell in tot.cells:
        if acell.type != 0:
            decided_values.append(acell.type)
        else:
            # Sorry for being backwards.  If the value isn't decided yet,
            # then we still have a list of possible values.  If any combo
            # has none of the values in a cell's list of possibles, then
            # it's not viable, so kill it.
            for acombo in tuple(tot.combos):
                for aval in acell.possibles:
                    if aval in acombo:
                        break
                else:
                    # This combo has none of the values that this cell can
                    # have.  Therefore it's not viable.
                    ret += 1
                    #print "%%% eliminating", acombo, "from", tot.cell.name()
                    tot.combos.remove(acombo)

    #print "%%% combos for", tot.cell.name(), "mustn't exclude", decided_values
    for aval in decided_values:
        for acombo in tuple(tot.combos):
            if aval not in acombo:
                #print ">>> removing", acombo
                tot.combos.remove(acombo)
                ret += 1
    return ret

def cut_permutes(tot):
    """Given a Total structure whose "permutes" is filled in, cull out
    the permutes that aren't possible given the values of possibles
    in the corresponding cells.  Return nonzero if we cut any."""
    # Create a function to satisfy constraints
    for idx,acell in enumerate(tot.cells):
        if idx == 0:
            mms = "lambda vec: ("
        else:
            mms += " and "
        mms += "vec[" + `idx` + "]"
        if acell.type == 0:
            mms += " in " + `acell.possibles`
        else:
            mms += " == " + `acell.type`
    mms += ")"
    #print "<br> mms is", mms
    mm = eval(mms)
    old_len = len(tot.permutes)
    tot.permutes = [x for x in tot.permutes if mm(x)]
    return old_len - len(tot.permutes) 

def cut_possibles_with_permutes(tot):
    """Given a Total structure whose "permutes" is filled in, trim out
    the allegedly possible values in each cell that aren't possible
    according to the permutations."""
    # realpvs (really possible values) are what the permutations allow.
    # If you just say "zip(tot.permutes)", zip thinks tot.permutes is one
    # argument.  Hence:
    realpvs = apply(zip, tot.permutes)
    # Those are indexed by position.  So let's see if a cell has any
    # "possible" value that isn't in realpvs.
    for acell,arealpvlist in zip(tot.cells, realpvs):
        if acell.type == 0:
            #print "%%%", acell.name(),
            for aval in list(acell.possibles):
                if aval not in arealpvlist:
                    #print aval, "not in", arealpvlist, "\n\t",
                    acell.possibles.remove(aval)
            #print
            if len(acell.possibles) == 1:
                acell.type = acell.possibles[0]
                handle_decided_cells(acell)

def cut_contradictory_possibles(cell1, val1):
    """Given an undecided cell, see if any of its values leads to an 
    impossible situation.  If yes, kill that possibility and return nonzero.
    """
    cval = [(cell1, val1)]      # list of (cell, val) tuples
    for acell, aval in cval:    # we may add some
        if is_impossible(cval, acell, aval):
            cell1.possibles.remove(val1)
            return 1
    return 0

def is_impossible(cval, acell, aval):
    """Given a list of cell/value pairs, a cell and a value from that
    list, inspect the totals of the cell to see if any total is 
    now impossible to achieve given the pairs in the list, returning
    True if so. 
    Along the way, if the proposed value for the cell causes another 
    cell's value to be decided, append said cell/value pair to the list."""
    for atot in acell.atotal, acell.dtotal:
        if atot is None:
            continue
        #print "%%% checking", acell.name(), atot.kind
        possible_permutes = list()      # allowable permutations
        screen_array = list()           # which item#, val to check for
        for c0,v0 in cval:
            if c0 in atot.cells:
                screen_array.append((atot.cells.index(c0), v0))
        if screen_array[0][1] == 10:
            print "really can't happen; we should trap on the 'if'"
        for aperm in atot.permutes:
            for p0,v0 in screen_array:
                if aperm[p0] != v0:
                    break
            else:
                possible_permutes.append(aperm)
        if len(possible_permutes) == 0:
            #print "--- impossible", screen_array, "<br>"
            return True                 # Something is impossible!
        if len(possible_permutes) == 1:
            # Expand later? to look for commonalities amongst all
            # possible_permutes
            #print "--- unique!", possible_permutes[0], "<br>"
            for c0,v0 in zip(atot.cells, possible_permutes[0]):
                if c0.type == 0 and c0 not in [cv[0] for cv in cval]:
                    cval.append((c0, v0))
        else:
            pass
            #print "--- ambiguous, len was", len(possible_permutes), "<br>"
    return 0
            
def forbid(cell_or_cells, theval):
    """Make sure every cell in cell_or_cells doesn't think it can have theval.
    Return a list of cells whose values are now decided as a result."""
    ret = list()
    if isinstance(cell_or_cells,(list,tuple)):
        clist = cell_or_cells
    else:
        clist = [cell_or_cells]
    for acell in clist:
        if acell.type == 0 and theval in acell.possibles:
            acell.possibles.remove(theval)
            if len(acell.possibles) == 1:
                acell.type = acell.possibles[0]
                ret.append(acell)
                #print ">>>", acell.name(), "=", acell.type
    return ret

def blanks_across(arow, colnum):
    """Return a list of blank cells to the right of arow[colnum].  Abort if
    list is empty or contains only one element."""
    ret = list()
    for acell in arow[colnum+1:]:
        if acell.type not in (GRAY, SUMS):
            acell.atotal = arow[colnum].atotal
            ret.append(acell)
        else:
            break
    if len(ret) < 2:
        print "*** blanks_across: returning", ret, "for", arow, 
        print      "colnum =", colnum
        sys.exit(1)
    return ret

def blanks_down(it, rownum, colnum):
    """Return a list of blank cells below it[rownum][colnum].  Abort if
    list is empty or contains only one element."""
    ret = list()
    for acell in [arow[colnum] for arow in it[rownum+1:]]:
        if acell.type not in (GRAY, SUMS):
            acell.dtotal = it[rownum][colnum].dtotal
            ret.append(acell)
        else:
            break
    if len(ret) < 2:
        print "*** blanks_down: returning", ret, "for row,col =", 
        print      rownum, colnum
        sys.exit(1)
    return ret

def print_puzzle(it):
    BACKGROUNDIMAGE = "graytotals.png"
    BWIDTH = 42                         #pixels
    BHEIGHT = 42
    nrows = len(it)
    ncols = len(it[0])
    unknown_cells = 0
    # Header
    #RRR,  A  ,  B  , etc.
    print "<table border=1 cellspacing=0 cellpadding=0 >"
    print '<tr style="text-align:center"><td>&nbsp;'
    for cnum in range(ncols):
        print '<th width="' + `BWIDTH` + 'px">', col_name[cnum]
    for rnum,arow in enumerate(it):
        print '<tr height="' + `BHEIGHT` + 'px" valign=center ' \
                'style="text-align:center">'
        print "<td><b>", rnum, "</b>"
        for cnum,acell in enumerate(arow):
            if acell.type == GRAY:
                print '<td style="background:#666666">&nbsp;'
            elif acell.type == SUMS:
                print '<td background="' + BACKGROUNDIMAGE + '">'
                print '<table height="100%" width="100%" cellspacing=0 ' \
                        'cellpadding=0>'
                print '<tr height="50%">'
                print '<td style="color:white; text-align:right; ' \
                        'font-family:sans-serif">'
                if acell.atotal:
                    print acell.atotal.sum
                else:
                    print "&nbsp;"
                print '<tr>'
                print '<td style="color:white; text-align:left; ' \
                        'font-family:sans-serif">'
                if acell.dtotal:
                    print acell.dtotal.sum
                else:
                    print "&nbsp;"
                print "</table>"
            elif acell.type == 0:
                unknown_cells += 1
                print "<td>&nbsp;"
            else:
                print '<td style="font-size:larger;',
                print 'font-family:sans-serif">', acell.type
    print "</table>"
    # That's all folks
    if unknown_cells == 0:
        return 0
    # Not quite: if anybody is undecided, say what's in the possibles list
    print "<pre>"
    for arow in it:
        for acell in arow:
            if acell.type == 0:         # undecided
                print "%%%", acell.name(), acell.possibles
    # And combos
    for rnum,arow in enumerate(it):
        for acell in arow:
            if acell.type == SUMS:
                if acell.atotal and acell.atotal.has_undecided():
                    print "$$$", acell.name(), 'across', 
                    if acell.atotal.permutes:
                        print acell.atotal.permutes
                    else:
                        print acell.atotal.combos
                if acell.dtotal and acell.dtotal.has_undecided():
                    print "$$$", acell.name(), 'down',
                    if acell.dtotal.permutes:
                        print acell.dtotal.permutes
                    else:
                        print acell.dtotal.combos
    print "</pre>"
    return unknown_cells

def sums():
    """Return a dictionary of possible cell combos.
    Key is of the form (nsquares, desired_total) -- e.g., (2,6)
    Value is of the form ( set,set...) -- e.g. ( (1,5), (2,4) )
    Each set in the value will be in ascending order and will 
    contain no duplicate digits."""
    ret = dict()

    # Sorry, I think like a binary geek.
    # To get all possible subsets of non-repeating digits, use
    # a binary counter wherein if the 0x1 bit is 1 => 1 is in
    # the set.  If 0x2 is set, 2 is in; if 0x4 is set, 3 is in;
    # Generally if 2^X is set then (X-1) is in.
    bits = (0,1,2,4,8,0x10,0x20,0x40,0x80,0x100)
    for acounter in range(3, 0x1ff+1):
        set_rep = list()
        set_len = 0
        set_sum = 0
        for int1,abit in enumerate(bits):
            # Sloppy, but this'll never be true for 0
            if (acounter & abit) != 0:
                set_rep.append(int1)
                set_len += 1
                set_sum += int1
        if set_len < 2:
            continue
        #print acounter, set_rep
        akey = (set_len, set_sum) 
        dent = list(ret.get(akey, list()))
        dent.append(tuple(set_rep))
        ret[akey] = tuple(dent)
    #print ret
    return ret

def permute(alist):
    """Given a list, return a list of tuples.  Each tuple will be one
    permutation of the original list."""
    if len(alist) < 2:
        return [tuple(alist)]
    if len(alist) == 2:
        t = alist[1], alist[0]
        return [tuple(alist), t]
    # len > 2, so call recursively: take the last element and put it at
    # the beginning of the list all the way to the end.  So if alist=[a,b,c]
    # for example, call with [a,b]; you'll get back [(a,b),(b,a)].  
    # Then return [(c,a,b),(c,b,a),(a,c,b),(b,c,a),(a,b,c),(b,a,c)]
    sublist = permute(alist[:-1])
    ret = list()
    thelast = alist[-1]
    for idx in range(len(alist)):               # last pass is like "append"
        for j in [list(x) for x in sublist]:
            j.insert(idx,thelast)
            ret.append(tuple(j))
    return ret

        
if __name__ == "__main__":
    print """<!--
    k2.py: solve a kakuro puzzle from stdin
    Copyright (C) 2010 Collin Park

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    See &lt;<a href=http://www.gnu.org/licenses/>http://www.gnu.org/licenses/</a>> for full license text.  -->"""
    main(sys.stdin)