Update Seminar Form
This problem asks you to place a knight any place you like on a chess board and then move it around the board so that you visit each position on the board exactly once. A
requires that you are able to get back to the starting square with one more move.
This is an application of a
, a path that goes through every vertex of a graph exactly once.
Given a chessboard, make a graph G with vertices=squares and v
are connected by an edge if and only if there is a possible knight move from square v
to square v
. Then a Re-entrant Knight’s Tour on the chessboard = Hamiltonian Circuit.
What types of chessboards have Re-entrant Knight’s Tours?
No Re-entrant Knight’s Tour for n-odd.
Always have a Re-entrant Knight’s Tour for n-even (n >= 6).
Prof. Ashay Dharwadker