Gamer say:

Spiral the words Gamer says around in a 3 by 3 board like this:

G A M
Y   E
A S R

On each turn, you may slide one letter horizontally or vertically into the blank space (the square it moved from becomes the new empty square).

You want to rearrange the letters so that the same word is spelled out around the edge, but beginning from one of the edges instead of the corner.

In other words, the board should look like one of these configurations:

Y G A  S A Y  E R S  A M E
A   M  R   G  M   A  G   R
S R E  E M A  A G Y  Y A S

What is the fewest number of turns it takes to do this?

Here are the 6 sequences that accomplish this in 18 moves,
which is in fact the minimum.  
All leave the G at the top middle position.  
All start from

gAm
y e
asr

where the all letters except the first A have been converted to lower case:

 ygAygasregaAyagmag          18
yga
A m
sre
 ygAygasgaAyagremag          18
yga
A m
sre
 yasreyagAaymaygAyg          18
yga
A m
sre
 yasyagAayremaygAyg          18
yga
A m
sre
 AgyasreAaygaAmagyA          18
yga
A m
sre
 AgyasAaygaAremagyA          18
yga
A m
sre

These were found by the recursive program:

DECLARE SUB showBoard ()
DECLARE SUB move ()
DEFINT A-Z
DATA g,A,m,y," ",e,a,s,r
DIM SHARED board$(3, 3)
FOR i = 1 TO 3
 FOR j = 1 TO 3
  READ board$(i, j)
 NEXT
NEXT
DIM SHARED seqX(16), seqY(16)
DATA 1,2, 1,3, 2,3, 3,3, 3,2, 3,1, 2,1, 1,1
DATA 1,2, 1,3, 2,3, 3,3, 3,2, 3,1, 2,1, 1,1
FOR i = 1 TO 16
 READ seqY(i)
 READ seqX(i)
NEXT

DIM SHARED gX, gY, blX, blY, hist$

gY = 1: gX = 1
blY = 2: blX = 2
hist$ = " "

CLS
showBoard

move

SUB move
 STATIC solCt
 IF LEN(hist$) > 19 THEN EXIT SUB
 lMove$ = RIGHT$(hist$, 1)
 IF blX = 2 AND blY = 2 THEN
  mY = 2: mX = 1: GOSUB moveIt
  mX = 3: GOSUB moveIt
  mY = 1: mX = 2: GOSUB moveIt
  mY = 3: GOSUB moveIt
 ELSEIF blY = 2 AND blX = 1 THEN
  mY = 1: mX = 1: GOSUB moveIt
  mY = 3: GOSUB moveIt
  mY = 2: mX = 2: GOSUB moveIt
 ELSEIF blY = 2 AND blX = 3 THEN
  mY = 1: mX = 3: GOSUB moveIt
  mY = 3: GOSUB moveIt
  mY = 2: mX = 2: GOSUB moveIt
 ELSEIF blY = 1 AND blX = 2 THEN
  mX = 1: mY = 1: GOSUB moveIt
  mX = 3: GOSUB moveIt
  mX = 2: mY = 2: GOSUB moveIt
 ELSEIF blY = 3 AND blX = 2 THEN
  mX = 1: mY = 3: GOSUB moveIt
  mX = 3: GOSUB moveIt
  mX = 2: mY = 2: GOSUB moveIt
 ELSEIF blY = 1 AND blX = 1 THEN
  mX = 1: mY = 2: GOSUB moveIt
  SWAP mX, mY: GOSUB moveIt
 ELSEIF blY = 1 AND blX = 3 THEN
  mX = 2: mY = 1: GOSUB moveIt
  mX = 3: mY = 2: GOSUB moveIt
 ELSEIF blY = 3 AND blX = 1 THEN
  mX = 2: mY = 3: GOSUB moveIt
  mX = 1: mY = 2: GOSUB moveIt
 ELSEIF blY = 3 AND blX = 3 THEN
  mX = 3: mY = 2: GOSUB moveIt
  SWAP mX, mY: GOSUB moveIt
 END IF
 EXIT SUB

moveIt:
 IF board$(mY, mX) <> RIGHT$(hist$, 1) THEN
   hist$ = hist$ + board$(mY, mX)
   sblY = blY: sblX = blX: sgY = gY: sgX = gX
   board$(blY, blX) = board$(mY, mX)
   board$(mY, mX) = " "
   IF board$(blY, blX) = "g" THEN
    gY = blY: gX = blX
   END IF
   blY = mY: blX = mX

   move
   IF LEN(hist$) > 8 THEN GOSUB checkIt

   board$(sblY, sblX) = " "
   board$(blY, blX) = RIGHT$(hist$, 1)
   hist$ = LEFT$(hist$, LEN(hist$) - 1)
   gY = sgY: gX = sgX: blY = sblY: blX = sblX
 END IF
RETURN

checkIt:
  good = 0
  FOR i = 1 TO 7 STEP 2
    IF gY = seqY(i) AND gX = seqX(i) THEN
     good = 1: EXIT FOR
    END IF
  NEXT
  IF good THEN
    FOR j = 1 TO 7
      IF LCASE$(board$(seqY(i + j), seqX(i + j))) <> MID$("amersay", j, 1) THEN
        good = 0: EXIT FOR
      END IF
    NEXT
  END IF
  IF good THEN
   PRINT hist$, LEN(hist$) - 1
   showBoard
   solCt = solCt + 1
   IF solCt / 10 = INT(solCt / 10) THEN : DO: LOOP UNTIL INKEY$ > ""
  END IF
RETURN
END SUB

SUB showBoard
 FOR i = 1 TO 3
  FOR j = 1 TO 3
   PRINT board$(i, j);
  NEXT
  PRINT
 NEXT
END SUB

Posted by Charlie on 2004-03-19 11:00:59