#!/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
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
HTML=True
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
while more_to_do:
more_to_do = 0
# 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,HTML) # done with this part
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)
# Calculate permutations.
for atot in utotals:
permutes = list()
for acombo in atot.combos:
permutes += permute(acombo)
atot.permutes = permutes
# Now we can trim permutations and possible values in cells.
more_to_do = 1
while more_to_do:
more_to_do = 0
for atot in utotals:
more_to_do += cut_permutes(atot)
#print "%%%", more_to_do, "permutations removed"
if more_to_do > 0:
for atot in utotals:
cut_possibles_with_permutes(atot)
unknown_cells = print_puzzle(the_puzzle,HTML) # 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
# This is the only time that we force the value without trimmming
# down the possibles. Therefore correct the latter.
tail.possibles = [tail.type]
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
# 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 handle_decided_cells(cells_decided):
while len(cells_decided):
acell = cells_decided.pop()
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 forbid(clist, theval):
"""Make sure every cell in clist doesn't think it can have theval.
Return a list of cells whose values are now decided as a result."""
ret = list()
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, do_html):
nrows = len(it)
ncols = len(it[0])
unknown_cells = 0
# Header
#RRR, A , B , etc.
if do_html:
print ""
print '| '
for cnum in range(ncols):
print " | " , col_name[cnum] , " "
else:
print " ",
for cnum in range(ncols):
print " " + col_name[cnum] + " ",
print
ROWDIVIDER = lambda: sys.stdout.write(" +" + ("-----+" * ncols) + '\n')
ROWDIVIDER()
if do_html:
for rnum,arow in enumerate(it):
print ' |
|---|
'
print "| ", rnum, ""
for cnum,acell in enumerate(arow):
if acell.type == GRAY:
print ' | '
elif acell.type == SUMS:
print ' | '
print ''
print ''
print '| '
if acell.atotal:
print `acell.atotal.sum` + "⇒"
else:
print " "
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 " |
"
else:
for rnum,arow in enumerate(it):
rstring = "%3d|" % rnum
for cnum,acell in enumerate(arow):
if acell.type == GRAY:
rstring += "XXXXX|"
elif acell.type == SUMS:
if acell.dtotal:
c = "%2d" % acell.dtotal.sum + '\\'
else:
c = ' \\'
if acell.atotal:
c += "%2d|" % acell.atotal.sum
else:
c += " |"
rstring += c
elif acell.type == 0:
unknown_cells += 1
rstring += " ___ |"
else:
rstring += "%3d |" % acell.type
print rstring
ROWDIVIDER()
# That's all folks
if unknown_cells == 0:
return 0
# Not quite: if anybody is undecided, say what's in the possibles list
if do_html:
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
if do_html:
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)