import xml.dom.minidom, os, time, random
import cv2
from PIL import Image
import pytesseract
import matplotlib.pyplot as plt
import PIL, numpy, time
import pickle
def run_adb_way(adb_command):
process = os.popen(adb_command)
output = process.read()
return output
def go_to_input(x, y):
run_adb_way('adb shell input tap {} {}'.format(x, y))
def get_shudu_png():
t1=time.time()
run_adb_way("adb shell screencap /sdcard/screen.png") # adb shell screencap /sdcard/截图名称
run_adb_way("adb pull /sdcard/screen.png {}\screen.png".format(os.getcwd()))
img = cv2.imread(r'{}\screen.png'.format(os.getcwd()))
x=[]
y=[]
#for i in range(len(img)):、
#for j in range(len(img[i])):
#if 208 in img[i][j] and 134 in img[i][j] and 42 in img[i][j]:#橙色线条的rgb是208,134,42
#if i not in y:
#y.append(i)
#if j not in x:
#x.append(j)
#zuobiao = (x[0],y[0],x[0]+len(x),y[0]+len(y))
zuobiao=(13, 464, 1069, 1520)
img = Image.open(r'{}\screen.png'.format(os.getcwd()))
cropped = img.crop(zuobiao)
cropped.save(r'{}\shudu.png'.format(os.getcwd()))
os.remove(r'{}\screen.png'.format(os.getcwd()))
print('将截屏中的数独单独裁剪出来,耗时{}秒'.format(time.time()-t1))
def get_shuzi():
q=0
img = Image.open(r'{}\shudu.png'.format(os.getcwd()))
shudu=[]
print('正在识别数字中....请稍后')
for i in range(0, 1056, 117)[:-1]:
for j in range(0, 1056, 117)[:-1]:
q+=1
zuobiao = (35, 20, 86, 100)#将数独分割之后再切割
cropped = img.crop((j, i, j + 117, i + 117)).crop(zuobiao)
path=r'{}\shuduqiege\temp{}.png'.format(os.getcwd(),q)
cropped.save(path)
try:
num = get_num(path)
except:
num=0
shudu.append(num)
result=[]
for y in range(0, 9):
for x in range(0, 9):
if x == 0:
result.append([])
result[y].append(shudu[x + y * 9])
return result
def pretreatment(ima):
ima = ima.convert('L')
im = numpy.array(ima)
for i in range(im.shape[0]): # 转化为二值矩阵
for j in range(im.shape[1]):
if im[i, j] == 105 or im[i, j] == 160 or im[i, j] == 126:
im[i, j] = 1
else:
im[i, j] = 0
return im
# 提取图片特征
def feature(A):
midx = int(A.shape[1] / 2) + 1
midy = int(A.shape[0] / 2) + 1
A1 = A[0:midy, 0:midx].mean()
A2 = A[midy:A.shape[0], 0:midx].mean()
A3 = A[0:midy, midx:A.shape[1]].mean()
A4 = A[midy:A.shape[0], midx:A.shape[1]].mean()
A5 = A.mean()
AF = [A1, A2, A3, A4, A5]
return AF
# 切割图片并返回每个子图片特征
def incise(im):
# 竖直切割并返回切割的坐标
a = [];
b = []
if any(im[:, 0] == 1):
a.append(0)
for i in range(im.shape[1] - 1): # 第i列
if all(im[:, i] == 0) and any(im[:, i + 1] == 1): # 判断左边界并选择切割坐标
a.append(i + 1)
elif any(im[:, i] == 1) and all(im[:, i + 1] == 0): # 判断右边界
b.append(i + 1)
if any(im[:, im.shape[1] - 1] == 1):
b.append(im.shape[1])
# 水平切割并返回分割图片特征
names = locals();
AF = []
for i in range(len(a)):
names['na%s' % i] = im[:, range(a[i], b[i])]
if any(names['na%s' % i][0, :] == 1): # 如果第一行含1，则直接从第一行开始截取
c = 0
elif any(names['na%s' % i][names['na%s' % i].shape[0] - 1, :] == 1): # 如果最后一行含1，则直接从最后一行开始截取
d = names['na%s' % i].shape[0] - 1
for j in range(names['na%s' % i].shape[0] - 1): # 每行开始循环
if all(names['na%s' % i][j, :] == 0) and any(names['na%s' % i][j + 1, :] == 1): # 寻找上边界
c = j + 1
elif any(names['na%s' % i][j, :] == 1) and all(names['na%s' % i][j + 1, :] == 0): # 寻找下边界
d = j + 1
names['na%s' % i] = names['na%s' % i][range(c, d), :]
AF.append(feature(names['na%s' % i])) # 提取特征
return AF
def training():
train_set = {}
for i in range(1, 10):
value = []
for j in range(1, 5):
try:
ima = PIL.Image.open('C:\\Users\\m\\Desktop\\shibie\\' + str(i) + '\\' + str(i) + '-' + str(j) + '.png')
im = pretreatment(ima)
AF = incise(im)
value.append(AF[0])
except:
pass
train_set[i] = value
# 把训练结果存为永久文件，以备下次使用
# output=open(r'C:\Users\m\Desktop\train_set.pkl','wb')
# pickle.dump(train_set,output)
# output.close()
return train_set
def distance(v1, v2):
vector1 = numpy.array(v1)
vector2 = numpy.array(v2)
Vector = (vector1 - vector2) ** 2
distance = Vector.sum() ** 0.5
return distance
def knn(train_set, V, k):
key_sort = [9] * k
value_sort = [9] * k
for key in range(1, 10):
for value in train_set[key]:
d = distance(V, value)
for i in range(k):
if d < value_sort[i]:
for j in range(k - 2, i - 1, -1):
key_sort[j + 1] = key_sort[j]
value_sort[j + 1] = value_sort[j]
key_sort[i] = key
value_sort[i] = d
break
max_key_count = -1
key_set = set(key_sort)
for key in key_set:
if max_key_count < key_sort.count(key):
max_key_count = key_sort.count(key)
max_key = key
return max_key
def get_num(ima_path):
ima = PIL.Image.open(ima_path)
im = pretreatment(ima) # 图片预处理
AF = incise(im) # 切割图片并提取特征
train_set = {
1: [[0.16285714285714287, 0.0, 0.6928571428571428, 0.625, 0.3389694041867955],
[0.1746031746031746, 0.0, 0.6928571428571428, 0.625, 0.35720375106564367]],
2: [[0.16326530612244897, 0.28715728715728717, 0.30142857142857143, 0.21515151515151515, 0.24103299856527977],
[0.16054421768707483, 0.28851540616246496, 0.2985714285714286, 0.21029411764705883, 0.23895369388476492]],
3: [[0.1856060606060606, 0.1697860962566845, 0.33611111111111114, 0.31176470588235294, 0.24761904761904763],
[0.17803030303030304, 0.17914438502673796, 0.31805555555555554, 0.3191176470588235, 0.24523809523809523]],
4: [[0.13942857142857143, 0.2109090909090909, 0.27701863354037265, 0.31488801054018445, 0.23223039215686275],
[0.12738095238095237, 0.20955882352941177, 0.32919254658385094, 0.34782608695652173, 0.25131051495528833],
[0.13714285714285715, 0.21212121212121213, 0.31801242236024846, 0.35046113306982873, 0.2503063725490196],
[0.12738095238095237, 0.20955882352941177, 0.32919254658385094, 0.34782608695652173, 0.25131051495528833]],
5: [[0.44027777777777777, 0.20285714285714285, 0.21637426900584794, 0.28421052631578947, 0.28746840014445646],
[0.44027777777777777, 0.20285714285714285, 0.21637426900584794, 0.28421052631578947, 0.28746840014445646]],
6: [[0.34903381642512077, 0.30807453416149067, 0.24735449735449735, 0.28843537414965986, 0.29961587708066584],
[0.34782608695652173, 0.2979539641943734, 0.23677248677248677, 0.28851540616246496, 0.29415584415584417]],
7: [[0.11428571428571428, 0.20202020202020202, 0.37293233082706767, 0.07177033492822966, 0.1900735294117647],
[0.14285714285714285, 0.19624819624819625, 0.3894736842105263, 0.08133971291866028, 0.2025735294117647],
[0.11428571428571428, 0.20202020202020202, 0.37293233082706767, 0.07177033492822966, 0.1900735294117647],
[0.11428571428571428, 0.1976911976911977, 0.3744360902255639, 0.07655502392344497, 0.19044117647058822]],
8: [[0.30434782608695654, 0.30051150895140666, 0.3029100529100529, 0.28711484593837533, 0.29902597402597403],
[0.31313131313131315, 0.3155080213903743, 0.30687830687830686, 0.29411764705882354, 0.30764119601328904],
[0.31691919191919193, 0.3114973262032086, 0.31084656084656087, 0.2913165266106443, 0.3079734219269103],
[0.31691919191919193, 0.3114973262032086, 0.31084656084656087, 0.2913165266106443, 0.3079734219269103]],
9: [[0.2979591836734694, 0.2703081232492997, 0.3157894736842105, 0.3668730650154799, 0.31123188405797103]]}
#train_set = training()
num = knn(train_set, AF, 1)
return num
class SuduKu():
def __init__(self, sudu_ku_data):
if not isinstance(sudu_ku_data, list):
raise TypeError(f'数独必须是一个列表, 但是{sudo_ku_data}却是 {type(sudo_ku_data)}')
if len(sudu_ku_data) != 9 or len(sudu_ku_data[0]) != 9:
raise TypeError(f'数独必须是 9*9 列表, 但是 {sudo_ku_data} 是一个{len(sudo_ku_data)}*{len(sudo_ku_data[0])}的列表')
self.sudo_ku = sudu_ku_data
# 存放每一行已有的数据
self.every_row_data = {}
# 存放每一列已有的数据
self.every_column_data = {}
# 存放每一个3*3已有的数字
self.every_three_to_three_data = {}
# 存放每一个空缺的位置
self.vacant_position = []
# 每一个空缺位置尝试了的数字
self.every_vacant_position_tried_values = {}
# 初始化数据
self._init()
def _add_row_data(self, row, value):
if row not in self.every_row_data:
self.every_row_data[row] = set()
if value in self.every_row_data[row]:
raise TypeError(f'{self.sudo_ku}是个无效数独')
self.every_row_data[row].add(value)
def _add_column_data(self, column, value):
if column not in self.every_column_data:
self.every_column_data[column] = set()
if value in self.every_column_data[column]:
raise TypeError(f'{self.sudo_ku}是个无效数独')
self.every_column_data[column].add(value)
def _get_three_to_three_key(self, row, column):
if row in [0, 1, 2]:
if column in [0, 1, 2]:
key = 1
elif column in [3, 4, 5]:
key = 2
else:
key = 3
elif row in [3, 4, 5]:
if column in [0, 1, 2]:
key = 4
elif column in [3, 4, 5]:
key = 5
else:
key = 6
elif row in [6, 7, 8]:
if column in [0, 1, 2]:
key = 7
elif column in [3, 4, 5]:
key = 8
else:
key = 9
return key
def _add_three_to_three_data(self, row, column, value):
key = self._get_three_to_three_key(row, column)
if key not in self.every_three_to_three_data:
self.every_three_to_three_data[key] = set()
self.every_three_to_three_data[key].add(value)
def _init(self):
for row, row_datas in enumerate(self.sudo_ku):
for column, value in enumerate(row_datas):
if value == 0:
self.vacant_position.append((row, column))
else:
self._add_row_data(row, value)
self._add_column_data(column, value)
self._add_three_to_three_data(row, column, value)
def _judge_value_is_legal(self, row, column, value): # 判断放置的数据是否合法
if value in self.every_row_data[row]:
return False
if value in self.every_column_data[column]:
return False
key = self._get_three_to_three_key(row, column)
if value in self.every_three_to_three_data[key]:
return False
return True
def _calculate(self, vacant_position): # 计算，开始对数独进行放置值
row, column = vacant_position
values = set(range(1, 10))
key = str(row) + str(column) # 对当前为位置创建一个唯一key,用来存放当前位置已经尝试了的数据
if key in self.every_vacant_position_tried_values:
values = values - self.every_vacant_position_tried_values[key]
else:
self.every_vacant_position_tried_values[key] = set()
for value in values:
self.every_vacant_position_tried_values[key].add(value)
if self._judge_value_is_legal(row, column, value): # 如果当前value合法，可以放置
#print(f"{vacant_position}空值的值是{value}")
self.every_column_data[column].add(value)
self.every_row_data[row].add(value)
key = self._get_three_to_three_key(row, column)
self.every_three_to_three_data[key].add(value)
self.sudo_ku[row][column] = value # 修改这个位置的值为value
return True, value # 返回True 和填充的 value
return False, None
def _backtrack(self, current_vacant_position, previous_vacant_position, previous_value):
"""
回溯
:param current_vacant_position: 当前尝试失败的位置
:param previous_vacant_position: 上一次成功的位置
:param previous_value:上一次成功的值
:return:
"""
#print(f"上一次成功的值是{previous_value}，上一次成功的位置是{previous_vacant_position}")
row, column = previous_vacant_position
# 对上一次成功的值从需要用到的判断的数据中移除
self.every_column_data[column].remove(previous_value)
self.every_row_data[row].remove(previous_value)
key = self._get_three_to_three_key(row, column)
self.every_three_to_three_data[key].remove(previous_value)
self.sudo_ku[row][column] = '' # 并且上一次改变的的值变回去
current_row, current_column = current_vacant_position
key = str(current_row) + str(current_column)
self.every_vacant_position_tried_values.pop(key)
def get_result(self):
print('正在计算数独中....请稍后')
q = 0
t1 = time.time()
length = len(self.vacant_position) # 空缺位置的长度
index = 0 # 空缺位置的下标
tried_values = [] # 存放已经尝试了的数据
while index < length:
q += 1
vacant_position = self.vacant_position[index]
is_success, value = self._calculate(vacant_position)
if is_success:
tried_values.append(value)
index += 1
else:
self._backtrack(vacant_position, self.vacant_position[index - 1], tried_values.pop())
index -= 1
if index < 0:
raise ValueError(f"{self.sudo_ku}是无效的数独")
self.show_sudu_ku()
print(time.time() - t1,q)
return self.sudo_ku
def show_sudu_ku(self):
for row in self.sudo_ku:
print(row)
def judge_value_is_legal(row, column, value, sudo_ku): # 判断值是否合法
# column
for i in range(0, 9):
if row == i:
continue
if value == sudo_ku[i][column]:
return False
# row
for i in range(0, 9):
if column == i:
continue
if value == sudo_ku[row][i]:
return False
# three_to_three
for i in range(row // 3 * 3, row // 3 * 3 + 3):
for j in range(column // 3 * 3, column // 3 * 3 + 3):
if i == row and j == column:
continue
if value == sudo_ku[i][j]:
return False
return True
def judge_sudo_ku_is_legal(sudo_ku): # 判断数独是否合法
for row, row_valus in enumerate(sudo_ku):
for column, value in enumerate(row_valus):
if not judge_value_is_legal(row, column, value, sudo_ku):
return False
return True
def shudu_to_screen(SuduKu):
num_xy_dict = dict(zip([num for num in range(1, 10)], [(x, 1982) for x in range(91, 1000, 112)]))#获得备选数字的坐标
num_screen_xy_dict = [(j + 99, i + 550) for i in range(0, 1056, 117)[:-1] for j in range(0, 1056, 117)[:-1]]#获得数独每个单元格的坐标
for i in range(9):
for j in range(9):
x1, y1 = num_xy_dict[SuduKu[i][j]]
x2, y2 = num_screen_xy_dict[i * 9 + j]
# time.sleep(0.1)
go_to_input(x2, y2)#先填数独需要填的单元格坐标
# time.sleep(0.1)
go_to_input(x1, y1)#后点该单元格的正确数字
print(x2, y2, x1, y1, "第{}行第{}列的数字是{}".format(i + 1, j + 1, SuduKu[i][j]))
def main():
get_shudu_png()#获得数独图片
sudo_ku_data = get_shuzi()#数独图片识别未数字数独
shudu_answer = SuduKu(sudo_ku_data).get_result()#解数独
shudu_to_screen(shudu_answer)#将数独的结果传到手机上面
if __name__=='__main__':
main()
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-3-29 13:41:30
置顶卡
千斤顶
显身卡
发表于 2022-3-29 20:07:12
