Rook and Queen Tour Puzzles: How to Visit Every Square Once

A rook tour puzzle asks a chess rook to land on every allowed square of a board exactly once, and the fastest route to an answer is to settle the cramped squares first, such as corners and squares beside blocked cells, then fill the open space in long back-and-forth rows. A queen tour follows the same plan, but its slanting moves give far more routes, so cramped squares matter less.

This guide sets out the rules of the common versions, explains open and closed tours, shows the row-by-row plan and the corner habit, and walks through a full worked example. A practice puzzle with its answer comes at the end.

What is a rook tour puzzle?

A rook moves in straight lines along a row or a column, never on a slant. In a tour puzzle you place the rook on a starting square and keep moving it until it has landed on every allowed square once. Landing on any square a second time breaks the rule.

Puzzle setters use two kinds of move, so always check which one a puzzle means:

• Step tour. The rook moves exactly one square up, down, left or right each turn. Many grid puzzles use this version, including the worked example below.
• Slide tour. The rook may glide any distance along its row or column. Squares it glides over do not count as visited. Many slide puzzles also forbid gliding across a blocked square or a square it has already landed on.

The visited-square rule is a choice made by puzzle setters, not a rule of chess. The blocked-square rule does come from chess, where pieces do not move through other pieces: a pawn standing between two queens on one line stops them reaching each other ^[1].

Many tour puzzles add blocked squares, shown as dark cells, and some fix the square where the tour must start, finish, or both.

How do open tours and closed tours differ?

An open tour is free to end on any square. A closed tour must end one move away from where it began, so the piece could step back to the start and go round again.

It helps to picture the board as a network. Each square becomes a dot, and a line links two dots whenever the piece can travel between them in one move. Seen this way, a closed tour is a loop through every dot.

In such a loop, each dot uses exactly two of the chosen lines, one to arrive and one to leave. A network with a dot that has only one line, or none, has no loop through every dot ^[2].

That gives the first check for any closed tour puzzle. If an allowed square has a single open neighbour, stop: the puzzle has no answer.

A paper published on 21 June 2011 noted that for decades the best known method for deciding whether a network has a loop through every dot took time that doubles with each extra dot, until a faster randomised method appeared shortly before the paper ^[2]. The same paper gave a faster method for listing every such loop in networks where each dot has exactly three lines ^[2].

How do you plan a tour by rows?

The snake plan is the simplest open tour. Run along the top row to its end, step down one square, run back along the second row, step down again and repeat. The route folds back and forth across the board, and it gives an open step tour of any rectangle with no blocked squares.

A closed tour needs one change. Leave the first column empty. Snake through the rest of the board row by row, then climb the empty first column back to the start. This closes neatly when the board has an even number of rows, because the snake then finishes at the foot of the empty column.

The table shows our own computer count of step tours on small boards. Open tours start from the top-left corner, and each closed loop is counted once, whichever way it is travelled.

Open tours are plentiful. Closed ones are rare, and on the odd-sized boards there are none at all.

Why do odd boards have no closed step tour?

Shade the board like a chessboard. Each step of a step rook changes shade, so a closed step loop must contain equal numbers of light and dark squares. When the number of allowed squares is odd, that balance is impossible, which explains the zeros in the table. Slide tours escape this test, because a glide of two squares keeps the same shade.

Why should corners and cramped squares come first?

On a step tour, a corner square has only two neighbours. If the corner is not the start or the finish, the tour must arrive through one neighbour and leave through the other. Both of its lines are forced, and you can draw them at once.

The same holds for any square squeezed down to two open neighbours, for example by a blocked cell next to it. Drawing forced lines starts a chain reaction:

1. Draw both lines of every square that has exactly two open neighbours and is not an end.
2. Any square that now has two drawn lines is full. Cross out its other links.
3. Crossing out links can leave new squares with only two choices. Draw their lines too.
4. A square left with one choice must be the start or the finish. If it is neither, the last move was wrong.

This is the main tool for hand solving. The snake plan fills open space, and forced lines decide how the snake bends around obstacles.

What does the queen add?

The queen moves along rows, columns and both diagonals ^[1]. In a step tour that means it may also step one square on a slant, and in a slide tour it may glide along diagonals as well.

Its extra freedom changes the puzzle in three ways:

• Colour stops working. A slanting step keeps the same shade, so a queen can close a loop on an odd board, which a step rook never can.
• Corners are no longer tight. A queen in a corner has three step neighbours, so few lines are forced and you must plan rather than deduce.
• The number of routes soars. Puzzles built for the queen may need more blocked squares to have one answer.

On an empty 8 by 8 board the gap is just as clear when you count the squares each piece can reach in one move.

The queen's long reach is also the heart of a classic placement puzzle. Because a queen reaches along its whole row and column, no two queens that must not reach each other can share a row, so at most n of them fit on a board n squares wide ^[1]. That puzzle has an answer for a board of a single square and for every board of four or more squares per side ^[1].

Blocked squares change this too. With pawns placed between them, more queens fit, but two queens on touching squares always reach each other, so an even-sided board can hold at most one queen for every four squares ^[1].

How do you solve a step rook tour, step by step?

1. Read the rules. Step or slide, open or closed, and whether the ends are fixed.
2. Test a closed tour first. No allowed square may have a single neighbour, and the two shades must balance.
3. Mark cramped squares. Write the number of open neighbours in each square near corners and blocked cells.
4. Draw forced lines. Settle every square with two choices, then cross out links of full squares.
5. Look for strand traps. Before each free choice, ask whether it leaves a square with one way in.
6. Fill open space with snake runs. Long straight runs keep the route tidy.
7. Check the result. Every allowed square once, every move a single step, and for a closed tour the last square next to the first.

How do forced lines crack a board with two blocked squares?

In this 5 by 5 puzzle the squares marked X are blocked. The tour must begin at S and end at F, using step moves only. Every move below comes from forced lines and one strand trap, with no guessing.

Forced lines. Row 1, column 2 touches only S and the square below it, so the tour runs S, then row 1 column 2, then row 2 column 2. Row 1, column 4 and the top-right corner each have two neighbours, which forces the chain row 2 column 4, row 1 column 4, row 1 column 5, row 2 column 5.

Forced lines at the bottom. Row 5, column 3 sits below a blocked square, so it links row 5 column 2 to row 5 column 4. The bottom-left corner joins that chain from row 4 column 1.

Follow the start. S already uses its only line, so row 2, column 1 cannot link to S. Its remaining neighbours are row 2 column 2 and row 3 column 1, so both lines are forced. The tour now reads: S, row 1 column 2, row 2 column 2, row 2 column 1, row 3 column 1.

Avoid a strand trap. From row 3 column 1, going straight down to row 4 column 1 would leave row 4 column 2 with only one free neighbour, and it is not an end. So the tour turns right to row 3 column 2, drops to row 4 column 2, steps left to row 4 column 1 and joins the forced bottom chain to row 5 column 4.

Finish the right side. From row 5 column 4 the tour cannot enter F yet, so it climbs to row 4 column 4. Row 3 column 3 has only two free neighbours left, which forces row 3 column 4, row 3 column 3, row 2 column 3 and on into the top chain. The top chain ends at row 2 column 5, and the tour runs down column 5 to F.

A full computer search of every possible route confirms that this is the only tour from S to F on this board.

Can you solve this closed tour?

Find a closed step tour of this board. The squares marked X are blocked, and every other square must be visited once before you return to your start.

Start with the corners and the square in row 1, column 2, which has just two neighbours.

Answer: There is exactly one loop. Numbered from row 1, column 2, it runs as follows.

Square 22 sits right next to square 1, so the loop closes.

For a different kind of trail, start at the star, follow the arrows and work out which word you spell: