Feb
22
Chess Pathfinder (Knight’s Tour) 1.2
It seems I’ve made some significant progress with the algorithm, just not enough yet.
After some discussion in the comments of my last entry, I decided that my next attempt should be to add a check after every move to make sure that I hadn’t boxed any positions in, making them unreachable.
I almost dismissed this idea because I originally thought that it would involve checking every position on the board after every move, but it’s only necessary to check the eight positions that can be moved to from the current one.
The end result was this: on a 7×7 board, I can now compute the same path in 614 iterations as opposed to the 4430 required before. This represents an efficiency increase of slightly better than 720% (although that admittedly doesn’t account for the overhead added to each iteration by the check itself). An 8×8 board still takes an unknown amount of time however.
The thing that this check doesn’t take into account is the fact that there could be a cluster of positions that can reach each other, but can’t be reached from outside; as opposed to a single, isolated position. I had thought of this before I implemented the check, but hoped that it wouldn’t be a significant problem. It now seems that it may be.
It would seem that the next step is to find a way to look for clusters of isolated positions, although I haven’t yet quite decided how to go about that from a programming standpoint. Whatever I do, I’ll have to make sure that the checking process itself is as efficient as possible.
More details as I make more progress. As usual, here’s the source and documentation.
EDIT – 13 Feb 2011:
The source and documentation for this version were lost. I was able to recover the source (without doxygen comments) from Google’s cache, but I had to re-write much of the documentation. The code is now hosted at GitHub.
Subscribe to RSS Feed
Follow us on Twitter
Our Mailing Lists
Visit Kwartzlab TV
With the new algorithm, I’ve been able to calculate a path for an 8×8 board overnight. Here’s the output:
1 52 47 56 43 58 61 34
46 55 50 31 48 33 42 59
51 2 53 44 57 60 35 62
54 45 30 49 32 37 16 41
29 26 3 38 17 40 63 36
20 23 18 27 10 13 6 15
25 28 21 4 39 8 11 64
22 19 24 9 12 5 14 7
Calculation completed after -1040148249 iterations.
It seems that there was an overflow in the iteration counter.
If you get tired of the Knight’s Tour, perhaps you can tackle the Bin Packing Problem. It’s a real-world problem, of great interest to carpenters.
Suppose wood trim is sold in 10′ lengths. Given a list of required lengths of cut pieces (all less than 10′, obviously), compute a cut plan that yields all the required pieces from the smallest number of 10′ lengths.
If you can find a really efficient solution for this, there may be a Fields Medal with your name on it. The problem is NP-hard.
Most real-world implementations use heuristics, yielding good, but not necessarily optimal solutions.
Android game is most of the fevoriovte game. There are many outdoor and indoor games.I do not like all the game.It give me great joy. There is no Unmixed good on earth.It is my favourite things to game.