Re: Polymino & Polycube - 拼圖

※ 引述《EIORU ()》之銘言：
: (1)★★★★
: ███ Q:必須用到幾個該方塊 才能拼出最小的長方形
: ███ (7個1x1)
: █
: (2)★★
: ██ Q:必須用到幾個該方塊 才能拼出最小的長方體
: ██ (第一層4個1x1x1 第二層1個1x1)

以下只剩第一題還沒有完全解，不過差不多了 xD（寫程式或努力算一定有答案）

































第二題簡單很多：

AA BB BB CD DD
AA AB CC CC DD

第一題。以下是上界 28 漂亮的點對稱！

AAABBBAAABBBAA
AAABBCCAABBBAA
BBABBCCAABDAAA
BBDDDCCCDDDBBB
BBBDDBBBDDDBBB
AAADDBBBAACCCB
AAACAAABAACCCA
ACCCAABAAACAAA
BCCCAABBBDDAAA
BBBDDDBBBDDBBB
BBBDDDCCCDDDBB
AAADBAACCBBABB
AABBBAACCBBAAA
AABBBAAABBBAAA

（C 和 A 有另一種排法，然後中間的 A 和 B 至少有另一種排法，總共至少 64
種對稱解？）

下界：固定長方形一邊寬度。

首先要知道固定的那邊一定是 2 或 3 組成，而且下面是基本型：

(1) X 必導致 B 和 C
_______ _______ _____
XBBB |XXX XBBB|
XBBB |XXX XBBB|
XX B |BBX XBCC|
|BBCCC DDDCC|
|BBBCC DDCCC|
| CC DD

(2) 無解
XXXXXXXX
XXX XXXXX XXXX X X XXXXXX XXXXXXX XXXXXXXX
X X XX X XX X X X XXXX X X XX XX XX
X X X X X X X X XX X X X
X X XXX X X ? X X
X X
X X

(3) 固定的邊上 2 不可能比 3 多

(4) 角落為 3 3 時只有四種（不對稱）擺法
______ ______ ______ ______
|AAADDD |AAABBB |AAABBB |AAABBB
|AAADD? |AAABBB |AAAABB |AABBBB
|BBAD? |ACCCDB |AAAABB? |AABBBB
|BBCCC |CCCCDDD |CAAADDD |CCBBB
|BBBCC |CCCCDDD |CCC ?DD |CCDDD
| CC |CCC |CCC ?? |CCCDD
| DD

1, 2: 不行
3: 基本型 (1) 無解
4: 一定是 2+2 不行。
5: 一定是 3+2 參考基本型 (1) 無解
6: 必為 3+3 若 A 為
______
|AAA |
|AAA |
|BBA |
|BBCCC?|
|BBBCC?|
| CC?|

問號處無解。其他都要七格以上。

7: 7=2+2+3 不行
8: 3+3+2 若為 3 3 2 則 A 怎麼擺都不對
________
|AAABBBCC|
| A BBBCC|
| BDCCC|
DDD
DDD

若為 3 2 3 則 C 往那一方向都是無解
________
|AAACCAAA|
|AAACCAAA|
|A CCC A|

9: 必為 3+3+3 若 A 如下則...
_________
|AAABBBCCC|
|AAABBBCCC|
|A BCDD|
| EEEDD|
| EEDDD|
EE

若 A 如下也無解
_________
|AAA |
|AAA |
|DDA |
|DDEEE |
|DDDEE |
EE |

剩下就是 A 和 B 如下
_________
|AAACCCBBB|
|AA C BB|
|AA BB|

C 無所適從

10: 必為 3+3+2+2 如果是 2 3 2 3 或 3 2 2 3
__________
|AA BBCCDDD|
|AA BBCCDDD|
|A BCCC D|

或是 2 3 3 2 也無解
__________
|AABBBCCCDD|
|AABBBCCCDD|
|AAA BCEDDD|
| EEE |
| EEE |

所以長方形邊長 >= 11 又因為有一邊要是 7 的倍數所以至少是 14*11
也就是 22 個以上。上界是 14*14 所以只要爆搜 11*14 12*14 13*14 三種
狀況就好。如果有一邊是 21 以上，因為 11*21 一定比 14*14 大所以不用
考慮。

===

繼續：邊長 11 時只有這一種擺法（去掉對稱的形狀）
___________
|AAABBBCCCDD|
|AABBBBCCCDD|
|AABBBBCFDDD|
|EEBBBFFF
|EEGGGFFF
|EEEGG
| GG

然而...
___________
|XXXXXXXXXXX|
|XXXXXXXXXXX|
|XXXXXXXXXXX|
|XXXXXXXX |
|XXXXXXXX |
|XXXXX |
| XX |
| YY |
| YYYYY|
| YYYYYYYY|
| YYYYYYYY|
|YYYYYYYYYYY|
|YYYYYYYYYYY|
|YYYYYYYYYYY|
^^^^^^^^^^^

或是 Y 反過來都不可能。（可以從中間狹窄的地方開始試驗。注意一旦切開
左右兩邊的空格都要是七的倍數。）

===

13 也不可能。2 3 2 3 3, 2 3 3 2 3, 2 3 3 3 2, 3 2 2 3 3, 3 2 3 2 3
全都不行。可能的對手只剩下 12.

===

12 好像也不可能。所以我相信 28 是最佳解。可是還沒找到很短的證明否決
12*14. 總之就是角落基本型組合一下變成：
____________ ____________
|AAABBBCCCDDD| |AAABBBCCCDDD|
|AAABBBCCCCDD| |AAAABBCCCCDD|
|AEEEFBCCCCDD| |AAAABBCCCCDD|
|EEEEFFFCCCGG| |EAAAFFFCCCGG|
|EEEEFFFHHHGG| |EEE FFHHHGG|
|EEE HHGGG| |EEE FFHHGGG|
HH HH
--