Queen's Quadrille
From a standard chess set, remove the pawns and the white queen. Place
the remaining pieces on a 4x4 chessboard (leaving one empty space.) Pieces
move as in regular chess, but moves don't need to alternate in color and no
piece can be captured (removed). The object is to move the queen along a
specified path.
 Find a configuration and moves to let the queen visit every square of
the board in the minimum possible total moves. You may count the starting
square as "visited".
The theoretical minimum is 29
moves (the queen moves 15 times, each other piece once.) How close can you
get to this minimum?
 Find a configuration and moves to let the queen visit every square
and return to her starting square in the minimum number of moves
(the theoretical minimum is 31 moves, as explained above.)
Source: Original, based on a game described in the June 1998 Games
magazine, Page 50, Karen Deal Robinson.
Solutions were received from
Alexander Doskey:

first tour discovered with 29 moves:
(I liked the knights in the four corners)
starting board position on the left:
+++++ +++++
nqrn f023
+++++ +++++
rsbb e154
+++++ +++++
kkbr cd96
+++++ +++++
nrbn ba87
+++++ +++++
order the queen traveled  0123456789abcdef
pieces: qqueen, sspace, bbishop, rrook, nknight, kking

tour discovered with 29 moves, and best cycle I have found so far 32 moves:
+++++ +++++
skbk 12fe
+++++ +++++
rqnr 30cd
+++++ +++++
nrnb 478b
+++++ +++++
rnbb 659a
+++++ +++++
To make the tour a cycle, move the king back into the corner, and the
other king into the vacated middle square, and the queen can return to
her starting square.
Sandy Thompson sent these results from his computer search for a 31move
cycle 12/14/01:
I set up an exhaustive search that would play out all possible board layouts
(ignoring rotations and reflections). It took a few weeks worth of evenings
and weekends, but my soldier of a computer eventually came up with the final
answer.
First, some explanations of the columns that you'll see in the chart.
 "Q" or "S": The starting board location of the queen and the space. The
board squares were numbered as follows:
+++++
 1 2 3 4
+++++
 5 6 7 8
+++++
 9101112
+++++
13141516
+++++
 "29's": Total number of 29move solution
 "30's": Total number of 30move solutions. In other words, after the
29move solution is found, the piece on the Queen's starting square can
legally move to the blank square.
 "31's": Total number of 31move solutions. In other words, after the
30move solution, the queen can legally move back onto her starting square
(which is blank after a 30move solution).
What I found is the following:
Q S 29's 30's 31's

1 2 495 0 0
1 6 100 0 0
2 1 535 40 0
2 3 15 0 0
2 5 50 0 0
2 6 45 0 0
2 7 0 0 0
6 1 100 0 0
6 2 15 0 0
6 3 25 0 0
6 7 0 0 0
6 11 0 0 0
 You will notice that all possible reflections and rotations are covered in
the 12 cases I've examined.
 In only 40 of the 1380 29move solutions could the piece on the queen's
starting square actually move to the blank square, and in none of those
cases could the queen then return home.
It's kind of neat being the only guy on the planet (I'm assuming) to know
the final answer to this problem... even if it was for only a few days.
Sick exhaustive search obsessions have their perks.
Sandy
Mail to Ken