数独（sudoku）盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
明白了原理之后就很简单了，首先我们在代码里生成一个9x9的二维数组。如下图所示，因为第1、第5、第9宫格之间是没有关联的，只需要保证这三个宫格之中都包含1到9的数字就只可以了，所以我们可以生成3组1-9的数字，分别将3组数字打乱顺序后填入蓝色格式，如下图所示。
9x9二维数组
接着我们只需要遍历每个个格子，排除不可填的数字之后，随机给它填入一个数字，如果发现当前格子没有可填的值，则退回去上一个格子，将此格子原有的值排除后再重新选一个新的值填入，如果发现也没有合适的值，再退一个格子....在不停的重复这个过程之后，就可以得到一个正确的数独矩阵，这里用到了深度优先算法和回溯算法。
以下为示例代码：
import random
import math
matrix = []
# 生成一个随机的数组
def get_random_unit():
_num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
random.shuffle(_num_list)
return _num_list
def print_grid(arr):
for i in range(9):
print(arr[i])
def get_row(row):
row_arr = []
for v in matrix[row]:
if v == 0:
continue
row_arr.append(v)
return row_arr
def get_col(col):
col_arr = []
for i in range(9):
val = matrix[i][col]
if val == 0:
continue
col_arr.append(matrix[i][col])
return col_arr
def get_block(num):
col_arr = []
seq = num % 3
col_end = 9 if seq == 0 else seq * 3
row_end = int(math.ceil(num / 3) * 3)
for i in range(row_end - 3, row_end):
for j in range(col_end - 3, col_end):
val = matrix[i][j]
if val != 0:
col_arr.append(matrix[i][j])
return col_arr
def get_block_seq(row, col):
col_seq = int(math.ceil((col + 0.1) / 3))
row_seq = int(math.ceil((row + 0.1) / 3))
return 3 * (row_seq - 1) + col_seq
def get_enable_arr(row, col):
avail_arr = get_random_unit()
seq = get_block_seq(row, col)
block = get_block(seq)
row = get_row(row)
col = get_col(col)
unable_arr = list(set(block + row + col))
for v in unable_arr:
if v in avail_arr:
avail_arr.remove(v)
return avail_arr
def main():
can_num = {}
count = 0
# 初始化一个9行9列的数组
for i in range(9):
matrix.append([0] * 9)
num_list = get_random_unit()
for row in range(3):
for col in range(3):
matrix[row][col] = num_list.pop(0)
num_list = get_random_unit()
for row in range(3, 6):
for col in range(3, 6):
matrix[row][col] = num_list.pop(0)
num_list = get_random_unit()
for row in range(6, 9):
for col in range(6, 9):
matrix[row][col] = num_list.pop(0)
box_list = []
for row in range(9):
for col in range(9):
if matrix[row][col] == 0:
box_list.append({'row': row, 'col': col})
i = 0
while i < len(box_list):
count += 1
position = box_list[i]
row = position['row']
col = position['col']
key = '%dx%d' % (row, col)
if key in can_num:
enable_arr = can_num[key]
else:
enable_arr = get_enable_arr(row, col)
can_num[key] = enable_arr
if len(enable_arr) <= 0:
i -= 1
if key in can_num:
del (can_num[key])
matrix[row][col] = 0
continue
else:
matrix[row][col] = enable_arr.pop()
i += 1
print_grid(matrix)
print(count)
if __name__ == "__main__":
main()
