#!/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() 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()+atot.kind, \ "(" + `len(atot.combos)`, "combos) at", stime, permutes = list() for acombo in atot.combos: permutes += [x for x in permute(acombo) if x[0] in atot.cells[0].possibles and x[-1] in atot.cells[-1].possibles] print "#permutes:", len(permutes), print "elapsed", time.clock()-stime, "
" 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() passno += 1 for atot in utotals: more_to_do += cut_permutes(atot) print "%%%", more_to_do, "permutations removed" 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, "
" 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.""" ret = 0 for aperm in list(tot.permutes): is_bad = False for per_val, cposs in zip(aperm, [x.possibles for x in tot.cells]): if per_val not in cposs: is_bad = True # permutation isn't possible break if is_bad: tot.permutes.remove(aperm) ret += 1 return ret 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, "
" 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], "
" 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), "
" 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 "" print '' print "
 ' for cnum in range(ncols): print '', col_name[cnum] for rnum,arow in enumerate(it): print '
", rnum, "" for cnum,acell in enumerate(arow): if acell.type == GRAY: print ' ' elif acell.type == SUMS: print '' print '' print '' print '' print '
' if acell.atotal: print acell.atotal.sum else: print " " print '
' if acell.dtotal: print acell.dtotal.sum else: print " " print "
" elif acell.type == 0: unknown_cells += 1 print "
 " else: print '', acell.type print "
" # That's all folks if unknown_cells == 0: return 0 # Not quite: if anybody is undecided, say what's in the possibles list print "
"
    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 "
" 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 """""" main(sys.stdin)