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


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.
 Clive Tooth

