All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Count the ways... (Posted on 2005-10-28)
How many ways can you fit 8 identical 2 by 1 rectangles into a 4 by 4 square? Reflections and rotations count separately.

 See The Solution Submitted by Tristan Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: computer solution -- now checking rotations and reflections | Comment 3 of 6 |
(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       6aabb    aabb    aabb    aabb    aabb    aabbccdd    ccdd    ccdd    ccdd    ccdd    ccdeeeff    eefg    effg    efgg    efgh    ffdegghh    hhfg    ehhg    efhh    efgh    gghh                        Ref 2`
` 7       8       9       10      11      12aabb    aabb    aabb    aabb    aabb    aabcccde    cdde    cdee    cdee    cdef    ddbcfgde    cffe    cdff    cdfg    cdef    eefffghh    gghh    gghh    hhfg    gghh    gghh                Rot 6   Ref 7           Ref 2`
` 13      14      15      16      17      18aabc    aabc    aabc    aabc    aabc    aabcddbc    ddbc    ddbc    ddbc    debc    debceefg    effg    efgg    efgh    deff    defghhfg    ehhg    efhh    efgh    gghh    hhfgRot 5   Rot 7           Ref 2   Rot 7   Rot 3`
` 19      20      21      22      23      24abbc    abbc    abbc    abbc    abbc    abbcaddc    addc    addc    addc    addc    adeceeff    eefg    effg    efgg    efgh    fdeggghh    hhfg    ehhg    efhh    efgh    fhhgRot 3   Ref 7   Rot 11  Rot 7   Rot 6   Rot 8`
` 25      26      27      28      29      30abcc    abcc    abcc    abcc    abcc    abccabdd    abdd    abdd    abdd    abdd    abdeeeff    eefg    effg    efgg    efgh    ffdegghh    hhfg    ehhg    efhh    efgh    gghhRot 2   Ref 15  Ref 7   Rot 5   Rot 2   Ref 7`
` 31      32      33      34      35      36abcc    abcd    abcd    abcd    abcd    abcdabde    abcd    abcd    abcd    abcd    abcdfgde    eeff    eefg    effg    efgg    efghfghh    gghh    hhfg    ehhg    efhh    efghRot 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

 Search: Search body:
Forums (0)