18
Is this open rook's tour actually impossible? (lemmy.ml)
submitted 1 year ago* by to c/chess@lemmy.ml
28 comments fedilink hide all child comments
 

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?

you are viewing a single comment's thread
view the rest of the comments
[โ€“] 4 points 1 year ago (1 child)

This puzzle is definitely impossible. In fact it seems to be some sort of parity issue, although I'm having trouble with the actual proof. Basically if you always keep the start in the top left corner, then you can only complete a rook's tour if the end square has an odd manhattan distance (x distance + y distance). If you put the end square an even manhattan distance away, then you create this issue where you're always unable to hit one square.

For example, even parity, impossible:

Odd parity, possible:

  • permalink
  • fedilink
  • source
  • hideshow 2 child comments
    •
  • [โ€“] 4 points 1 year ago*

    You start in white and you can only move to black. Then you have to move to white again then black, then white, then black and so on. For a sequence with an even number of terms you have to end on black if you start in white .Since the puzzle states you have to start and end on white it's impossible.

  • permalink
  • fedilink
  • source
  • parent