Traditional chessboard consists of an 8-by-8 grid with 64 squares. For the purposes of this activity, only a 4-by-4 grid is considered.
If a knight is placed in the upper left-hand square, is there a sequence of moves that allows the knight to visit every square on the chessboard exactly once and then return in the last move to its starting place? The remainder of this activity sheet will help you answer this question.
1. Decide how to use a graph to model the Knight's Tour problem. Carefully define what your vertices represent adn how you know when two vertices are connected by an edge.
2. Based on your model, restate the Knight's Tour problem.
3. What type of previously encountered problem in this unit is this problem related to?
Traditional chessboard consists of an 8-by-8 grid with 64 squares. For the purposes of this activity, only a 4-by-4 grid is considered.
If a knight is placed in the upper left-hand square, is there a sequence of moves that allows the knight to visit every square on the chessboard exactly once and then return in the last move to its starting place? The remainder of this activity sheet will help you answer this question.
1. Decide how to use a graph to model the Knight's Tour problem. Carefully define what your vertices represent adn how you know when two vertices are connected by an edge.
2. Based on your model, restate the Knight's Tour problem.
3. What type of previously encountered problem in this unit is this problem related to?