數獨實驗報告范文

發布時間：2020-03-19

Sudoku 數獨實驗報告

一、 算法描述

求解Sudoku讓人最容易想到的方法是窮舉每個方格可能的值，如果符合條件，則得到解，不符合條件則進行回溯。通過遞歸的方法，顯然可以得到數獨的解。

我想到的簡單的遞歸方法，是每一行從左到右，試驗每一個方格可能的數字，進行遞歸。這種方法看似非常麻煩，實際上對于一般的數獨題，速度是非常快的，思想比較簡單，寫出來的代碼也非常簡單、易懂。

算法1：簡單遞歸方法

從第一個格開始，從1到9試驗，是否滿足行、列、九宮格互不相同的條件。若滿足條件，則填入該數字，再試驗下一個格。當一個格子出現沒有數字能填的情況時，說明已經填的數字有誤，回溯，再進行遞歸。

算法2：優化的遞歸算法

先遍歷所有格子，統計每種格子可能出現數字的個數。每次挑選可能出現數字個數最少的格子來進行遞歸。

設置三維數組poss[i][j][k]來存儲可能出現數字的信息。poss[i][j][0]記錄i行j列的格子可能出現數字的個數，poss[i][j][k](1<=k<=9) 若poss[i][j][k]=1，表示k可能在(i，j)格出現。若poss[i][j][k]=0，表示k不可能在(i，j)格中出現。每次找poss[i][j][0]最小的格子，來進行下一個遞歸。

算法3：生成數獨棋盤的算法

我最開始的想法是窮舉法，隨機生成滿足行各不相同的9行，再判斷9宮格、每列是否符合要求，符合條件時，隨機生成停止。然而，這種算法的當然時間復雜度顯然是過高。第99一步的隨機生成的次數是9*9/P9=9608。隨機生成一組棋盤耗時就非常大。后來，我從求解的個數的程序獲得啟發。算法二對于1000多組解的數獨棋盤，解起來也很快。隨機生成填9個方格，再用算法一的方法解出來，取第一組正確的解作為棋盤即可生成填好的棋盤。再把一定數量的格子的數字隨機刪除，計算解的個數。如果解唯一，就得到了棋盤。

二、數據結構

這三種算法的數據結構不是非常復雜，只是普通的數組。

算法一：數組a[i][j]

算法二：數組a[i][j]和poss[i][j][k]

算法三：數組a[i][j]和poss[i][j][k]

三、時間效率分析

算法1：這種算法在tsinsen系統上只用了15ms得到全部答案。

雖然這種算法在tsinsen系統的測試中有很好的表現，但是我試了試在幾道骨灰級難度的題，發現這種算法可能會用到10秒以上的時間，并且測試數據不同，時間差異非常大。

我認為，這種算法的漏洞在于，如果開始的格子可能出現的數字非常多，遞歸樹開始的枝會非常多。并且，我們一般做數獨題，都會先挑可能出現數字個數最少的格子來填，充分利用了已知條件。然而，這種算法只按格子的行列順序來試驗，顯然非常傻。于是，我想出了第二種算法。

算法2：這種算法耗時長。

非常令人失望的是，雖然它能在短時間內解出骨灰級題目，但是，和上一個算法相比，對于簡單的題目，它比較耗時。在tsinsen系統中測試的時間是91ms。它的缺陷在于，每次遞歸都必須更新(i，j)格子所在的行、列、九宮格所有的元素。每次要求20個數的poss[i][j]。回溯同樣要更新。并且求poss[i][j]的函數時間復雜度是O(n)。每一步所耗時間比上一種算法多很多。但是，總的試驗的步數能顯著減少。 所以，這種算法適用于數獨解題的動畫演示和解極難題目。

四、程序結構

五、運行結果

六、總結和反思

后來老師提高了難度，要求程序能求出多解數獨題的解的個數。幾千個解的數據都能迅速得出答案，但是幾萬個解的數據，需要很長時間，更別提幾百萬的數據。這兩種遞歸的算法都有問題，優化的空間也有限，需要更強大、高效的算法。

這次Project讓我不斷思考，改進了最初的算法。編程是確實是一個克服困難、不斷改進與超越的過程。總有新的數據擺在面前，把原來的算法打擊得很慘，激勵著我們研究更加先進的算法。

數獨實驗報告范文 相關內容:

弗蘭克-赫茲實驗為能級的存在提供了直接的證據，對玻爾的原子理論是一個有力支持，那么，下面是第一范文網小編給大家整理收集的弗蘭克赫茲實驗報告內容，供大家閱讀參考。...

初中化學實驗報告如何寫?下面是第一范文網小編給大家整理收集的初中化學實驗報告的相關模板，僅供參考。初中化學實驗報告1實驗名稱 組裝實驗室制取氧氣的裝置實驗目的 正確地組裝一套實驗室制取氧氣的裝置，并做好排水集氣的準備實驗器材...

本科生實驗報告格式及相關要求填寫說明1、 適用于本科生所有的實驗報告(印制實驗報告冊除外)；2、 專業填寫為專業全稱，有專業方向的用小括號標明；3、 格式要求：① 用A4紙雙面打印(封面雙面打印)或在A4大小紙上用藍黑色水筆書寫。...

大學物理實驗報告模板實驗報告一.預習報告1.簡要原理2.注意事項二.實驗目的三.實驗器材四.實驗原理五.實驗內容、步驟六.實驗數據記錄與處理七.實驗結果分析以及實驗心得八.原始數據記錄欄(最后一頁)把實驗的目的、方法、過程、結果等記錄...

一、實驗目的1、了解局域網的組網方式以及雙絞線的兩種制作規范； 2、掌握RJ－45水晶頭的制作，以及網線連通性的測試。二、實驗環境RJ－45水晶頭若干、雙絞線若干米、壓線鉗一把、測線儀一套。...

一、背景作業場所的合理采光與照明，對生產中的效率、衛生和安全都有重要的意義。它是工作場所設計中的重要項目，無論是天然采光還是人工照明，其主要目的都是給人們的生活和生產提供必需的視覺條件。...

一、問題的提出長期以來，我國中學外語教學效果不理想。學生從初中開始上外語課，上幾 學期外語課之后就迅速地產生 了對外語課的厭煩情緒，即使研究生畢業之后， 絕大多數人也只能書面翻譯和閱讀本學科的外文資料，而不能 流利地與外國專...

【提出問題】(1)在前面做過了“測量小燈泡的電阻”的實驗，參考它的思路，怎樣測量小燈泡的電功率?(2)如果給你額定電壓分別為2.5V和3.8V的小燈泡各一只，你能測出它們的電功率嗎?(3)小燈泡上面如果標有額定功率，所標額定功率與通過P=UI測...

查看更多>>

總結

以上是生活随笔為你收集整理的android 数独实训报告,数独实验报告范文的全部內容，希望文章能夠幫你解決所遇到的問題。

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