0

I'm not sure if this problem fits here. Consider a rook taking a tour on a chessboard with a number of squares blocked (see attached figure). Here, our rook started in the upper left corner and visited each square once in 23 moves. But what starting point and route yields the minimum? Also, which row (or rows) won't allow that minimum?enter image description here

Ken Bannister
  • 31
  • Start from A8 can give route containing 18 moves. Start from A7 can give route containing 16 moves. I don't know if these route are minimal. – Ivan Kaznacheyeu Apr 05 '23 at 14:31

1 Answers1

1

I think an $n\times (n+1)$ square is covered optimally in $2n-1$ moves. Without the A and H files your region is a $7\times 8$ region so you need 13 moves to cover that, so it seems we'll at least never beat 15.

Here's a 16 move route: (B1) H1 H2 B2 B3 H3 H4 B4 B5 H5 H6 B6, then B7 G7 G8 A8 A7

tomos
  • 1,650
  • I understand that MATLAB offers a function "BFS" (Breadth First Search?) that could be used to do searches. Has anyone tried it with a rook's tour problem like the one above? – Ken Bannister Apr 08 '23 at 00:50