The following is a simple set-up for the familiar Knight's Tour puzzle, in this case on a 5x5 chess board only, with the start/finish positions as indicated:

		1
25

One day, being rather jealous of all the attention the Knight gets with these kind of tours, the Knave loudly proclaimed that he too could complete this same tour board. But of course, as with Liars and Knights puzzles, the Knave will alternate between Knightly moves (the standard chess move) and Liar's moves (2 squares up, down, left, or right, starting and ending on the same color).

Could the Knave complete the tour where he initially starts with a Knightly move? How about starting with a Liar's move? (There may be more than one solution.)

Dim x, y, h$, b$(5, 5), hx(25), hy(25), hdx(25), hdy(25), mSize
Dim max, maxH$
Private Sub Form_Load()
For r = 1 To 5: For c = 1 To 5
  b$(r, c) = Mid$("abcdefghijklmnopqrstuvwxyz", r * 5 + c - 5, 1)
  Print b$(r, c);
Next: Print: Next
Print CurDir
Open "knaves tour.txt" For Output As #2
Print
x = 3: y = 3: h$ = "m": hx(1) = 3: hy(1) = 3
hdx(1) = 0: hdy(1) = 0
Me.Visible = True

mSize = 3: moveIt

End Sub
Sub moveIt()
 
 DoEvents
 mNo = Len(h$)
 For dx0 = -2 To 2 Step 2
 For dy0 = -2 To 2 Step 2
  If (dx0 <> 0 Or dy0 <> 0) And (dx0 = 0 Or dy0 = 0) Then
   If mSize = 2 Then
     dx1 = dx0: dx2 = dx0: dy1 = dy0: dy2 = dy0
   Else
     If dx0 = 0 Then
       dy1 = dy0: dy2 = dy0: dx1 = -1: dx2 = 1
     Else
       dx1 = dx0: dx2 = dx0: dy1 = -1: dy2 = 1
     End If
   End If

   For dx = dx1 To dx2 Step 2
   For dy = dy1 To dy2 Step 2
      newX = hx(mNo) + dx: newY = hy(mNo) + dy
      If newX > 0 And newX <= 5 And newY > 0 And newY <= 5 Then
       If InStr(h$, b$(newY, newX)) = 0 Then
        mNo = mNo + 1
        mSize = 5 - mSize
        h$ = h$ + b$(newY, newX)
        hx(mNo) = newX: hy(mNo) = newY
        hdx(mNo) = dx: hdy(mNo) = dy
        If b$(newY, newX) = "u" And Len(h$) > 20 Then
          Text1.Text = h$
         
          If Len(h$) > max Or Len(h$) = 25 Then
           max = Len(h$): maxH$ = h$
           Print h$; Len(h$), max; maxH$
           Print #2, h$; Len(h$), max; maxH$
          End If
        Else
          moveIt
        End If
              
        h$ = Left$(h$, Len(h$) - 1)
        mSize = 5 - mSize
        mNo = mNo - 1
       End If
      End If
   Next
   Next

  End If
 Next
 Next
End Sub

The mSize = 3 starts it off with a knight's move; mSize = 2 would start it off with a liar's move.

Posted by Charlie on 2009-01-23 21:42:06