Sudoku

def quadfinder(find): # to figure out which quad to check for a position while solving
    global quad_position
    for quadcount in range(0, 9):
        if find in quad_position[quadcount]:
            return quadcount

print "Welcome to Daniel Veazey's Sudoku Solver 7."
print "http://www.danielveazey.com"
print "Please fill in the available numbers on the board,"
print "starting on the top row (Row 1), going left to right."
print "If a square is blank, put a 0 in its place."
print "Separate each position with a comma and a space."
print "Each position can be only one digit, 0 through 9."
print "Example:"
print "Row 1: 5, 6, 0, 0, 4, 1, 0, 0, 8"
print "Row 2: 1, 0, 0, 0, 0, 9, 0, 7, 0"
print "etc."
print
print "Let's get started."
print
print

## ask the user to populate the board by rows
row = [0, 1, 2, 3, 4, 5, 6, 7, 8]
for x in range(0, 9):
    row[x] = list(input("Row " + str(x+1) + ": "))

print
print
print "Original board:"
for x in range (0, 9):
    print row[x]

## define and populate the columns by referring to the rows
col = [0, 1, 2, 3, 4, 5, 6, 7, 8]
for x in range (0, 9):
    col[x] = [row[0][x], row[1][x], row[2][x], row[3][x], row[4][x], row[5][x], row[6][x], row[7][x], row[8][x]]

## define and populate quads by referring to slices of rows
quad = [0, 1, 2, 3, 4, 5, 6, 7, 8]
quad[0] = row[0][0:3] + row[1][0:3] + row[2][0:3]
quad[1] = row[0][3:6] + row[1][3:6] + row[2][3:6]
quad[2] = row[0][6:] + row[1][6:] + row[2][6:]
quad[3] = row[3][0:3] + row[4][0:3] + row[5][0:3]
quad[4] = row[3][3:6] + row[4][3:6] + row[5][3:6]
quad[5] = row[3][6:] + row[4][6:] + row[5][6:]
quad[6] = row[6][0:3] + row[7][0:3] + row[8][0:3]
quad[7] = row[6][3:6] + row[7][3:6] + row[8][3:6]
quad[8] = row[6][6:] + row[7][6:] + row[8][6:]

## populate list of single positions
position = list()
for z in range(0, 81):
    for x in range(0, 9):
        for y in range(0, 9):
            position.append(row[x][y])

## put list of possible answers in unsolved single positions
for x in range(0, 81):
    if position[x] == 0:
        position[x] = [1, 2, 3, 4, 5, 6, 7, 8, 9]

## define which positions are in which quads
quad_position = [0, 1, 2, 3, 4, 5, 6, 7, 8]
quad_position[0] = [0, 1, 2, 9, 10, 11, 18, 19, 20]
quad_position[1] = [3, 4, 5, 12, 13, 14, 21, 22, 23]
quad_position[2] = [6, 7, 8, 15, 16, 17, 24, 25, 26]
quad_position[3] = [27, 28, 29, 36, 37, 38, 45, 46, 47]
quad_position[4] = [30, 31, 32, 39, 40, 41, 48, 49, 50]
quad_position[5] = [33, 34, 35, 42, 43, 44, 51, 52, 53]
quad_position[6] = [54, 55, 56, 63, 64, 65, 72, 73, 74]
quad_position[7] = [57, 58, 59, 66, 67, 68, 75, 76, 77]
quad_position[8] = [60, 61, 62, 69, 70, 71, 78, 79, 80]

################# SOLVING ######################################
## this program uses only a very simple method to solve the puzzle,
## just checking to see if a possible answer for a position
## is already in its row, column or quad. if so, the possible answer
## is eliminated from the list of possible answers.

did_change = True
while did_change == True:
    did_change = False
    for x in range(0, 81):
        if type(position[x]) == list:
            y = 0
            while type(position[x]) == list and y < len(position[x]): # to only keep checking if there are more items in the list of possible answers
                # check to see if the possible answer is already in a position in the row, column or quad
                if position[x][y] in row[x/9] or position[x][y] in col[x%9] or position[x][y] in quad[quadfinder(x)]: # quadfinder tells us which quad to check
                    del position[x][y] ## delete the possible answer if it's found elsewhere
                    did_change = True ## to keep the loop going
                    if len(position[x]) == 1: ## if list of possible answers is only one item long,
                        position[x] = position[x][0] ## remove the nested list
                        row[x/9][x%9] = position[x] ## and copy the answer to the rows,
                        col[x%9][x/9] = position[x] ## columns,
                        for quad_count in range(0, 9): ## and quads
                            if x in quad_position[quad_count]: ## similar to function quadfinder(), but used on its own here
                                for z in range(0, 9):
                                    if x == quad_position[quad_count][z]:
                                        quad[quad_count][z] = position[x]
                else: y = y + 1 # to check the next item in the list of possible answers

## additional methods will go here in the future

## find out if the puzzle was solved:
solved = True
for x in range(0, 81):
    if type(position[x]) == list:
        solved = False

if solved == False:
    print
    print
    print "Here is a list of positions with either"
    print "the correct answers or"
    print "a list of possible correct answers:"
    for x in range(0, 81):
        print str(x+1) + ': ' + str(position[x])

    ## also print board by rows
    print
    print
    print "This is as far as I got using the simple method Scroll up"
    print "to see a list of possible answers for each position on the board."
    for x in range (0, 9):
        print row[x]
else:
    print
    print
    print "I SOLVED IT!!!"
    for x in range (0, 9):
        print row[x]