# My attempt to solve a basic sudoku puzzle

# This is the starting point
# Blank spaces are represented by 0's
start = [[4,0,0,5,0,0,0,1,0],
         [0,3,0,0,0,0,0,0,8],
         [0,0,0,0,2,0,3,0,0],
         [0,0,4,0,0,9,5,0,2],
         [2,0,0,0,0,0,0,0,6],
         [5,0,0,0,0,0,4,3,0],
         [0,0,7,0,0,3,0,0,9],
         [0,0,1,9,6,0,0,8,0],
         [6,0,0,0,1,7,0,4,0]]

# Big, long, ugly answer matrix
ans = [[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
            [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
            [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
            [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
            [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
            [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
            [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
            [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]],
            [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],
            [1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9]]]

changed = True

# Remove numbers that also appear in
# a direct row, column, or square
def rowcolcheck(chk, answ, r, c):
    for numb in chk:
        if answ.__contains__(numb):
            answ.remove(numb)
    ans[r][c] = answ

# If the answer is down to a list of length 1
# then just copy it out of the list to a normal number
def makereal(answ):
    for row in range(9):
        for column in range(9):
            if type(answ[row][column]) == list and len(answ[row][column]) == 1:
                ans[row][column] = answ[row][column][0]

# Defines the 3x3 squares
def defineSquare(r,c):
    numbersUsed = []
    rows = []
    columns = []
    
    if r < 3: rows = [0,1,2]
    elif r < 6: rows = [3,4,5]
    else: rows = [6,7,8]

    if c < 3: columns = [0,1,2]
    elif c < 6: columns = [3,4,5]
    else: columns = [6,7,8]

    for row in rows:
        for column in columns:
            if type(ans[row][column]) != list: numbersUsed.append(ans[row][column])

    return numbersUsed

# Take in 9 sudoku spots in a row
# If one of the spots is the only option
# for a given value, put that value there
def pass9 (listRow,ansRow):
    possibles = []
    yesses = []
    
    for entry in listRow:
       if type(entry) == list:
           for subEntry in entry:
               possibles.append(subEntry)
               
    for n in range(1,10):
        if possibles.count(n) == 1:
            yesses.append(n)

    for z in range(9):
        if type(listRow[z]) == list:
            for yes in yesses:
                if listRow[z].__contains__(yes): ans[ansRow][z] = yes


# Copy the existing answers
for row in range(9):
    for column in range(9):
        if start[row][column] != 0:
            ans[row][column] = start[row][column]

x=1
while (changed):
    otherans = []
    print "iteration", x
    x += 1
    changed = False

    for y in ans:
        otherans.append(y[:])

    # Cancel out rows and columns
    for row in range(9):
        for column in range(9):
            if type(ans[row][column]) != list: continue
            checker = []
            for point in ans[row]:
                if type(point) != list: checker.append(point)
            for point2 in ans:
                if type(point2): checker.append(point2[column])
            for point3 in defineSquare(row,column):
                checker.append(point3)
            rowcolcheck(checker, ans[row][column], row, column)

    makereal(ans)

    if otherans != ans: changed = True
    else:
        for pt in range(9):
            pass9(ans[pt],pt)

        makereal(ans)

        if otherans != ans:
            changed = True


for row in range(9):
    for column in range(9):
        print ans[row][column],
    print