import copy

def condense(vals):

    if len(vals) == 0:
	return ""
    ranges = [0]
    ranges += [i+1 for i, v in enumerate(vals[:-1]) if vals[i+1] - v > 1]
    ranges.append(len(vals))
    ranges = zip(ranges[:-1], ranges[1:])    
    def f(l):
	if len(l) > 1:
	    return "%i-%i" % (l[0], l[-1])
	return "%i" % l[0]
    return ", ".join([f(vals[a:b]) for a,b in ranges])


riddle1 = """
1**83***2
57***1***
***5*9*64
7*4**859*
**3*1*4**
*514**3*6
36*7*4***
***6***79
8***52**3
"""
riddle2 = """
 **2*9*1*7 
 *386***** 
 4******** 
 *****5*** 
 **9*1*3** 
 ***4***** 
 ********4 
 *****792* 
 8*6*3*7** 
"""
class Constraint(object):
    def __init__(self, fields):
	self.__fields = fields

    def apply(self, sudoko, all_nums = set(xrange(1,10))):
	changed = False	
	placed = set()
	[placed.update(sudoko[x][y]) for x,y  in self.__fields if len(sudoko[x][y]) == 1]	
	news = []
	for x,y  in self.__fields:
	    old = sudoko[x][y]
	    if len(old) > 1:
		new = old.intersection(all_nums.difference(placed))
		if len(new) == 0:
		    raise ValueError()
		if old != new:
		    changed = True
		sudoko[x][y] = new
		news.append(((x,y), new))
	# naked pair elimination
	if changed:
	    return True
	pair_found = False
	#print "-" * 30
	#print sudoko
	#print "-" * 30
	for i in xrange(2, 5):
	    all = [list(n) for f,n in news if len(n) == i]
	    [l.sort() for l in all]
	    all = [tuple(l) for l in all]
	    all.sort()
	    #print "all ", all
	    for j, l in enumerate(all[:-1]):
		if len(all[j:j+i]) == i and len(set(all[j:j+i])) == 1:
		    np = set(l)
		    #print "naked pair", np
		    for k, (f, n) in enumerate(news):
			if n != np:
			    #print "Adjusted ", f, n
			    new = n.difference(np)
			    if len(new) == 0:
				raise ValueError()

			    if new != n:
				pair_found =True
			    news[k] = (f, new)
	if pair_found:
	    for (x,y), n in news:
		sudoko[x][y] = n
	return pair_found
	    
class Sudoku(object):
    def __init__(self, parent=None):
	if parent is None:
	    self.__field = [[set(xrange(1, 10)) for i in xrange(9)] for j in xrange(9)]
	    self.__constraints = []
	    # row constraints
	    for y in xrange(9):
		self.__constraints.append(Constraint([(x,y) for x in xrange(9)]))
	    # column constraints
	    for x in xrange(9):
		self.__constraints.append(Constraint([(x,y) for y in xrange(9)]))
	    # field constraints
	    for xx in xrange(0,9,3):
		for yy in xrange(0,9,3):
		    self.__constraints.append(Constraint([(x+xx, y+yy) for x in xrange(3) for y in xrange(3)]))
	else:
	    self.__field = copy.deepcopy(parent.__field)
	    self.__constraints = parent.__constraints
	    			 

    def __getitem__(self, index):
	class Column(object):
	    def __init__(self, column, field):
		self.__column = column
		self.__field = field

	    def __setitem__(self, index, value):
		self.__field[self.__column][index] = value

	    def __getitem__(self, index):
		return self.__field[self.__column][index]

	return Column(index, self.__field)

    def __repr__(self):
	res = [[None for i in xrange(9)] for j in xrange(9)]
	col_widths = [0 for i in xrange(9)]
	for x in xrange(9):
	    for y in xrange(9):
		vals = list(self[x][y])
		vals.sort()
		r  = condense(vals)
		res[x][y] = r
		if col_widths[x] < len(r):
		    col_widths[x] = len(r)

	rows = []
	for y in xrange(9):
	    rows.append(" ".join(["%s%s" % (res[x][y], " " * (col_widths[x] - len(res[x][y]))) for x in xrange(9)]))
		    
	return "\n".join(rows)

    def load(self, instance):
	lines = [line for line in instance.split() if line]
	for x in xrange(9):
	    for y in xrange(9):
		v = lines[y][x]
		if v != "*":
		    self[x][y] = set([int(v)])


    def solve(self):
	changed = set([True])
	while True in changed:
	    changed = set([c.apply(self) for c in self.__constraints])
	if not self.solved:
	    #print self
	    def enum_squares():
		sqs = [(len(sq), (pos, sq)) for pos, sq in self.squares if len(sq) > 1]
		sqs.sort()
		for _, (pos, square) in sqs:
		    for v in square:
			yield pos, v
	    for (x, y), v in enum_squares():
		child = Sudoku(self)
		child[x][y] = set([v])
		try:
		    child.solve()
		    if child.solved:
			self.__field = child.__field
			return
		except ValueError:
		    pass
		
    def squares(self):
	for x in xrange(9):
	    for y in xrange(9):
		yield (x,y), self[x][y]
    squares = property(squares)

    def solved(self):
	return len([1 for _, square in self.squares if len(square) == 1]) == 81
    solved = property(solved)



if __name__ == "__main__":
    s = Sudoku()
    s.load(riddle2)
    s.solve()
    print s