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.
  1. 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?
  2. 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: 
  1. first tour discovered with 29 moves:
(I liked the knights in the four corners)
starting board position on the left:

+-+-+-+-+       +-+-+-+-+
|n|q|r|n|       |f|0|2|3|
+-+-+-+-+       +-+-+-+-+
|r|s|b|b|       |e|1|5|4|
+-+-+-+-+       +-+-+-+-+
|k|k|b|r|       |c|d|9|6|
+-+-+-+-+       +-+-+-+-+
|n|r|b|n|       |b|a|8|7|
+-+-+-+-+       +-+-+-+-+

order the queen traveled - 0123456789abcdef
pieces: q-queen, s-space, b-bishop, r-rook, n-knight, k-king

  2. tour discovered with 29 moves, and best cycle I have found so far 32 moves:

+-+-+-+-+       +-+-+-+-+
|s|k|b|k|       |1|2|f|e|
+-+-+-+-+       +-+-+-+-+
|r|q|n|r|       |3|0|c|d|
+-+-+-+-+       +-+-+-+-+
|n|r|n|b|       |4|7|8|b|
+-+-+-+-+       +-+-+-+-+
|r|n|b|b|       |6|5|9|a|
+-+-+-+-+       +-+-+-+-+

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 31-move 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|
 +--+--+--+--+
 | 9|10|11|12|
 +--+--+--+--+
 |13|14|15|16|
 +--+--+--+--+

- "29's": Total number of 29-move solution
- "30's": Total number of 30-move solutions.  In other words, after the
29-move solution is found, the piece on the Queen's starting square can
legally move to the blank square.
- "31's": Total number of 31-move solutions.  In other words, after the
30-move solution, the queen can legally move back onto her starting square
(which is blank after a 30-move 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 29-move 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