
Re: Continous path on square grid
Posted:
Feb 6, 2013 1:04 PM


clive tooth wrote: > > On Feb 6, 11:36 am, Frederick Williams <freddywilli...@btinternet.com> > wrote: > > > That's neat. What algorithm did you use to find the paths? The answer > > may be long and complicated, and if so I'll not press you for it; but if > > it's short and simple I wouldn't mind knowing. > > Thanks. As to the algorithm... > > The algorithm effectively has two parameters: > > n = the number of spots along the side of the square. In our case 5. > m = the maximum number of moves to make. In our case 8. > > By the way, when looking for P(5,8) the program never found a solution > in less than 8 moves. > > The program deals with points and lines. > > Each point is defined by a triple of integers: (x,y,z). > > # An object of this class represents the point (x/z, y/z). > # z must not be negative. > # If any of x, y, z are nonzero then gcd(x, y, z) must be 1. > # If z = 0 the point is at infinity. > # The point (0, 0, 0) lies on every line. > > Each line is defined by a triple of integers: [a,b,c]. > > # An object of this class represents the line a*x + b*y + c = 0. > # c must not be negative. > # If any of a, b, c are nonzero then gcd(a, b, c) must be 1. > # If a = 0 and b = 0 then c must be 0 or 1. > # The line [0, 0, 1] is the line at infinity. > # Every point at infinity lies on this line. > # No finite point lies on this line. > # The line [0, 0, 0] passes through every point. > > The point (x,y,z) lies on the line [a,b,c] iff a*x + b*y + c*z = 0. > > With these definitions the code for computing the intersection of two > lines or the join of two points is identical: > > public static Point Intersection(Line l1, Line l2) > { > int x = l1.b*l2.c  l2.b*l1.c; > int y = l2.a*l1.c  l1.a*l2.c; > int z = l1.a*l2.b  l2.a*l1.b; > > if (z < 0  (z == 0 && x < 0)  (z == 0 && x == 0 && y < 0)) > { > x = x; > y = y; > z = z; > } > int gcd = U.gcd(U.gcd(Math.Abs(x), Math.Abs(y)), z); > > return gcd == 0? new Point(): new Point(x/gcd, y/gcd, z/gcd); > } // Intersection > > public static Line Join(Point p1, Point p2) > { > int a = p1.y*p2.z  p2.y*p1.z; > int b = p2.x*p1.z  p1.x*p2.z; > int c = p1.x*p2.y  p2.x*p1.y; > > if (c < 0  (c == 0 && a < 0)  (c == 0 && a == 0 && b < 0)) > { > a = a; > b = b; > c = c; > } > int gcd = U.gcd(U.gcd(Math.Abs(a), Math.Abs(b)), c); > > return gcd == 0? new Line(): new Line(a/gcd, b/gcd, c/gcd); > } // Join > > So, our entire universe of points and lines is defined in terms of > integers. And all questions about points and lines can be answered by > comparing integers. > > The program uses a traditional backtracking approach, but before the > search starts the program computes a number of data structures. > > A) The program computes all the lines defined by the 25 spots. There > are 140 such lines. > > B) The program computes all the (finite) intersections of those 140 > lines. There are 3,861 such points (including the 25 spots). > > C) For each of the 3,861 points the program computes a list of the > lines through that point. > > D) For each of the 140 lines the program computes a list of the points > on that line. The program sorts each such list into sequential order > along the line. [Essentially, sorting the points by their x/z value > (or by y/z if the line is parallel to the yaxis) although no > divisions are required in the comparison process.] > > E) Using the structures that are now available, for each of the 3,861 > points the program now computes a list of allowable moves from that > point. An allowable move being along a line through the point and > including at least TWO spots [not counting the starting point, if it > happens to be a spot, but counting the finishing point, if it happens > to be a spot]. The data stored for the move is a reference to the > finishing point and a list of the spots crossed. > > F) The program finally finds, for each of the 3,861 points, the 7 > points which are the rotations and reflections of that point. This > helps in discarding duplicate solutions during the search. > > G) The program now does the usual depthfirst search of the tree of > possible moves, being careful to avoid moves which include an already > traversed spot. > > The program never considers a move which crosses fewer than two spots. > Whilst a line segment which includes NO spots is, perhaps, unlikely, a > segment which crosses just one spot is entirely possible and the > program may certainly have missed some solutions because of this. > Originally I did include such onespot moves but the program ran very > slowly, so I changed it. Currently the program takes about 17 minutes > to find the 118 5x5 solutions. [I have just noticed an error in the > program which probably causes it to miss certain solutions. I will > look into this.] > > I have tried the 6x6 puzzle but the program has never found a single > solution. However, looking at the 5x5 solutions it is clear that some > of them, > http://www.flickr.com/photos/lhc_logs/8449496846/in/set72157632699998440 > for example, could easily be extended to a P(6,10). > > I hope this gives you some feeling for how the search algorithm works.
Yes it does, thank you. Netiquette probably required me to snip a lot of your reply before adding mine, but it's such a clear description I didn't like to.
 When a true genius appears in the world, you may know him by this sign, that the dunces are all in confederacy against him. Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

