JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » Java 程式分享區 » 數獨、猜數字  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to topicthreaded modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 挑戰 su do ku
jimmy14

Give me J-Power !



發文: 787
積分: 3
於 2005-06-02 15:54 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
http://www.sudoku.com/index.htm (中國時報這幾天都有刊登)
規則很簡單, 9*9 的格子中,每列,每行數字不可重複。
每個 "3*3" 的 "Box" (共9個) 內的數字也不可重複。
附件是 eclipse java project, 請將你的演算法寫在 SolvePuzzle() 內
1
2
3
4
5
6
    static void SolvePuzzle() {
        /*
         * write your algorithm here
         */
        ReadPuzzle("answer.txt"); // 還不知怎麼解, 直接偷看答案
}

可以從 Eclipse, 或在 Command 底下執行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
C:\eclipse\workspace\sudoku>java -classpath bin sudoku
Read puzzle file:sudoku.txt
 |123456789
-+---------
1|-6-1-4-5-
2|--83-56--
3|2-------1
4|8--4-7--6
5|--6---3--
6|7--9-1--4
7|5-------2
8|--72-69--
9|-4-5-8-7-
-+---------
 
Solve puzzle in 15 microseconds.
 |123456789
-+---------
1|963174258
2|178325649
3|254689731
4|821437596
5|496852317
6|735961824
7|589713462
8|317246985
9|642598173
-+---------
Good Job!

歡迎大家來挑戰最佳的演算法 Thumbs up
~~~
更新一下 class name, sudoku.txt 增加 6/1, 6/2 的資料
想測試其它資料,可到 http://www.griffiths-jones.co.uk/sudoku/index.html

sudoku.zip (4.77k)


caterpillar edited on 2006-11-09 08:35
reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
jd001982





發文: 366
積分: 6
於 2005-06-04 08:44 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
規則很簡單, 9*9 的格子中,每列,每行數字不可重複。
每個 "3*3" 的 "Box" (共9個) 內的數字也不可重複。
1
2
3
4
5
6
7
8
9
10
11
12
 |123456789
-+---------
1|963174258
2|178325649
3|254689731
4|821437596
5|496852317
6|735961824
7|589713462
8|317246985
9|642598173
-+---------

紅色的 3x3 box 不是有重複嗎? (5 和 6)


reply to postreply to post
作者 Re:挑戰 su do ku [Re:jd001982]
jimmy14

Give me J-Power !



發文: 787
積分: 3
於 2005-06-04 11:09 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
我還以為太簡單沒人回應了 Dead
(其實應該還蠻簡單的啦).

不是任何相鄰的 3x3 box, 是
1
2
3
[1..3][1..3], [1..3][4..6], [1..3][7..9]
[4..6][1..3], [4..6][4..6], [4..6][7..9]
[7..9][1..3], [7..9][4..6], [7..9][7..9]

上面這9個 box, 每個 box 內的數字不能重複。


reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
porcupine





發文: 1
積分: 1
於 2005-06-06 21:22 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
用recursive 寫了一個解決的solution,沒有考慮速度,不過執行了一下還滿快的!參考參考!

sudoku.java (5.86k)


reply to postreply to post
作者 Re:挑戰 su do ku [Re:porcupine]
jimmy14

Give me J-Power !



發文: 787
積分: 3
於 2005-06-06 23:31 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
第一編Post就來挑戰 Thumbs up
該不是為了這個題目特地註冊一個ID吧Cool ?

答案的確很快就找出來了 (31 ms, AMD XP 1700+, Win XP).


reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
jimmy14

Give me J-Power !



發文: 787
積分: 3
於 2005-06-07 00:36 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
找答案看起來蠻簡單,但不知題目 "如何" 產生Stupid

挑戰:
(1) SuDoKu generator
(2) 目前看到的題目中, Very Hard 用到 28 格數字,
能找到用更少數字的"題目"嗎 (只能有一組解的題目)

這應該就有點挑戰性了,如果用暴力法求解,應該會花一點時間吧


reply to postreply to post
作者 Re:挑戰 su do ku [Re:porcupine]
yaocl





發文: 101
積分: 4
於 2005-06-07 09:57 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
提供一個解法,計算速度沒有你寫的厲害,但程式比較"物件"一點
Class的關係為

1
2
3
Puzzle --- PuzzleSquare ------- PuzzleData
   |           |                   |
   ----- ---PuzzleConstraint --- PuzzleConstraintData


另增加一個 constraint.txt 可以設定 constraint block 的限制
(因為有些puzzle的書裡面,有提供一些題目,
並不是使用3x3的九公格,而是任意設定的blocks)

porcupine wrote:
用recursive 寫了一個解決的solution,沒有考慮速度,不過執行了一下還滿快的!參考參考!


sudoku.zip (22.05k)


yaocl edited on 2005-06-07 09:59
reply to postreply to post
Sandglass Principle
作者 Re:挑戰 su do ku [Re:porcupine]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2005-06-07 21:15 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
porcupine wrote:
用recursive 寫了一個解決的solution,沒有考慮速度,不過執行了一下還滿快的!參考參考!


稍微修改一下, 加上簡單的 checking rule, 速度就已經提高 ~50% ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
  static void SolvePuzzle() {
    GetAns();
  }
 
  static boolean GetAns() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (puzzle[i][j] <= 0) {
                    next_value: for (int value = 1; value <= 9; value++) {
                        // On the same column, make sure no any row already used it
                        // On the same row, make sure no any column already used it
                        for (int k = 0; k < 9; k++) {
                            if ((puzzle[k][j] == value) || (puzzle[i][k] == value)) {
                                continue next_value;
                            }
                        }
                        // On the 3x3 box, make sure no other cell already used it
                        int p = (i / 3) * 3;
                        int q = (j / 3) * 3;
                        for (int x = 0; x < 3; x++) {
                            for (int y = 0; y < 3; y++) {
                                if (puzzle[p+x][q+y] == value) {
                                    continue next_value;
                                }
                            }
                        }
                        
                        puzzle[i][j] = (byte) value;
                        if (GetAns()) {
                            return true;
                        } else {
                            puzzle[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }


T55555 edited on 2005-06-07 21:30
reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
jimmy14

Give me J-Power !



發文: 787
積分: 3
於 2005-06-07 22:54 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
jimmy14 wrote:
找答案看起來蠻簡單,但不知題目 "如何" 產生Stupid

挑戰:
(1) SuDoKu generator
(2) 目前看到的題目中, Very Hard 用到 28 格數字,
能找到用更少數字的"題目"嗎 (只能有一組解的題目)

這應該就有點挑戰性了,如果用暴力法求解,應該會花一點時間吧

找到一組只填了20格的SuDoKu
1
2
3
4
5
6
7
8
9
----5---3
-1----9--
--2--6---
8----7-5-
-6-----1-
-9-3----4
---1--8--
--7----2-
4---9----

解題很快,可是要怎麼出題呢,目前還沒想到演算法。
請大家提供一點方向吧


jimmy14 edited on 2005-06-07 22:57
reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2005-06-07 23:56 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
jimmy14 wrote:
找到一組只填了20格的SuDoKu
1
2
3
4
5
6
7
8
9
----5---3
-1----9--
--2--6---
8----7-5-
-6-----1-
-9-3----4
---1--8--
--7----2-
4---9----

解題很快,可是要怎麼出題呢,目前還沒想到演算法。
請大家提供一點方向吧


Let's Make Sudoku!
http://www.pro.or.jp/~fuji/java/puzzle/numplace/makesudoku/sudoku01.html.en

Su DoKu composer
http://www.act365.com/sudoku/
http://www.act365.com/sudoku/Composer.htm

Oxford University Computing Laboratory
Sudoku: a programming competition
http://spivey.oriel.ox.ac.uk/mike/comp2005/

If you like read more math ...
Proof that Sudoju are NP-hard
http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf

... etc


T55555 edited on 2005-06-08 00:01
reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2005-06-09 00:13 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
Hi jimmy14,

我看您對 SuDoKu 非常非常熱心... 還跑到灌水版去找 combination.
您的問題一老早就已有人問了.

(1) 最少格數 (17, 18 ?) 讓 SuDoKu 只有一解 ?
(2) Empty 9x9 (81) 總共有多少解 ?

Check this forum thread.
http://www.sudoku.com/forums/viewtopic.php?t=44

討論很長很長, 我沒有耐心去看完它, 等您看完有答案再告訴我好了. Smile


reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2005-06-09 01:39 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
再給您一些消息:

Unsolved Problem in Mathematics #2242 : The Secret of Sudoku
http://blogs.warwick.ac.uk/fangz/entry/unsolved_problems_in/

The number of valid Sudoku solution grids for the standard 9×9 grid
with 3×3 regions was calculated by Bertram Felgenhauer to be
6,670,903,752,021,072,936,960
This number is equivalent to 9! × 722 × 27 × 27,704,267,971
the last factor of which is prime.
http://en.wikipedia.org/wiki/Sudoku#Mathematics_of_Sudoku
Source Code:
http://www.inf.tu-dresden.de/~bf3/sudoku/

According
Unsolved Problem in Mathematics #2242 : The Secret of Sudoku
http://blogs.warwick.ac.uk/fangz/entry/unsolved_problems_in/
They said:
So, what's the minimum number of hints we need to give to get a single unique solution? We don't know. The best that has been found is 18. But we really don't know. (Or at least, I don't know.)

所以 最少 18 格已有人找到了.
你去挑戰 17 格吧.
(當然如果你找到數學理論去證明最少格數更好, 目前好像沒人知道最少格數是多少, 也沒有任何證明文件)


reply to postreply to post
作者 Re:挑戰 su do ku [Re:T55555]
jimmy14

Give me J-Power !



發文: 787
積分: 3
於 2005-06-09 09:30 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
上網一看,已經有一組 17 格的 SuDoKu 被找到了。
1
2
3
4
5
6
7
8
9
--69---7-
----1---2
8--------
-2------4
--------1
--5--6---
-------6-
-----2-5-
-1--43---

用自已寫的solver跑, 花了137,906ms, 如果要跑完 all test
確定是否是唯一解, 不曉得要跑多久 Dead

還以為 9x9 的 grid, 暴力法應措措有餘,
看來太小看 NP Complete 的威力了Embaressed


jimmy14 edited on 2005-06-09 09:36
reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2005-06-09 21:34 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
jimmy14 wrote:
上網一看,已經有一組 17 格的 SuDoKu 被找到了。
1
2
3
4
5
6
7
8
9
--69---7-
----1---2
8--------
-2------4
--------1
--5--6---
-------6-
-----2-5-
-1--43---

用自已寫的solver跑, 花了137,906ms, 如果要跑完 all test
確定是否是唯一解, 不曉得要跑多久 Dead

還以為 9x9 的 grid, 暴力法應措措有餘,
看來太小看 NP Complete 的威力了Embaressed


用上次我的解法 ( without recopy the puzzle ),
http://www.javaworld.com.tw/jute/post/view?bid=35&id=111071&sty=3
解這 17 格 puzzle 只需 4860 ms ( 我的 computer speed is like yours ).

現在把上次的程式稍加修改就可以找出所有答案,
用這改過的程式去解這 17 格 puzzle,
的確只有一解, 我的暴力法對這 17 格 NP-complete 還可以,
只用了 ~ 10969 ms 就 check 完所有的 possibilities.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
  static void SolvePuzzle() {
    GetAllAns();
  }
 
  static void GetAllAns() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (puzzle[i][j] <= 0) {
                    next_value: for (int value = 1; value <= 9; value++) {
                        // On the same column, make sure no any row already used it
                        // On the same row, make sure no any column already used it
                        for (int k = 0; k < 9; k++) {
                            if ((puzzle[k][j] == value) || (puzzle[i][k] == value)) {
                                continue next_value;
                            }
                        }
                        // On the 3x3 box, make sure no other cell already used it
                        int p = (i / 3) * 3;
                        int q = (j / 3) * 3;
                        for (int x = 0; x < 3; x++) {
                            for (int y = 0; y < 3; y++) {
                                if (puzzle[p+x][q+y] == value) {
                                    continue next_value;
                                }
                            }
                        }
                        
                        puzzle[i][j] = (byte) value;
                        GetAllAns();
                        puzzle[i][j] = 0;
                    }
                    return;  // cannot find any possible value, just return
                }
            }
        }
        PrintPuzzle();
        boolean success = CheckRule();
        if (success)
            System.out.println("Good Job!");
        else
            System.out.println("Oops! test failed, try again.");
    }


BTW: This will backtracking to default input value, so ignore the very last check and Oops message (on the main method).

你可以嘗試拿掉 17 格的任一數字 to reduce to 16 格,
再用這改過的去解, 你就會得到不只一解的所有答案.


reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
jimmy14

Give me J-Power !



發文: 787
積分: 3
於 2005-06-11 23:52 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
改良過的 SuDoKu Solver,
找到第一組答案: 1500 ms.
確認唯一解: 3719 ms.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
C:\eclipse\workspace\sudoku>java -classpath bin sudoku
Read puzzle file:sudoku.txt
 |123456789
-+---------
1|--69---7-
2|----1---2
3|8--------
4|-2------4
5|--------1
6|--5--6---
7|-------6-
8|-----2-5-
9|-1--43---
-+---------
Find answer 1 in 1500 ms.
 |123456789
-+---------
1|146928375
2|593617842
3|872435916
4|721359684
5|968274531
6|435186297
7|257891463
8|384762159
9|619543728
-+---------
No more answer in 3719 ms.
 
C:\eclipse\workspace\sudoku>

如果有人看見少於17格的SuDoKu, 記得post上來讓大家分享哦.
(不曉得這組是如何找出來的 Stupid )

sudoku.zip (5.24k)


reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
vincentwin





發文: 2
積分: 0
於 2005-07-30 20:59 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
http://www.setbb.com/phpbb/index.php?mforum=sudoku

reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
忙至極





發文: 116
積分: 5
於 2005-12-13 00:04 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
最近想試試寫一個sudoku的小程序玩玩﹐來到這裡找資料時才發覺原來半年前就已經有人開始討論這個題目了﹐而且還討論到非常深入的地步……

小弟實在有些偷懶﹐把各位前輩討論的成果組合起來試玩了一段時間﹐可惜到現在還未找到自己滿意的解題方法﹐弄得自己有些灰心……﹐現在先把我試玩了一段時間的程序放上來給大家一起玩玩吧。

SuDoKu.jar (7.66k)


reply to postreply to post
  【忙至極者﹐閒也;忙中藏閒﹐願也】

我比較喜歡寫以 Applet 形式出現的小程序,因為可以在不需膽心安全問題下,在自己平時用慣的瀏覽軟件中去體會這些小程序的趣味。
作者 Re:挑戰 su do ku [Re:jimmy14]
忙至極





發文: 116
積分: 5
於 2006-05-25 22:31 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
最近買了部新手機﹐嘗試把手機版的sudoku寫出來﹐現在把它放上來給大家看看﹐這個程序在se 的k700i試過﹐其他的牌子手機不太過清楚是否能正常運作。

p.s. 因為是剛開始學寫手機版的java程序﹐很多東西都不懂﹐很多謝王森的Java手機/PDA程序設計入門這本書讓我學到很多手機版的入門知識。

.
.
.
補充:

一直想把這篇文章完成後才發表與大家分享﹐可惜我的表達能力不足﹐每次寫好
一部份又覺得寫得不好﹐結果又重新再寫......明明只有兩條問題﹐但總是寫不
出想表達的意思來。希大家看得明白 ^__^"

寫這個程序時所出現過的主要問題及自己用來解決的笨方法:

1. 這個程序出新題目(new game)時需要找出一個題目有多少個解嗎?
應該不需要知道題目共有多少個解﹐只要知道該題目是否只有唯一的解
就足夠了(一個新題目應該只有唯一的一個解)。
我計算是否唯一解的方法: 分別用相反的9x9順序執行 解題程序兩次
再比較兩次的答案就可以知道是否只有唯一解了。

2. 怎樣產生一個新題目?
我用的方法:用亂數重定9x9這81格的順序再以此順序執行解題程序﹐
再以另一個弄亂的順序逐次減少一格再測試減少該格後是否能得到
唯一解。(如果減少不能得到唯一解就不減少。)

SuDoKu13.jar (10.57k)


忙至極 edited on 2006-05-26 23:50
reply to postreply to post
  【忙至極者﹐閒也;忙中藏閒﹐願也】

我比較喜歡寫以 Applet 形式出現的小程序,因為可以在不需膽心安全問題下,在自己平時用慣的瀏覽軟件中去體會這些小程序的趣味。
作者 Re:挑戰 su do ku [Re:jimmy14]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2006-05-26 18:12 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list



我也寫了個 Sukoku Solver, 解出上述所有的題目 (共四題, 包括17格的最難的那題), 用普通的電腦跑, 在假設題目正確的條件下(意即沒有重複的解), 所花的時間都是 0 ms.


worookie edited on 2006-05-26 18:16
reply to postreply to post
作者 Re:挑戰 su do ku [Re:worookie]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2006-05-26 19:03 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
程式如附件, 沒有好好整理, 有點亂, 請包含.

Sudoku.java (9.47k)


worookie edited on 2006-05-26 19:47
reply to postreply to post
作者 Re:挑戰 su do ku [Re:worookie]
jimmy14

Give me J-Power !



發文: 787
積分: 3
於 2006-05-26 23:21 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
太神啦!!
「我才不及卿,乃覺三十里。」


reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2006-05-27 02:33 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
jimmy14 wrote:
太神啦!!


不敢當不敢當
其實程式還有很大的改善空間 (例如在最後那裏的 TODO 部分), 目前還沒有空去完成他.
而且有個比較討厭的地方是, 程式的解題速度已經達到 0 ms, 就算改了程式, 也很難判斷到底解題速度有沒有進步.
所以我相信一定有許多人寫的比我好


worookie edited on 2006-05-27 02:37
reply to postreply to post
作者 Re:挑戰 su do ku [Re:jimmy14]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2006-05-27 04:06 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
FYI - Ruby version
http://www.rubyquiz.com/quiz43.html


reply to postreply to post
作者 Re:挑戰 su do ku [Re:worookie]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2006-05-29 17:06 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
程式大改, 速度快了三倍.

sudoku.jar (17.32k)


reply to postreply to post
作者 Re:挑戰 su do ku [Re:忙至極]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2006-06-01 19:19 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
目前我研究的 sudoku 相關資訊並不是很多, 如果以下的理解有誤的話, 還請多多指教:

忙至極 wrote:
我計算是否唯一解的方法: 分別用相反的9x9順序執行 解題程序兩次
再比較兩次的答案就可以知道是否只有唯一解了。

這樣應該還無法證明是否只有唯一解


2. 怎樣產生一個新題目?
我用的方法:用亂數重定9x9這81格的順序再以此順序執行解題程序﹐
再以另一個弄亂的順序逐次減少一格再測試減少該格後是否能得到
唯一解。(如果減少不能得到唯一解就不減少。)

這樣的程式要跑很久, 肯定在我們的有生之年看不到他跑完.

目前世界上可找到的所謂 sudoku 題目產生器, 不外乎下列幾種:
(1) 從現有的已知題庫中隨機抓一個
(2) 從已知的題目模式 (pattern or template) 來動態產生一個新題目
(3) 很多個 hints 的題目 (也就是數目字很多個的題目) 產生器
(4) 真正萬能的題目產生器, 理論上可以產生各種模式的題目, 但實際上程式執行的速度很慢, 想要產生真的有價值的 "新的" 題目, 可能程式一輩子都跑不完.

其實上述幾種題目產生器, 程式都很簡單就可以寫出來. 但是我個人覺得寫出這樣的程式來並沒有多大價值. 厲害的是要能寫出程式來找尋出沒有被別人發現過的新的題目模式 pattern/template. 所以我覺得我自己一點也不厲害.


worookie edited on 2006-06-06 18:13
reply to postreply to post
go to first page go to previous page  1   2  go to next page go to last page
» JWorld@TW »  Java 程式分享區 » 數獨、猜數字

reply to topicthreaded modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8