This question was posed to me, and I was surprised that I could not find a solution (as I thought that all rook tours [open or closed] were possible). Starting from a8, could a rook visit every square on the board once, ending on f3?

I tried a few times, with a few different strategies, but I always ended up missing one square.

It’s really easy to burn pairs of rows or columns, so the problem space could be reduced…

…but at some point (4x4), I was able to convince myself that it is impossible (at least at this size and state):

…but it might be possible that shaving off column or row pairs is also discarding a solution?

  • hexabs@lemmy.world
    3·
    7 days ago

    All the grids have even number of squares (equal black and white). Therefore it is impossible to start on white and end on white while covering everything else.

    I don’t have the formal proof for this, but can be proven with examples. In each of your grids.

    I’ll be following this thread to see if someone shares the formal proof for this, fingers crossed!

    • 7uWqKj@lemmy.world
      3·
      7 days ago

      You’re right, guess the reason is that the rook changes the colour of the square it’s on with every move. After an odd number of moves it’s on the opposite colour, after an even number of moves it’s back on the colour it started on. So, no sequence of 63 moves starting on a light square can ever end on another light square.