Laurent_R
Veteran
/ Moderator
Nov 22, 2013, 4:25 PM
Views: 5872

Re: [zing] Conversion of tree to graph to resolve shortcomings



Hi, this reminds me of another problem I solved a few months ago. This was a game with stones on a 4x4 board. Stones had a white and a black side. So you could have 2^16 = 65536 initial positions. You had 46 authorized moves, each turning around 3 to 4 stones (turning around a full line, a full column, a diagonal or a L pattern). The aim is to have all the stones on their white side. Any game can be solved in 5 moves, so that each initial solution can lead to 46 ^5 games (206 millions), but, given the number of initial positions, that leads to a huge amount of possible games, about 1.35 x 10^13 (13 thousand billion) possibilities. A quick test showed that checking all the possible paths would require more than 225 days on my computer. But at the same time, any move starts from one of 65k position and leads to 65k positions. So my idea was to start from the winning position (step 0), find the 46 positions that can lead to that (step 1) and record them in a hash as winning in one move, examine all the positions leading to one of those 46 positions (step 2) and removing from the problem any position already seen (already in the hash), and so on. Overall, I had to check only 2.34 million moves and that took me about 1.5 seconds. That took 11 lines of code. Your problem may look very different, but I am pretty much convinced that the very same approach can lead to an easy solution. If you think about the game mentioned above, my problem was really to find the shortest path between the winning position and any original position. And that is very very similar to your problem. My approach made it possible to eliminate very early any solution that could be determined to be suboptimal, and I am quite sure the same approach would work in your case. So I would load your data in an appropriate date structure, start from Q, look for all precedessors, mark up those already found by storing them in a hash, look for the predecessors of those predecessors, unless they have been already been visited, etc. until all lines have been marked as solved. It is quite late here now, but I am willing to give you the code tomorrow (hopefully, I will not forget) if you confirm that this is really what you are looking for.
