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