Write a recursive function named knightsTour that uses backtracking to try to find a "Knight's tour" path on a chess board of a given size.
A Knight's tour is a path on an empty chess board traveled by a knight piece that touches each square on the board exactly once.
A knight chess piece moves in an "L" pattern where its row/col change by 2/1 or 1/2 in either direction, as shown in the figure below.
(This problem uses the Stanford "SPL" collections.)
You will be passed two parameters: a reference to a Grid of ints representing the chess board, and a starting location row/column.
Your code should explore whether a knight's tour can be made starting at that location.
If you find such a tour, print the board to show it. If not, do not print any output.
The grid passed to your function will be square (it will have the same number of rows as columns) and will initially be filled with 0s.
You should try to fill it with integers from 1 to N inclusive representing the order in which the knight should visit the squares of the board, starting from the indicated location, where N is the number of rows times columns.
To help you solve this problem, we provide you several pieces of starter code.
Since grids often refer to individual squares with a row and column, we provide a structure type to represent a single row/column location on the board.
We also provide you with a function to print a board, and a function to generate all neighboring moves from a given location.
These can help simplify your solution to this problem.
// starter code (assume that all of this is provided)
struct Location { // represents one square on the board
int row;
int col;
};
void printBoard(Grid& board); // print a board in the format shown below
Vector getMoves(Location loc); // all moves a knight can make from this location
The getMoves function returns all board squares that are 2/1 rows/columns away from the location you pass it.
It does not exclude squares that are out of bounds on the board.
For example, if your current row/col location is {1,1}, then getMoves returns a vector containing [{-1,0}, {0,-1}, {0,2}, {2,-1}, {2,3}, {3,0}, {3,1}, {3,2}].
For example, if we call your function as shown below at left on a 5x5 board starting from (2, 2):
Grid<int> board(5, 5);
Location start {2, 2};
knightsTour(board, start);
One acceptable result would be to output the following knight's tour along with modifying the grid to store these integer values in its 25 squares:
21 2 7 12 23
8 13 22 17 6
3 20 1 24 11
14 9 18 5 16
19 4 15 10 25
If there are multiple valid knight's tours of the given board, you may print any of them.
Regardless of which tour you print, your code must stop after finding/print a single solution; you should not find or print all possible solutions.
Your function must return when it is complete; it is not allowed to stop your function by calling exit or other such trickery.
Efficiency: While your code is not required to have any particular Big-Oh, you should avoid code that is extremely inefficient or repeatedly re-explores the same path multiple times.
Pass data structures by reference to avoid making copies.
Constraints:
Do not declare any global variables.
You may use loops in solving this problem if you like, but your overall solution must use recursive backtracking.
You may define helper functions if you like.
