new puzzle challenge

[Claudio L.]

(04-02-2015 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(i-1)>=19

Which limits a lot the set of numbers we can pick from.

Also from the equations:

n(i+1)=38-n(i)-n(i-1)

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 19-n(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)=38-n(i)-n(i-1)
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!