How many ways can you fit 8 identical 2 by 1 rectangles into a 4 by 4 square? Reflections and rotations count separately.
(In reply to
computer solution by Charlie)
Here the placements are numbered, and if a placement is a rotation or reflection of a previous placement, that's noted. (Of course those that reference the same previous placement are rotations and reflections of each other, but reference is made only to the original.) Nine are original, not rotations or reflections of previous placements.
1 2 3 4 5 6
aabb aabb aabb aabb aabb aabb
ccdd ccdd ccdd ccdd ccdd ccde
eeff eefg effg efgg efgh ffde
gghh hhfg ehhg efhh efgh gghh
Ref 2
7 8 9 10 11 12
aabb aabb aabb aabb aabb aabc
ccde cdde cdee cdee cdef ddbc
fgde cffe cdff cdfg cdef eeff
fghh gghh gghh hhfg gghh gghh
Rot 6 Ref 7 Ref 2
13 14 15 16 17 18
aabc aabc aabc aabc aabc aabc
ddbc ddbc ddbc ddbc debc debc
eefg effg efgg efgh deff defg
hhfg ehhg efhh efgh gghh hhfg
Rot 5 Rot 7 Ref 2 Rot 7 Rot 3
19 20 21 22 23 24
abbc abbc abbc abbc abbc abbc
addc addc addc addc addc adec
eeff eefg effg efgg efgh fdeg
gghh hhfg ehhg efhh efgh fhhg
Rot 3 Ref 7 Rot 11 Rot 7 Rot 6 Rot 8
25 26 27 28 29 30
abcc abcc abcc abcc abcc abcc
abdd abdd abdd abdd abdd abde
eeff eefg effg efgg efgh ffde
gghh hhfg ehhg efhh efgh gghh
Rot 2 Ref 15 Ref 7 Rot 5 Rot 2 Ref 7
31 32 33 34 35 36
abcc abcd abcd abcd abcd abcd
abde abcd abcd abcd abcd abcd
fgde eeff eefg effg efgg efgh
fghh gghh hhfg ehhg efhh efgh
Rot 3 Rot 5 Rot 2 Rot 6 Ref 2 Rot 1
Note for example, due to the symmetry of placements 6 and 9, while one is a 180-degree rotation of the other, it's also true that one is the left-right reflection of the other about a vertical axis. Only one type of transformation is noted, with rotation being checked first:
DECLARE SUB place ()
CLEAR , , 9000
DIM SHARED sz, numb, solCt, lvl, vCt, hCt
sz = 4: numb = sz * sz / 2
DIM SHARED board$(sz, sz)
CLS
DIM SHARED hist$(36, sz, sz)
place
SUB place
lvl = lvl + 1
ltr$ = MID$("abcdefghijklmnopqrstuvwxyz", lvl, 1)
found = 0
FOR i = 1 TO sz
FOR j = 1 TO sz
IF LTRIM$(board$(i, j)) = "" THEN
rw = i: cl = j: found = 1: EXIT FOR
END IF
NEXT
IF found THEN EXIT FOR
NEXT
IF found = 0 THEN
rw = solCt \ 6: cl = solCt MOD 6
solCt = solCt + 1
LOCATE rw * 7 + 1, cl * 8 + 1
PRINT solCt;
FOR i = 1 TO sz
LOCATE rw * 7 + i + 1, cl * 8 + 1
FOR j = 1 TO sz
PRINT board$(i, j);
hist$(solCt, i, j) = board$(i, j)
NEXT
NEXT
LOCATE rw * 7 + sz + 2, cl * 8 + 1
GOSUB matcher
ELSE
' horiz
IF cl < sz THEN
IF board$(rw, cl + 1) = "" THEN
board$(rw, cl) = ltr$
board$(rw, cl + 1) = ltr$
hCt = hCt + 1
place
hCt = hCt - 1
board$(rw, cl) = ""
board$(rw, cl + 1) = ""
END IF
END IF
' vert
IF rw < sz THEN
IF board$(rw + 1, cl) = "" THEN
board$(rw, cl) = ltr$
board$(rw + 1, cl) = ltr$
vCt = vCt + 1
place
vCt = vCt - 1
board$(rw, cl) = ""
board$(rw + 1, cl) = ""
END IF
END IF
END IF
lvl = lvl - 1
EXIT SUB
matcher:
FOR old = 1 TO solCt - 1
ref = 0
FOR rot = 1 TO 3
GOSUB cmpr: IF mFound THEN EXIT FOR
NEXT
IF mFound = 0 THEN
rot = 0
FOR ref = 1 TO 4
GOSUB cmpr: IF mFound THEN EXIT FOR
NEXT
END IF
IF mFound THEN
IF ref THEN PRINT "Ref"; : ELSE PRINT "Rot";
PRINT old;
EXIT FOR
END IF
NEXT old
RETURN
cmpr:
mFound = 1
tranIn$ = "": tranOut$ = ""
FOR r = 1 TO sz
FOR c = 1 TO sz
IF rot THEN
SELECT CASE rot
CASE 1
ro = c: co = sz + 1 - r
CASE 2
ro = sz + 1 - r: co = sz + 1 - c
CASE 3
ro = sz + 1 - c: co = r
END SELECT
ELSE
SELECT CASE ref
CASE 1
ro = r: co = sz + 1 - c
CASE 2
ro = sz + 1 - r: co = c
CASE 3
ro = c: co = r
CASE 4
ro = sz + 1 - c: co = sz + 1 - r
END SELECT
END IF
oldLet$ = hist$(old, ro, co): newLet$ = board$(r, c)
ix = INSTR(tranIn$, oldLet$)
IF ix = 0 THEN
IF INSTR(tranOut$, newLet$) THEN mFound = 0: EXIT FOR
tranIn$ = tranIn$ + oldLet$
tranOut$ = tranOut$ + newLet$
ELSE
IF INSTR(tranOut$, newLet$) <> ix THEN mFound = 0: EXIT FOR
END IF
NEXT
IF mFound = 0 THEN EXIT FOR
NEXT
RETURN
END SUB
Edited on October 28, 2005, 12:31 pm
|
|
Posted by Charlie
on 2005-10-28 12:19:06 |
re: computer solution -- now checking rotations and reflections
