How to Solve the Knight's Tour Problem
Let’s work through the problem of the knight’s tour problem.
A knight’s tour is a sequence of moves by a knight on a chessboard such that all squares are visited once.
Given N, write a function to return the number of knight’s tours on an N by N chessboard.
The brute force solution is here to try every possible permutation of moves and see if they’re valid. That would be pretty much computationally infeasible, since we have N * N possible spots. That would be N^2!
We can improve the performance on this using backtracking, similar to the N queens problem (#38) or the flight itinerary problem (#41). The basic idea is this:
- For every possible square, initialize a knight there, and then:
- Try every valid move from that square.
- Once we’ve hit every single square, we can add to our count.
We’ll represent the tour as just a sequence of tuples
(r, c). To speed things up and to avoid having to look at the whole tour to check whether a space has been used before, we can create an N by N board to mark whether we’ve seen it already.
def is_valid_move(board, move, n):
This takes O(N * N) space and potentially O(8^(N^2)) time, since at each step we have potentially 8 moves to check, and we have to do this for each square.
Are you interviewing for programming jobs, or do you just enjoy fun programming questions? Check out our newsletter, Daily Coding Problem, to get a question in your inbox every day.
Ace your programming interview
Get a coding problem every day in your inbox!