7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "touching or moving over an square", let me clarify please, so just "jumping" over a square (without landing on it) makes it marked? $\endgroup$ – d'alar'cop Oct 21 '14 at 1:02
  • $\begingroup$ @d'alar'cop Yes, sorry for not responding soon enough. For this bishops don't jump, they move over the square and mark it on the way. $\endgroup$ – kaine Oct 21 '14 at 2:15
  • $\begingroup$ Let me Clarify so if a bishop goes from a1 to b2 which are the squares that would be considered "Marked" a1,b2 or more? $\endgroup$ – skv Oct 21 '14 at 7:42
  • 1
    $\begingroup$ @sky a1 and b2. If it went from a1 to c3 then a1, b2, and c3 would be marked. $\endgroup$ – kaine Oct 21 '14 at 12:43
4
$\begingroup$

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.1 Fig. 2 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. 3 Fig. 4 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 black path ends.)

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 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.

$\endgroup$
  • $\begingroup$ What do you think about that bunny tour then? (puzzling.stackexchange.com/questions/2929/the-bunnys-tour). Strongly related imo. $\endgroup$ – d'alar'cop Oct 24 '14 at 14:25
  • $\begingroup$ Yes, it is related, and no, I haven't tried it seriously yet. The bunny problem implies 4 solutions to this problem with strong constraints regarding placement of the ends and how the paths all interrelate. $\endgroup$ – Florian F Oct 24 '14 at 15:23
  • $\begingroup$ There is a flaw in your proof. You are assuming that a path in P_T has always two different endpoints and therefore 4 endpoints of P_T are not on the diagonal. As a consequence if P_S has contains exactly four paths no endpoint of these paths could lie on one of the small ( = 7 square) diagonals. But a path that consists of only one point has only one endpoint. Both diagrams in this answer have endpoints on the small diagonals and the associated P_T contain one node paths. $\endgroup$ – miracle173 Nov 5 '14 at 7:11
  • $\begingroup$ I tried to explain that in the note at the bottom. A single-node path counts as 2 endpoints on the same square. But only one of these endpoints can extend the path outside of the triangle. So there still must remain 4 endpoints on the triangle, whether on the large diagonal or the smaller ones. $\endgroup$ – Florian F Nov 5 '14 at 8:51
8
$\begingroup$

I conjecture that you need 8. 4 for each colour. The issue is clearly about getting stuck in "corners" (even artificial ones created by marking nearby squares.). Here is a couple of crude diagrams illustrating half of the solution (the other half is the same, but for the other colour):

enter image description here

And in case you thought that going diagonally would help:

enter image description here

$\endgroup$
  • $\begingroup$ related: puzzling.stackexchange.com/questions/2929/the-bunnys-tour $\endgroup$ – d'alar'cop Oct 21 '14 at 0:31
  • $\begingroup$ They are quite actively enjoyed it seems, and I credit this diagram to: chess.com/forum/view/more-puzzles/bishops-tour $\endgroup$ – d'alar'cop Oct 21 '14 at 1:01
  • $\begingroup$ You are going over the same squares multiple times. After a bishop stops on or moves over any square it is considered marked and cannot be passed over again. $\endgroup$ – kaine Oct 21 '14 at 2:13
  • $\begingroup$ @kaine yes, I understand now. Give me a little bit to sort out a new answer $\endgroup$ – d'alar'cop Oct 21 '14 at 2:16
  • $\begingroup$ +1. Note that you can arrange these in a somewhat more-organized, easier-to-grasp fashion by having one bishop zigzag over all of the first two rows, one over the third and fourth rows, one over the fifth and sixth rows, and one over the last two rows. $\endgroup$ – ruakh Oct 21 '14 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.