From knight’s tours to complexity

 Von Warnsdorf’s Rule source

Christian von Warnsdorf did more and less than solve the Knight’s Tour puzzle. In 1823 he published a short book whose title translates to, The Leaping Knight’s Simplest and Most General Solution. The ‘more’ is that his simple algorithm works for boards of any size. The ‘less’ is that its correctness remains yet unproven even for square ${n \times n}$ boards.

Today we consider ways for chess pieces to tour not 64 but up to ${2^{64}}$ configurations on a chessboard.

Von Warnsdorf’s rule works only for the ‘path’ form of the puzzle, where the knight is started in a corner of an ${n \times n}$ board and must visit all the other squares in ${n^2 - 1}$ hops. It does not yield a final hop back to start to make a Hamilton cycle. The rule is always to move the knight to the available square with the fewest connections to open squares. In case of two or more tied options, von Warnsdorf incorrectly believed the choice could be arbitrary, but simple tiebreak rules have been devised that work in all known cases. More-recent news is found in papers linked from a website maintained by Douglas Squirrel of Frogholt, England. We took the above screenshot from his animated implementation of the rule when the knight, having started in the upper-left corner, is a few hops from finishing at upper right.

The first person known to have published a solution was the Kashmiri poet Rudrata in the 9th century. He found a neat way to express his solution in 4 lines of 8-syllable Sanskritic verse that extend to an 8×8 solution when repeated. In modern terms he solved the following:

Color the squares so that for all k, the k-th square of the tour has the same color as the k-th square in row-major order—in other words, the usual way of reading left-to-right and down by rows—while maximizing the number m of colors used.

Note that we can guarantee ${m \geq 2}$ by starting in the upper-left corner and using a different color for all other squares. However, the usual parity argument with the knight doesn’t even let us 2-color the remaining squares to guarantee ${m \geq 3}$ because the last square of the first row and the first square of the second row have the same parity. Rudrata achieved ${m = 4}$ for the upper half with cell 21 also a singleton color; this implies ${m = 8}$ for the whole ${8 \times 8}$ board and ${m = n}$ for ${n \times 8}$. Can it be beaten? Most to our point, is there a “Rudrata Rule” for ${n \times n}$ as simple as von Warnsdorf’s?

## Warming Up the Coins

We now put a coin heads-down on each square. Our chess pieces are going to move virtually through the space ${\{0,1\}^{64}}$ by flipping over the coins in squares they attack. Our questions will be of the form, can they reach all configurations, and if not:

How small can Boolean circuits be to recognize the set of reachable strings?

Let’s warm up with a different problem. Suppose the coins are colored not embossed so you cannot tell by touch which side is which, and the room is pitch dark. You are told that k of the coins are showing heads but not which ones. You must take some of the coins off the board, optionally flipping some or all while placing them nearby on the table. The lights are then switched on, and you win if your coins have the same number of heads as the ones left on the board. Can you always win?

I may have seen this puzzle as a child but it was fresh when I read it here. Our point connecting to this post is that the solution, which can be looked up here, is simple in terms of k and so can be computed by tiny Boolean circuits.

Since the tours will be reversible, we can equally well start with any coin configuration and ask whether the piece can transform it to the all-tails state. This resembles solving Rubik’s Cube. We’ll try each chess piece one-by-one, the knights last.

## The Rook’s Succinct Tours

Our rook can start on any square. It flips each coin in the same row or column (“rank” and “file” in chess parlance) as the square it landed on. Then it moves to one of those squares and repeats the flipping. If it moved within a rank then the coins in that row will be back the way they were except that the two the rook was on will be flipped. We can produce a perfect checkerboard pattern by moving the rook a1-c1-c3-c5-e5-g5-g7 then back g5-c5-c1. Since order doesn’t matter and operations from the same square cancel, this has the same effect as doing a1, c3, e5, and g7 “by helicopter.”

Since the rook always attacks 14 squares, an even number of coins flip at each move, so half the space is ruled out by parity. There is however a stronger limitation. Each rook flip is equivalent to flipping the entire row and then the entire column. We can amplify the rook by allowing row and column flips singly. But then we see that there are only 16 such operations. Again since repeats cancel, this means at most ${2^{16}}$ configurations are possible. We ask:

Is there a simple formula, yielding small Boolean circuits, for determining which configurations are reachable on an ${n \times n}$ board?

We can pose this for the Rook, with-or-without “helicoptering,” and for the row-or-column flips individually. Small circuits would mean that strings in ${\{0,1\}^{n^2}}$ denoting reachable configurations enjoy a particular form of succinctness.

Since the rook fails to tour the whole exponential-sized space, let’s try the bishop.

## Her Majesty Interrupts

The bishop can flip any odd number of coins from 7 to 13. It is limited to squares of one color but we can allow the opposite-color bishop to tag-team with it. I was just about to pose the same questions as above for the bishops when a familiar imperious voice swelled behind me. It was the Red Queen.

“I have all the power of your towers and prelates—and you need only one of me. I shall surely fill the space.”

I was no one to stand in her way, but the Dormouse awoke and quietly began scratching figures on paper. “Besides the sixteen ranks and files, there are fifteen southeast-to-northwest diagonals, including the corner squares a1 and h8 by themselves. And there are fifteen southwest-to-northeast diagonals. This makes only 16 + 15 + 15 = 46 ${<}$ 64 operations. Hence, Your Majesty, even if we could parcel out your powers, you could fill out at most a ${2^{46 - 64} = 0.0000038}$ fraction ${S}$ of the space.”

I expected the Red Queen to yell, “Off with his head!” But instead she stooped over the Dormouse and hissed,

“You’re in the wrong book.”

“Sorry—I slept through the rest of Alice,” explained the Dormouse as he slunk away. Despite the Dormouse’s proof I thought it worth asking the same questions as for the rook and bishop about the queen’s subspace ${S}$. What kind of small formulas or circuits can recognize it, whether requiring her to flip all coins in all directions or allowing to flip just one rank or file or diagonal at a time?

## Soft Power and Softer

While I was wondering, His Majesty quietly strode to the center and said,

“I do not wantonly project power without bound; I reserve my influence so that my action on every square is distinctive.”

We can emphasize how far things stay distinctive by posing our basic questions in a more technical manner:

Do the sixty-four vectors over ${\mathbb{Z}_2}$ representing the king’s flipping action on each square span the vector space ${\mathbb{Z}_2^{64}}$? If not, what can we say about the circuit complexity of the linear subspace they generate?

On a ${2 \times 2}$ board the four ${4}$-vectors form a basis, but for ${3 \times 3}$ and ${4 \times 4}$ the king fails to span. For ${3 \times 3}$, kings in the two lower corners produce the same configuration as kings in the two upper corners. For ${4 \times 4}$, kings in a ring on a2, b4, d3, and c1 flip just the corner coins, as do the kings in the mirror-image ring. What about ${6 \times 6}$ and ${8 \times 8}$? Is there an easy answer?

Meeker still are the pawns, who attack only the two squares diagonally in front, or just one if on an edge file. They cannot attack their first rank, nor the second in legal chess games, but opposing pawns can. Then it is easy to see that the pawn actions span the space. The lowly contribution by the edge pawn is crucial, since it flips just one coin not two.

## Enter the Knight

The knight flips all the coins a knight’s move away. One difference from the queen, rook, bishop, and king is that on its next move all the coins it flips will be new. Our revised Knight’s Tour question is:

Can the knight connect the string ${0^{64}}$ to any configuration by a sequence of knight’s moves, perhaps allowing multiple visits to some squares? Or if we disallow multiple visits in a tour, can we do it by “helicoptering”? Same questions for ${n \times n}$ boards. If the answer is no, then are there easy formulas or succinct circuits determining the space of reachable configurations?

An example for needing multiple visits or helicoptering is that the configuration with heads on c2,b3 and g6,f7 is produced by knights acting in the corners a1 and h8, which are not connected by a knight’s move. If there is some other one-action-per-square combination that produces it, then by simple counting the knight cannot span—even with helicoptering.

The knight does fail to span a ${4 \times 4}$ board because the corner d4 produces the same result as the knight on a1: heads on c2 and b3. The regular knight’s tour fails too on a ${4 \times 4}$ so this can be excused for the same “lack of legroom” reason. What about ${5 \times 5}$ and higher?

Thus having coins on the chessboard scales up some classic tour problems exponentially. Our larger motivation is what the solutions might tell us about complexity.

## Open Problems

Do you like our exponential “tour” problems? Really they are reachability problems. Can you solve them?

Will von Warnsdorf’s rule ever be proved correct for all higher n?

Note: To update our recent quantum post, Gil Kalai released an expanded version of his AMS Notices article, “The Quantum Computer Puzzle.” We also congratulate him on being elected an Honorary Member of the Hungarian Academy of Sciences.

1. May 15, 2016 4:08 am

For the king problem:
For all odd square boards the kings fail to span. Place kings in every cell where the coordinates are both odd.
Kings span the 6×6 board. To prove this, and search on larger boards, first observe that a counterexample should have 8-fold symmetry. If two distinct configurations (vectors in Z_2) of pieces yield the same vector of coins, you can add them to get a nonzero configuration that yields 0^64. If a configuration yields 0^64 and isn’t symmetric, you can add it to its symmetry and still yield 0^64. The sum configuration will be nonzero if the starting configuration was asymmetric.
Now that we only have to look at symmetric configurations, we only have to choose for 6 cells whether to place kings in them, and the rest is determined. The computation is not too hard.

For the knight problem:
Knights don’t span the 7×7 board. Put knights at (1,1), (1,7), (7,1), (7,7), and (4,4).

• May 15, 2016 11:04 am

Very nice, thanks! Especially the use of symmetry about the kings—the exponentially scaled-effect of these succinct symmetries is what we are interested in.

2. May 15, 2016 4:26 pm

Except for pawns, the problems with or without helicoptering are equivalent. If you want to helicopter to positions p1, p2, …, pk, do the following: Start in any arbitrary position q. Take some (possibly empty) path to p1. Retrace your steps to q, thus canceling all the flips except at p1. Take one step along the path to p2 and treat this as your new starting position.

Furthermore, reachability for helicoptering can be solved with Gaussian elimination. Just check if the vectors representing flipping actions at each location include the target configuration in their span. This is polynomial time in n. Is that the kind of succinctness you were hoping for?

3. May 17, 2016 12:30 pm

szívből köszönöm