作者raincole (冷雨)
看板Prob_Solve
標題[問題] 填色問題
時間Thu Sep 17 23:38:51 2009
※ [本文轉錄自 puzzle 看板]
作者: raincole (冷雨) 看板: puzzle
標題: [問題] 填色問題
時間: Wed Sep 16 07:36:52 2009
有一張6*4的方格紙，將其中12格塗黑，使每列皆有2格、每行皆有3格為黑。
問有多少種上色方法？
原方格紙：
□□□□
□□□□
□□□□
□□□□
□□□□
□□□□
其中一種上色方法：
■■□□
□■■□
□□■■
■■□□
■□□■
□□■■
這題有沒有什麼方法可以計算？
又，如果每列要求的黑格數是不等的呢？（每行仍然相等）
版友rehearttw提出交換法，
但假設我一開始的盤面是這樣：
□■■□
□■■□
□■■□
■□□■
■□□■
■□□■
交換以後就會產生重複解了...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 113.61.199.94
1F：推 rehearttw:先找一解，然後橫的交換乘上直的交換，注意一樣的 09/16 09:24
2F：推 isnoneval:老師, 並非所有解之間都可以經由交換變過去的說 09/16 09:54
3F：→ raincole:我一開始也是那想法，但那樣會多很多重複解...？ 09/16 10:40
4F：→ raincole:而且有一些交換會產生不合法解吧... 09/16 10:42
5F：推 dzihaenn:舉例錯了? 每行四個圖黑? 09/16 12:01
6F：→ dzihaenn:題目每行四個塗黑??? 09/16 12:04
7F：→ raincole:三格 打題目時疏忽抱歉，謝謝提醒 09/16 12:20
※ 編輯: raincole 來自: 113.61.199.94 (09/16 12:21)
※ 編輯: raincole 來自: 113.61.199.94 (09/16 12:22)
8F：推 rehearttw:例如我把第一橫列和第五橫列交換，不是答案嗎？ 09/16 15:03
9F：→ rehearttw:我把第二直行和第三直行交換，不是答案嗎？ 09/16 15:03
10F：→ rehearttw:橫的單獨有幾種換法，直的單獨有幾轉換法... 09/16 15:04
11F：→ rehearttw:這應該是高中的不盡相異物排列，只是我不知道是否就是 09/16 15:04
12F：→ rehearttw:全部的答案... 09/16 15:04
13F：→ rehearttw:每列要求的黑格數是不等的，我還沒想出來... 09/16 15:05
14F：→ raincole:呃...應該不會產生不合法解沒錯，但重複解呢？ 09/16 15:18
※ 編輯: raincole 來自: 113.61.199.94 (09/16 15:19)
※ 編輯: raincole 來自: 113.61.199.94 (09/16 15:19)
15F：推 isnoneval:我的意思就是, 靠交換無法配出所有的解 09/16 15:40
16F：推 rehearttw:能不能證明呢？ 09/16 21:57
17F：推 rehearttw:照我的算法，原題目有 4320 種答案。不知答案是？ 09/16 22:00
18F：推 rehearttw:嗯！原 PO 後來加的例子，是不能由原解交換得來 09/16 22:05
19F：→ rehearttw:但後來的例子，交換可以得到很多答案 09/16 22:05
20F：推 puzzlez:還想不出好算的方法耶～0.0 09/17 05:57
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 113.61.199.94
21F：推 seanwu:試試Ploya 09/18 00:34
22F：→ seanwu: polya 09/18 00:34
24F：→ seanwu:呃...|| 沒事，我好像看錯題意了.. 09/18 00:42
25F：推 LinkCar:DP 遞迴???左行往右行發展 09/19 13:43
※ 編輯: raincole 來自: 113.61.199.94 (09/19 16:58)
26F：→ raincole:不懂 怎麼弄？他每行並非只跟上一行有關係吧... 09/19 16:58
27F：→ raincole:我有想過一個DP解 但維度要和每行黑格數相同... 09/19 16:58
28F：→ raincole:無法直接開陣列使用，只能拿排序樹存狀態 09/19 16:59
29F：→ raincole:但應該有更好的解法 09/19 17:02
30F：推 seanwu:rain你說的dp，是像這樣? dp[6][4][4][4][4] ? 09/19 21:43
31F：→ raincole:對，我看到維數那麼多就高估了空間需求，其實是放的下XD 09/21 01:28