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

 'Chess' Polygons (Posted on 2009-04-24)

a b c d e f g h i j
1
 C E B F E A E B H A A E H D F G E G D C F E B A H H B B C F D A D G E D H D B C C E D E G C G C D F C C B F A A C D G C F B C B C C B H E C A C E B E B A D D G D E G B C H D E B C
2
3
4
5
6
7
8
9

Draw the following set of convex polygons with vertices in ascending and consecutive alphabetical order:
triangle, square, pentagon, hexagon, heptagon and octagon.

Each vertex sequence begins with an A with subsequent (and all) vertices being 3 squares apart as defined by a chess knight's "L" shaped move or the queen's diagonal or orthogonal move.

No polygon is to have a common vertex with another. Should this occur then one or the other is not part of the solution.

 See The Solution Submitted by brianjn No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(2): computer solutions -- fixed | Comment 4 of 5 |
(In reply to re: computer solutions by Charlie)

Revised to have true polygons rather than stars:

Available polygons:

`3d 3g 6g 3d                     90 135 135                     RRB4b 6c 7e 4b                    -37-162-162                     NNB4b 7b 7e 4b                    -90-135-135                     RRB8a 8d 5a 8a                   -135-135 -90                     RBR1f 4i 7f 4c 1f                  90  90  90  90                 BBBB6e 7g 5h 4f 6e                 -90 -90 -90 -90                 NNNN8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR8g 8d 5a 2d 2g 5j 8g            45  90  45  45  90  45         RBBRBB6e 7g 4j 2i 1g 1d 4d 6e        -72 -72 -37 -27 -90 -27 -37     NBNNRRN6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`

The solutions (only 14 of them now):

`8a 8d 5a 8a                   -135-135 -90                     RBR1f 4i 7f 4c 1f                  90  90  90  90                 BBBB4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`8a 8d 5a 8a                   -135-135 -90                     RBR8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`8a 8d 5a 8a                   -135-135 -90                     RBR1f 4i 7f 4c 1f                  90  90  90  90                 BBBB4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`8a 8d 5a 8a                   -135-135 -90                     RBR8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`4b 6c 7e 4b                    -37-162-162                     NNB8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`4b 7b 7e 4b                    -90-135-135                     RRB8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`8a 8d 5a 8a                   -135-135 -90                     RBR1f 4i 7f 4c 1f                  90  90  90  90                 BBBB4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`8a 8d 5a 8a                   -135-135 -90                     RBR8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`8a 8d 5a 8a                   -135-135 -90                     RBR1f 4i 7f 4c 1f                  90  90  90  90                 BBBB4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`8a 8d 5a 8a                   -135-135 -90                     RBR8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`4b 6c 7e 4b                    -37-162-162                     NNB8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`4b 7b 7e 4b                    -90-135-135                     RRB8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`3d 3g 6g 3d                     90 135 135                     RRB1f 4i 7f 4c 1f                  90  90  90  90                 BBBB4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB8g 8d 5a 2d 2g 5j 8g            45  90  45  45  90  45         RBBRBB6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`
`3d 3g 6g 3d                     90 135 135                     RRB1f 4i 7f 4c 1f                  90  90  90  90                 BBBB4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB8g 8d 5a 2d 2g 5j 8g            45  90  45  45  90  45         RBBRBB6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN`

The revised program (added code bolded):

DECLARE FUNCTION angleSum! (p\$)
DECLARE SUB reportPoly (p\$)
DECLARE SUB setUp (size!)
DECLARE FUNCTION norm! (x!)
DECLARE SUB rect2theta ()
DATA CEBFEAEBHA
DATA AEHDFGEGDC
DATA FEBAHHBBCF
DATA CEDEGCGCDF
DATA CCBFAACDGC
DATA FBCBCCBHEC
DATA DEGBCHDEBC

DIM SHARED b\$(9, 10), h\$, num\$, let\$, lnCt, dir\$, dx, dy, theta, pi, firstTheta
DIM SHARED poly\$(3 TO 8, 99), solSet(3 TO 8), used(9, 10), solCt

num\$ = "123456789": let\$ = "abcdefghij"
pi = ATN(1) * 4
CLS

FOR row = 1 TO 9
FOR col = 1 TO 10
b\$(row, col) = MID\$(s\$, col, 1)
NEXT
NEXT

OPEN "chespoly.txt" FOR OUTPUT AS #2

FOR size = 3 TO 8
FOR r = 1 TO 9
FOR c = 1 TO 10
IF b\$(r, c) = "A" THEN
h\$ = MID\$(num\$, r, 1) + MID\$(let\$, c, 1)
addon size ' 3 is for triangle
END IF
NEXT
NEXT
NEXT size

PRINT lnCt
PRINT #2,

FOR sz = 3 TO 8
PRINT VAL(poly\$(sz, 0));
NEXT
PRINT

setUp 8

PRINT solCt

END

ln = LEN(h\$): sz = ln / 2
currR = VAL(MID\$(h\$, ln - 1, 1))
currC = INSTR(let\$, MID\$(h\$, ln, 1))
IF sz > 1 THEN
prevR = VAL(MID\$(h\$, ln - 3, 1))
prevC = INSTR(let\$, MID\$(h\$, ln - 2, 1))
dx = currC - prevC: dy = prevR - currR
rect2theta
oldtheta = theta
IF sz = 2 THEN firstTheta = theta
END IF

strtDR = -3: endDR = 3
' IF sz = size THEN
'  firstR = VAL(MID\$(h\$, 1, 1))
'  firstC = INSTR(let\$, MID\$(h\$, 2, 1))
'  strtDR = firstR - currR: endDR = strtDR
' END IF

FOR dr = strtDR TO endDR
dca = 3 - ABS(dr)
stp = 2 * dca
IF dca = 0 THEN dca = 3: stp = 3
strtDC = -dca: endDC = dca
'  IF sz = size THEN
'    strtDC = firstC - currC: endDC = strtDC
'  END IF
FOR dc = strtDC TO endDC STEP stp
dx = dc: dy = -dr
rect2theta
good = 1
newtheta = theta
IF size = 4 AND sz > 1 AND (ABS(norm(theta - oldtheta)) < 3.14 / 2 OR ABS(norm(theta - oldtheta)) > 3.15 / 2) THEN good = 0
IF sz = 2 THEN
IF norm(newtheta - oldtheta) > 0 THEN
dir\$ = "ccw"
ELSEIF norm(newtheta - oldtheta) = 0 THEN
dir\$ = "": good = 0
ELSE
dir\$ = "cw"
END IF
ELSEIF sz > 2 THEN
IF norm(newtheta - oldtheta) > 0 THEN
newdir\$ = "ccw":
ELSEIF norm(newtheta - oldtheta) < 0 THEN
newdir\$ = "cw"
ELSE
newdir\$ = "": good = 0
END IF
END IF
r = currR + dr: c = currC + dc

IF good = 1 AND (newdir\$ = dir\$ OR newdir\$ = "" OR sz < 3) AND r >= 1 AND r <= 9 AND c >= 1 AND c <= 10 THEN
diff = ASC(b\$(r, c)) - ASC(b\$(currR, currC))
IF diff = 1 OR sz = size THEN
h\$ = h\$ + MID\$(num\$, r, 1) + MID\$(let\$, c, 1)
IF sz = size THEN
IF norm(firstTheta - newtheta) > 0 AND dir\$ = "ccw" OR norm(firstTheta - newtheta) < 0 AND dir\$ = "cw" THEN
IF RIGHT\$(h\$, 2) = LEFT\$(h\$, 2) THEN
IF ABS(180 * (size - 2) - angleSum(h\$)) < 2 THEN
reportPoly h\$
lnCt = lnCt + 1
poly\$(size, 0) = LTRIM\$(STR\$(VAL(poly\$(size, 0)) + 1))
poly\$(size, VAL(poly\$(size, 0))) = h\$
END IF
END IF
END IF
ELSE
END IF
h\$ = LEFT\$(h\$, LEN(h\$) - 2)
END IF
END IF
NEXT
NEXT
END SUB

FUNCTION angleSum (p\$)
q\$ = p\$ + MID\$(p\$, 3, 2)
sum = 0
FOR i = 1 TO LEN(p\$) - 2 STEP 2
r1 = VAL(MID\$(q\$, i, 1))
c1 = INSTR(let\$, MID\$(q\$, i + 1, 1))
r2 = VAL(MID\$(q\$, i + 2, 1))
c2 = INSTR(let\$, MID\$(q\$, i + 3, 1))
r3 = VAL(MID\$(q\$, i + 4, 1))
c3 = INSTR(let\$, MID\$(q\$, i + 5, 1))
dx = c2 - c1: dy = r2 - r1: rect2theta: th1 = theta
dx = c3 - c2: dy = r3 - r2: rect2theta: th2 = theta
chg = ABS(norm(th2 - th1) * 180 / pi)
sum = sum + 180 - chg
NEXT i
angleSum = sum
END FUNCTION

FUNCTION norm (x)
v = x
DO
IF v > pi THEN v = v - 2 * pi
IF v < -pi THEN v = v + 2 * pi
LOOP UNTIL v >= -pi AND v <= pi
norm = v
END FUNCTION

SUB rect2theta
IF dx = 0 THEN
th = pi / 2 * SGN(dy)
ELSE
th = ATN(dy / dx)
IF dx < 0 THEN th = th + pi
IF th > pi THEN th = th - 2 * pi
END IF
theta = th
END SUB

SUB reportPoly (p\$)
FOR i = 1 TO LEN(p\$) STEP 2
PRINT #2, MID\$(p\$, i, 2); " ";
NEXT i
PRINT #2, TAB(31);
q\$ = p\$ + MID\$(p\$, 3, 2)
FOR i = 1 TO LEN(p\$) - 2 STEP 2
r1 = VAL(MID\$(q\$, i, 1))
c1 = INSTR(let\$, MID\$(q\$, i + 1, 1))
r2 = VAL(MID\$(q\$, i + 2, 1))
c2 = INSTR(let\$, MID\$(q\$, i + 3, 1))
r3 = VAL(MID\$(q\$, i + 4, 1))
c3 = INSTR(let\$, MID\$(q\$, i + 5, 1))
dx = c2 - c1: dy = r2 - r1: rect2theta: th1 = theta
dx = c3 - c2: dy = r3 - r2: rect2theta: th2 = theta
chg = norm(th2 - th1)
PRINT #2, USING "####"; chg * 180 / pi;
NEXT i
PRINT #2, TAB(64);
FOR i = 1 TO LEN(p\$) - 2 STEP 2
r1 = VAL(MID\$(q\$, i, 1))
c1 = INSTR(let\$, MID\$(q\$, i + 1, 1))
r2 = VAL(MID\$(q\$, i + 2, 1))
c2 = INSTR(let\$, MID\$(q\$, i + 3, 1))
dx = ABS(c2 - c1): dy = ABS(r2 - r1)
IF dx = 3 AND dy = 3 THEN
PRINT #2, "B";
ELSEIF dx = 3 OR dy = 3 THEN
PRINT #2, "R";
ELSEIF dx = 1 AND dy = 2 OR dy = 1 AND dx = 2 THEN
PRINT #2, "N";
ELSE
PRINT #2, "?";
END IF
NEXT i
PRINT #2,
END SUB

SUB setUp (size)
numb = VAL(poly\$(size, 0))
FOR i = 1 TO numb
solSet(size) = i
tr\$ = poly\$(size, i)
good = 1
FOR j = 1 TO LEN(tr\$) STEP 2
r = VAL(MID\$(tr\$, j, 1))
c = INSTR(let\$, MID\$(tr\$, j + 1, 1))
IF used(r, c) THEN good = 0: EXIT FOR
NEXT
IF good THEN
FOR j = 1 TO LEN(tr\$) STEP 2
r = VAL(MID\$(tr\$, j, 1))
c = INSTR(let\$, MID\$(tr\$, j + 1, 1))
used(r, c) = 1
NEXT

IF size = 3 THEN
FOR k = 3 TO 8
reportPoly poly\$(k, solSet(k))
NEXT
PRINT #2,
solCt = solCt + 1
ELSE
setUp size - 1
END IF

FOR j = 1 TO LEN(tr\$) STEP 2
r = VAL(MID\$(tr\$, j, 1))
c = INSTR(let\$, MID\$(tr\$, j + 1, 1))
used(r, c) = 0
NEXT
END IF
NEXT
END SUB

 Posted by Charlie on 2009-04-25 00:57:55

 Search: Search body:
Forums (0)