chess - How many bishops to walk across the board

N bishops are placed on a standard 8x8 chess board.

Each bishop can move normally but after touching or moving over an square, that square is considered marked. A bishop cannot pass over or land on a marked square again.

Each bishop may stop any number of times.

What is the minimum number (N) of bishops required to mark every square but follow these rules?

Answer

Preliminary remarks

It is quite obvious that visiting the black squares and visiting the white squares are two independent problems. No bishop can move from one color to the other and they don’t hinder each other in any way.

If N bishops can visit all squares of one color, then 2N bishops can visit all squares of the board.

The problem to solve

Because of the above, we will consider the problem of visiting all grey squares on the board on fig. 1 using N paths that each follows the movement rules of a bishop.

Fig.1 . . . Fig. 2

Fig. 2 illustrates one possible solution of visiting all squares with 4 paths. The direction of the movements is irrelevant.

If you try to solve the problem manually, you will probably find solutions in 4 paths, and you will experience that it resists being solved in less than 4 paths. It feels like, regardless of how you arrange the paths, there is a resource that gets exhausted and you need to add more paths to provide that resource.

A subproblem

To see what it is you are short of, consider another problem, which is to visit half of the board only. Let’s consider the upper-left triangular half (fig.3).

Fig. 3 . . . Fig. 4

Let’s add black and white dots on the board (fig. 4) in some kind of second-level chessboard pattern.

You can see that any bishop path must alternate between black and white dots. So, any bishop path will visit as many black as white dots, with maybe one extra black or white dot. But the imbalance between black and white dots for a single path will never be more than one dot.

On the other side, the imbalance of black and white dots in the triangle is important. There are 10 black dots and only 6 white dots, that is an excess of 4 black dots. This imbalance must be reflected in the paths that cover them. Since we have an excess of 4 black dots, and since one path can only have an excess of 1 black dot, no matter how we arrange the paths, we need 4 paths to reach the same imbalance.

This already proves that you need 4 disjoint paths to cover the triangular board.

(And to answer the question: you are short of white-dotted squares.)

Back to the problem

Let’s now consider the upper-left triangle as part of a square board. Let’s assume we have a set $P_S$ of paths that visit all gray squares of the square board. Let $P_T$ be the set $P_S$ restricted to the squares of the upper-left triangle. $P_T$ is made of pieces of paths in $P_S$.

$P_T$ covers the triangle exaclty so it must include at least 4 disjoint paths.

The fact that $P_T$ includes 4 paths doesn’t imply that $P_S$ also includes 4 paths, because the paths in $P_T$ can join each other via the other half. For example, the bottom right triangle on fig. 2 is completely covered with 3 paths.

The important thing is to see is that a set of paths also defines a set of path ends. (A single-square path counts as 2 ends, the start and the end). If $P_T$ includes 4 paths, it defines 8 path ends within the triangle. We can even assert that it defines 8 path ends located on black dots. That is because only a path with 2 black ends contributes to the imbalance of black dots over white ones.

Let’s take the solution on fig. 2 and see the set $P_T$ covering the upper left triangle (fig. 5).

Fig. 5

As expected, there are at least 4 paths and 8 black path ends.

Only 4 of the black path ends are located near the diagonal. So if we stick the 2 halves back together, only 4 of the black ends can be extended to the other side. The at least 4 remaining black ends are not affected by the other half. That means at least 4 black ends in $P_T$ are also path ends in $P_S$.

The result is that $P_S$ has at least 4 path ends in the upper-left triangle. Likewise, it has 4 path ends in the lower-right triangle. Altogether $P_S$ has at least 8 path ends. And this requires at least 4 paths in $P_S$.

So, to cover the square board, you need 4 bishop paths.

Conclusion

Visiting all squares of one color on a standard chess board requires 4 disjoint bishop paths. To do both colors you need twice as much, you need 8 bishops.

Note

In counting path ends, it is important to remember the multiplicity of path ends when the path starts and ends on the same square. This requires some precautions. For a single-square path, count 2 ends on that same square. This is compatible with the fact that one path has always 2 ends. Another point is that you could have a double path end on a square of the diagonal. This is not a problem since only one can extend to the other side. It doesn’t allow to extend more than 4 paths to the other side.