|Main||Links||Orders||Post||Next Page||Next + 10|
Patrick M Hamlyn@MULTIPROGRAMMING
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?
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.
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
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 32-bit 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 30-piece 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
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 24-piece 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.