I read it many years ago, it suddenly came into my mind, while I was working on Rainbowduino. Rainbowduino has a 8x8 RGB display matrix, I think is suitable to display Knight's tour solution.
Knight's tour (or Journey of Knight) is a mathematical problem. Is common exists in computer science study. The problem can be solved by a computer program.
Given a 8x8 chessboard, the knight is place on arbitrary point, find a route for the knight to travel all the 64 point without repeat according the the chess rule. That means, the knight will only visit each point once.
Journey of the knight is like Rubik cube for me, I don't know how to prove the solution exist. There is ready solution on the internet, just write the provided algorithm into codes.
The Warnsdorff's algorithm should be easy to understand. For any given point, there are maximum of 8 routes to choose. Choose the one with least possible routes.
Take the example from the Wikipedia. The start point has 6 routes to choose, each route has 3, 7, 7, 7, 5, 2 possible route. Choose the least possible route, which is 2.
By following the algorithm, I write a program which print out the following result:
14 27 16 51 12 29 34 63
17 52 13 28 55 62 11 30
26 15 54 59 50 33 64 35
53 18 25 56 61 58 31 10
24 1 60 49 32 45 36 47
19 40 21 44 57 48 9 6
2 23 42 39 4 7 46 37
41 20 3 22 43 38 5 8
New knowledge for me, but i think my development never use it... haha..
ReplyDeletemost software development don't need it, just for practice.
ReplyDelete