這篇“基于Matlab如何制作一個數獨求解器”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“基于Matlab如何制作一個數獨求解器”文章吧。
首先我們先嘗試如果只滿足行、列、3x3塊加和均為45的等式約束是否有效。即約束為：
每行和為45:
每列和為45:
每個3x3塊和為45:
其中對此編寫如下代碼：
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塊內不出現同樣的數字，那咋辦，總不能一個元素一個元素添加不相等信息吧、我們怎樣能讓矩陣包含更多的信息，更方便的闡述各個元素之間的聯系呢？
欸，我們原本是9x9大小的矩陣，要描述每個元素和同一行各個元素、和同一列各個元素之間的聯系，一個很自然的想法就是升維！
將9×9的數獨矩陣轉化為9×9×9的三維矩陣(張量),此時X(i,j,k)=1意味原矩陣第i行，第j列的元素為k，整個整數規劃從現在開始變成了0-1規劃，要想同一行的數值都不一樣，只需要所有的行纖維的和都是1，想要同一列的數值都不一樣，只需要所有列纖維的和都是1，非常奇妙的，我們又把問題轉換為了一個線性求和的問題，very amazing??！
此時約束條件變為：
原矩陣每個小格子只能有一個數值：
原矩陣每一行的各個數字均不同：
原矩陣每一列的各個數字均不同：
原矩陣每一個3x3塊各個數字均不同：
其中因此編寫如下代碼
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！
想要做讀取圖片后識別數獨矩陣的功能，但是本文做的只是一個基礎款，沒打算搞歪歪斜斜的數獨題目圖像，也沒打算識別那些手寫字體，于是既沒有做角度矯正，也沒搞CNN數字識別，大家學會基礎款后可以自行添加相關功能，本文中的數字識別只是將圖像切割后和數字庫里幾個圖像進行對比：
只是做了簡單的最小二乘法，求差值平方和，找到差異最小的圖片，非常的簡單，因此只能應對一些橫平豎直的數獨題目。
反正都很簡單，我就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如何制作一個數獨求解器”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
