c/c++开发分享基于Matlab制作一个数独求解器

讲解一个完整的小项目,顺便说明如何使用整数规划求解数独。1.完整效果2.数独求解(错误示范)首先我们先尝试如果只满足行、列、3×3块加和均为45的等式约束是否有效。即约束为:每行和为45:每列和为45

讲解一个完整的小项目,顺便说明如何使用整数规划求解数独。

1.完整效果

基于Matlab制作一个数独求解器

基于Matlab制作一个数独求解器

2.数独求解(错误示范)

首先我们先尝试如果只满足行、列、3×3块加和均为45的等式约束是否有效。即约束为:

每行和为45:

基于Matlab制作一个数独求解器

每列和为45:

基于Matlab制作一个数独求解器

每个3×3块和为45:

基于Matlab制作一个数独求解器

其中对此编写如下代码:

sudokumat=[1 0 5 0 2 0 0 0 0       0 0 0 7 4 3 0 0 5       3 0 7 0 0 0 0 0 9       0 2 0 0 0 0 4 5 0       0 6 0 4 0 1 0 8 0       0 7 4 0 0 0 0 6 0       2 0 0 0 0 0 3 0 8       4 0 0 8 5 6 0 0 0       0 0 0 0 3 0 5 0 6];  % 记录原本各个数字所在位置,构造等式约束  n0ind=find(sudokumat~=0);   aeq1=zeros(length(n0ind),81);  for i=1:length(n0ind)      aeq1(i,n0ind(i))=1;  end  beq1=sudokumat(sudokumat~=0);    % 行等式约束和列等式约束  aeq2=zeros(9,81);  aeq3=zeros(9,81);  for i=1:9      aeq2(i,(i-1)*9+1:i*9)=1;      aeq3(i,i:9:81)=1;  end  beq2=ones(9,1).*45;  beq3=ones(9,1).*45;    % 3x3块等式约束  aeq4=zeros(9,81);  for i=1:3      for j=1:3          tmat=zeros(9,9);          tmat((i-1)*3+1:i*3,(j-1)*3+1:j*3)=1;          aeq4((i-1)*3+j,:)=tmat(:)';      end  end  beq4=ones(9,1).*45;    f=ones(1,81);    % 不重要,随便设置  intcon=1:81;     % 所有元素都要求为整数  lb=ones(81,1);   % 下限为1  ub=ones(81,1).*9;% 上限为1  aeq=[aeq1;aeq2;aeq3;aeq4];  beq=[beq1;beq2;beq3;beq4];  % 求解整数规划  x=intlinprog(f,intcon,[],[],aeq,beq,lb,ub);  % 重新 构造数独矩阵  x=reshape(x,[9,9])

那么,这么简单就能够解决数独了嘛???

当然不行。。。。

上述程序运行结果为:

1 8 5 6 2 9 9 1 4
2 9 9 7 4 3 5 1 5
3 1 7 1 4 9 8 3 9
7 2 1 8 9 4 4 5 5
9 6 1 4 1 1 9 8 6
8 7 4 1 8 9 1 6 1
2 1 9 1 9 3 3 9 8
4 9 8 8 5 6 1 3 1
9 2 1 9 3 1 5 9 6

可以发现我们的约束确实保证了三种加和都是45,但是不能保证同行、同列、同3×3块内不出现同样的数字,那咋办,总不能一个元素一个元素添加不相等信息吧、我们怎样能让矩阵包含更多的信息,更方便的阐述各个元素之间的联系呢?

3.数独求解(升维)

欸,我们原本是9×9大小的矩阵,要描述每个元素和同一行各个元素、和同一列各个元素之间的联系,一个很自然的想法就是升维!

将9×9的数独矩阵转化为9×9×9的三维矩阵(张量),此时x(i,j,k)=1意味原矩阵第i行,第j列的元素为k,整个整数规划从现在开始变成了0-1规划,要想同一行的数值都不一样,只需要所有的行纤维的和都是1,想要同一列的数值都不一样,只需要所有列纤维的和都是1,非常奇妙的,我们又把问题转换为了一个线性求和的问题,very amazing啊!

此时约束条件变为:

原矩阵每个小格子只能有一个数值:

基于Matlab制作一个数独求解器

原矩阵每一行的各个数字均不同:

基于Matlab制作一个数独求解器

原矩阵每一列的各个数字均不同:

基于Matlab制作一个数独求解器

原矩阵每一个3×3块各个数字均不同:

基于Matlab制作一个数独求解器

其中因此编写如下代码

sudokumat=[1 0 5 0 2 0 0 0 0       0 0 0 7 4 3 0 0 5       3 0 7 0 0 0 0 0 9       0 2 0 0 0 0 4 5 0       0 6 0 4 0 1 0 8 0       0 7 4 0 0 0 0 6 0       2 0 0 0 0 0 3 0 8       4 0 0 8 5 6 0 0 0       0 0 0 0 3 0 5 0 6];    % 记录原本1所在位置,构造等式约束  n0ind=find(sudokumat~=0);   aeq0=zeros(length(n0ind),9^3);  for i=1:length(n0ind)      aeq0(i,n0ind(i)+(sudokumat(n0ind(i))-1)*81)=1;  end    % 每一行、列、管都只能有一个1  aeq1=zeros(81,9^3);  aeq2=zeros(81,9^3);  aeq3=zeros(81,9^3);  for i=1:9      for j=1:9          a1=zeros(9,9,9);          a2=zeros(9,9,9);          a3=zeros(9,9,9);          a1(:,i,j)=1;aeq1((i-1)*9+j,:)=a1(:)';          a2(i,:,j)=1;aeq2((i-1)*9+j,:)=a2(:)';          a3(i,j,:)=1;aeq3((i-1)*9+j,:)=a3(:)';      end  end    % 每个3x3的小矩阵都只能有一个1  aeq4=zeros(81,9^3);  for k=1:9      for i=1:3          for j=1:3              a4=zeros(9,9,9);              a4((i-1)*3+1:i*3,(j-1)*3+1:j*3,k)=1;              aeq4((k-1)*9+(i-1)*3+j,:)=a4(:)';          end      end  end    f=ones(1,9^3);  % 不重要,随便设置  intcon=1:9^3;   % 所有元素都要求为整数  lb=zeros(9^3,1);% 下限为0  ub=ones(9^3,1); % 上限为1  aeq=[aeq0;aeq1;aeq2;aeq3;aeq4];  beq=ones(size(aeq,1),1);  % 求解整数规划  x=intlinprog(f,intcon,[],[],aeq,beq,lb,ub);  % 重新 构造数独矩阵  x=reshape(x,[9,9,9]);  resultmat=zeros(9,9);  for i=1:9      resultmat=resultmat+x(:,:,i).*i;  end  resultmat

求解结果为:

lp:optimal objective value is 81.000000.

optimal solution found.

intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.absolutegaptolerance = 0 

the intcon variables are integer within tolerance, options.integertolerance = 1e-05

resultmat 

1 8 5 6 2 9 7 3 4
6 9 2 7 4 3 8 1 5
3 4 7 1 8 5 6 2 9
9 2 1 3 6 8 4 5 7
5 6 3 4 7 1 9 8 2
8 7 4 5 9 2 1 6 3
2 5 6 9 1 7 3 4 8
4 3 9 8 5 6 2 7 1
7 1 8 2 3 4 5 9 6

历时 0.017170 秒,快到离谱。不得不说matlab规划算法还是niubility!

4.数字识别

想要做读取图片后识别数独矩阵的功能,但是c/c++开发分享基于Matlab制作一个数独求解器做的只是一个基础款,没打算搞歪歪斜斜的数独题目图像,也没打算识别那些手写字体,于是既没有做角度矫正,也没搞cnn数字识别,大家学会基础款后可以自行添加相关功能,c/c++开发分享基于Matlab制作一个数独求解器中的数字识别只是将图像切割后和数字库里几个图像进行对比:

基于Matlab制作一个数独求解器

只是做了简单的最小二乘法,求差值平方和,找到差异最小的图片,非常的简单,因此只能应对一些横平竖直的数独题目。

5.gui / app

反正都很简单,我就gui版本和app designer版本都做了,以下仅展示 gui 版本代码

function sudokugui  % @author:slandarer    % gui图窗创建  sdkfig=uifigure('units','pixels',...      'position',[300 100 450 500],...      'numbertitle','off',...      'menubar','none',...      'resize','off',...      'name','数独求解器 1.0',...      'color',[1,1,1].*0.97);  sdkfig.autoresizechildren='off';  sdkaxes=uiaxes('units','pixels',...        'parent',sdkfig,...        'plotboxaspectratio',[1 1 1],...        'position',[15 15 420 420],...        'color',[0.99 0.99 0.99],...         'box','on', ...        'xlim',[0 1],'ylim',[0 1],...        'xtick',[],'ytick',[]);  hold(sdkaxes,'on');  % sdkaxes.toolbar.visible='off';  % 按钮创建  uibutton(sdkfig,'text','导  入  图  片','backgroundcolor',[0.31 0.58 0.80],'fontcolor',[1 1 1],...      'fontweight','bold','position',[25,450,150,35],'fontsize',13,'buttonpushedfcn',@loadpic);    uibutton(sdkfig,'text','开  始  计  算','backgroundcolor',[0.31 0.58 0.80],'fontcolor',[1 1 1],...      'fontweight','bold','position',[200,450,150,35],'fontsize',13,'buttonpushedfcn',@solvesdk);   % =========================================================================  % 读取图像库内图像  path='数字图像库';  picinfor=dir(fullfile(path,'*.jpg'));  sdkpicset{size(picinfor,1)}=[];  for n=1:size(picinfor,1)      temppic=imread([path,'',picinfor(n).name]);      sdkpicset(n)={temppic};  end  oripic=[];        % 图像读取函数      function loadpic(~,~)          try              [filename, pathname] = uigetfile({'*.jpg;*.tif;*.png;*.gif','all image files';...                  '*.*','all files' });              oripic=imread([pathname,filename]);              lim=max(size(oripic));              sdkaxes.xlim=[0 lim];              sdkaxes.ylim=[0 lim];              imshow(oripic,'parent',sdkaxes)          catch          end      end        % 数独求解函数      function solvesdk(~,~)          % 提取数独矩阵及数独矩阵在图片中位置          [xlim,ylim,sudokumat]=getmat(oripic);                    % 整数规划求解数独          resultmat=sudoku(sudokumat);disp(resultmat)            % 补全数独图像          fillsdk(xlim,ylim,resultmat,sudokumat)      end      % =========================================================================      % 提取数独矩阵      function [xlim,ylim,sudokumat]=getmat(oripic)          bw=~im2bw(oripic);          deletedrange=round(((size(bw,1)+size(bw,2))/2)^2*0.00005);          bw=bwareaopen(bw,deletedrange);          % 定位数独表格          xdistrib=find(sum(bw,2)~=0);          ydistrib=find(sum(bw,1)~=0);          xlim=[xdistrib(1),xdistrib(end)];          ylim=[ydistrib(1),ydistrib(end)];          % 将图像进行切割并将数字填入矩阵          numpicsize=[round((xlim(2)-xlim(1)+1)/9),round((ylim(2)-ylim(1)+1)/9)];          selectedpic=imresize(bw(xlim(1):xlim(2),ylim(1):ylim(2)),9.*numpicsize);          sudokumat=zeros(9,9);          for i=1:9              for j=1:9                  % 切割出每个数字                  numpic=selectedpic((i-1)*numpicsize(1)+1:i*numpicsize(1),(j-1)*numpicsize(2)+1:j*numpicsize(2));                  numpic=imclearborder(numpic);                  xdistrib=find(sum(numpic,2)~=0);                  ydistrib=find(sum(numpic,1)~=0);                  if ~any(xdistrib)||~any(ydistrib)% 若是方框是空的设置矩阵数值为0                      sudokumat(i,j)=0;                  else                      xlim=[xdistrib(1),xdistrib(end)];                      ylim=[ydistrib(1),ydistrib(end)];                      % 为了区分1和7,这里多删去一块                      numpic=numpic(xlim(1):xlim(2)-round(0.1*(xlim(2)-xlim(1))),ylim(1):ylim(2));                      xdistrib=find(sum(numpic,2)~=0);                      ydistrib=find(sum(numpic,1)~=0);                      xlim=[xdistrib(1),xdistrib(end)];                      ylim=[ydistrib(1),ydistrib(end)];                      numpic=numpic(xlim(1):xlim(2),ylim(1):ylim(2));                      numpic=imresize(numpic,[70 40]);                      % 最小二乘法选出最可能的数值                      tempvarin=inf.*ones(1,size(picinfor,1));                      % 循环和图像库中图像做差值并求平方和                      for k=1:size(picinfor,1)                          tempvarin(k)=sum((double(sdkpicset{k})-numpic.*255).^2,[1,2]);                      end                      tempstr=picinfor(tempvarin==min(tempvarin)).name;                      sudokumat(i,j)=str2double(tempstr(1));                  end              end          end      end  % -------------------------------------------------------------------------      % 整数规划求解数独      function resultmat=sudoku(sudokumat)          % 记录原本1所在位置,构造等式约束          n0ind=find(sudokumat~=0);          aeq0=zeros(length(n0ind),9^3);          for i=1:length(n0ind)              aeq0(i,n0ind(i)+(sudokumat(n0ind(i))-1)*81)=1;          end          % 每一行、列、管都只能有一个1          aeq1=zeros(81,9^3);          aeq2=zeros(81,9^3);          aeq3=zeros(81,9^3);          for i=1:9              for j=1:9                  a1=zeros(9,9,9);                  a2=zeros(9,9,9);                  a3=zeros(9,9,9);                  a1(:,i,j)=1;aeq1((i-1)*9+j,:)=a1(:)';                  a2(i,:,j)=1;aeq2((i-1)*9+j,:)=a2(:)';                  a3(i,j,:)=1;aeq3((i-1)*9+j,:)=a3(:)';              end          end          % 每个3x3的小矩阵都只能有一个1          aeq4=zeros(81,9^3);          for k=1:9              for i=1:3                  for j=1:3                      a4=zeros(9,9,9);                      a4((i-1)*3+1:i*3,(j-1)*3+1:j*3,k)=1;                      aeq4((k-1)*9+(i-1)*3+j,:)=a4(:)';                  end              end          end          f=ones(1,9^3);  % 不重要,随便设置          intcon=1:9^3;   % 所有元素都要求为整数          lb=zeros(9^3,1);% 下限为0          ub=ones(9^3,1); % 上限为1          aeq=[aeq0;aeq1;aeq2;aeq3;aeq4];          beq=ones(size(aeq,1),1);          % 求解整数规划          x=intlinprog(f,intcon,[],[],aeq,beq,lb,ub);          % 重新 构造数独矩阵          x=reshape(x,[9,9,9]);          resultmat=zeros(9,9);          for i=1:9              resultmat=resultmat+x(:,:,i).*i;          end      end  % -------------------------------------------------------------------------      % 补全数独      function fillsdk(xlim,ylim,resultmat,sudokumat)          for i=0:9              plot(sdkaxes,[ylim(1),ylim(1)]+i*(ylim(2)-ylim(1))/9,[xlim(1),xlim(2)],'color',[0.29 0.65 0.85],'linewidth',2)              plot(sdkaxes,[ylim(1),ylim(2)],[xlim(1),xlim(1)]+i*(xlim(2)-xlim(1))/9,'color',[0.29 0.65 0.85],'linewidth',2)          end          fontsize=18;          if (xlim(2)-xlim(1))>0.8*size(oripic,1)              fontsize=36;          end          for i=1:9              for j=1:9                  if (resultmat(j,i)~=0)&&(sudokumat(j,i)==0)                  text(sdkaxes,ylim(1)+(i-1)*(ylim(2)-ylim(1))/9+(ylim(2)-ylim(1))/9/2,...                               xlim(1)+(j-1)*(xlim(2)-xlim(1))/9+(xlim(2)-xlim(1))/9/2,...                               num2str(resultmat(j,i)),'horizontalalignment','center',...                               'color',[0.29 0.65 0.85],'fontweight','bold','fontsize',fontsize)                  end              end          end      end  end

到此这篇关于基于matlab制作一个数独求解器的文章就介绍到这了,更多相关matlab数独求解器内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享基于Matlab制作一个数独求解器,都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/1240291.html

(0)
上一篇 2022年9月19日 上午10:50
下一篇 2022年9月19日 上午10:54

精彩推荐

发表回复

您的电子邮箱地址不会被公开。