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

 Cutting a Rectangle (Posted on 2007-12-07)
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.)
 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

 Search: Search body:
Forums (0)