Taking a 4 by 5 grid, How many possible Knight's tours are there starting in the upper left corner and ending in the lower right? (Reflections and rotations don't count)
(A Knight's move is as in chess, an L shaped move, 2 squares in one direction and 1 square in the other direction.)
A Knight's tour is visiting every square once and only once (and the square you start on is considered "visited" for these problems)
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
The lettered route:
A B A B A
A B A B A
B A B A B
B A B A B
If a path were constructed that switched from A to B more than once, it would need to use either 8 or 13 as a cross over point for two reasons: First, there are only 2 cross over points from A to B that don't require 8 or 13 (12-9 and 14-7) and since 1 is an A and 10 is a B, you would need to cross over an odd number of times. Secondly, you would need to stop or start on 8 and 13 as part of the tour. In other words, you can't use 11-8-15 or 10-13-6 as part of your path because this would leave 5 or 16 unvisitable. This means that you can go from an A tile to a B tile or from a B tile to an A tile at most 4 times if there is any chance of a knight's tour to be constructed.
So the four cross overs are: 12-9, 14-7, (11 or 15)-8, (10 or 6)-13. If we wanted to cross over 3 times, and if both of the last two cross overs are used, then this leaves two possibilities; either 12-9 is used or 14-7 is used.
Since 1-8 and 20-13 aren't used, then 1-12 and 9-20 must be used. 12-9 can't be used because then the sequence 1-12-9-20 would follow, and this would lead to a contradiction.
14-7 can't be used as well if the last two crossovers are used because then the path must include (10 or 6)-13-16-7-14-5-8-(11 or 15) and then 4 and 17 will be unvisitable.
Not being able to use either of the first two cross overs results in inability to use 3 cross overs, which is a contradiction. So, only one of the last two cross overs can be used, which means that both 12-9 and 14-7 need to be used.
But if 13-(10 or 6) isn't used, then the chain must contain (11 or 15)-8-5-14. 14-7 must be used because it's a cross over. 1-8 can't be used because 8 is already in the chain, so 1-12-9 must be the beginning of the chain since 12-9 is a crossover. 20-13-16-7 must be used because 1-8 can't be used. This leads to the chain of (11 or 15)-8-5-14-7-16-13-20. Again, 4 is isolated and can't be visited, leading to this situation as a contradiction.
If 13-(10 or 6) was used and (11 or 15)-8 wasn't used, then similar logic could be used because the grid is exactly the same when flipped such that 1 becomes 20, 5 becomes 16 and so on. In this situation 17 is the space that can't be visited.
All four situations where 3 of the 4 cross overs were used result in spaces unable to be visited, which means a knight's tour can't be accomplished with 3 cross overs. Since no more than 4 cross overs can be done, only an odd number of cross overs can happen since you need to start on A and end on B, and you can't cross over 3 times, you must visit all the As then go on to the Bs since you can only cross over once.
This allows the problem to be broken down further.
1 3 5
6 8 10
12 14
17 19
Rearranging this so knights moves are seen easier:
/---8---\
/ / \ \
1 | | 5
| | | |
12-19 17-14
| | | |
| 10 6 |
| \ / |
\---3---/
Through deduction it can be seen there are 7 half-routes:
1 route for 1 to 12:
1 8 5 14 17 6 3 10 12
3 routes for 1 to 10:
1 8 5 14 17 6 3 12 19 10
1 12 19 8 5 14 17 6 3 10
1 12 3 6 17 14 5 8 19 10
1 route for 1 to 8:
1 12 19 10 3 6 17 14 5 8
2 routes for 1 to 6:
1 12 3 10 19 8 5 14 17 6
1 12 19 10 3 14 8 17 6
1 route for 1 to 14:
1 12 19 10 3 6 17 8 5 14
The other set of letters follows the same pattern, so these may be reflected over the horizontal middle of the board. Doing this shows that routes that end in 6 or 10 can match up with flipped-8 (13) and routes that end in flipped-6 (11) or flipped-10 (15) can match up with 8. Also, routes that end in 12 match up with flipped-14 (9) and routes that end in flipped-12 (7) match up with 14.
So this means the routes can be defined as 6-8 + 8-6 + 10-8 + 8-10 + 12-14 + 14-12, where a dash means the number of routs ending in one number times the number of routes ending in the other. This means the asnwer is (2*1)+(1*2)+(3*1)+(1*3)+(1*1)+(1*1) which equals 12. This means there are 12 knight's tours starting from 1 and ending in 20.
im just kidding i stole this solution. HA HA HA ∑
this is easy
