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 |
computer solution
