欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

基于Matlab制作一個數(shù)獨求解器

 更新時間:2022年05月23日 12:08:43   作者:slandarer  
這篇文章主要為大家詳細介紹了如何利用Matlab制作一個數(shù)獨求解器,文中的示例代碼講解詳細,對我們學(xué)習(xí)Matlab有一定幫助,需要的可以參考一下

講解一個完整的小項目,順便說明如何使用整數(shù)規(guī)劃求解數(shù)獨。

1.完整效果

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

首先我們先嘗試如果只滿足行、列、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];
% 記錄原本各個數(shù)字所在位置,構(gòu)造等式約束
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);    % 不重要,隨便設(shè)置
intcon=1:81;     % 所有元素都要求為整數(shù)
lb=ones(81,1);   % 下限為1
ub=ones(81,1).*9;% 上限為1
Aeq=[Aeq1;Aeq2;Aeq3;Aeq4];
beq=[beq1;beq2;beq3;beq4];
% 求解整數(shù)規(guī)劃
X=intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);
% 重新 構(gòu)造數(shù)獨矩陣
X=reshape(X,[9,9])

那么,這么簡單就能夠解決數(shù)獨了嘛???

當(dāng)然不行。。。。

上述程序運行結(jié)果為:

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

可以發(fā)現(xiàn)我們的約束確實保證了三種加和都是45,但是不能保證同行、同列、同3x3塊內(nèi)不出現(xiàn)同樣的數(shù)字,那咋辦,總不能一個元素一個元素添加不相等信息吧、我們怎樣能讓矩陣包含更多的信息,更方便的闡述各個元素之間的聯(lián)系呢?

3.數(shù)獨求解(升維)

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

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

此時約束條件變?yōu)椋?/p>

原矩陣每個小格子只能有一個數(shù)值:

原矩陣每一行的各個數(shù)字均不同:

原矩陣每一列的各個數(shù)字均不同:

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

其中因此編寫如下代碼

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所在位置,構(gòu)造等式約束
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);  % 不重要,隨便設(shè)置
intcon=1:9^3;   % 所有元素都要求為整數(shù)
lb=zeros(9^3,1);% 下限為0
ub=ones(9^3,1); % 上限為1
Aeq=[Aeq0;Aeq1;Aeq2;Aeq3;Aeq4];
beq=ones(size(Aeq,1),1);
% 求解整數(shù)規(guī)劃
X=intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);
% 重新 構(gòu)造數(shù)獨矩陣
X=reshape(X,[9,9,9]);
resultMat=zeros(9,9);
for i=1:9
    resultMat=resultMat+X(:,:,i).*i;
end
resultMat

求解結(jié)果為:

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規(guī)劃算法還是niubility!

4.數(shù)字識別

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

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

5.GUI / APP

反正都很簡單,我就GUI版本和App designer版本都做了,以下僅展示 GUI 版本代碼

function sudokuGui
% @author:slandarer

% GUI圖窗創(chuàng)建
SDKFig=uifigure('units','pixels',...
    'position',[300 100 450 500],...
    'Numbertitle','off',...
    'menubar','none',...
    'resize','off',...
    'name','數(shù)獨求解器 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';
% 按鈕創(chuàng)建
uibutton(SDKFig,'Text','導(dǎo)  入  圖  片','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); 
% =========================================================================
% 讀取圖像庫內(nèi)圖像
path='數(shù)字圖像庫';
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=[];

    % 圖像讀取函數(shù)
    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

    % 數(shù)獨求解函數(shù)
    function solveSDK(~,~)
        % 提取數(shù)獨矩陣及數(shù)獨矩陣在圖片中位置
        [XLim,YLim,sudokuMat]=getMat(oriPic);
        
        % 整數(shù)規(guī)劃求解數(shù)獨
        resultMat=sudoku(sudokuMat);disp(resultMat)

        % 補全數(shù)獨圖像
        fillSDK(XLim,YLim,resultMat,sudokuMat)
    end


% =========================================================================
    % 提取數(shù)獨矩陣
    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);
        % 定位數(shù)獨表格
        xDistrib=find(sum(bw,2)~=0);
        yDistrib=find(sum(bw,1)~=0);
        XLim=[xDistrib(1),xDistrib(end)];
        YLim=[yDistrib(1),yDistrib(end)];
        % 將圖像進行切割并將數(shù)字填入矩陣
        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
                % 切割出每個數(shù)字
                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)% 若是方框是空的設(shè)置矩陣數(shù)值為0
                    sudokuMat(i,j)=0;
                else
                    xLim=[xDistrib(1),xDistrib(end)];
                    yLim=[yDistrib(1),yDistrib(end)];
                    % 為了區(qū)分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]);
                    % 最小二乘法選出最可能的數(shù)值
                    tempVarin=inf.*ones(1,size(picInfor,1));
                    % 循環(huán)和圖像庫中圖像做差值并求平方和
                    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
% -------------------------------------------------------------------------
    % 整數(shù)規(guī)劃求解數(shù)獨
    function resultMat=sudoku(sudokuMat)
        % 記錄原本1所在位置,構(gòu)造等式約束
        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);  % 不重要,隨便設(shè)置
        intcon=1:9^3;   % 所有元素都要求為整數(shù)
        lb=zeros(9^3,1);% 下限為0
        ub=ones(9^3,1); % 上限為1
        Aeq=[Aeq0;Aeq1;Aeq2;Aeq3;Aeq4];
        beq=ones(size(Aeq,1),1);
        % 求解整數(shù)規(guī)劃
        X=intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);
        % 重新 構(gòu)造數(shù)獨矩陣
        X=reshape(X,[9,9,9]);
        resultMat=zeros(9,9);
        for i=1:9
            resultMat=resultMat+X(:,:,i).*i;
        end
    end
% -------------------------------------------------------------------------
    % 補全數(shù)獨
    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

到此這篇關(guān)于基于Matlab制作一個數(shù)獨求解器的文章就介紹到這了,更多相關(guān)Matlab數(shù)獨求解器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • c語言如何設(shè)置隨機數(shù)及逐行解析

    c語言如何設(shè)置隨機數(shù)及逐行解析

    在C語言中,rand()函數(shù)可以用來產(chǎn)生隨機數(shù),但是這不是真真意義上的隨機數(shù),是一個偽隨機數(shù),下面這篇文章主要給大家介紹了關(guān)于c語言如何設(shè)置隨機數(shù)及逐行解析的相關(guān)資料,需要的朋友可以參考下
    2022-11-11
  • C++中的偽隨機數(shù)

    C++中的偽隨機數(shù)

    這篇文章主要介紹了C++中的偽隨機數(shù),具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-07-07
  • C C++ 算法實例大全

    C C++ 算法實例大全

    這篇文章主要介紹了C C++ 算法實例大全,里面大量的實例介紹,學(xué)習(xí)c語言的朋友可以收藏
    2016-12-12
  • C語言實現(xiàn)從指定位置截取文件內(nèi)容

    C語言實現(xiàn)從指定位置截取文件內(nèi)容

    這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)從指定位置截取文件內(nèi)容,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-11-11
  • C語言實現(xiàn)賓果消消樂

    C語言實現(xiàn)賓果消消樂

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)賓果消消樂,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-12-12
  • C語言學(xué)生信息管理系統(tǒng)小項目

    C語言學(xué)生信息管理系統(tǒng)小項目

    這篇文章主要為大家詳細介紹了C語言學(xué)生信息管理系統(tǒng)小項目,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • C++實現(xiàn)二叉樹的堂兄弟節(jié)點查詢

    C++實現(xiàn)二叉樹的堂兄弟節(jié)點查詢

    C++實現(xiàn)二叉樹的堂兄弟節(jié)點查詢,是指在二叉樹中,找到兩個節(jié)點深度相同但父節(jié)點不同的節(jié)點,即為堂兄弟節(jié)點。實現(xiàn)這一功能可以通過遍歷二叉樹并記錄節(jié)點深度和父節(jié)點來實現(xiàn)
    2023-04-04
  • 詳解設(shè)計模式中的中介者模式在C++編程中的運用

    詳解設(shè)計模式中的中介者模式在C++編程中的運用

    這篇文章主要介紹了設(shè)計模式中的中介者模式在C++編程中的運用,中介者模式將對象間的通信封裝到一個類中,將多對多的通信轉(zhuǎn)化為一對多的通信,降低了系統(tǒng)的復(fù)雜性,需要的朋友可以參考下
    2016-03-03
  • 基于OpenCV實現(xiàn)車道線檢測(自動駕駛 機器視覺)

    基于OpenCV實現(xiàn)車道線檢測(自動駕駛 機器視覺)

    無人駕駛技術(shù)是機器學(xué)習(xí)為主的一門前沿領(lǐng)域,在無人駕駛領(lǐng)域中機器學(xué)習(xí)的各種算法隨處可見,本文將為大家介紹無人駕駛技術(shù)中的車道線檢測,感興趣的小伙伴可以了解一下
    2021-11-11
  • 利用Matlab實現(xiàn)圖像亮度分布統(tǒng)計圖

    利用Matlab實現(xiàn)圖像亮度分布統(tǒng)計圖

    這篇文章主要介紹了如何利用Matlab實現(xiàn)圖像亮度分布統(tǒng)計圖的繪制,文中的示例代碼講解詳細,對我們學(xué)習(xí)Matlab有一定的幫助,感興趣的可以了解一下
    2022-05-05

最新評論