Cross Set

Cross Set

Not enough ratings
Cross Set 規則介紹與解題策略
By rahnoc
遊戲規則說明,並提供解題方法原理與使用時機。
   
Award
Favorite
Favorited
Unfavorite
遊戲基本規則說明
題目中,玩家會看到一個長m寬n的棋盤。每個格子裡面會有一到多個數字可供選擇。

正確答案要的是:對每一行/列,1,2,3...x(依長度決定) 每個數字都要出現,且不重複。
以長度為5為例,正解的每一行/列中,會是由 1,2,3,4,5 分配給每一格,數字不會重複。

範例:

[1] [2] [3] [4] [5]
> 這是可接受的答案。

[5] [4] [1] [3] [2]
> 這是可接受的答案。

[1] [1] [1] [2] [3]
> 這答案不行,1重複,也缺少 4, 5。

玩家的任務,就是於不違反規則下,找出每一格的數字。


遊戲中,每一格內會有多個數字。這些數字表示在本題中,此格的「可能填入值」。
玩家可藉由滑鼠左鍵點擊,選取你認為的答案。

範例:

[1,2] [2,3] [3]
> 第一格答案可能為 [1] 或是 [2]
> 第二格答案可能為 [2] 或是 [3]
> 第三格沒得選

[5,3,1,2,4] [2] [4,3] [3,4] [5]
> 第一格可以在 1~5 選一個答案 (題目中順序不見得是 12345 升冪排序)
> 第三第四格可選範圍相同,都是 [3,4]
解題基本原理
針對某行/列,於所有可能解答中,將違反規則的答案丟掉,當剩下最後一個時就找到答案了。

範例:

[1,2] [1,3] [2]

列出所有解答的話,有四種可能:

[1] [1] [2]
[2] [1] [2]
[1] [3] [2]
[2] [3] [2]

根據規則來檢查每一筆答案:

[1] [1] [2] > 1 重複了,而且缺 3。

[2] [1] [2] > 2 重複了,而且缺 3。

[1] [3] [2] > 合格!

[2] [3] [2] > 2 重複了,而且缺 1。

只有 [1] [3] [2] 剩下來,這就是我們要的答案。

------

當然正常人沒有時間去「全部」條列所有可能狀況,所以接下來要介紹的,是以與「條列後刪除矛盾」方法同樣道理,但採另一個方向的實戰策略。
實戰策略
共計四條

  1. 若某格只剩一個選擇,那個就是答案。

  2. 對某行/列來說,若某個數字在各格可選範圍加起來考慮下,只出現一次,那該數字一定是答案。

  3. 對某行/列,用重複出現n次的 n-tuple 刪減其他格的可選數字。 (詳細說明後述)

  4. 針對某格,把其同行/同列上,已確定會被他格用掉的數字,自其可選擇範圍中移除。

1,2 為確認某格答案。 3,4 為精簡某格的可選範圍。
實際遊戲中,玩家透過 1,2 <-> 3,4 來回反饋解題。
1. 若某格只剩一個選擇,那個就是答案。
> 意義在於,規則中有說「同行/列中,數字不能重複」。
> 確認某格,相當於告訴玩家,這個數字在其他格中不會出現。
> 延伸就是 策略3,4 的基礎

範例:

[1] [1,2]

> [1] 沒得選,所以這是答案。
> 對 [1,2] 來說,這一列的 1 被用掉了,所以可選範圍能把 1 擦掉,變成 [2]。 然後也能套用策略1來解右邊這格。

[1] [2]
2. 對某行/列來說,若某個數字在各格可選範圍加起來考慮下,只出現一次,為答案。
範例:

[1,2] [3] [1,3] [2,4]

> 對 4 來說,只有最右邊那格有得選。
> 如果最右邊那格玩家選 [2],則這一列剩下再怎麼選,都不會有 4 出現,違反「1,2,3...x(依長度決定) 每個數字都要出現」。
> 所以最右那格 4 一定要選。

變成 [1,2] [3] [1,3] [4]

> 然後 2 是不是只出現一次呢?因此第一格可決定

變成 [2] [3] [1,3] [4]

> 接下來 1 只出現一次,所以

變成 [2] [3] [1] [4]


* 對 [2] [3] [1,3] [4] 來說,也可以用策略4來解
> 因為 3 確定被用掉了,所以 [1,3] 可以把 3 擦掉。
3. 對某行/列,用重複出現n次的 n-tuple 刪減其他格的可選數字。
先定義名詞 n-tuple

> [1,2] 有兩個可選的,稱其為 2-tuple

> [3,1,2] 有三個可選的,稱其為 3-tuple

> [9,5,7,2] 有四個可選的,稱其為 4-tuple

> 以此類推...


對某行/列,重複出現n次的 n-tuple

範例:

[1,3] [1,3] [1,2,3,4] [4]
> [1,3] 為 2-tuple,且此列出現兩次。 (這是我們要的)

[1,2,3] [1,2,3] [1,2,3] [4] [5]
> [1,2,3] 為 3-tuple,且此列出現三次。 (這是我們要的)

[1,2,3] [1,2,3] [3,4] [4,5] [3,5]
> [1,2,3] 為 3-tuple,但是此列只出現兩次。 (這個不要!)


怎麼用?

[1,3] [1,3] [1,2,3,4] [4]

> 對上面的例子來說,第一格和第二格都是只能選 1 或 3。
> 規則為數字不可重複

[1] [1] [1,2,3,4] [4] > 這個不行
[3] [3] [1,2,3,4] [4] > 這個也不行

> 因為格子一定要選個數字,不能重複的條件下

[1] [3] [1,2,3,4] [4] > 不是 13 這樣
[3] [1] [1,2,3,4] [4] > 就是 31 這樣

> 那第一格和第二格到底是什麼,還是不知道呀!?
> 對,前兩格還不能確定。
> 但是對這一列來說,1 和 3 確定會被前兩格用掉。
> (關鍵) 對同列的其他格子來說, 像是 [1,2,3,4],他的可選範圍 1,3 可以擦掉了,因為「確定會被別格用掉」(雖然明確順序此時還不知道)。

[1] [3] [2,4] [4] > 第三格可精簡為
[3] [1] [2,4] [4] > ...或是這樣

> 因為 2 只出現在第 3 格; 或是你要說 4 已經被第四格用掉了,所以

[1] [3] [2] [4]
[3] [1] [2] [4]


* 為鴿籠原理(Pigeonhole principle) 推廣應用 (m=n)

對有連續n個 n-tuple 的行列來說,「不是」要解 n-tuple 的格子,而是可以縮減「其他格子」的可能範圍。
4. 針對某格,把其同行/同列上,已確定會被他格用掉的數字,自其可選擇範圍中移除。
範例:

[2,3,4] [1] [3] [2]

> 2 確定被用掉了,所以 第一格可以精簡為 [3,4]
> 同樣的 3 也確定被用掉了,所以 第一格可以再精簡為 [4]

[4] [1] [3] [2]
> 當然你也可以不分兩步驟,一次把 2,3 擦掉。


範例:

[2,3,4] [4] [1,3,4] [1,2,4]

> 4 確認用掉了,所以別的格子通通擦掉

[2,3] [4] [1,3] [1,2]

> 很不幸的,這裡沒辦法繼續下去了... 是嗎?
> 列卡住時,可以改用行來參考(見下個例子)


範例:

[2]
[2,3] [4] [1,3] [1,2]
[1]
[4]

> 用直行來看原本的第一格 [2,3],有沒有發現 2, 1, 4 都被用掉了呢?
> [2,3] 可以精簡為 [3]

[2]
[3] [4] [1,3] [1,2]
[1]
[4]

> [3] [4] [1,3] [1,2] 是不是就可以繼續解下去了?

[3] [4] [1] [1,2] > 3 被用掉
[3] [4] [1] [2] > 1 被用掉


列解到卡住時,挑其中一格,轉個90度改用行考慮。


範例(進階):
[1,3]
[1,2,3] [2,3] [1,3] [4]
[1,3]
[2,4]

> 就 [1,2,3] [2,3] [1,3] [4] 來看,沒辦法繼續下去。

[1,3]
[1,2,3]
[1,3]
[2,4]

> 但是直行來看,有兩個2-tuple [1,3]
> 所以 1和3 一定會被用掉,[1,2,3]可以精簡為 [2]

[1,3]
[2]
[1,3]
[2,4]

> 2 被用掉了,最下面一格可以擦掉 2

[1,3]
[2]
[1,3]
[4]

> 這裡就卡住了,沒關係,回到橫列...

[2] [2,3] [1,3] [4]

> 2 被用掉,擦掉其他格子的 2

[2] [3] [1,3] [4]

> 3 被用掉,精簡 [1,3]

[2] [3] [1] [4]

> 最後會停在這裡,

[1,3]
[2] [3] [1] [4]
[1,3]
[4]

> 不能繼續了? 誰說的,你可以嘗試其他的行列(雖然本例子沒有提供)
總結
綜上所述,將策略 1,2,3,4 混合使用,可以一步一步的減少可能範圍。

實際遊玩時,筆者建議玩家可以將題目用「鉛筆」謄寫到紙上,然後用上述策略解題時,刪減範圍後就直接擦掉或劃掉數字。
這個遊戲因為被用掉的數字還會留在畫面上,所以後期反而一堆數字會看得眼花撩亂。

但是採紙筆解時要注意,若是擦錯了,重來會相當麻煩⋯⋯





Ex 進階策略:
有的題目,光靠上面 策略1~4 去解,會發生「解到卡住」,也就是盤面以策略1~4重複套用,都無法產生變動的情況。

(這裡不討論 出現錯誤,(e.g. 題目抄錯),導致發生矛盾 無法繼續動作 的情況)

範例:

[1,2] [1,2]
[1,2] [1,2]

> 有兩種解答

[1] [2]
[2] [1]

[2] [1]
[1] [2]

遇到這種情況時,可以採用策略 5

5. 挑一個有兩個以上數字的格子,猜它是其中某個數字,然後試著解解看。 不行再換別的猜。
5. 挑一個有兩個以上數字的格子,猜它是其中某個數字,然後試著解解看。 不行再換別的猜。
例如上面那個範例,若左上角 [1, 2] 猜是 [1], 則會取得答案 A。 若猜是 [2],會取得答案 B。

也有可能你一猜下去,之後解完某行,發現另一列出現兩個 [4] [4],這就代表這次的猜測不行。

而且可能在猜測之後,又解到卡住,需要在這個猜測的前提下,再開始下一層的猜測⋯⋯ (recursive)

(若你打算寫程式來解的話,請留意盤面快照,與多層猜測的 backtracking。)

(不同猜測可能最後會引向相同解答,想提升程式效率可以在這點著手。)

策略 5 算是暴力解法,其實可以在任何盤面時間點使用。 但還是建議手動玩家先依靠 策略 1~4 解到極限再去使用。


Cross Set Infinity 的 "5-14" 就是光靠 策略 1~4 你會解到 halt 住的問題。

351,613,342,512,625,135,
423,342,125,623,563,341,
624,451,534,561,635,136,
461,345,634,523,251,456,
356,145,451,534,145,251,
135,462,236,524,312,514

> 解到這裡會卡住

[1, 3, 5] [6, 1, 3] [4] [2, 5, 1] [5, 6, 2] [1, 5, 3]
[4, 3] [3, 2] [1, 5, 2] [6, 2] [3, 6, 5] [4, 1, 3]
[2] [4] [5, 3] [6, 1, 5] [3, 5, 6] [6, 1, 3]
[4, 1] [5, 3] [3, 6] [5, 2] [5, 2, 1] [5, 4, 6]
[6] [5, 1] [1, 5] [3] [4] [2]
[3, 1, 5] [6, 2] [2, 3, 6] [4] [2, 3, 1] [1, 5]

> 若你猜左上角為 [1], 某一行會出現重複數字,

> 當你猜左上角為 [5], 將會導向下面的答案:

[5] [1] [4] [2] [6] [3]
[4] [2] [5] [6] [3] [1]
[2] [4] [3] [1] [5] [6]
[1] [3] [6] [5] [2] [4]
[6] [5] [1] [3] [4] [2]
[3] [6] [2] [4] [1] [5]