使用matlab生成數獨

常見生成數獨程序
常見的數獨生成方法是首先產生一張完整的9宮數字圖，然后隨機挖掉一些數字，產生數獨。也就是說要產生數獨，首先產生答案。
本人在開始寫程序前想在csdn中尋找一些經驗，奈何多數大神都是用java和c++寫的，而且數學思想都是使用回溯法，回溯法的核心思想為:
1·在一格內隨機填入1~9內的一個數，并按照數獨規則判斷此時這個數是否合適。
2·若合適，則繼續填寫下一格的數字。
3·若1~9都不合適，也返回上一格，修改其中數字，然后再次嘗試填入數字。
4·不斷循環，直到81格全部填入數字。
按各位大神的文章來說，這種方法的效率感人，可是我對遞歸的理解不深，java和c++的基礎也比較薄弱，完全看不懂大神的程序，也就無法判斷效率到底有多感人。
除此以外還有一些其他思路，比如用0-1規劃，約束問題，可是這些方法我連數學原理都沒看懂，更不用說程序。
那不用回溯法就不能寫數獨了嗎？當然不是的，不然我也不會來寫博客。

我的數獨產生方法
我的數獨產生思想為:
1·首先產生1~9的隨機數列，填入九宮圖第一行。(此時整個圖都是空的，所以一定不會有問題)
2·從第二行第一列開始，在每一格填數前，首先取出此格所在行，所在列，所在宮，已經填入的所有數，判斷在1~9中還有哪些數可以填，這些數稱為備選數。隨機從備選數中選擇一個填入此格。
3·不斷循環，填入其余72個格。
這種方法乍一聽好像可行，按這種思想寫出以下程序:

clc clear A = zeros(9,9); a = (1:9); b = randperm(9); A(1,:) = b; for i = 2:9 for j = 1:9 x = A(i,:); y = A(:,j); if 0<j && j<4 z = A(:,1:3); else if 3<j && j<7 z = A(:,4:6); else z = A(:,7:9); end endif 0<i && i<4z = z(1:3,:); else if 3<i && i<7 z = z(4:6,:); else z = z(7:9,:); end end X = x(x~=0); Y = y(y~=0); Z = z(z~=0); t = union(X,Y); t = union(t,Z); n = setxor(t,a); L = length(n); r = rand(1); h = ceil(r*L); if h == 0 break end A(i,j) = n(h); end if A(i,j) == 0 break endend

但實際運行以后生成的大部分都是這種矩陣:
A =

4 2 8 5 1 3 9 6 77 9 3 2 6 4 8 5 11 6 5 9 7 8 4 2 36 1 9 8 4 5 7 3 28 4 7 1 9 2 5 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0

顯然第五行中還缺少3，可是在第8列和第9列中都已經填入了3，這時就出現矛盾了，無法繼續進行下去。
但是所有數獨答案都滿足我上述的思想，而且在我多次運行這段程序時確實輸出了一個正確的數獨矩陣。也就是說只要多次循環這段程序就可以產生數獨，只是循環次數不固定。但是對于計算機來說，這種循環還是很快的，所以我改進了程序如下:

clc clear c = 1;%生成數獨數量 num = zeros(1,c);%生成一個數獨的的循環次數 shudu = zeros(9,9,c); for k = 1:c num(1,k) = 0; while(sum(sum(shudu(:,:,k)))~=405) A = zeros(9,9); a = (1:9); b = randperm(9); A(1,:) = b; for i = 2:9 for j = 1:9 x = A(i,:); y = A(:,j); if 0<j && j<4 z = A(:,1:3); else if 3<j && j<7 z = A(:,4:6); else z = A(:,7:9); end end if 0<i && i<4 z = z(1:3,:); else if 3<i && i<7 z = z(4:6,:); else z = z(7:9,:); end end X = x(x~=0); Y = y(y~=0); Z = z(z~=0); t = union(X,Y); t = union(t,Z); n = setxor(t,a); L = length(n); r = rand(1); h = ceil(r*L); if h == 0 num(1,k) = num(1,k)+1; break end A(i,j) = n(h); end if A(i,j) == 0 break end end shudu(:,:,k) = A; end shudu(:,:,k)end

那這種方法的效率怎么樣呢？我使用這段程序一次生成過800個數獨答案，取得循環次數的平均值是49次，對于電腦來說不到一秒鐘，最多的一次循環了一千四百多次，大約是5~6秒的時間，最短的一次只循環了兩次，這個時間也不知道和回溯法比起來怎么樣。

數獨生成
隨機挖空比較容易，代碼如下:

b = 3;%設置難度，一行中隨機挖掉幾個數 A;%完整的數獨九宮格 for i = 1:9a = randperm(9);for j = 1:bA(i,a(j)) = 0;end end

優缺點分析
產生答案部分最大的優點就是代碼長度很短，便于理解，不需要用到遞歸這樣的高級程序手段，我看其他人的代碼長度基本都在一百五十行左右。缺點就在于產生一個答案的時間不固定，且差距較大。
主要缺點集中在產生數獨部分，這種方法產生的數獨只能保證有解，但并不能保證有唯一解。而且數獨的難度并不是僅在每行缺少的數字個數，而重點在于每個空格的備選數是否唯一，每行缺少4個數字可能會比每行缺少6個數字更難。

一點小期待
這是我第一次在csdn寫博客，還有很多不足之處，功能使用也不是很熟練，希望各位能提出意見，無論是在程序方面，還是在博客文案，排版方面，歡迎交流，感激不盡。
我也在嘗試寫解數獨的程序，但是目前還不完善，如果把每行缺少3個數稱為3級難度，那我現有的成果是，3級難度成功率為100％，4級難度成功率為98.5%，5級難度成功率為78%，6級難度成功率為17.8%，希望未來我可以將其完善。

總結

以上是生活随笔為你收集整理的使用matlab生成数独(无回溯法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。