Python解数独

本文分别使用迭代和回溯（递归）两种方式求解任意大小的标准数独问题。

1.迭代：分别考虑行方向、列方向和区块内的限制条件，通过循环迭代的方式缩减每一单元格的可能取值，并积极判断根据现有可能取值是否已经可以确定该单元格的解。（此方法仅适用于唯一解问题，若解不唯一，仍需在此基础上回溯求可行解）

2.回溯（递归）：对每一单元格任意取满足约束条件的可能值，并向下递归，若无法找到解则向上回溯重新取值。（此方法的实现仅求出一种可行解，感兴趣可以在此基础上扩充求出所有解）

import copy
import math

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

size = len(questions)
# generate size*size candidate answer table
answers = [[questions[i][j] if questions[i][j] else set(range(1,size+1)) for j in range(size)] for i in range(size)]

def generalView():
	while True:
		last_answers = copy.deepcopy(answers)
		# Iterate through each row, update answer table
		for i in range(size):
			for j in range(size):
				if isinstance(answers[i][j],int):
					num = answers[i][j]
					for k in range(size):
						if isinstance(answers[i][k],int):
							continue
						answers[i][k].discard(num)  # discard candidate numbers that occour in the same row
						if len(answers[i][k]) == 1:
							answers[i][k] = answers[i][k].pop()
				else:
					lis = []             # if one of the numbers in the candidate set is the only one in the whole row, that's it
					for k in range(size):
						if k == j:
							continue
						if isinstance(answers[i][k],int):
							lis.append(answers[i][k])
						else:
							lis += list(answers[i][k])
					for k in answers[i][j]:
						if k not in lis:
							answers[i][j] = k
							break

		# Iterate through each column, update answer table
		for j in range(size):
			for i in range(size):
				if isinstance(answers[i][j],int):
					num = answers[i][j]
					for k in range(size):
						if isinstance(answers[k][j],int):
							continue
						answers[k][j].discard(num)
						if len(answers[k][j]) == 1:
							answers[k][j] = answers[k][j].pop()
				else:
					lis = []
					for k in range(size):
						if k == i:
							continue
						if isinstance(answers[k][j],int):
							lis.append(answers[k][j])
						else:
							lis += list(answers[k][j])
					for k in answers[i][j]:
						if k not in lis:
							answers[i][j] = k
							break

		# Iterate through each block, update answer table
		sqrt = int(math.sqrt(size))
		blocks = [[i*sqrt+j for j in range(sqrt)] for i in range(sqrt)]
		for a in range(sqrt):
			for b in range(sqrt):
				for i in blocks[a]:
					for j in blocks[b]:
						if isinstance(answers[i][j],int):
							num = answers[i][j]
							for m in blocks[a]:
								for n in blocks[b]:
									if isinstance(answers[m][n],int):
										continue
									answers[m][n].discard(num)
									if len(answers[m][n]) == 1:
										answers[m][n] = answers[m][n].pop()
						else:
							lis = []
							for m in blocks[a]:
								for n in blocks[b]:
									if m == i and n == j:
										continue
									if isinstance(answers[m][n],int):
										lis.append(answers[m][n])
									else:
										lis += list(answers[m][n])
							for k in answers[i][j]:
								if k not in lis:
									answers[i][j] = k
									break

		if answers == last_answers:
			break

def validate(board, i, j):
	target = board[i][j]
	for a in range(size):
		if a == j:
			continue
		if isinstance(board[i][a],int):
			if target == board[i][a]:
				return False

	for a in range(size):
		if a == i:
			continue
		if isinstance(board[a][j],int):
			if target == board[a][j]:
				return False

	sqrt = int(math.sqrt(size))
	blocks = [[i*sqrt+j for j in range(sqrt)] for i in range(sqrt)]
	for a in blocks[i//sqrt]:
		for b in blocks[j//sqrt]:
			if a == i and b == j:
				continue
			if isinstance(board[a][b],int):
				if target == board[a][b]:
					return False

	return True

def backTracing(board):
	for i in range(size):
		for j in range(size):
			if isinstance(board[i][j],int):
				continue
			for n in board[i][j]:
				new_board = copy.deepcopy(board)
				new_board[i][j] = n
				if validate(new_board,i,j):
					res = backTracing(new_board)
					if res == -1:
						continue
					else:
						return res
				else:
					continue
			else:
				return -1
	return board


answers = backTracing(answers)

for row in answers:
	print(row)