|
|
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 non-zero 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 non-zero 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 y-axis) 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 depth-first 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 one-spot 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/set-72157632699998440
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
|
|
