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

Home > Shapes
Count the ways... (Posted on 2005-10-28) Difficulty: 2 of 5
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 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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       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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information