A knight\'s circuit of an n x n chessboard starts at some square H on the board,

Question

A knight's circuit of an n x n chessboard starts at some square H on the board, follows knight's moves, visits every square exactly once, and returns to H. Show that there is a Knight's circuit of the 6 x 6 chessboard. An invariant is a statement which is TRUE for each phase of a computation or construction. (In constructing a Knight's circuit the partial sequence of squares you have visited could be considered a "phase".) Use the idea of invariant to show that there cannot be a Knight's circuit of an n x n when n is odd and n > 1.

Explanation / Answer

Since there are nn squares on the n×n board, n is odd, there are an odd number of squares.
the graph is bipartite,
it has no cycle of odd length, i.e. it has no Hamilton circuit. Hence, there cannot be a knight’s circuit .

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.