.  .  . 
Main  Links  Orders  Post  Next Page  Next + 10 
Patrick M Hamlyn@MULTIPROGRAMMING
01/04/99 08:29
Mike Reid asked: as a slight variation, i propose to use the two trominoes instead of a repeated hexomino. can six 6x6 squares be made now?
Yes indeed:
In at least two different ways, and the search is about a quarter
done or less:
Three of the squares have 2 packings, the rest are unique. The
second solution differs only in squares 4 and 5 as shown. Thanks to Mike
Reid for pointing out a few things which brought the problem within range
of my PC. Rough algorithm at the end if anyone is interested. Note that
upper and lower case labels refer to distinct pieces.
1
MMRRRB BMMRRR
AMMRRB BAMMRR
AMDeRB BAMDeR
AMDeeB BAMDee
ADDDeB BADDDe
AADeeB BAADee
2
GUUZZZ
GGUUZh
GUUZZh
GXXXhh
GXPhhP
XXPPPP
3
HiOOOO HiOOOO
HiiOWO HiiOWO
HHiWWW HHiWWW
HciiaW HaiicW
HcccaW HacccW
ccaaaa aaaacc
4
 4
fggbbb fIIbbb  Fggbbb FIIbbb
ffgggb ffIbgb  FFgggb FFIbgb
CfIgbb CfIggb  FFIgbb FFIggb
CfIIII CfIIgg  SFIIII SFIIgg
CfFFFI CfFFFg  SSSddI SSSddg
CCCFFF CCCFFF  SSdddd SSdddd

5
 5
JJKSSS  fLLLTT
JJKKSS  ffLTTT
JKKLSd  CfLKTJ
JTKLdd  CfLKKJ
TTTLdd  CfKKJJ
TTLLLd  CCCKJJ
6
QQQxxx
EEQQQN
EENNNN
EEVNYY
VVVYYy
VVYYyy
Algorithm:
1. Find all 6x6 squares using any 6 of the 35 hexominos. List only
the
pieces used. Sort and discard duplicates  13710 entries, call
this list A.
2. Find all 6x6 squares using any 5 hexominos and the tromino pair.
sort
and discard duplicates  60729 entries, call this list B.
3. Read lists A and B into memory. Encode them as a pair of 32bit
words
with a bit set corresponding to each piece present. The tromino
pair are
regarded as a single piece. The original piece lists are kept unencoded
for
list A as well.
4. Invert list B in memory, so it has all bits set except those
corresponding to each piece.
5. Sort list B.
6. Recurse through list A, finding all occurrences of five sets
of 6 pieces
with none in common. Or the words together. Keep track of the five
entry
numbers as well.
7. For each 30piece set found in (6), do a binary search in the
sorted
list B. If it exists, this is a solution, so print out the five
entries
used from list A
8. Plug each of the 6 piece sets in the solutions back into the
poly solver
to find the actual packings again, since they were discarded.
Each step took two minutes or less, except step 6 which is still
less than
a quarter done after 8 hours. If I was in a rush I could speed
it up using
a 'divide and conquer' approach and much longer 12 or 24piece
lists.
Someone was inquiring after the number of 5 simultaneous 6x6 squares

these are found at step 6, so far there are almost 2 million. I'm
storing
them so I can search for another nice puzzle by examining all the
ways the
unused hexominos fit together for each entry. If anyone wants the
list, I
can put it on the web.