作者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