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

Home > Shapes
Cutting a Rectangle (Posted on 2007-12-07) Difficulty: 3 of 5
How many ways can a 3x4 rectangle be cut into two polyominoes by cutting along the grid lines? (Not counting reflections and rotations.)
Examples of valid cuts are shown in the first row and invalid cuts are shown in the second row:
+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+
|     |     |   |           |   |  |        |   |  |        |
+  +  +  +  +   +  +--+  +  +   +  +--+--+  +   +  +  +  +  +
|     |     |   |  |  |     |   |        |  |   |  |        |
+--+--+  +  +   +  +--+  +  +   +  +  +--+  +   +  +  +  +  +
|           |   |           |   |     |     |   |  |        |
+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+

+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+
|     |     |   |           |   |  |        |   |     /     |
+  +  +  +  +   +--+--+  +  +   +  +  +--+  +   +  + /+  +  +
|     |     |   |  |  |     |   |        |  |   |   /       |
+--+--+  +  +   +  +--+  +  +   +  +--+--+  +   +  +  +  +  +
|     |     |   |           |   |     |     |   |  |        |
+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+

See The Solution Submitted by Brian Smith    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 3 of 8 |

There are two types: those made with a closed cut, leaving one polyomino with a hole in it; and those with a cut that goes from edge to edge of the original rectangle.

There are only two varieties of those with a closed cut, leaving a hole in one of the polyominoes:

+--+--+--+--+      +--+--+--+--+
|           |      |           |
+  +--+  +  +      +  +--+--+  +
|  |  |     |      |  |     |  |
+  +--+  +  +      +  +--+--+  +
|           |      |           |
+--+--+--+--+      +--+--+--+--+

Only reflection or rotation would switch the first of these to a different apparent configuration, but really the same, given the statement of the puzzle.

There are 44 different configurations involving a cut that goes from edge to edge on the original rectangle:

+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |  |     |      |  |        |      |  |        |      |     |     |
+  +--+  +  +      +  +--+  +  +      +  +  +  +  +      +  +  +  +  +
|           |      |     |     |      |  |        |      |     |     |
+  +  +  +  +      +  +  +--+  +      +  +--+--+--+      +  +  +--+--+
|           |      |        |  |      |           |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  1        1        12       12        24       23        41       34
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |     |  |      |  |        |      |  |        |      |     |     |
+  +--+--+  +      +  +--+  +  +      +  +  +  +  +      +  +  +  +  +
|           |      |     |     |      |  |        |      |     |     |
+  +  +  +  +      +  +  +  +  +      +  +--+  +  +      +  +  +  +  +
|           |      |     |     |      |     |     |      |     |     |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  2        2        13       13        26       24        43       35
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |        |      |  |        |      |  |        |      |           |
+  +--+--+--+      +  +--+  +  +      +  +  +  +  +      +--+--+--+--+
|           |      |     |     |      |  |        |      |           |
+  +  +  +  +      +  +--+  +  +      +  +  +  +  +      +  +  +  +  +
|           |      |  |        |      |  |        |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  3        3        14       14        27       25        60       36
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |        |      |  |        |      |  |        |      |           |
+  +--+--+  +      +  +--+  +  +      +  +  +  +  +      +--+--+--+  +
|        |  |      |     |     |      |  |        |      |        |  |
+  +  +  +--+      +--+--+  +  +      +--+  +  +  +      +  +  +  +--+
|           |      |           |      |           |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  4        4        15       15        28       26        61       37
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |        |      |  |  |     |      |  |        |      |           |
+  +--+--+  +      +  +  +  +  +      +--+  +  +  +      +--+--+--+  +
|        |  |      |  |  |     |      |           |      |        |  |
+  +  +  +  +      +  +--+  +  +      +  +  +  +  +      +--+--+--+  +
|        |  |      |           |      |           |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  5        5        16       16        29       27        65       38
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |        |      |  |        |      |     |     |      |           |
+  +--+--+  +      +  +  +--+--+      +  +  +--+--+      +--+--+  +--+
|        |  |      |  |  |     |      |           |      |     |  |  |
+  +  +--+  +      +  +--+  +  +      +  +  +  +  +      +  +  +--+  +
|     |     |      |           |      |           |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  6        6        18       17        31       28        67       39
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |        |      |  |        |      |     |     |      |           |
+  +--+--+  +      +  +  +--+  +      +  +  +--+  +      +--+--+  +  +
|        |  |      |  |  |  |  |      |        |  |      |     |     |
+  +--+--+  +      +  +--+  +--+      +  +  +  +--+      +  +  +--+--+
|  |        |      |           |      |           |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  7        7        19       18        32       29        68       40
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |        |      |  |        |      |     |     |      |           |
+  +--+--+  +      +  +  +--+  +      +  +  +--+  +      +--+--+  +  +
|        |  |      |  |  |  |  |      |        |  |      |     |     |
+--+--+--+  +      +  +--+  +  +      +  +  +--+  +      +--+--+  +  +
|           |      |        |  |      |     |     |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  8        8        20       19        34       30        72       41
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |     |  |      |  |     |  |      |     |     |      |           |
+  +--+  +  +      +  +  +  +  +      +--+  +--+  +      +--+  +--+  +
|     |  |  |      |  |     |  |      |  |     |  |      |  |  |  |  |
+  +  +--+  +      +  +--+--+  +      +  +--+--+  +      +  +--+  +--+
|           |      |           |      |           |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
  9        9        21       20        36       31        76       42
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |        |      |  |        |      |     |     |      |           |
+  +--+  +--+      +  +  +  +--+      +  +  +--+  +      +--+  +  +--+
|     |  |  |      |  |     |  |      |        |  |      |  |     |  |
+  +  +--+  +      +  +--+--+  +      +--+--+--+  +      +  +--+--+  +
|           |      |           |      |           |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
 10       10        22       21        38       32        79       43
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
|  |        |      |  |  |     |      |     |     |      |           |
+  +--+  +  +      +  +  +--+  +      +  +  +  +--+      +--+  +  +  +
|     |     |      |  |     |  |      |     |  |  |      |  |        |
+  +  +--+--+      +  +--+--+  +      +  +  +--+  +      +--+  +  +  +
|           |      |           |      |           |      |           |
+--+--+--+--+      +--+--+--+--+      +--+--+--+--+      +--+--+--+--+
 11       11        23       22        40       33        85       44

These are numbered in two different ways. The number at the left bottom of each diagram is the order in which it was produced in the first pass of the program that produced these. The second number counts only those that are left after weeding out trivial rotations and reflections.

With the possible horizontal line positions numbered 0 through 3 (top row to bottom row) and the vertical line positions numbered 0 through 4 (left column to right column), the first pass of the program started lines at row 0, column 1; row 0 column 2; and row 1, column 0, as every cut that goes from edge to edge must have an end that's either one place removed from a corner, either on a long side or a short side, or in the middle of a long side.

At every intersection, the program tries to go first up; next, to the right; next down and finally to the left, varying first from the last choice made and then going back hierarchically. (This is programmed recursively.)

The second pass weeded out rotations and reflections.  For example, the case originally found as number 17 (lower left number) is missing as it would be the left-right mirror image of case 9. So solution 18 is only the 17th kept, with numbers shown above to indicate such. Similarly original solution 25 was tossed out as it is the 180 rotation of solution 5.

This leaves 44 solutions where the cut goes edge to edge. Added to the two solutions where the cut is closed, creating a polyomino with a hole, that makes 46 solutions altogether, not counting rotations and reflections.

DECLARE SUB place (row!, col!)
DIM SHARED visited(3, 4), ct, lvl, hist(20, 2), sol(100, 20, 2)

CLS

place 0, 1

place 0, 2

place 1, 0

PRINT ct

OPEN "cutarect.txt" FOR OUTPUT AS #2

FOR s = 1 TO ct
 good = 1
 FOR ps = 1 TO s - 1
   IF sol(ps, 0, 1) <> sol(s, 0, 1) THEN
     match = 0
   ELSE
     match = 1
     FOR i = 1 TO sol(s, 0, 1)
       j = sol(s, 0, 1) + 1 - i
       IF sol(s, i, 1) <> 3 - sol(ps, j, 1) OR sol(s, i, 2) <> sol(ps, j, 2) THEN match = 0: EXIT FOR
     NEXT
     IF match THEN good = 0: EXIT FOR
     match = 1
     FOR i = 1 TO sol(s, 0, 1)
       j = sol(s, 0, 1) + 1 - i
       IF sol(s, i, 1) <> 3 - sol(ps, j, 1) OR sol(s, i, 2) <> 4 - sol(ps, j, 2) THEN match = 0: EXIT FOR
     NEXT
     IF match THEN good = 0: EXIT FOR
     match = 1
     FOR i = 1 TO sol(s, 0, 1)
       j = i
       IF sol(s, i, 1) <> sol(ps, j, 1) OR sol(s, i, 2) <> 4 - sol(ps, j, 2) THEN match = 0: EXIT FOR
     NEXT
     IF match THEN good = 0: EXIT FOR
     match = 1
     FOR i = 1 TO sol(s, 0, 1)
       j = sol(s, 0, 1) + 1 - i
       IF sol(s, i, 1) <> sol(ps, j, 1) OR sol(s, i, 2) <> 4 - sol(ps, j, 2) THEN match = 0: EXIT FOR
     NEXT
     IF match THEN good = 0: EXIT FOR
     match = 1
     FOR i = 1 TO sol(s, 0, 1)
       j = sol(s, 0, 1) + 1 - i
       IF sol(s, i, 1) <> sol(ps, j, 1) OR sol(s, i, 2) <> sol(ps, j, 2) THEN match = 0: EXIT FOR
     NEXT
     IF match THEN good = 0: EXIT FOR
   END IF
 NEXT
 IF good THEN
   REDIM ar$(7, 13)
   FOR i = 1 TO 7 STEP 2
    FOR j = 1 TO 13 STEP 3
     ar$(i, j) = "+"
    NEXT
   NEXT
   FOR i = 1 TO 7 STEP 6
     FOR j = 2 TO 11 STEP 3
      ar$(i, j) = "-": ar$(i, j + 1) = "-"
     NEXT
   NEXT
   FOR i = 2 TO 6 STEP 2
    FOR j = 1 TO 13 STEP 12
     ar$(i, j) = "|"
    NEXT
   NEXT
   FOR mv = 2 TO sol(s, 0, 1)
      IF sol(s, mv - 1, 1) = sol(s, mv, 1) THEN
        sb = 3 * (sol(s, mv - 1, 2) + sol(s, mv, 2)) / 2 + .5
        ar$(sol(s, mv - 1, 1) * 2 + 1, sb) = "-"
        ar$(sol(s, mv - 1, 1) * 2 + 1, sb + 1) = "-"
      ELSE
        sb = 2 * (sol(s, mv - 1, 1) + sol(s, mv, 1)) / 2 + 1
        ar$(sb, 3 * sol(s, mv, 2) + 1) = "|"
      END IF
   NEXT mv
   FOR i = 1 TO 7
    FOR j = 1 TO 13
     IF ar$(i, j) = "" THEN
      PRINT " ";
      PRINT #2, " ";
     ELSE
      PRINT ar$(i, j); :
      PRINT #2, ar$(i, j); :
     END IF
    NEXT
    PRINT
    PRINT #2,
   NEXT
   ct2 = ct2 + 1
   PRINT USING "###      ###"; s; ct2
   PRINT #2, USING "###      ###"; s; ct2
   PRINT #2,
 END IF
NEXT
PRINT ct, ct2

END

SUB place (row, col)
 lvl = lvl + 1
 visited(row, col) = 1
 hist(lvl, 1) = row: hist(lvl, 2) = col

 dr = -1: dc = 0: GOSUB moveIt
 dr = 0: dc = 1: GOSUB moveIt
 dr = 1: dc = 0: GOSUB moveIt
 dr = 0: dc = -1: GOSUB moveIt

 visited(row, col) = 0
 lvl = lvl - 1
 EXIT SUB

moveIt:
  r = row + dr: c = col + dc
  IF r < 0 OR r > UBOUND(visited, 1) OR c < 0 OR c > UBOUND(visited, 2) THEN RETURN
  IF visited(r, c) THEN RETURN
  IF r = 0 OR r = UBOUND(visited, 1) OR c = 0 OR c = UBOUND(visited, 2) THEN
    IF lvl = 1 THEN RETURN
    lvl = lvl + 1
    hist(lvl, 1) = r: hist(lvl, 2) = c
    ct = ct + 1
    FOR i = 1 TO lvl
      sol(ct, i, 1) = hist(i, 1)
      sol(ct, i, 2) = hist(i, 2)
    NEXT
    sol(ct, 0, 1) = lvl
    lvl = lvl - 1
  ELSE
    place r, c
  END IF

RETURN

END SUB

 


  Posted by Charlie on 2007-12-07 15:34:08
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 (3)
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