Threaded Mode | Linear Mode

Don Shepherd · 03-30-2015, 02:30 AM

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.

Paul Dale · 03-30-2015, 03:19 AM

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

Paul Dale · 03-30-2015, 04:00 AM

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>

/*

     a b c

    d e f g

   h i j k l

    m n o p

     q r s

*/

int main() {

    unsigned char usedbuf[120], *used;

    for (int i=0; i<120; i++)

        usedbuf[i] = 1;

    used = usedbuf + 60;

    for (int i=1; i<20; i++) used[i] = 0;

    for (int a=1; a<20; a++) {

        used[a] = 1;

        for (int b=1; b<20; b++) {

            if (used[b]) continue;

            int c = 38 - a - b;

            if (used[c] || c == b) continue;

            used[b] = used[c] = 1;

            for (int d=1; d<20; d++) {

                if (used[d]) continue;

                int h = 38 - a - d;

                if (used[h] || d == h) continue;

                used[d] = used[h] = 1;

                for (int g=1; g<20; g++) {

                    if (used[g]) continue;

                    int l = 38 - c - g;

                    if (used[l] || l == g) continue;

                    used[l] = used[g] = 1;

                    for (int m=1; m<20; m++) {

                        if (used[m]) continue;

                        int q = 38 - m - h;

                        if (used[q] || m == q) continue;

                        used[m] = used[q] = 1;

                            for (int p=1; p<20; p++) {

                                if (used[p]) continue;

                                int s = 38 - p - l;

                                if (used[s] || p == s) continue;

                                int r = 38 - s - q;

                                if (used[r] || r == s || r == p) continue;

                                used[p] = used[s] = used[r] = 1;

                                for (int e=1; e<20; e++) {

                                    if (used[e]) continue;

                                    int f = 38 - d - e - g;

                                    if (used[f] || e == f) continue;

                                    int i = 38 - b - e - m;

                                    if (used[i] || i == f || i == e) continue;

                                    int k = 38 - b - f - p;

                                    if (used[k] || k == i || k == f || k == e) continue;

                                    used[e] = used[f] = used[i] = used[k] = 1;

                                    int o = 38 - r - k - g;

                                    if (used[o]) goto ex;

                                    int n = 38 - i - d - r;

                                    if (used[n] || n==o) goto ex;

                                    int j = 38 - a - e - o - s;

                                    if (used[j] || j==o || j==n) goto ex;

                                    printf("    %3d %3d %3d\n", a, b, c);

                                    printf("  %3d %3d %3d %3d\n", d, e, f, g);

                                    printf("%3d %3d %3d %3d %3d\n", h, i, j, k, l);

                                    printf("  %3d %3d %3d %3d\n", m, n, o, p);

                                    printf("    %3d %3d %3d\n\n", q, r, s);

ex:                                 used[e] = used[f] = used[i] = used[k] = 0;

                                }

                                used[p] = used[s] = used[r] = 0;

                        }

                        used[m] = used[q] = 0;

                    }

                    used[l] = used[g] = 0;

                }

                used[d] = used[h] = 0;

            }

            used[b] = used[c] = 0;

        }

        used[a] = 0;

    }

}

brouhaha · 03-30-2015, 04:35 AM

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:

#!/usr/bin/python2

import sys

import time

size = 19

avail = [ True ] * size

board = [ None ] * size

# first element of each row tuple should be the highest location in the tuple,

# and the list should be sorted by the first element of the tuple

rows = {  2: ((2, 1, 0),),

          6: ((6, 5, 4, 3),),

          7: ((7, 3, 0),),

         11: ((11, 6, 2),

              (11, 10, 9, 8, 7)),

         12: ((12, 8, 4, 1),),

         15: ((15, 10, 5, 1),

              (15, 14, 13, 12)),

         16: ((16, 12, 7),

              (16, 13, 9, 5, 2)),

         17: ((17, 13, 8, 3),

              (17, 14, 10, 6)),

         18: ((18, 15, 11),

              (18, 17, 16),

              (18, 14, 9, 4, 0)) }

def print_board():

    global start_time

    print "elapsed time:",time.time() - start_time

    print '   ', '  '.join(["%2d" % board[pos] for pos in range(0, 3)])

    print ' ', '  '.join(["%2d" % board[pos] for pos in range(3, 7)])

    print '  '.join(["%2d" % board[pos] for pos in range(7, 12)])

    print ' ', '  '.join(["%2d" % board[pos] for pos in range(12, 16)])

    print '   ', '  '.join(["%2d" % board[pos] for pos in range(16, 19)])

    print

    sys.stdout.flush()

def check_board(pos):

    # remove the following test if you want all 12 solutions

    if pos == 1 and board[0] > 11 and board[1] > 11:

        return False

    rows_to_check = rows.get(pos)

    if rows_to_check is not None:

        for row in rows_to_check:

            #print "row", row, "content", [board[pos] for pos in row], "sum", sum([board[pos] for pos in row])

            if sum([board[pos] for pos in row]) != 38:

                return False

    return True

def fill_position(pos):

    for piece in range(size):

        if avail[piece]:

            board[pos] = piece + 1

            if check_board(pos):

                avail[piece] = False

                if (pos+1) == size:

                    print_board()

                else:

                    fill_position(pos+1)

                avail[piece] = True

start_time = time.time()

fill_position(0)

print "total elapsed time:",time.time() - start_time

Paul Dale · 03-30-2015, 04:50 AM

(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

    d e f g

   h i j k l

    m n o p

     q r s

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>

/*

     a b c

    d e f g

   h i j k l

    m n o p

     q r s

*/

int main() {

    unsigned char usedbuf[120], *used;

    for (int i=0; i<120; i++)

        usedbuf[i] = 1;

    used = usedbuf + 60;

    for (int i=1; i<20; i++) used[i] = 0;

    for (int a=1; a<20; a++) {

        used[a] = 1;

        for (int b=1; b<20; b++) {

            if (used[b]) continue;

            int c = 38 - a - b;

            if (used[c] || c <= b || c < a) continue;

            used[b] = used[c] = 1;

            for (int d=1; d<20; d++) {

                if (used[d]) continue;

                int h = 38 - a - d;

                if (used[h] || d == h || h < a) continue;

                used[d] = used[h] = 1;

                for (int g=1; g<20; g++) {

                    if (used[g]) continue;

                    int l = 38 - c - g;

                    if (used[l] || l == g || l < a) continue;

                    used[l] = used[g] = 1;

                    for (int m=1; m<20; m++) {

                        if (used[m]) continue;

                        int q = 38 - m - h;

                        if (used[q] || m == q || q < a) continue;

                        used[m] = used[q] = 1;

                            for (int p=1; p<20; p++) {

                                if (used[p]) continue;

                                int s = 38 - p - l;

                                if (used[s] || p == s || s < a) continue;

                                int r = 38 - s - q;

                                if (used[r] || r == s || r == p) continue;

                                used[p] = used[s] = used[r] = 1;

                                for (int e=1; e<20; e++) {

                                    if (used[e]) continue;

                                    int f = 38 - d - e - g;

                                    if (used[f] || e == f) continue;

                                    int i = 38 - b - e - m;

                                    if (used[i] || i == f || i == e) continue;

                                    int k = 38 - b - f - p;

                                    if (used[k] || k == i || k == f || k == e) continue;

                                    used[e] = used[f] = used[i] = used[k] = 1;

                                    int o = 38 - r - k - g;

                                    if (used[o]) goto ex;

                                    int n = 38 - i - d - r;

                                    if (used[n] || n==o) goto ex;

                                    int j = 38 - a - e - o - s;

                                    if (used[j] || j==o || j==n) goto ex;

                                    printf("    %3d %3d %3d\n", a, b, c);

                                    printf("  %3d %3d %3d %3d\n", d, e, f, g);

                                    printf("%3d %3d %3d %3d %3d\n", h, i, j, k, l);

                                    printf("  %3d %3d %3d %3d\n", m, n, o, p);

                                    printf("    %3d %3d %3d\n\n", q, r, s);

ex:                                 used[e] = used[f] = used[i] = used[k] = 0;

                                }

                                used[p] = used[s] = used[r] = 0;

                        }

                        used[m] = used[q] = 0;

                    }

                    used[l] = used[g] = 0;

                }

                used[d] = used[h] = 0;

            }

            used[b] = used[c] = 0;

        }

        used[a] = 0;

    }

}

Tugdual · 03-30-2015, 05:45 AM

Candidate thread for "Not remotely HP Calculators" ?

Don Shepherd · 03-30-2015, 11:44 AM

(03-30-2015 05:45 AM)Tugdual Wrote: Candidate thread for "Not remotely HP Calculators" ?

Well, that depends upon the offered solutions. I'm hoping to see a BASIC solution, a la HP71b, and some RPL solutions hopefully. Or maybe a 32sii.

Claudio L. · 03-30-2015, 02:34 PM

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

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

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.

Don Shepherd · 03-30-2015, 04:40 PM

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.

Claudio L. · 03-30-2015, 04:58 PM

(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:

     1      2     3

  4     5     6     7  

8    9    10   11    12

 13   14    15   16

     17   18   19

Paul Dale · 03-30-2015, 10:11 PM

(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

Claudio L. · 03-31-2015, 12:40 PM

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

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

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.

Claudio L. · 03-31-2015, 05:31 PM

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.

Gilles · (This post was last modified: 03-31-2015 07:49 PM by Gilles.)

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

16 linearly equations because of :
A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S=190

Claudio L. · 03-31-2015, 10:03 PM

(03-31-2015 06:00 PM)Gilles Wrote:
(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, ...

16 linearly equations because of :
A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S=190

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.
That's only 7 days running non-stop. Big improvement.

Claudio L. · 04-01-2015, 12:25 PM

(03-31-2015 10:03 PM)Claudio L. Wrote:
(03-31-2015 06:00 PM)Gilles Wrote: 16 linearly equations because of :
A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S=190
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.
That's only 7 days running non-stop. Big improvement.

Wait... not so fast.
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.

Gilles · (This post was last modified: 04-01-2015 07:23 PM by Gilles.)

(04-01-2015 12:25 PM)Claudio L. Wrote: Wait... not so fast.
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.

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

RayAtHP · 04-02-2015, 07:32 PM

(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:

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.

Meng did a lot of work here, partially a spoiler alarm for these who strive for Easter weekend solution search activities!

Meng

Don Shepherd · 04-02-2015, 08:30 PM

(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!

Meng

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

RayAtHP · 04-02-2015, 08:58 PM

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.