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.)
 computer solution | Comment 1 of 6

The following are the 36 patterns found by computer.  Indeed, each reflection and rotation is counted as a separate way.  It might also be interesting to classify by reflection and rotation.  As a start toward classification, below each layout is shown the number of horizontal and vertical rectangles within each layout.

`aabb  aabb  aabb  aabb  aabb  aabbccdd  ccdd  ccdd  ccdd  ccdd  ccdeeeff  eefg  effg  efgg  efgh  ffdegghh  hhfg  ehhg  efhh  efgh  gghh8  0  6  2  6  2  6  2  4  4  6  2`
`aabb  aabb  aabb  aabb  aabb  aabcccde  cdde  cdee  cdee  cdef  ddbcfgde  cffe  cdff  cdfg  cdef  eefffghh  gghh  gghh  hhfg  gghh  gghh4  4  6  2  6  2  4  4  4  4  6  2`
`aabc  aabc  aabc  aabc  aabc  aabcddbc  ddbc  ddbc  ddbc  debc  debceefg  effg  efgg  efgh  deff  defghhfg  ehhg  efhh  efgh  gghh  hhfg4  4  4  4  4  4  2  6  4  4  2  6`
`abbc  abbc  abbc  abbc  abbc  abbcaddc  addc  addc  addc  addc  adeceeff  eefg  effg  efgg  efgh  fdeggghh  hhfg  ehhg  efhh  efgh  fhhg6  2  4  4  4  4  4  4  2  6  2  6`
`abcc  abcc  abcc  abcc  abcc  abccabdd  abdd  abdd  abdd  abdd  abdeeeff  eefg  effg  efgg  efgh  ffdegghh  hhfg  ehhg  efhh  efgh  gghh6  2  4  4  4  4  4  4  2  6  4  4`
`abcc  abcd  abcd  abcd  abcd  abcdabde  abcd  abcd  abcd  abcd  abcdfgde  eeff  eefg  effg  efgg  efghfghh  gghh  hhfg  ehhg  efhh  efgh2  6  4  4  2  6  2  6  2  6  0  8`

Notice for example how the solution at the top left is actually the same, rotated, as the one at the lower right.  The letters are merely for identification of which half-rectangle goes with which other.

DECLARE SUB place ()
DIM SHARED sz, numb, solCt, lvl, vCt, hCt
sz = 4: numb = sz * sz / 2
DIM SHARED board\$(sz, sz)
CLS

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
FOR i = 1 TO sz
LOCATE rw * 6 + i, cl * 6 + 1
FOR j = 1 TO sz
PRINT board\$(i, j);
NEXT
NEXT
LOCATE rw * 6 + sz + 1, cl * 6 + 1
PRINT USING "# ##"; hCt; vCt;
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
END SUB

 Posted by Charlie on 2005-10-28 10:27:06

 Search: Search body:
Forums (1)