|
|
|
|
|
|
|
|
|
|
|
"""
|
|
|
|
|
|
@Author: packy945
|
|
|
|
|
|
@FileName: data.py
|
|
|
|
|
|
@DateTime: 2023/4/27 17:42
|
|
|
|
|
|
@SoftWare: PyCharm
|
|
|
|
|
|
"""
|
|
|
|
|
|
# -*- encoding: utf-8 -*-
|
|
|
|
|
|
import numpy as np
|
|
|
|
|
|
import random
|
|
|
|
|
|
from collections import Counter
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def Init():
|
|
|
|
|
|
# 构建9*9数组
|
|
|
|
|
|
martix = np.zeros((9, 9), dtype='i1') # 初始化9*9数组并赋值0
|
|
|
|
|
|
for row in range(0, 9):
|
|
|
|
|
|
for col in range(0, 9):
|
|
|
|
|
|
value = random.randint(0, 9)
|
|
|
|
|
|
martix[row, col] = value # 给9*9数组martix随机赋值
|
|
|
|
|
|
return martix
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def Judge(martix):
|
|
|
|
|
|
# 计算整个数组是否符合要求
|
|
|
|
|
|
for row in range(0, 9):
|
|
|
|
|
|
for col in range(0, 9):
|
|
|
|
|
|
if martix[row][col] == 0:
|
|
|
|
|
|
continue
|
|
|
|
|
|
m, n = row // 3, col // 3 # [m, n] 为宫位置, 即九个小格子为一个宫
|
|
|
|
|
|
row_martix = martix[row, :] # [row, col] 所在行的数字数组
|
|
|
|
|
|
row_set = set(row_martix) - {0} # [row, col] 所在行的数字集合（1~9）
|
|
|
|
|
|
col_martix = martix[:, col] # [row, col] 所在列的数字数组
|
|
|
|
|
|
col_set = set(col_martix) - {0} # [row, col] 所在列的数字集合（1~9）
|
|
|
|
|
|
block_martix = martix[m * 3: m * 3 + 3, n * 3: n * 3 + 3].reshape(9) # [row, col] 所在的宫的数字数组
|
|
|
|
|
|
block_set = set(block_martix) - {0} # [row, col] 所在的宫的数字集合（1~9）
|
|
|
|
|
|
if len(row_martix) != (len(row_set) + Counter(row_martix)[0]):
|
|
|
|
|
|
return False #若集合里的数字个数（不包括0）加上0的个数小于9，说明有非0的数字重复
|
|
|
|
|
|
if len(col_martix) != (len(col_set) + Counter(col_martix)[0]):
|
|
|
|
|
|
return False #若行、列、九宫格有非0的数字重复，则说明不满足数独要求
|
|
|
|
|
|
if len(block_martix) != (len(block_set) + Counter(block_martix)[0]):
|
|
|
|
|
|
return False
|
|
|
|
|
|
return True #若全部满足要求，则返回判断成功
|
|
|
|
|
|
|
|
|
|
|
|
def GetPossible(martix, row, col):# 获取一个格子里可能可以填的值
|
|
|
|
|
|
|
|
|
|
|
|
Nums = {1, 2, 3, 4, 5, 6, 7, 8, 9}
|
|
|
|
|
|
Set = set()
|
|
|
|
|
|
m, n = row // 3, col // 3 # 计算所在九宫格的编号
|
|
|
|
|
|
for i in range(9):
|
|
|
|
|
|
if i == row:
|
|
|
|
|
|
continue
|
|
|
|
|
|
Set.add(martix[i][col])# 将所在列出现数字加入集合
|
|
|
|
|
|
for j in range(9):
|
|
|
|
|
|
if j == col:
|
|
|
|
|
|
continue
|
|
|
|
|
|
Set.add(martix[row][j])# 将所在行出现数字加入集合
|
|
|
|
|
|
for i in range(m * 3, m * 3 + 3):
|
|
|
|
|
|
for j in range(n * 3, n * 3 + 3):
|
|
|
|
|
|
if row == i and j == col:
|
|
|
|
|
|
continue
|
|
|
|
|
|
Set.add(martix[i][j])# 将所在九宫格出现数字加入集合
|
|
|
|
|
|
return Nums - Set # 返回1~9中没出现过的数字，即可选的值
|
|
|
|
|
|
|
|
|
|
|
|
def Solve(martix):
|
|
|
|
|
|
"""求解数组"""
|
|
|
|
|
|
for i in range(9):
|
|
|
|
|
|
row = (i + 5) % 9
|
|
|
|
|
|
for j in range(9):
|
|
|
|
|
|
col = (j + 4) % 9
|
|
|
|
|
|
if martix[row, col] == 0:
|
|
|
|
|
|
possible = GetPossible(martix, row, col) # 所有的可能的数字
|
|
|
|
|
|
for value in possible:
|
|
|
|
|
|
martix[row, col] = value # 将可能的数组填入
|
|
|
|
|
|
if Solve(martix): # 继续深度优先遍历填入数字
|
|
|
|
|
|
return True # 填完最后一个数字
|
|
|
|
|
|
martix[row, col] = 0 # 如果当前状况无解则归位，然后回溯
|
|
|
|
|
|
return False
|
|
|
|
|
|
# 当所有的数字填完,数独求解完毕
|
|
|
|
|
|
return True
|
|
|
|
|
|
|
|
|
|
|
|
def question(martix):#随机生成一个数独
|
|
|
|
|
|
for row in range(9):
|
|
|
|
|
|
for col in range(9):
|
|
|
|
|
|
if martix[row, col] == 0:
|
|
|
|
|
|
possible = GetPossible(martix, row, col) # 所有的可能的数字
|
|
|
|
|
|
ran_possible = list(possible) #将可能值集合转为列表
|
|
|
|
|
|
random.shuffle(ran_possible)#随机打乱可能值列表
|
|
|
|
|
|
for value in ran_possible:#逐个选择可能值列表
|
|
|
|
|
|
martix[row, col] = value # 将可能的数组填入
|
|
|
|
|
|
if question(martix): # 继续深度优先遍历填入数字
|
|
|
|
|
|
return True # 填完最后一个数字
|
|
|
|
|
|
martix[row, col] = 0 # 如果当前状况无解则归位，然后回溯
|
|
|
|
|
|
return False
|
|
|
|
|
|
return True# 当所有的数字填完,数独求解完毕
|
|
|
|
|
|
|
|
|
|
|
|
def InitMartix(n):
|
|
|
|
|
|
'''
|
|
|
|
|
|
创建一个符合要求的带空数组
|
|
|
|
|
|
:return: 生产完成的数组
|
|
|
|
|
|
'''
|
|
|
|
|
|
martix = np.zeros((9, 9), dtype='i1')
|
|
|
|
|
|
question(martix) # 随机生成一个数独题目
|
|
|
|
|
|
while n:
|
|
|
|
|
|
row = random.randint(0, 8)#随机生成一个行数
|
|
|
|
|
|
col = random.randint(0, 8)#随机生成一个列数
|
|
|
|
|
|
if not martix[row][col] == 0:
|
|
|
|
|
|
martix[row][col] = 0#若该格不为空，则置为空
|
|
|
|
|
|
n -= 1#空格数减一
|
|
|
|
|
|
return martix
|
|
|
|
|
|
|
|
|
|
|
|
def InitMartix_new():
|
|
|
|
|
|
'''
|
|
|
|
|
|
创建一个符合要求的带空数组
|
|
|
|
|
|
:return: 生产完成的数组
|
|
|
|
|
|
'''
|
|
|
|
|
|
martix = np.zeros((9, 9), dtype='i1')
|
|
|
|
|
|
question(martix) # 随机生成一个数独题目
|
|
|
|
|
|
for i in range(9):
|
|
|
|
|
|
for j in range(9):
|
|
|
|
|
|
x = random.randint(-50, 100)#生成随机数
|
|
|
|
|
|
if x < 0:#根据随机数来决定该格子是否显示
|
|
|
|
|
|
martix[i][j] = 0 # 若该格不为空，则置为空
|
|
|
|
|
|
return martix
|
