def solveRows():
    """eliminates solved numbers by row"""
    for x in range(0, 81, 9):
        row = puzzle[x : x+9]#loops through each row
        for space in row: #loops through each space
            if len(space) == 1: #space is solved
                for space2 in row: #loops through spaces again
                    if len(space2) != 1: #space isnt already solved
                        if space[0] in space2: #the solved number is a possibility
                            del space2[space2.index(space[0])] #deletes the number as a possiblbitly                
def solveColumns():
    """eliminates solved numbers by column"""
    rows = []#splits up the puzzle into rows
    for x in range(0, 81, 9):
        rows.append(puzzle[x:x+9])
    for n in range(0, 9):
        column = [x[n] for x in rows] #loops through each column
        #the next part is taken from solveRows()
        for space in column: #loops through each space
            if len(space) == 1: #space is solved
                for space2 in column: #loops through spaces again
                    if len(space2) != 1: #space isnt already solved
                        if space[0] in space2: #the solved number is a possibility
                            del space2[space2.index(space[0])] #deletes the number as a possiblbitly
 
def solveBoxes():
    """eliminates solved numbers by box"""
    rows = []#splits up the puzzle into rows
    for x in range(0, 81, 9):
        rows.append(puzzle[x:x+9])
    #this next part just splits the puzzle into boxes
    for x in range(0, 9, 3):
        for y in range(0, 9, 3):
            tempRows = rows[x:x+3]
            tempBox = [row[y:y+3] for row in tempRows]
            #the next part just formats the box
            #basically it was a list of lists of lists
            #and i need it as a list of lists
            box = []
            for row in tempBox:
                for space in row:
                    box.append(space)
            #the next part is taken from solveRows()
            for space in box: #loops through each space
                if len(space) == 1: #space is solved
                    for space2 in box: #loops through spaces again
                        if len(space2) != 1: #space isnt already solved
                            if space[0] in space2: #the solved number is a possibility
                                del space2[space2.index(space[0])] #deletes the number as a possiblbitly
 
def isSolved():
    """Checks to see if the puzzle is solved"""
    for x in puzzle:
        if len(x) != 1:
            return False
    else:
        return True
 
def main():
    while True:
        temp = puzzle #used to see when puzzle is solved
        solveBoxes()
        solveRows()
        solveColumns()
        if isSolved():#puzzle is solved
            return
 
def display():
    """ displays the puzzle"""
    copy = puzzle #copy of the puzzle
    copy = map(str, [x[0] for x in copy]) #makes the ints strs so i can use S.join()
    #next part just displays the puzzle all nice and pretty
    for x in range(0, 9):
        print ', '.join(copy[x:x+9])
 
def getInput():
    """gets a puzzle to be solved from the user"""
    puzzle = []
    for x in range(1, 10): #1 for each line of the puzzle
        puzzle.append(raw_input('enter one line of the puzzle '))
    puzStr = '\n'.join(puzzle)
    puzzle = []#a soon to be matrix holding possibilities for each space
    for letter in puzStr:
        if letter == 'x':
            puzzle.append(range(1, 10)) #adds all possibilities if square is blank
        elif letter == '\n' or letter ==' ':
            continue
        else:
            puzzle.append([int(letter)]) #adds the already given number
    return puzzle
 
print """This program will solve some suDoku puzzles
If it can't it will just hang indefinately so give it a little
while then if nothing happens assume that either you entered
the puzzle incorrectly, it is not solvable, or this program
can't solve it.
 
Begin by entering the puzzle in line by line.
Represent empty spaces by an 'x'. So a line
migh look like '6x12x897x'. This program as of now
will not catch your errors so try not to make mistakes.
You can but do not have to add any spaces when entering the puzzle.
 
Enjoy!
"""
puzzle = getInput()
main()
print 'The answer is:'
print
display()