Interestingly the run time highly fluctuates, depending on the ordering of the possible moves. In general a gigabyte of ram, used to remember the known boards, should be enough to allow for a solution to be found. Not doing so means that my computer is still working on a solution since 24 hours (however it is using almost no ram). Remembering the boards that we have already seen (and not rechecking them unnecessarily) means that a solution is found in a very reasonable time (usually a few seconds). With this particular algorithm it is no different. There is often a tradeoff with algorithms when it comes to memory usage and run time. You can find more details on this in the comment header of the program below. The really interesting part is that the algorithm is optimized by reverting the search direction. Checking of possible moves and applying them can be done by using simple bit operations. However there are some bits that are not valid and never used, i.e. The first 49 bits (7 x 7) of the long represent the board. The idea is as following: Since there exists 33 slots on the board, it can not be represented by using an integer (32 bits), but we can use a long (64 bits). The implementation is highly optimized and uses bit operators to efficiently find a solution. English Peg Solitaire Solution Implementation
0 kommentar(er)
