Consider the movement of a knight on an n x m chessboard (move two fields horizontally/vertically...

 

Transcribed Image Text:

Consider the movement of a knight on an n x m chessboard (move two fields horizontally/vertically plus one field vertically/horizontally). A knight's tour is a sequence of moves, where each field is visited exactly once. A knight's tour is re-entrant iff there is a move from the last field back to the start field. (i) Define a graph modelling the moves of a knight on such a chessboard. (ii) Show that a knight's tour exists iff the corresponding graph has a Hamilton path. (iii) Show that a re-entrant knight's tour exists iff the corresponding graph has a Hamilton cycle. (iv) Show that for odd n there is no re-entrant knight's tour on an n x n chessboard. Consider the movement of a knight on an n x m chessboard (move two fields horizontally/vertically plus one field vertically/horizontally). A knight's tour is a sequence of moves, where each field is visited exactly once. A knight's tour is re-entrant iff there is a move from the last field back to the start field. (i) Define a graph modelling the moves of a knight on such a chessboard. (ii) Show that a knight's tour exists iff the corresponding graph has a Hamilton path. (iii) Show that a re-entrant knight's tour exists iff the corresponding graph has a Hamilton cycle. (iv) Show that for odd n there is no re-entrant knight's tour on an n x n chessboard.

Answer rating: 100% (QA)

i Graph Modeling To model the knights movements on an n x m chessboard as a graph we can represent each cell on the chessboard as a vertex and the possible knight moves as edges connecting the vertice... View the full answer