基于Matlab如何制作一個數獨求解器

蝸牛 互聯網技術資訊 2022-05-23 9 0

這篇“基于Matlab如何制作一個數獨求解器”文章的知識點大部分人都不太理解,所以小編給大家總結了以下內容,內容詳細,步驟清晰,具有一定的借鑒價值,希望大家閱讀完這篇文章能有所收獲,下面我們一起來看看這篇“基于Matlab如何制作一個數獨求解器”文章吧。

1.完整效果

基于Matlab如何制作一個數獨求解器  matlab 第1張

基于Matlab如何制作一個數獨求解器  matlab 第2張

2.數獨求解(錯誤示范)

首先我們先嘗試如果只滿足行、列、3x3塊加和均為45的等式約束是否有效。即約束為:

每行和為45:

基于Matlab如何制作一個數獨求解器  matlab 第3張

每列和為45:

基于Matlab如何制作一個數獨求解器  matlab 第4張

每個3x3塊和為45:

基于Matlab如何制作一個數獨求解器  matlab 第5張

其中對此編寫如下代碼:

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,但是不能保證同行、同列、同3x3塊內不出現同樣的數字,那咋辦,總不能一個元素一個元素添加不相等信息吧、我們怎樣能讓矩陣包含更多的信息,更方便的闡述各個元素之間的聯系呢?

3.數獨求解(升維)

欸,我們原本是9x9大小的矩陣,要描述每個元素和同一行各個元素、和同一列各個元素之間的聯系,一個很自然的想法就是升維!

將9×9的數獨矩陣轉化為9×9×9的三維矩陣(張量),此時X(i,j,k)=1意味原矩陣第i行,第j列的元素為k,整個整數規劃從現在開始變成了0-1規劃,要想同一行的數值都不一樣,只需要所有的行纖維的和都是1,想要同一列的數值都不一樣,只需要所有列纖維的和都是1,非常奇妙的,我們又把問題轉換為了一個線性求和的問題,very amazing??!

此時約束條件變為:

原矩陣每個小格子只能有一個數值:

基于Matlab如何制作一個數獨求解器  matlab 第6張

原矩陣每一行的各個數字均不同:

原矩陣每一列的各個數字均不同:

基于Matlab如何制作一個數獨求解器  matlab 第7張

原矩陣每一個3x3塊各個數字均不同:

基于Matlab如何制作一個數獨求解器  matlab 第8張

其中因此編寫如下代碼

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.數字識別

想要做讀取圖片后識別數獨矩陣的功能,但是本文做的只是一個基礎款,沒打算搞歪歪斜斜的數獨題目圖像,也沒打算識別那些手寫字體,于是既沒有做角度矯正,也沒搞CNN數字識別,大家學會基礎款后可以自行添加相關功能,本文中的數字識別只是將圖像切割后和數字庫里幾個圖像進行對比:

基于Matlab如何制作一個數獨求解器  matlab 第9張

只是做了簡單的最小二乘法,求差值平方和,找到差異最小的圖片,非常的簡單,因此只能應對一些橫平豎直的數獨題目。

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如何制作一個數獨求解器”這篇文章的內容,相信大家都有了一定的了解,希望小編分享的內容對大家有幫助,若想了解更多相關的知識內容,請關注蝸牛博客行業資訊頻道。

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:niceseo99@gmail.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

評論

日本韩欧美一级A片在线观看