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

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

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to postflat modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 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
話題樹型展開
人氣 標題 作者 字數 發文時間
21943 挑戰 su do ku jimmy14 955 2005-06-02 15:54
17705 Re:挑戰 su do ku jd001982 334 2005-06-04 08:44
17482 Re:挑戰 su do ku jimmy14 225 2005-06-04 11:09
13584 Re:挑戰 su do ku T55555 190 2006-08-29 22:11
17667 Re:挑戰 su do ku porcupine 51 2005-06-06 21:22
17380 Re:挑戰 su do ku jimmy14 87 2005-06-06 23:31
17259 Re:挑戰 su do ku jimmy14 154 2005-06-07 00:36
17168 Re:挑戰 su do ku jimmy14 363 2005-06-07 22:54
17232 Re:挑戰 su do ku T55555 665 2005-06-07 23:56
21090 Re:挑戰 su do ku yaocl 399 2005-06-07 09:57
17779 Re:挑戰 su do ku T55555 1775 2005-06-07 21:15
17567 Re:挑戰 su do ku T55555 260 2005-06-09 00:13
17048 Re:挑戰 su do ku T55555 951 2005-06-09 01:39
16987 Re:挑戰 su do ku jimmy14 267 2005-06-09 09:30
17237 Re:挑戰 su do ku T55555 2567 2005-06-09 21:34
18505 Re:挑戰 su do ku jimmy14 614 2005-06-11 23:52
14456 Re:挑戰 su do ku worookie 203 2006-05-26 18:12
14753 Re:挑戰 su do ku worookie 24 2006-05-26 19:03
14349 Re:挑戰 su do ku jimmy14 21 2006-05-26 23:21
14412 Re:挑戰 su do ku worookie 179 2006-05-27 02:33
14641 Re:挑戰 su do ku worookie 13 2006-05-29 17:06
16606 Re:挑戰 su do ku vincentwin 50 2005-07-30 20:59
15675 Re:挑戰 su do ku 忙至極 159 2005-12-13 00:04
14579 Re:挑戰 su do ku 忙至極 569 2006-05-25 22:31
14385 Re:挑戰 su do ku worookie 658 2006-06-01 19:19
14122 Re:挑戰 su do ku 忙至極 325 2006-06-07 12:52
14457 Re:挑戰 su do ku T55555 55 2006-05-27 04:06
» JWorld@TW »  Java 程式分享區 » 數獨、猜數字

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

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8