A sudoku solver created while I was very tired.

ugly_sudokusolver.py

# usage: just import this file and use the solve_sudoku function with your own sudokus
# this ↓ is how a sudoku is structured: a list with 81 fields (read row-by-row or column-by-column)
TEST_SUDOKU = [
	None, None, None,    8,    1,    3,    5,    4, None,
	   2, None,    1, None,    4,    5, None,    6,    3,
	None,    4, None, None, None, None, None, None, None,
	None, None, None, None,    2, None, None, None,    9,
	None, None,    9, None, None, None,    2, None, None,
	   7, None, None, None,    3,    4, None, None, None,
	None, None, None, None, None, None, None,    9, None,
	   5, None, None,    3, None, None,    1, None,    4,
	None,    2,    7,    4,    5,    9,    3, None, None
]

HARD_SUDOKU = [
	None, None, None, None,    5, None, None, None, None,
	   9, None,    6, None, None, None,    3, None,    7,
	None, None, None,    4, None,    9, None, None, None,
	None,    1, None, None, None, None, None,    5, None,
	   2, None, None,    6, None,    7, None, None,    1,
	None,    4, None, None, None, None, None,    9, None,
	None, None, None,    7, None,    1, None, None, None,
	   7, None,    9, None, None, None,    2, None,    6,
	None, None, None, None,    3, None, None, None, None
]

def get_row(sudoku, position):
	start = position - position%9
	return sudoku[start:start+9]

def get_column(sudoku, position):
	c = []
	start = position%9
	for i in range(start, start+81, 9):
		c.append(sudoku[i])
	return c

def get_block(sudoku, position):
	b = []
	start = position - position%27
	start += position%9 - position%3
	for y in range(3):
		for x in range(3):
			b.append(sudoku[start+x+y*9])
	return b

def missing_numbers(l):
	s = set(l)
	return set(i for i in [1,2,3,4,5,6,7,8,9] if i not in s)

def possible_numbers(sudoku, position):
	if sudoku[position]:
		return set()
	
	s =                missing_numbers(get_row(sudoku, position))
	s = s.intersection(missing_numbers(get_column(sudoku, position)))
	s = s.intersection(missing_numbers(get_block(sudoku, position)))
	return s

def presolve_sudoku(sudoku):
	changed = True
	while changed:
		changed = False
		for pos in range(81):
			if not sudoku[pos]:
				sls = possible_numbers(sudoku, pos)
				if len(sls) == 1:
					sudoku[pos] = sls.pop()
					changed = True

def solve_sudoku(sudoku, pos=0):
	while pos < 81 and sudoku[pos]:
		pos += 1
	
	if pos < 81:
		solutions = []
		sls = possible_numbers(sudoku, pos)
		if not sls:
			return solutions
	
		for num in sls:
			sudoku[pos] = num
			solutions.extend(solve_sudoku(sudoku, pos+1))
			sudoku[pos] = None
		return solutions
	else:
		return [list(sudoku)]

def display_sudoku(sudoku):
	sudoku = [i or "_" for i in sudoku]
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[0:9]))
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[9:18]))
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[18:27]))
	print("-----+-----+-----")
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[27:36]))
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[36:45]))
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[45:54]))
	print("-----+-----+-----")
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[54:63]))
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[63:72]))
	print("{0[0]} {0[1]} {0[2]}|{0[3]} {0[4]} {0[5]}|{0[6]} {0[7]} {0[8]}".format(sudoku[72:81]))

if __name__ == "__main__":
	print("----- easy sudoku with multiple possible solutions -----")
	sudoku = TEST_SUDOKU
	display_sudoku(sudoku)
	print("\nPresolving...")
	presolve_sudoku(sudoku)
	display_sudoku(sudoku)
	print("\nSolving...")
	for solution in solve_sudoku(sudoku):
		print("\nSolution found:")
		display_sudoku(solution)
	
	print("\n\n----- harder sudoku -----")
	sudoku = HARD_SUDOKU
	display_sudoku(sudoku)
	print("\nPresolving...")
	presolve_sudoku(sudoku)
	display_sudoku(sudoku)
	print("\nSolving...")
	for solution in solve_sudoku(sudoku):
		print("\nSolution found:")
		display_sudoku(solution)