new puzzle challenge

04022015, 10:08 PM
Post: #21




RE: new puzzle challenge
(04022015 08:58 PM)RayAtHP Wrote: Don, maybe you should reconsider your initial request ... Oh, I didn't really expect a oneline RPL solution. But I've posted several puzzle challenges over the years in which the very clever RPL people posted very short RPL solutions to what I thought would be rather complex problems, and I am always kind of in awe of those people and their programs. But I am not awed quite enough to want to learn RPL myself! 

04022015, 10:53 PM
Post: #22




RE: new puzzle challenge
(04012015 12:25 PM)Claudio L. Wrote: Back to the drawing board. To speed up the program, it seems is optimum (Paul made a good call there) to choose the corners as the independent variables. This makes the first 6 equations to try also the shortest (3 elements), fastest, and completely decoupled, only dependent on the 6 known variables. This allows for quickly discarding a lot of cases. The 7th variable needs to be in the inner hexagon, but not the center (choosing the center results in coupled equations, so you can't solve all variables one by one without working out the algebra to decouple the equations first). I'll see if I can rework the RPL code to work with this new numbering scheme and will report on the speed improvement. 

04022015, 11:11 PM
Post: #23




RE: new puzzle challenge
Early pruning of the search is probably also advisable, I suspect it doesn't save a lot of searching but every bit helps.
The search space can be reduced by forcing the first corner chosen to be the smallest corner and not producing the six rotations for each solution. The first corner can then only range from 1 through 14 and the other corners must be larger.  Pauli 

04032015, 11:31 AM
Post: #24




RE: new puzzle challenge
(04022015 10:53 PM)Claudio L. Wrote: I'll see if I can rework the RPL code to work with this new numbering scheme and will report on the speed improvement. I think I found a way to simplify the algorithm to solve the outer ring. If we number the values consecutively n(i), turns out that for any two values in the outer ring: n(i)+n(i1)>=19 Which limits a lot the set of numbers we can pick from. Also from the equations: n(i+1)=38n(i)n(i1) So the algorithm can work like this: Put a number on the stack from 1 to 19 (in a FOR loop), as the first number, and call the recursive routine. A recursive routine will simply do: Add a number on the stack from 19n(i) to 19 in a FOR loop. Check that the new number is not taken (as in not already present in the stack). If not taken, add a second number n(i+1)=38n(i)n(i1) Check that this new number is not taken. If not taken, recurse, otherwise drop the last two values and continue to loop. This routine also has to check if we already did the 6 corners. In such case, needs to do the special case to connect the last corner with the first, and if it works, we have a solution to the outer ring. The inner ring is easy: there's one independent variable and can only take 7 possible numbers, so it's easy to check in a separate routine, once the outer ring is solved. With this algorithm, there's very little math, most of the time is spent checking that a number in level 1 of the stack is not present in the stack already, which should be fast I think. I'll see if I can put this together during the weekend. Feel free to beat me to it! 

04032015, 07:04 PM
Post: #25




RE: new puzzle challenge
Good news. The outer ring solution only took about 40 minutes on the 50g to complete the checks for one initial value, and determine all solutions for the other 5 independent variables.
When I add the inner ring checks (which only need to be checked for the solutions found in the outer ring, which were 160 for the initial value of 3, so they are not that many), I estimate it will be about 1 hr per initial value worst case. To cover all 19 initial values, the total running time is now down to 19 hrs to obtain all solutions. This is now into "tolerable" territory. newRPL should be able to do this with a speedup of about 200x (per these results), which would put it around 6 minutes. I'll report back with the source code once I complete the inner ring checks. 

04032015, 07:36 PM
Post: #26




RE: new puzzle challenge
(04032015 07:04 PM)Claudio L. Wrote: Good news. The outer ring solution only took about 40 minutes on the 50g to complete the checks for one initial value, and determine all solutions for the other 5 independent variables. Hope you have a nice supply of batteries handy.... wow, 19 hours of continuous 50g runtime. Now that's a serious amount of calculating. Did you peek at the author's paper to know the answer you should be getting? Bob Prosperi 

04032015, 08:09 PM
Post: #27




RE: new puzzle challenge
(04032015 07:36 PM)rprosperi Wrote:(04032015 07:04 PM)Claudio L. Wrote: Good news. The outer ring solution only took about 40 minutes on the 50g to complete the checks for one initial value, and determine all solutions for the other 5 independent variables. Just plug it into a USB port and you can run without batteries :) Graph 3D  QPI  SolveSys 

04032015, 08:43 PM
Post: #28




RE: new puzzle challenge
Perhaps you are aware, perhaps not, that many other members or nonmembers are reading this thread with great pleasure, seeing your efforts and results, without being able to participate in these kind of mathematics games, but admiring it. I'm one of these quiet readers and want to congratulate any of you in advance for finding all the nth order solution eggs.
Happy Easter! Bernhard That's one small step for a man  one giant leap for mankind. 

04042015, 12:48 PM
(This post was last modified: 04052015 02:37 AM by Claudio L..)
Post: #29




RE: new puzzle challenge
(04032015 08:43 PM)PANAMATIK Wrote: Perhaps you are aware, perhaps not, that many other members or nonmembers are reading this thread with great pleasure, seeing your efforts and results, without being able to participate in these kind of mathematics games, but admiring it. I'm one of these quiet readers and want to congratulate any of you in advance for finding all the nth order solution eggs. Thanks for the encouragement. You shall be rewarded with the full source code: For proper code optimization, this is the variable numbering (quite strange for humans, but optimized for the machine: Code:
A trough L are the outer ring, where we can write the first 6 equations with only 3 letters each, and completely decoupled from the rest. This allows to solve for the first 6 variables out of seven. As explained in my previous post, the code walks the perimeter setting a number for A, then trying all values of B knowing A+B>=19, and computing C per the corresponding equation C=38(A+B). This is done by this code: Code:
M is the 7th independent variable. Once the outer ring is known, trying all possible values for M allows to calculate all letters N through R in the "inner ring" by using the 4term equations. N=38(B+M+F) O=38(D+N+H) ... The inner ring code expects to find already on the stack the 12 variables A through L with L on level 1. The inner ring is solved by this code: Code:
Finally, we need to do the proper checks with the center value (last position, S). All we have to do is find the only number that was not taken in the stack and check all 3 equations with 5terms. This is done here: Code:
And to wrap it all up, the code above needs a couple of things to run properly:
This is done here: Code:
For the short of patience, partial tests can be ran, if you put a partial list of numbers (must be a valid partial solution, of course), and run the DOLOOP test to see if any solutions are found. Just make sure 'SOLUTIONS' contains an empty list and that there's nothing else in the stack but your partial solution. The partial solution has to contain 1, 3, 5... elements. In other words, think of the corners as the independent variables, then to give 2 independent variables you must also provide the intermediate value between them (A, B and C). This is tested and finds all 12 solutions, but of course I tested it on a PC with newRPL, don't have the patience to wait 19 hours, but if somebody does, please measure time and report here. Happy coding. PS: Still not a oneline RPL solution... but faster than my first try at 97 days! EDIT: Forgot to mention, if you don't wait to wait 19 hours, and don't care about the different rotations, you can get a nice solution by doing: Code: { } 'SOLUTIONS' STO 3 DOLOOP This will leave SOLUTIONS with all solutions that have a 3 in the first variable: exactly 2 solutions, one mirror of the other, and only for about 1 hr of your time. 

04042015, 12:53 PM
Post: #30




RE: new puzzle challenge  
04042015, 03:06 PM
Post: #31




RE: new puzzle challenge
(04042015 12:48 PM)Claudio L. Wrote: PS: Still not a oneline RPL solution... but faster than my first try at 97 days! Claudio, that is great work, thank you. Can you clarify, is there only one real solution, the others being reflections or rotations of the one? The puzzlemaker claimed several solutions, but I have a feeling that they are all reflections/rotations of the original. Don 

04042015, 06:44 PM
Post: #32




RE: new puzzle challenge
(04042015 03:06 PM)Don Shepherd Wrote: Claudio, that is great work, thank you. There's only one "true" solution. The rest are rotations and mirror images. There's all kinds of interesting observations on this problem. For example, I replaced the routine CHKINNER to always store the solution instead of checking the inner ring, to obtain all the outer ring solutions: Code:
Turns out that starting with the number 3 as the first variable, there's 160 solutions of the outer ring (actually 80 if you remove the mirrors). Among these sets, only 2 (one and its mirror) will pass the inner ring check. Starting with number 4, there's 184 solutions to the outer ring (actually 92), but none of them will pass the inner ring check. 

04042015, 07:02 PM
Post: #33




RE: new puzzle challenge
(04022015 11:11 PM)Paul Dale Wrote: Early pruning of the search is probably also advisable, I suspect it doesn't save a lot of searching but every bit helps. If we are discarding, then the count would start from 3, as 1 and 2 are easy to discard as follows: If a vertex contains 1, the 2 adjacent variables can only be 18 and 19 (left and right, or viceversa doesn't matter), because n(i)+n(i1)>=19. The following corners would have to be: 38181 = 19 38191 = 18 But both numbers are already being used, so we can conclude the number 1 cannot appear on any vertex. Similar deal with number 2, the adjacent can only be 17, 18 and 19, and the following corners would be 17,18 or 19, it's easy to see that we have 3 valid numbers to fill in 4 spaces, so there's no solution, concluding that 2 cannot be on any vertex of the solution. There might be other logical rules like these ones to discard more options that could help a human solve the problem by hand. 

04042015, 11:43 PM
Post: #34




RE: new puzzle challenge
(04042015 07:02 PM)Claudio L. Wrote: If we are discarding, then the count would start from 3, as 1 and 2 are easy to discard as follows: I thought there was a way to exclude these two but didn't think it through enough. Getting rid of reflections is easy by forcing the order of two adjacent edge middles. E.g. B>D. This would give an early pruning of the search space.  Pauli 

04052015, 02:29 AM
Post: #35




RE: new puzzle challenge
(04042015 11:43 PM)Paul Dale Wrote: Getting rid of reflections is easy by forcing the order of two adjacent edge middles. E.g. B>D. This would give an early pruning of the search space. I think it eliminates some reflections but may not work all the time, because depending on your choice of variables you are using a different axis of symmetry. For example, the 2 solutions with initial variable A=3 are: Code:
In this case, B>L would be perhaps a better choice since it is mirroring about the axis that passes through the initial value and the center of the hexagon. But this would only eliminate a solution after we computed L, which means we already have the outer ring completely solved, so not much of a speedup in this algorithm. Also, it wouldn't eliminate the reflections of the rotated solutions, since the axis of symmetry is different. Perhaps if the algorithm tried to advance in both directions at once it would be much quicker to eliminate the reflections (but what a mess trying to find values with PICK for the equations!). In any case, I'm inclined to leave those optimizations "as an exercise for the reader". 

04052015, 03:24 AM
Post: #36




RE: new puzzle challenge
You are correct, it has to be B and L. You could force C to be smallest in which case it would be B and D but this complicates.
Thinking about it more, H and F would also work since they are on the same axis of symmetry. They'd likely be better than B and L since the pruning would occur earlier.  Pauli 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)