數(shù)學(xué)建模-Argyle(數(shù)獨)問題.doc

論文題目：Argyle問題 姓名1：學(xué)號：專業(yè)：姓名2：學(xué)號：專業(yè)： 姓名3：學(xué)號：專業(yè)：2013年 07 月 17 日目錄一.摘要2二.問題的重述2三.問題的分析3四、模型建立34.1模型假設(shè)34.2符號說明34.3模型的建立與求解3（1）問題1解析4（2）問題2解析4五.模型的評價與改進(jìn)6六.參考文獻(xiàn)6七、附錄61.摘要九宮格數(shù)獨，是一種源自18世紀(jì)末期的瑞士，之后在各個國家發(fā)展。數(shù)獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數(shù)字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數(shù)字。使1-9每個數(shù)字在每一行，每一列和每一宮中都只出現(xiàn)一次。這種游戲全面考驗做題者觀察能力和推理能力。而Argyle數(shù)獨除了滿足標(biāo)準(zhǔn)數(shù)獨的要求外，還要求標(biāo)出的對角線上的數(shù)字也不重復(fù)。這一要求加深了解開數(shù)獨的難度。所以，解開Argyle數(shù)獨，關(guān)鍵在于很多點的候選值又很多，需要不斷的嘗試、不斷的排除的這樣一個過程。因此，通過使用Matlab軟件編寫代碼來代替人腦進(jìn)行嘗試與排除，這樣既節(jié)省了求解者的解題時間，同時也將當(dāng)代計算機科技技術(shù)運用到解題的實踐中，豐富了數(shù)學(xué)建模的解題靈活性，加強了求解的嚴(yán)謹(jǐn)性。針對問題1、2，可以將其統(tǒng)一化為一個問題，運用Matlab軟件編寫代碼，之后通過建立“數(shù)獨”矩陣，改變其大小，從而求解不同的Argyle問題。關(guān)鍵詞：候選數(shù)、Argyle數(shù)獨要求、Matlab軟件2.問題的重述Argyle問題Argyle數(shù)獨是標(biāo)準(zhǔn)數(shù)獨的變形，標(biāo)準(zhǔn)數(shù)獨是根據(jù)99盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個粗線宮內(nèi)的數(shù)字均含1-9，不重復(fù)。每一道合適的數(shù)獨謎題都有且僅有唯一答案，推理方法也以此為基礎(chǔ)，任何無解或多解的題目都是不合格的。Argyle數(shù)獨除了滿足以上要求之外，同時還要求標(biāo)出的對角線上的數(shù)字也不重復(fù)。如下圖所示：現(xiàn)有以下問題待求解：根據(jù)以上描述，試完成以下問題：1.用matlab進(jìn)行求解；2.利用matlab畫出各個問題及解答的圖形。3.問題的分析這兩個問題的核心在于如何用matlab來代替人來進(jìn)行求解中候選數(shù)的嘗試與排除這一重復(fù)的過程。且必須用matlab畫出兩個問題及解答的圖形，此必須用到matlab中的plot與text這兩個函數(shù)分別進(jìn)行線與數(shù)字的顯示工作。我們小組的思路是運用matlab中語言的If語句與For語句進(jìn)行對問題的候選數(shù)進(jìn)行篩選，先將滿足的候選數(shù)存儲在C中，之后再進(jìn)行篩選，得到滿意的答案。之后將所求結(jié)果放入事先準(zhǔn)備好的九宮格中，使其一一對應(yīng)，最終得出結(jié)果。4.模型建立4.1模型假設(shè)所有Argyle問題都是99盤狀所有Argyle都必須依照數(shù)獨游戲的基本規(guī)則進(jìn)行所有Argyle無數(shù)字的方格都填0來轉(zhuǎn)化為99矩陣4.2符號說明A所求解問題所轉(zhuǎn)化的矩陣candidates求解問題候選數(shù)的函數(shù)sudoku解出數(shù)獨問題的函數(shù)（遞歸法）C存儲候選數(shù)X結(jié)果矩陣4.3模型的建立與求解問題1解析根據(jù)所輸入的矩陣來進(jìn)行求解；在輸入頁面輸入矩陣：A=0,0,8,0,0,0,0,0,2; 0,0,0,0,7,3,0,0,0; 0,6,3,0,0,0,0,0,7; 0,4,0,0,0,9,0,7,0; 0,0,0,0,0,0,0,0,0; 6,0,0,0,0,0,8,5,1; 0,2,0,0,0,0,0,0,5; 0,0,0,4,0,0,0,0,0; 0,9,0,5,0,0,0,0,0;將候選數(shù)先行選出，排除一行、一列、一宮格里數(shù)字相同的情況；通過for語句的循環(huán)效果，先將一個數(shù)字填入矩陣中，之后利用遞歸法，將所有符合的數(shù)字填入矩陣中；最后，將矩陣上的數(shù)一一對應(yīng)在九宮格框里，得出結(jié)果。如下圖所示：問題2解析根據(jù)所輸入的矩陣來進(jìn)行求解：在輸入頁面輸入矩陣：A=0,8,0,0,0,0,0,0,0; 0,1,0,0,2,5,0,4,3; 0,0,2,0,0,0,0,5,0; 0,0,0,9,0,3,0,0,0; 0,2,0,0,0,0,0,8,0; 0,0,0,0,0,0,0,0,0; 3,0,7,0,8,0,6,0,0; 0,0,0,0,7,0,1,0,0; 0,0,0,0,5,0,0,0,8;同問題1一致，得出結(jié)果：如下圖所示：5.模型的評價與改進(jìn)5.1優(yōu)點：此模型運用matlab軟件進(jìn)行求解，大大增添了該模型的規(guī)范化。同時，通過輸入矩陣的不同，從而達(dá)到解析不同的Argyle問題。此模型中運用了遞歸法，從而將程序大大簡化了，加強了該模型的使用性，使得將該算法的合理性加強了。5.2缺點與改進(jìn)：此模型中，在運行之前必須輸入原問題的矩陣式，從而使得程序能夠運行。這樣一來，將求解時的輸入時間增加了。因此，應(yīng)該用程序?qū)㈦[藏在問題中的矩陣式直接找出來，而不是人工輸入，這樣一來將會節(jié)省更多的時間，使得該模型更加完善。6.參考文獻(xiàn)1. Matlab程序設(shè)計與應(yīng)用（第二版）劉衛(wèi)國 主編2. sudokkusudoku-Cleve Moler=Experiments with MATLAB-chapter18-2009年7.附錄7.1問題1代碼：clear;clc;close allhold on;for i=0:9 if rem(i,3)=0 plot(0,9,i,i,k,LineWidth,3) else plot(0,9,i,i,k,LineWidth,2) endendtext(8.5,3.5,1)text(8.5,8.5,2)text(1.5,2.5,2)text(2.5,6.5,3)text(5.5,7.5,3)text(1.5,5.5,4)text(3.5,1.5,4)text(3.5,0.5,5)text(7.5,3.5,5)text(8.5,2.5,5)text(0.5,3.5,6)text(1.5,6.5,6)text(4.5,7.5,7)text(7.5,5.5,7)text(8.5,6.5,7)text(2.5,8.5,8)text(6.5,3.5,8)text(1.5,0.5,9)text(5.5,5.5,9)for j=0:9 if rem(j,3)=0 plot(j,j,0,9,k,LineWidth,3) else plot(j,j,0,9,k,LineWidth,2) end end plot(4,9,0,5,k,LineWidth,1) plot(1,9,0,8,k,LineWidth,1) plot(0,8,1,9,k,LineWidth,1) plot(0,5,4,9,k,LineWidth,1) plot(0,5,5,0,k,LineWidth,1) plot(0,8,8,0,k,LineWidth,1) plot(1,9,9,1,k,LineWidth,1) plot(4,9,9,4,k,LineWidth,1) A=0,0,8,0,0,0,0,0,2; 0,0,0,0,7,3,0,0,0; 0,6,3,0,0,0,0,0,7; 0,4,0,0,0,9,0,7,0; 0,0,0,0,0,0,0,0,0; 6,0,0,0,0,0,8,5,1; 0,2,0,0,0,0,0,0,5; 0,0,0,4,0,0,0,0,0; 0,9,0,5,0,0,0,0,0; X = sudoku(A) for i=1:9 for j=1:9text(j-0.5,9.5-i,num2str(X(i,j); endend function X = sudoku(X)C,s,e = candidates(X);while isempty(s) & isempty(e)X(s) = Cs;C,s,e = candidates(X);endif isempty(e)returnendif any(X(:) = 0)Y = X;z = find(X(:) = 0,1); for r = Cz X = Y;X(z) = r;X = sudoku(X);if all(X(:) 0) returnendendendfunction C,s,e = candidates(X)C = cell(9,9);tri = (k) 3*ceil(k/3-1) + (1:3);for j = 1:9 for i = 1:9 if X(i,j)=0 z = 1:9; z(nonzeros(X(i,:) = 0; z(nonzeros(X(:,j) = 0; z(nonzeros(X(tri(i),tri(j) = 0; Ci,j = nonzeros(z); end endendL = cellfun(length,C); s = find(X=0 & L=1,1);e = find(X=0 & L=0,1);end7.2問題2代碼：clear;clc;close allhold on;for i=0:9 if rem(i,3)=0 plot(0,9,i,i,k,LineWidth,3) else plot(0,9,i,i,k,LineWidth,2) endendtext(8.5,3.5,1)text(8.5,8.5,2)text(1.5,2.5,2)text(2.5,6.5,3)text(5.5,7.5,3)text(1.5,5.5,4)text(3.5,1.5,4)text(3.5,0.5,5)text(7.5,3.5,5)text(8.5,2.5,5)text(0.5,3.5,6)text(1.5,6.5,6)text(4.5,7.5,7)text(7.5,5.5,7)text(8.5,6.5,7)text(2.5,8.5,8)text(6.5,3.5,8)text(1.5,0.5,9)text(5.5,5.5,9)for j=0:9 if rem(j,3)=0 plot(j,j,0,9,k,LineWidth,3) else plot(j,j,0,9,k,LineWidth,2) end end plot(4,9,0,5,k,LineWidth,1) plot(1,9,0,8,k,LineWidth,1) plot(0,8,1,9,k,LineWidth,1) plot(0,5,4,9,k,LineWidth,1) plot(0,5,5,0,k,LineWidth,1) plot(0,8,8,0,k,LineWidth,1) plot(1,9,9,1,k,LineWidth,1) plot(4,9,9,4,k,LineWidth,1) A=0,8,0,0,0,0,0,0,0; 0,1,0,0,2,5,0,4,3; 0,0,2,0,0,0,0,5,0; 0,0,0,9,0,3,0,0,0; 0,2,0,0,0,0,0,8,0; 0,0,0,0,0,0,0,0,0; 3,0,7,0,8,0,6,0,0; 0,0,0,0,7,0,1,0,0; 0,0,0,0,5,0,0,0,8; X = sudoku(A) for i=1:9 for j=1:9text(j-0.5,9.5-i,num2str(X(i,j); endend function X = sudoku(X)C,s,e = candidates(X);while isempty(s) & isempty(e)X(s) = Cs;C,s,e = candidates(X);endif isempty(e)returnendif any(X(:) = 0)Y = X;z = find(X(:) = 0,1); for r = Cz X = Y;X(z) = r;X = sudoku(X);if all(X(:) 0) returnendendendfunction C,s,e = candidates(X)C = cell(9,9);