perplexus.info :: Shapes : 'Chess' Polygons

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

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

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                     RRB
4b 6c 7e 4b                    -37-162-162                     NNB
4b 7b 7e 4b                    -90-135-135                     RRB
8a 8d 5a 8a                   -135-135 -90                     RBR
1f 4i 7f 4c 1f                  90  90  90  90                 BBBB
6e 7g 5h 4f 6e                 -90 -90 -90 -90                 NNNN
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB
4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB
8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB
3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR
3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR
8g 8d 5a 2d 2g 5j 8g            45  90  45  45  90  45         RBBRBB
6e 7g 4j 2i 1g 1d 4d 6e        -72 -72 -37 -27 -90 -27 -37     NBNNRRN
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 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                     RBR
1f 4i 7f 4c 1f                  90  90  90  90                 BBBB
4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB
3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

8a 8d 5a 8a                   -135-135 -90                     RBR
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB
3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

8a 8d 5a 8a                   -135-135 -90                     RBR
1f 4i 7f 4c 1f                  90  90  90  90                 BBBB
4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB
3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

8a 8d 5a 8a                   -135-135 -90                     RBR
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB
3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

4b 6c 7e 4b                    -37-162-162                     NNB
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB
3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

4b 7b 7e 4b                    -90-135-135                     RRB
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB
3d 3g 5h 8h 8e 6d 3d            63  27  90  63  27  90         RNRRNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

8a 8d 5a 8a                   -135-135 -90                     RBR
1f 4i 7f 4c 1f                  90  90  90  90                 BBBB
4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB
3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

8a 8d 5a 8a                   -135-135 -90                     RBR
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB
3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

8a 8d 5a 8a                   -135-135 -90                     RBR
1f 4i 7f 4c 1f                  90  90  90  90                 BBBB
4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB
3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

8a 8d 5a 8a                   -135-135 -90                     RBR
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB
3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

4b 6c 7e 4b                    -37-162-162                     NNB
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB
3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

4b 7b 7e 4b                    -90-135-135                     RRB
8g 9i 7j 6h 8g                 -90 -90 -90 -90                 NNNN
8a 8d 7f 4f 5d 8a              -27 -63-117 -18-135             RNRNB
3d 3g 6j 9g 8e 6d 3d            45  90  72  37  27  90         RBBNNR
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

3d 3g 6g 3d                     90 135 135                     RRB
1f 4i 7f 4c 1f                  90  90  90  90                 BBBB
4b 6c 7e 4h 1e 4b              -37 -72 -90 -90 -72             NNBBB
8g 8d 5a 2d 2g 5j 8g            45  90  45  45  90  45         RBBRBB
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 7d 6b 4a 2b 1d 2f 4g 6f      53  37  53  37  53  37  53  37 NNNNNNNN

3d 3g 6g 3d                     90 135 135                     RRB
1f 4i 7f 4c 1f                  90  90  90  90                 BBBB
4b 7b 7e 4h 1e 4b              -90 -45 -90 -90 -45             RRBBB
8g 8d 5a 2d 2g 5j 8g            45  90  45  45  90  45         RBBRBB
6e 7g 4j 2i 1g 2e 4d 6e        -72 -72 -37 -53 -37 -53 -37     NBNNNNN
6f 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 ()
DECLARE SUB addon (size!)
DATA CEBFEAEBHA
DATA AEHDFGEGDC
DATA FEBAHHBBCF
DATA DADGEDHDBC
DATA CEDEGCGCDF
DATA CCBFAACDGC
DATA FBCBCCBHEC
DATA ACEBEBADDG
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
READ s$
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

SUB addon (size)
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
          addon size
         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

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info