# Knight on a chessboard moving from a1 to h8

I was given a puzzle to solve which goes as:- Can a knight start at square a1 of a chessboard, and go to square h8, visiting each of the remaining squares once on the way ?

I reasoned that this won't be possible because both the squares a1 and h8 have the same colour ( say, black ). If we are not considering these squares, then the remaining chess board has 62 squares which means that there are 30 black squares and 32 white squares. If the knight was to visit each of these squares exactly once, then this would mean that we would be having the sequence WBWBWBWB.....W where the pair "WB" would be occuring 31 times. However, this is not possible as there are two extra whites than black. When I submitted this solution, I was told that it is wrong but no explanation was given. Can you help me out?

-
It is cleaner to say that any for any path that visits each square once, there will be an odd number $(63)$ of moves. That means we end up at a white square. – André Nicolas Aug 29 '13 at 16:14
@AndréNicolas Are you considering the squares excluding a1 or h8? – kusur Aug 29 '13 at 16:15
I am counting moves. So in a sense I am using h8 but not a1. Your version implicitly looks at the path until we are just about to get to h8. The idea is right, just a little fuzzily expressed. – André Nicolas Aug 29 '13 at 16:18
The question here is does the starting square count as a visit? If it does then you will have to make 63 moves to visit each square so your final square will have to be a different colour to your staring square so its impossible as both a1 and h8 are black. If the starting square does not count as a visit it may be possible however. – Warren Hill Aug 29 '13 at 16:52

There may a simpler explanation: to visit all the squares without returning to any takes 63 steps, an odd number, but each step changes the colour, so you cannot finish on the same colour as you started.

Perhaps you were failed because you gave a correct answer which was different to the one the tester was looking for.

-

Your idea is correct. Your explanation could be polished a little bit, but I don't see why it should be wrong.

-
I think that my argument could be wrong if we are considering all the squares and not just ones that will only visited. In fact, even if I consider 63 squares ( including h8 ), I am still having one white square in excess and hence the pairing won't be possible. – kusur Aug 29 '13 at 16:09
I don't see a problem. For 63 squares, you have a pairing plus the last square. – azimut Aug 29 '13 at 16:14

Converting your question into a Language.

L = { (wb)^i, 32>=i>=1,i belongs to Q}

with Grammar :

S->wA
A->bS
A->b


Its not exact solution, because you've been told that no square is visited twice,which I couldnt translate into above language.

Another approach, would be using Hamiltonian graph/circuit or Eulerian path concept.I dont know the solution as I've just started studying graphs & trees, but I'm sure the problem can be solved mathematically using either graph or by language, or maybe by both combined.

-
Please explain your solution in a language that can be most of us. – kusur Aug 29 '13 at 17:19