你也是数独爱好者吗？AakashJhawar和其他许多人一样，喜欢接受新的挑战。他在学校的时候，每天早上都会玩数独。等我们长大了，随着科技的进步，我们可以让电脑为我们解数独了！只需点击数独的图片，它就会为您填满所有九个方块。叮~这里有数独解析教程，等你来查看~喜欢收集硬核干货的朋友们来看看吧~我们都知道数独是由9×9的格子组成的，每一行、每一列、每一列宫位必填对于1-9的数字，每行、每列、每宫位的数字不能重复。解析数独的整个过程可以分为3个步骤：第一步：从图像中提取数独第二步：提取图像中出现的每个数字第三步：用算法计算数独的解第一步：从ExtractingSudokufrom图像首先需要图像处理。1.图像预处理首先，我们对图像应用高斯模糊，核大小（高，宽）为9。注意核大小必须为正奇数，核必须为正方形。然后对11个最近的邻居进行自适应阈值处理。proc=cv2.GaussianBlur(img.copy(),(9,9),0)proc=cv2.adaptiveThreshold(proc,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C,cv2.THRESH_BINARY,11,2)为了让网格线有非零像素值，我们反转颜色。此外，放大图像以增加网格线的大小。proc=cv2.bitwise_not(proc,proc)kernel=np.array([[0.,1.,0.],[1.,1.,1.],[0.,1.,0.]],np.uint8)proc=cv2.dilate(proc,kernel)阈值处理后的数独图像2.找到最大多边形的角点下一步是找到图像中最大轮廓的4个角点。所以需要找到所有的等高线，按面积从大到小排序，选择面积最大的那条。_,contours,h=cv2.findContours(img.copy(),cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)contours=sorted(contours,key=cv2.contourArea,reverse=True)polygon=contours[0]使用的运算符。带有max和min的itemgetter允许我们获取点的索引。每个点是一个坐标为1的数组，然后用[0]和[1]分别得到x和y。右下角的点（x+y）值最大；左上角的点具有最小的(x+y)值；左下角的点具有最小的(x-y)值；右上角的点具有最大的(x-y)值。bottom_right,_=max(enumerate([pt[0][0]+pt[0][1]forptinpolygon]),key=operator.itemgetter(1))top_left,_=min(enumerate([pt[0][0]+pt[0][1]forptinpolygon]),key=operator.itemgetter(1))bottom_left,_=min(enumerate([pt[0][0]-pt[0][1]forptinpolygon]),key=operator.itemgetter(1))top_right,_=max(enumerate([pt[0][0]-pt[0][1]forptinpolygon]),key=operator.itemgetter(1))现在我们有了4个点的坐标，那么就需要用索引返回4个点的数组。每个点都在它自己的坐标数组中。[polygon[top_left][0],polygon[top_right][0],polygon[bottom_right][0],polygon[bottom_left][0]]最大多边形的四个角3、用数独对图像进行裁剪变形后4坐标，我们需要将图像的矩形部分裁剪并弯曲成类似大小的正方形。由左上角、右上角、右下角和左下角点描述的矩形。注意：将数据类型显式设置为float32或“getPerspectiveTransform”将引发错误。top_left,top_right,bottom_right,bottom_left=crop_rect[0],crop_rect[1],crop_rect[2],crop_rect[3]src=np.array([top_left,top_right,bottom_right,bottom_left],dtype=float32)边=max([distance_between(bottom_right,top_right),distance_between(top_left,bottom_left),distance_between(bottom_right,bottom_left),distance_between(top_left,top_right)])描述一个边长为计算长度的正方形，这是要转向的新视角.接下来要做的就是比较前后4个点，得到倾斜图像的变换矩阵。最后，对原始图像进行变换。dst=np.array([[0,0],[side-1,0],[side-1,side-1],[0,side-1]],dtype=float32)m=cv2.getPerspectiveTransform(src,dst)cv2.warpPerspective(img,m,(int(side),int(side)))裁剪和变形后的数独图像4.InfergridfromsquareimageInfer81cellsfromsquareimage。我们在这里交换j和i，以便矩形存储在从左到右而不是从上到下读取的列表中。squares=[]side=img.shape[:1]sideside=side[0]/9forjinrange(9):foriinrange(9):p1=(i*side,j*side)#Topleftcornerofaboxp2=((i+1)*side,(j+1)*side)#Bottomrightcornersquares.append((p1,p2))returnssquares5.获取每个数字下一步是从其单元格中提取数字并构建一个数组。digits=[]img=pre_process_image(img.copy(),skip_dilate=True)forsquareinsquares:digits.append(extract_digit(img,square,size))extract_digit是从一个数独方块中提取一个数（如果有的话）的函数。它从整个盒子中得到数字框，使用填充特征查找得到盒子中间最大的特征，希望在边缘找到属于该数字的像素，并定义中间区域。接下来，需要对数字进行缩放和填充，使数字大小的平方适合机器学习。同时，我们必须忽略任何小边界。defextract_digit(img,rect,size):digit=cut_from_rect(img,rect)h,w=digit.shape[:2]margin=int(np.mean([h,w])/2.5)_,bbox,种子=find_largest_feature(digit,[margin,margin],[w-margin,h-margin])digit=cut_from_rect(digit,bbox)w=bbox[1][0]-bbox[0][0]h=bbox[1][1]-bbox[0][1]ifw>0andh>0and(w*h)>100andlen(digit)>0:returnsscale_and_centre(digit,size,4)else:returnnp.zeros((size,size),np.uint8)最终的数独图像现在我们有了最终的数独预处理图像，接下来的任务就是提取图像中的每个数字并将其存储在矩阵中，然后通过一些算法计算出数独的解。第2步：提取图像中出现的每个数字对于数字识别，我们将在MNIST数据集上训练神经网络，该数据集包含从0到9的60,000个数字图像。首先导入所有库。importnumpyimportcv2fromkeras.datasetsimportmnistfromkeras.modelsimportSequentialfromkeras.layersimportDensefromkeras.layersimportDropoutfromkeras.layersimportFlattenfromkeras.layers.convolutionalimportConv2Dfromkeras.layers.convolutionalimportMaxPooling2Dfromkeras.utilsimportnp_utilsfromkerasimportbackendasKimportmatplotlib.pyplotasplt需要修复随机种子以确保可重复性。K.set_image_dim_ordering(th)seed=7numpy.random.seed(seed)(X_train,y_train),(X_test,y_test)=mnist.load_data()然后将图像reshape成samples*pixels*width*height，输入从0-255归一化为0-1。在此之后，one-hot编码输出。X_trainX_train=X_train.reshape(X_train.shape[0],1,28,28).astype(float32)X_testX_test=X_test.reshape(X_test.shape[0],1,28,28).astype(float32)X_trainX_train=X_train/255X_testX_test=X_test/255y_train=np_utils.to_categorical(y_train)y_test=np_utils.to_categorical(y_test)num_classes=y_test.shape[1]接下来，我们将创建一个模型来预测手写数字。model=Sequential()model.add(Conv2D(32,(5,5),input_shape=(1,28,28),activation=relu))model.add(MaxPooling2D(pool_size=(2,2)))model.add(Conv2D(16,(3,3),activation=relu))model.add(MaxPooling2D(pool_size=(2,2)))model.add(Dropout(0.2))model.add(Flatten())model.add(Dense(128,activation=relu))model.add(Dense(64,activation=relu))model.add(Dense(num_classes,activation=softmax))模型总结创建模型后，需要已编译，将其拟合到数据集并对其进行评估。model.compile(loss=categorical_crossentropy,optimizer=adam,metrics=[accuracy])model.fit(X_train,y_train,validation_data=(X_test,y_test),epochs=10,batch_size=200)scores=model.evaluate(X_test,y_test,verbose=0)print("LargeCNNError:%.2f%%"%(100-scores[1]*100))现在，可以测试上面创建的模型了。test_images=X_test[1:5]test_imagestest_images=test_images.reshape(test_images.shape[0],28,28)print("Testimagesshape:{}".format(test_images.shape))fori,test_imageinumerate(test_images,start=1):org_image=test_imagetest_imagetest_image=test_image.reshape(1,1,28,28)prediction=model.predict_classes(test_image,verbose=0)print("Predicteddigit:{}".format(prediction[0]))plt.subplot(220+i)plt.axis(off)plt.title("Predicteddigit:{}".format(prediction[0]))plt.imshow(org_image,cmap=plt.get_cmap(gray))plt.show()手写数字分类模型预测数字，神经网络准确率高达98.314%！最后，保存序列模型，这样您就不必在需要使用它时重新训练它。#serializemodeltoJSONmodelmodel_json=model.to_json()withopen("model.json","w")asjson_file:json_file.write(model_json)#serializeweightstoHDF5model.save_weights("model.h5")print("Savedmodeltodisk")更多关于手写数字识别资料：https://github.com/aakashjhawar/Handwritten-Digit-Recognition接下来就是加载预训练好的模型了。json_file=open(model.json,r)loaded_model_json=json_file.read()json_file.close()loaded_model=model_from_json(loaded_model_json)loaded_model.load_weights("model.h5")调整图像大小并将图像分成9x9小图像。每个小图像都有一个1-9的数字。数独=cv2.resize(数独,(450,450))grid=np.zeros([9,9])foriinrange(9):forjinrange(9):image=数独[i*50:(i+1)*50,j*50:(j+1)*50]ifimage.sum()>25000:grid[i][j]=identify_number(image)否则：grid[i][j]=0gridgrid=grid.astype(int)identify_number函数获取数字图像并预测图像中的数字。defidentify_number(图像):image_resize=cv2.resize(image,(28,28))#Forplt.imshowimage_resizeimage_resize_2=image_resize.reshape(1,1,28,28)#Forinputtomodel.predict_classes#cv2.imshow(number,image_test_1)loaded_modelloaded_model_pred=loaded_model.predict_classes(image_resize_2,verbose=0)returnloaded_model_pred[0]完成上述步骤后，数独网格看起来像这样：ExtractedSudokuStep3:CalculatethesolutionofSudokuwiththebacktrackingalgorithm我们将使用回溯算法来计算数独的解决方案。在网格中搜索仍未分配的条目。如果找到引用参数行，则将col设置为未分配的位置并返回true。如果没有未分配的条目，则返回false。“l”是solve_sudoku函数传递的列表变量，用于跟踪行和列的增量。deffind_empty_location(arr,l):forrowinrange(9):forcolinrange(9):if(arr[row][col]==0):l[0]=rowl[1]=colreturnTrueturnFalse返回一个布尔值，指示指定的行是否有任何分配匹配给定的数字。defused_in_row(arr,row,num):foriinrange(9):if(arr[row][i]==num):returnTruereturnFalse返回一个布尔值，指示指定列中的任何分配是否与给定数字匹配。defused_in_col(arr,col,num):foriinrange(9):if(arr[i][col]==num):returnTruereturnFalse返回一个布尔值，指示指定3x3框中的任何分配是否与给定数字匹配。defused_in_box(arr,row,col,num):foriinrange(3):forjinrange(3):if(arr[i+row][j+col]==num):returnTruereturnFalse检查将num分配给given(row,col)是合法的。检查“num”是否已经放置在当前行、当前列和当前3x3框中。defcheck_location_is_safe(arr,row,col,num):返回notused_in_row(arr,row,num)和notused_in_col(arr,col,num)和notused_in_box(arr,row-row%3,col-col%3,num)部分使用填充网格，并尝试为所有满足数独解法要求的未赋值位置赋值（跨行、跨列、跨框不重复）。“l”是一个列表变量，保存了find_empty_location函数中的行列记录。将我们从上述函数中获得的行和列分配给列表值。defsolve_sudoku(arr):l=[0,0]if(notfind_empty_location(arr,l)):returnTruerow=l[0]col=l[1]fornuminrange(1,10):if(check_location_is_safe(arr,row,col,num)):arr[row][col]=numif(solve_sudoku(arr)):returnTrue#failure,unmake&tryagainarr[row][col]=0returnFalse最后就是打印网格。defprint_grid(arr):foriinrange(9):forjinrange(9):print(arr[i][j])print()最后在main函数中整合所有函数。defsudoku_solver(grid):if(solve_sudoku(grid)):print(---)else:print("Nosolutionexists")gridgrid=grid.astype(int)returngrid该函数的输出将是最终解出的数独。最后的解决方案当然，这个解决方案绝非万无一失，处理图片还是会出现一些问题，要么无法解析，要么解析不正确无法处理。但是，我们的目标是探索新技术，从这个角度来看，这个项目还是很有价值的。
