sudoku solver

sudoku.py

sudoku = [
	[None, None, 1, 7, None, None, None, 9, 5],
	[None, None, 7, None, 8, 9, 2, None, 3],
	[None, None, None, 6, None, None, 7, 4, None],
	[2, None, None, None, None, None, None, None, None],
	[None, None, 4, 9, None, 1, 6, None, None],
	[None, None, None, None, None, None, None, None, 8],
	[None, 3, 5, None, None, 4, None, None, None],
	[6, None, 8, 3, 1, None, 9, None, None],
	[1, 7, None, None, None, 6, 5, None, None],
] # this one is 1-hit-ko
sudoku = [
	[None, None, None, None, 3, None, 2, None, None],
	[None, 9, None, 8, None, 7, None, 5, None],
	[None, None, 6, 9, None, None, None, 8, 3],
	[6, None, None, None, None, None, 9, None, 8],
	[None, 2, None, 4, None, 3, None, 1, None],
	[5, None, 3, None, None, None, None, None, 4],
	[1, 6, None, None, None, 8, 3, None, None],
	[None, 3, None, 6, None, 5, None, 7, None],
	[None, None, 7, None, 4, None, None, None, None]
]
sudoku = [
	[1, None, None, None, None, 7, None, 9, None],
	[None, 3, None, None, 2, None, None, None, 8],
	[None, None, 9, 6, None, None, 5, None, None],
	[None, None, 5, 3, None, None, 9, None, None],
	[None, 1, None, None, 8, None, None, None, 2],
	[6, None, None, None, None, 4, None, None, None],
	[3, None, None, None, None, None, None, 1, None],
	[None, 4, None, None, None, None, None, None, 7],
	[None, None, 7, None, None, None, 3, None, None]
]
sudoku = [
	[None]*9
]*9

def get_region(num):
	# region is the zone that is guarded by bold border
	if num <= 2:
		return 0
	elif num <= 5:
		return 1
	else:
		return 2

def allowed(tbl, x, y):
	# get a list of numbers allowed in this field
	num = range(1, 10)
	# look horizontally
	for lineMem in tbl[y]:
		if lineMem:
			try:
				num.remove(lineMem)
			except ValueError:
				pass
	# look vertically
	for heightMem in range(9):
		try:
			num.remove(tbl[heightMem][x])
		except ValueError:
			pass
	# look in the same bounding box
	regionX = get_region(x)
	regionY = get_region(y)
	for ry in range(regionY*3, (regionY*3) + 3):
		for rx in range(regionX*3, (regionX*3) + 3):
			try:
				num.remove(tbl[ry][rx])
			except ValueError:
				pass
	return num

def gen_prob_or_assign(tbl):
	# run allowed() on all cells that is not filled
	# recursively
	didAssign = False
	for y in range(9):
		for x in range(9):
			if type(tbl[y][x]) != int:
				tbl[y][x] = allowed(tbl, x, y)
				if len(tbl[y][x]) == 0:
					print x, y
					raise Exception, "cannot be solved"
				elif len(tbl[y][x]) == 1:
					tbl[y][x] = tbl[y][x][0]
					didAssign = True
	if didAssign:
		# some number were solved, try again
		# this can solve some "easy" tables
		return gen_prob_or_assign(tbl)
	return tbl

def get_linked(tbl, myX, myY):
	# get value of fields that are blocking this field's choice
	out = []
	# horizontal
	for x in range(9):
		if myX == x:
			continue
		out.append(tbl[myY][x])
	# vertical
	for y in range(9):
		if myY == y:
			continue
		out.append(tbl[y][myX])
	# region
	regionX = get_region(myX)
	regionY = get_region(myY)
	for ry in range(regionY*3, (regionY*3) + 3):
		for rx in range(regionX*3, (regionX*3) + 3):
			if rx != myX and ry != myY:
				out.append(tbl[ry][rx])
	return out

def copy(x):
	x = x[::]
	for i in range(len(x)):
		if type(x[i]) == list:
			x[i] = x[i][::]
	return x


def pick(tbl,level=0):
	# it's ALL PICK! but try to draft the best numbers first
	# where to?
	targetX = -1
	targetY = -1
	for y in range(9):
		for x in range(9):
			if type(tbl[y][x]) == list:
				targetX = x
				targetY = y
				mine = tbl[y][x]
				break
		if targetY != -1:
			break
	if targetX == -1 or targetY == -1:
		# TODO: Table is already solved
		return tbl
	cnt = {}
	for x in mine:
		cnt[x] = 0
	for opt in get_linked(tbl, targetX, targetY):
		if type(opt) == list:
			for x in opt:
				if x not in mine:
					continue
				if x in cnt:
					cnt[x] += 1
		elif type(opt) == int:
			if opt in cnt:
				del cnt[opt]
	cnt = sorted(cnt.iteritems(), key=lambda x: x[1])
	out = False
	for x in cnt:
		# try this one
		cpy = copy(tbl)
		cpy[targetY][targetX] = x[0]
		print ">"*level + "Pos %s, %s trying pick %s score %s (less is better)"%(targetX, targetY, x[0], x[1])
		#dbg_print(cpy)
		picked = pick(cpy, level+1)
		if picked:
			out = picked
			break
	return out


def dbg_print(tbl):
	# helper function
	def pp(x):
		# print helper
		if x == None:
			return "-"
		elif type(x) == list:
			return "(" + (",".join([str(x) for x in x])) + ")"
		return str(x)
	for row in tbl:
		print " ".join([pp(x) for x in row])

def solve(tbl):
	tbl = gen_prob_or_assign(sudoku)
	out = pick(tbl)
	dbg_print(out)

#print allowed(sudoku, 7, 1)
solve(sudoku)