new puzzle challenge
|
03-30-2015, 02:30 AM
Post: #1
|
|||
|
|||
new puzzle challenge
I was browsing at my local Barnes & Noble Bookstore today and came across this number puzzle that struck my fancy:
38 puzzle It consists of a little wooden frame containing 19 removable hexagonal pieces, numbered 1 through 19. There are a total of 15 rows in all directions, each made up of 3, 4, or 5 pieces (5 parallel rows starting with 9, 11, 18; 5 parallel rows starting with 9, 14, 15; and 5 parallel rows starting with 18, 17, 3). To goal is to have the sum of each of the 15 rows be 38. The picture shows one solution, but the website of the puzzle maker says there is more than one solution. I'd like to find all possible solutions. A brute-force approach would require examining 19! possible configurations, a very large number (almost as many configurations as an Enigma machine). I'm sure Alan Turing could figure this out if he were alive today, but he is not. Who among us will pick up the gauntlet? I expect a one line RPL solution, as usual! I would love to see a BASIC solution. |
|||
03-30-2015, 03:19 AM
Post: #2
|
|||
|
|||
RE: new puzzle challenge
Just off the top of my head, there are five rotations of that position, plus the reflections and rotations.
The problem isn't as difficult as 19! There are a lot of short cuts a search can make. My initial thought is only ten locations need to be searched, the rest are determined by these ten numbers without choice. Pauli |
|||
03-30-2015, 04:00 AM
Post: #3
|
|||
|
|||
RE: new puzzle challenge
Only seven positions need to be searched over with some pruning.
The solution appears to be unique subject to reflections and rotations. - Pauli Code: #include <stdio.h> |
|||
03-30-2015, 04:35 AM
Post: #4
|
|||
|
|||
RE: new puzzle challenge
I wrote a recursive Python program to do a search with backtracking, and it finds 12 solutions, but only one is unique and the remainder are rotations and/or reflections. It would be much faster if written in C. It shouldn't be too difficult to translate the Python program to RPL, though it will take much longer to run on a 50g than the Python program takes on an x86.
I haven't figured out how to restrict the search space optimally to avoid rotations and reflections, but you can restrict it slightly. A row of three pieces must have at least one piece that is 11 or less. If you start from a row along one edge, and from one end of that edge, you only have to handle cases where that end piece is 1 through 11, or the end piece is greater than 11 and the middle piece of the row is 1 though 11. Unfortunately this doesn't actually speed up the program much if backtracking is used. On a 4.0 GHz AMD FX-8350 CPU, running Fedora 21 64-bit and Python 2.7.8, it finds the seven reported solutions in at elapsed times of 4.6, 8.0, 179.9, 200.8, 259.7, 265.2, and 917.9 seconds. Code:
|
|||
03-30-2015, 04:50 AM
Post: #5
|
|||
|
|||
RE: new puzzle challenge
(03-30-2015 04:35 AM)brouhaha Wrote: I wrote a recursive Python program to do a search with backtracking, and it finds 12 solutions, but only one is unique and the remainder are rotations and/or reflections. Detecting the rotations and reflections is easy enough. Only accept a case where the top left corner is the lowest value of any corner and the value to its right is smaller than the value below and to the left. Using my nomenclature: Code: a b c a = min(a, c, h, l, q, s) and b < d. These restrictions should be encoded into the search algorithm directly to increase pruning possibilities. Quote:It would be much faster if written in C. It is My program executes completely in under 0.01 seconds on a slower machine. Adding in the reflection and rotation constrains, reduces this by a factor of five. Pauli Code: #include <stdio.h> |
|||
03-30-2015, 05:45 AM
Post: #6
|
|||
|
|||
RE: new puzzle challenge
Candidate thread for "Not remotely HP Calculators" ?
|
|||
03-30-2015, 11:44 AM
Post: #7
|
|||
|
|||
RE: new puzzle challenge | |||
03-30-2015, 02:34 PM
Post: #8
|
|||
|
|||
RE: new puzzle challenge
(03-30-2015 03:19 AM)Paul Dale Wrote: Just off the top of my head, there are five rotations of that position, plus the reflections and rotations. There's 19 unknowns, and unless I'm mistaken we can write 15 linearly independent equations, so there's only 4 independent variables, not 10 I think. The first one can take 19 values, the second one only 18 possible values, the third one 17, and the last one 16. The maximum number of solutions to try by brute force then would be 19*18*17*16 = 93024, I'd say its manageable. Most of those solutions will end with some of the dependent variables with values outside the range of the problem. Sorting the equations from the simplest (w/3 elements) to the more complex would allow for faster testing, or even a matrix multiplication could yield all dependent variables at once, then the code only has to test if they all fall in the 1-19 range to discard the solution. Brute force doesn't look so bad, I think it's doable. |
|||
03-30-2015, 04:40 PM
Post: #9
|
|||
|
|||
RE: new puzzle challenge
I am especially interested in the number 5. In the solution in the picture, 5 is the only number that is common to every row with 5 members; it is not part of any row with 3 or 4 members.
I am wondering if that is true for other solutions as well. |
|||
03-30-2015, 04:58 PM
Post: #10
|
|||
|
|||
RE: new puzzle challenge
(03-30-2015 02:34 PM)Claudio L. Wrote: There's 19 unknowns, and unless I'm mistaken we can write 15 linearly independent equations, so there's only 4 independent variables, not 10 I think. I spoke too soon. Writing the equations in matrix form and row-reducing the resulting matrix, 3 of the 15 are dependent equations, so there's a total of 12 independent equations with 7 independent variables. The row-reduced form shows something interesting: variables 1-9, 12, 13 and 17 are dependent on 10,11,14,15,16,18,19. In a graph, this looks interesting as the independent variables also form a smaller hexagon (variables numbered as in the diagram below): Code:
|
|||
03-30-2015, 10:11 PM
Post: #11
|
|||
|
|||
RE: new puzzle challenge
(03-30-2015 04:58 PM)Claudio L. Wrote: The row-reduced form shows something interesting: variables 1-9, 12, 13 and 17 are dependent on 10,11,14,15,16,18,19. This isn't the only set of seven dependent variables that works. I walked around the edge of the hexagon first and got six dependent variables there. The final seventh was internal. Still, this would be well within the ability of the higher end calculators. - Pauli |
|||
03-31-2015, 12:40 PM
Post: #12
|
|||
|
|||
RE: new puzzle challenge
(03-30-2015 10:11 PM)Paul Dale Wrote:(03-30-2015 04:58 PM)Claudio L. Wrote: The row-reduced form shows something interesting: variables 1-9, 12, 13 and 17 are dependent on 10,11,14,15,16,18,19. Right, I never meant to say this was the only form, just wanted to point the peculiar shape (small hexagon) that resulted in row-reducing the equations when you number the variables like I did, I thought it was a cool shape that came out of nowhere. |
|||
03-31-2015, 05:31 PM
Post: #13
|
|||
|
|||
RE: new puzzle challenge
I did a brute force recursive RPL implementation on a 50g (source code will be published when I manage to get it out of the calc).
I think it works well but wasn't able to get any solutions because a level 6 round takes about 6 seconds to check 13*14 = 182 possible outcomes. This needs to be executed 19*18*17*16*15 = 1395360 times, for a total of about 8 million seconds, or 2326 hours, or 97 days. Obviously my implementation needs some serious improvement before it can be considered even remotely usable. |
|||
03-31-2015, 06:00 PM
(This post was last modified: 03-31-2015 07:49 PM by Gilles.)
Post: #14
|
|||
|
|||
RE: new puzzle challenge | |||
03-31-2015, 10:03 PM
Post: #15
|
|||
|
|||
RE: new puzzle challenge
(03-31-2015 06:00 PM)Gilles Wrote:This is genius! Adding this equation into the mix, we have only 6 independent variables to take care of. This reduces the brute force effort by a factor of 13.(03-30-2015 02:34 PM)Claudio L. Wrote: There's 19 unknowns, and unless I'm mistaken we can write 15 linearly independent equations, ... That's only 7 days running non-stop. Big improvement. |
|||
04-01-2015, 12:25 PM
Post: #16
|
|||
|
|||
RE: new puzzle challenge
(03-31-2015 10:03 PM)Claudio L. Wrote:Wait... not so fast.(03-31-2015 06:00 PM)Gilles Wrote: 16 linearly equations because of :This is genius! Adding this equation into the mix, we have only 6 independent variables to take care of. This reduces the brute force effort by a factor of 13. Adding all 15 equations, you get each letter 3 times exactly, so: 3*(A+B+....+R+S)=38*15 3*(A+B+....+R+S)=38*3*5 (A+B+....+R+S)=38*5=190 So that extra equation is not linearly independent. We still have 7 variables. Back to the drawing board. |
|||
04-01-2015, 07:22 PM
(This post was last modified: 04-01-2015 07:23 PM by Gilles.)
Post: #17
|
|||
|
|||
RE: new puzzle challenge
(04-01-2015 12:25 PM)Claudio L. Wrote: Wait... not so fast.Yes. You're right... A+B+C=38 D+E+F=38 etc.. (A+B+C)+(D+E+F)+.....= 5x38 I wrote a rpl program that explores 160.392.960 cases 'only' and use the solve command. But too slow to be usable even with emulator |
|||
04-02-2015, 07:32 PM
Post: #18
|
|||
|
|||
RE: new puzzle challenge
(03-30-2015 02:30 AM)Don Shepherd Wrote: I was browsing at my local Barnes & Noble Bookstore today and came across this number puzzle that struck my fancy: Meng did a lot of work here, partially a spoiler alarm for these who strive for Easter weekend solution search activities! Meng Best regards -Ray |
|||
04-02-2015, 08:30 PM
Post: #19
|
|||
|
|||
RE: new puzzle challenge
(04-02-2015 07:32 PM)RayAtHP Wrote: Meng did a lot of work here, partially a spoiler alarm for these who strive for Easter weekend solution search activities! Ray, thanks a lot for the link to that paper. I have downloaded it and will read it this weekend (I didn't say "understand" it, however!). So Meng proved that there is only one solution, ignoring reflections of the original. The puzzle-maker claimed that there are more than one solution, but the puzzle-maker probably doesn't understand reflections. thanks again Don |
|||
04-02-2015, 08:58 PM
Post: #20
|
|||
|
|||
RE: new puzzle challenge
Don, maybe you should reconsider your initial request ...
Quote:I expect a one line RPL solution, as usual! I would love to see a BASIC solution. A quick scan of Mings transcript could lead to massive exhaustion under RPL programmers if they try to comply to your request. Best regards -Ray |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 3 Guest(s)