When a Knight moves in chess, it can move to a square that is away two squares horizontally and one square vertically,or two squares vertically and one square horizontally.A closed tour for a Knight is a sequence of moves,which have the Knight start and end in the same square and visit each other square exactly once.On a $4 \times 3$ board,is there a possible closed tour for a Knight?
Re: Closed tour of a Knight
Posted: Thu Mar 01, 2018 6:47 pm
by samiul_samin
Hint
Use proof by contradiction & invariance pinciple
Answer
NO.
$4×3$ Chess Board
Screenshot_2018-03-01-18-22-01-1.png
Answer
According to the given chessboard the close knight tour is possible if and only if the knight can move from $A$ to $T$ and touch every squares exactly Once.
Let,this tour is possible.So,the knight has to move to $I$ before $T$.There is only $2$ ways to move to $I$, they are $R\rightarrow I$ and $O\rightarrow I$ It is obvious that $O\rightarrow I$ is not possible.So,the moves should be,$R\rightarrow I$,$I\rightarrow O$,$O\rightarrow I$.
Now if the knight wants to move from $A$ to $R$ under the condition of question in $8$ move,it can't do so.Because,In every move it alters the color of the square.If $A$ is black,$R$ is also black.But,move number is even.
A contradiction.
So,we are done.It is not possible.
Re: Closed tour of a Knight
Posted: Sat Mar 09, 2019 7:59 pm
by samiul_samin
Ignore the above solution.
Correct Solution
Let the tour is possible.
Total move $=12-1=11$
In every move it alters the color of the square.If the starting square is black,the ending square is not black.(Imagine it as a traditional chess board)
But,move number is odd.
A contradiction.
So,we are done.It is not possible.