anfa 的部落格

演算法 LAB1: SoDuKu Solver 1

"

資工三甲 493511632 岑志豪
進度: 解決 1-1 ~ 3-2 的題目


ADT

Sudoku()
初始化數獨

void Show()
顯示數獨表狀況

void showCheck(int r,int c)
顯示該位置有可能的答案

void checkValue(int r,int c,int v)
檢查數字是否存於指定位置的可能答案中

void eraseR(int r,int c)
清除第 r 列之不可能答案

void eraseC(int r,int c)
清除第 c 行之不可能答案

void eraseBox(int r,int c)
清除 第 r 列 第 c 行 所屬於的九方格區域中之不可能答案

void fill(int r,int c)
把唯一的答案儲存到指定的數獨格裡

void Input(String fInput) throws IOException
把指定的檔案讀入到數獨中

void Output(String fOutput) throws IOException
把數獨儲存到指定的檔案中

Boolean checkR(int r, int v)
檢查指定列中是否不存在某數值

Boolean checkC(int c, int v)
檢查指定行中是否不存在某數值

Boolean checkBox(int r, int c, int v)
檢查指定九方格區域中是否存在某數值

Boolean checkTotal()
檢查整體數獨和是否為 405 <= (1+9)*9/2*9

int sumTotal()
輸出現時整體數獨和

void solve()
解題


一開始先建立 Sudoku 物件, 透過 Input() 讀入檔案, 進而執行 solve() 開始解題.
Sudoku 基本是由一個 9x9 的 Integer Array 及 一個 9x9 的 HashSet 所組成.
Integer Array 儲存現時的數獨方格值, HashSet 為未知方格所存在的可能答案組.

在讀入檔案時, 把未知答案的 - 位置, 以數字0的方式記錄在 Integer Array 內,
同時也在該對應的 HashSet 內建位 1~9 的可能答案組.

透過 eraseR, eraseC, eraseBox, 把指定方格之可能答案逐漸減少.
假若檢查到該 HashSet 所存在的可能答案只剩下一個時, 則把該值記錄到 Integer Array 中.

solve 現時設定為最多執行 30次 清除可能答案步驟,
同時每次清除前後的答案相同次數不能多於8次.
如果在這之前, 透過 checkTotal 發現數獨問題已解決, 就不會再繼續執行清除回圈.
列出回圈執行次數, 清除回圈無效次數, 及解題所需時間.

最後用 Show() 顯示答案, 透過 Output() 記錄最後的結果到指定檔案中.

更新:

由於交作業的期限延長了, 現時進度為可解決到 3-2 的題目.

使用了以下的技巧 :

Hidden Singles Candidature
Naked Pairs
Hidden Pairs ( 不用這個也可解決 3-2 )

 正研究 X-Wing 的實踐方法, 應該會有助解決 4-X的題目


實測記錄

sdk1-1.txt
-----------------
Count: 4
Same:  0
Time:  6661461ns
-----------------
7 8 1 6 3 2 9 4 5
9 5 2 7 1 4 6 3 8
4 3 6 8 9 5 7 1 2
2 4 9 3 7 6 8 5 1
6 7 3 5 8 1 2 9 4
5 1 8 4 2 9 3 6 7
1 9 4 2 6 7 5 8 3
8 6 7 1 5 3 4 2 9
3 2 5 9 4 8 1 7 6
-----------------


sdk1-2.txt
-----------------
Count: 5
Same:  0
Time:  7626109ns
-----------------
9 8 2 5 4 7 3 6 1
4 6 5 1 8 3 9 2 7
7 3 1 9 2 6 8 4 5
3 2 6 8 1 5 4 7 9
8 7 9 3 6 4 5 1 2
5 1 4 2 7 9 6 8 3
1 5 7 4 9 8 2 3 6
2 4 3 6 5 1 7 9 8
6 9 8 7 3 2 1 5 4
-----------------


sdk1-3.txt
-----------------
Count: 5
Same:  0
Time:  10622020ns
-----------------
4 6 5 8 9 3 2 7 1
8 2 7 1 5 4 6 3 9
1 9 3 7 2 6 4 8 5
6 1 8 2 7 9 3 5 4
9 5 4 3 6 1 7 2 8
3 7 2 4 8 5 1 9 6
5 3 9 6 4 2 8 1 7
2 8 6 9 1 7 5 4 3
7 4 1 5 3 8 9 6 2
-----------------


sdk1-4.txt
-----------------
Count: 7
Same:  0
Time:  8541309ns
-----------------
8 1 7 2 6 4 5 3 9
9 5 2 7 8 3 1 4 6
3 6 4 9 1 5 2 8 7
1 7 6 3 9 8 4 2 5
4 2 8 5 7 6 9 1 3
5 3 9 1 4 2 7 6 8
6 9 3 4 5 1 8 7 2
2 4 5 8 3 7 6 9 1
7 8 1 6 2 9 3 5 4
-----------------


sdk1-5.txt
-----------------
Count: 12
Same:  0
Time:  9987582ns
-----------------
5 7 8 9 6 2 3 1 4
6 1 9 4 5 3 8 7 2
3 2 4 1 8 7 5 6 9
1 9 6 7 3 5 2 4 8
2 5 3 6 4 8 1 9 7
8 4 7 2 9 1 6 5 3
7 8 5 3 1 9 4 2 6
9 6 1 8 2 4 7 3 5
4 3 2 5 7 6 9 8 1
-----------------

 


讀入檔案名: sdk2-1.txt 

-----------------
Count: 9
Same:  2
Time:  18193374ns
-----------------
6 8 2 1 3 7 4 9 5
5 4 7 8 2 9 3 6 1
3 9 1 4 5 6 7 2 8
8 1 6 7 9 4 5 3 2
9 3 5 2 8 1 6 7 4
2 7 4 5 6 3 8 1 9
4 2 9 6 7 8 1 5 3
1 6 3 9 4 5 2 8 7
7 5 8 3 1 2 9 4 6
-----------------

 


 讀入檔案名: sdk2-2.txt
-----------------
Count: 18
Same:  2
Time:  19180930ns
-----------------
3 1 4 7 9 5 6 8 2
9 2 7 8 3 6 4 5 1
8 6 5 2 4 1 7 3 9
1 9 8 3 6 2 5 4 7
7 5 6 4 8 9 2 1 3
4 3 2 5 1 7 8 9 6
6 4 3 9 7 8 1 2 5
5 8 1 6 2 3 9 7 4
2 7 9 1 5 4 3 6 8
-----------------

 


 

 讀入檔案名: sdk3-1.txt
-----------------
Count: 14
Same:  4
Time:  18869996ns
-----------------
3 8 2 6 5 1 4 7 9
7 9 5 3 8 4 1 2 6
4 1 6 9 2 7 8 3 5
6 2 9 1 7 5 3 4 8
1 7 4 8 6 3 9 5 2
8 5 3 4 9 2 7 6 1
9 3 8 2 4 6 5 1 7
5 6 1 7 3 8 2 9 4
2 4 7 5 1 9 6 8 3
-----------------

 


 讀入檔案名: sdk3-2.txt
-----------------
Count: 16
Same:  5
Time:  25437869ns
-----------------
7 2 8 1 4 5 3 9 6
9 6 5 7 8 3 4 2 1
3 4 1 9 6 2 7 5 8
6 1 9 3 2 4 8 7 5
8 5 2 6 9 7 1 4 3
4 7 3 5 1 8 9 6 2
1 9 4 8 5 6 2 3 7
2 3 6 4 7 1 5 8 9
5 8 7 2 3 9 6 1 4
-----------------

 

"

LAB2

"LAB 02
組員: 493511632 岑志豪 資工三甲

Server 篇:
1. ASP.NET
起初以為要架一台 IIS Server 跑 ASP.NET 是一件很簡單的事情, 但後來我才發現這種想法有點天真...

先說要從哪裡灌 IIS 吧.
從 [控制台] -> [新增移除程式], 點選 [新增/移除 Windows 元件], 就會看到 IIS 的安裝選項.
把他打勾, 下一步, 就會開始灌的了. (需要 XP 安裝檔)

灌完後, 可以輸入 %SystemRoot%System32Inetsrviis.msc 進入他的設定介面.

在設定介面裡, 我們可以設定我們 IIS 所跑的 ASP.NE 版本.
這次我所使用的是 2.0.50727 版.

這個是需要在有安裝 .NET Framework 才可以使用的.
在這裡我有碰到個小問題.

起初就算有把 ASP.NET 的版本設定好, 但使用的時候會跑出 Error 來. ( Hello World 也 error? )
一定是哪裡出問題.

經過上網爬文後發現, 是 .NET Framework 1.1 和 2.0 之間的衝突引起的. ( 我2個都有灌. )

要解決問題, 需要重新定義一次我們現在需要用的 .NET 版本. ( 在那個 IIS 介面設定無效... )

先到 C:WINDOWSMicrosoft.NETFramework,
點選要使用該版本之資料夾. ( 現在為 v2.0.50727 )

執行 aspnet_regiis.exe -i, 那麼他就會把 ASP.NET 重新註冊一次的了.

然後我的 Hello World 就回來了. (笑)

2. JSP
JSP 我是使用 Apache Tomcat 5.0.28 (win32), 為什麼沒用上最新版的 5.5.20 呢? 因為 Server 這類東西有時間太新的話, 在技術支援上會不及舊版, 出問題機會也比較大, 所以我選擇了舊一點的版本.

除了主要的 Tomcat Server 外, 我還外加了一個 JDOM Package, 這樣可以比較方便對 XML 的運用.

雖然我有灌過 Apache ANT (1.6.5, win32), 但可能是我不太會設定的關係, Servlet 更新過後 Server 還是要重開.

3. PHP
這個我是使用大陸的 WAPM ( Apache + PHP + MySQL 整合包 ), 網路上也有不少這樣子的 整合包, 剛好看到這個就不想再找了. 簡單設定了一下, Apache 使用 2.0 版, PHP 5.0, MySQL 5.1 (這次沒用上),

編寫 篇:
1. ASP.NET
我把這次的作業先放到一叫 mytest 的虛擬資料夾中. (詳情如圖)


然後再由 http://localhost/Mytest/view.aspx 讀取我的網頁. ( 不知道為什麼不能用 127.0.0.1 )

這個網頁的功能是指照使用者所設定的檔案名稱去打開該 XML 檔, 預設名稱為 cdcatalog.xml


通過 post 的方式把設定傳回給自己再作處理, 以 table 的形式顯示出來.

瀏覽路徑: http://localhost/Mytest/view.aspx

Source Code:

view_aspx.jpg

cdcatalog_xml.jpg

2. JSP
我於 Tomcat 裡設定了一個叫 MyWeb 的 webapps,
內含 admin.jsp (瀏覽用), add.jsp (新增資料用), data.xml (預設之 XML 資料檔).
在 webappsMyWebWEB-INFlib 放了一個叫 jdom.jar 的 package.
另外在webappsMyWebWEB-INFclassestwcomfjuMyWeb 放了一個叫 XmlTest 的 Servlet.

admin.jsp 固定打開 data.xml 再以 table 的形式顯示出來, 這裡由於用上 jdom 的關係, 代碼比較簡潔.
add.jsp 提供使用者設定 輸入 輸出 之檔案名稱, 要寫入的 3個資料. ( 輸入 -> 修改 -> 輸出 )
設定好後會以 post 的方式把設定值傳給 Servlet XmlTest
在 XmlTest 有判斷是否使用 Post 形式連接, 不是的話會提出警告.
XML 之編碼有設定為 UTF-8, 經 jdom 處理後之 xml 能夠很工整地儲存起來.
( setNewlines, setIndent 設定. )

瀏覽路徑: http://localhost:8080/MyWeb/admin.jsp

Source:

add_jsp.jpg

admin_jsp.jpg

XmlTest.jpg

data_xml.jpg

3. PHP
PHP 這樣所寫的效果基本上和 JSP 所寫的一樣. ( admin.php, add.php, data.xml, XmlTest.php )
在每個 PHP 上有設定 header 為 Content-Type: text/html; charset=Big5 以確保以 Big5 編碼顯示.
這裡使用 DOM 來達成讀寫 XML 的目的. 但在使用的過程中, 碰到不少問題...

i. 這樣子, 寫入時他並不會自己縮排, 換行.
ii. 輸出 XML 檔時無法設定編碼. ( 固定為 <?xml version="1.0">, 但聽說文字是以 UTF-8 寫入的. )
iii. DOM 在讀取 UTF-8 形式之 XML 時會出現問題, 無法讀取.

因此這種方法只能讀寫 英文...

瀏覽路徑: http://127.0.0.1/MyWeb/admin.php

Source:

add_php.jpg

admin_php.jpg

XmlTest_php.jpg

其他 篇:
這裡作一點小補充, RoR 研究了好一陣子也沒成果... 囧 (怨念)
3種語言的 Server 是獨立的, 因為每次 只能/最好 開一個來測試.
但搞不太懂為什麼 ASP 的, 使用 IP 會被要求輸入密碼...
而 PHP 的輸入 localhost 無法讀取...

這次以能跑為目的, 美觀, 外形完全沒有考慮...

Orz

"

Lab1: Trackback 和 心得

"

這次的任務是嘗試引用這篇文章, 過程是很簡單的.

不過就算同學不會, 老師也有提供 trackback 教學的網址(這裡), Flash 教學, 看了就會懂 ^^

個人對 Blog 的感覺是和寫日記差不多, 但我不愛寫日記, 那就不愛寫 Blog 了... Orz

...傳說中好像還要建立 Basecamp Group 分組!?

難道我自己一個一組... ||

學號: 493511632

"

頁面