|
Home
|
Sign up!
|
Projects
|
Seminars
|
Research Notes
|
Today's Lecture
|
About
|
Update Seminar Form
Course:
Seminar Topic:
Seminar Description:
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
re-entrant tour
requires that you are able to get back to the starting square with one more move.
This is an application of a
Hamiltonian Path
, a path that goes through every vertex of a graph exactly once.
Given a chessboard, make a graph G with vertices=squares and v
i
and v
j
are connected by an edge if and only if there is a possible knight move from square v
i
to square v
j
. 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).
Your Password:
Prof. Ashay Dharwadker