Challenging Christmas Puzzle

[OwlHoot]

I get 836,864 solutions after 19 minutes running time in debug mode in VB.Net. 21, 071,715,921 positions examined, if only very briefly for the majority of them.

How many combinations are the on this grid, including those that don't add up to 15? Clearly this isn't as simple to calculate as 25! What is the divisor (I assume it's 25! divided by something), where there are 5 (*5) of each digit the same? Knowing that might give some indication of how inefficient these simple searches are compared to the efficiency they could approach. Certainly 836,864 is a drop in the ocean compared to 21, 071,715,921.

Holy carp - What are you running on, a Cray?!

[TimberWolf]

Holy carp - What are you running on, a Cray?!

Only 11 minutes when I run the release executable directly. My PC isn't high spec, try running (in a compiled language) 3 loops 1 to 381 inside each other, containing one if statement on the inside. It'll zip through 21 billion iterations. Ish.

Edit: 4 loops, not 3 as I said above.

[TimberWolf]

Here's a nice one:

15243
54231
12345
53421
31425

3's on the right diagonal, 12345 across the middle and a 3*3 magic square in the middle. Although I'm really looking for something super symmetrical.

[TimberWolf]

12345
52413
54321
35241
12345

12345 across top and bottom and on a diagonal. That should make solving it a second time quite memorable. Oh, 54321 across the middle too.

[TimberWolf]

12345
52413
54321
35241
12345

12345 across top and bottom and on a diagonal. That should make solving it a second time quite memorable. Oh, 54321 across the middle too.

Interestingly, just:

1 2 3 4
  2
5 4 3 2
      4
1 2 3

is enough to completely describe the previous (quoted) solution. You can get from here to there soduku style, without guesswork.

[Platypus]

I get 836,864 solutions after 19 minutes running time in debug mode in VB.Net. 21, 071,715,921 positions examined, if only very briefly for the majority of them.

Excellent work!!

Ok, here are my results:

Just using my 381 valid lines, trying all combinations on the first 4 rows then calculating the 5th row (per TW's earlier post) and no early rejections:
Tests = 2,974,547,521, Solutions = 836,864 (run time 19 minutes, MS VC 6, fully compiled)

Adding TW's optimisations (*) and early rejection:
Tests = 75,502,080, Solutions = 836,864 (run time 13 minutes)

(*) The final algorithm went like this,
- for each top row (381 combinations)
- select the first column from the pool which begins with the first row's first number (between 68 and 85 choices)
- select the 2nd row which begins with the 1st column's first number (also between 68 and 85 choices)
- select the 2nd column which begins with the 2nd row's digits in rows 1 and 2 (between 6 and 15 choices)
- select the 3rd row which begins with the 2nd column's first two digits (again, between 6 and 15 choices)
and so on

After the 2nd row and for every row and column thereafter, do a quick check to ensure that too many tiles of one particular number have not been used (e.g. more than 5 3's means early rejection).

Running on a Pentium dual core (not core 2 duo) at 3GHz.

It would be possible to more sophisticated early rejection, but I couldn't be bothered!

EDIT: just as a matter of interest, version 1 of my program assumed that each row and column would contain one each of 1,2,3,4,5. This yielded 4288 (IIRC) solutions and took one minute to run.

EDIT2: I notice that I seemed to do a lot fewer tests than TW, but that's because I did a quick check before doing a full check of the grid, like so:

        // calculate, do NOT cycle the final row
        s = Box[4][0] = 15 - Box[3][0] - Box[2][0] - Box[1][0] - Box[0][0];
        if (s < 1 || s > 5) continue;
        s = Box[4][1] = 15 - Box[3][1] - Box[2][1] - Box[1][1] - Box[0][1];
        if (s < 1 || s > 5) continue;
        s = Box[4][2] = 15 - Box[3][2] - Box[2][2] - Box[1][2] - Box[0][2];
        if (s < 1 || s > 5) continue;
        s = Box[4][3] = 15 - Box[3][3] - Box[2][3] - Box[1][3] - Box[0][3];
        if (s < 1 || s > 5) continue;
        s = Box[4][4] = 15 - Box[3][4] - Box[2][4] - Box[1][4] - Box[0][4];
        if (s < 1 || s > 5) continue;
        boxsolution(Box); // test full grid

[TimberWolf]

Excellent work!!

Ok, here are my results:

Just using my 381 valid lines, trying all combinations on the first 4 rows then calculating the 5th row (per TW's earlier post) and no early rejections:
Tests = 2,974,547,521, Solutions = 836,864 (run time 19 minutes, MS VC 6, fully compiled)

Adding TW's optimisations (*) and early rejection:
Tests = 75,502,080, Solutions = 836,864 (run time 13 minutes)

(*) The final algorithm went like this,
- for each top row (381 combinations)
- select the first column from the pool which begins with the first row's first number (between 68 and 85 choices)
- select the 2nd row which begins with the 1st column's first number (also between 68 and 85 choices)
- select the 2nd column which begins with the 2nd row's digits in rows 1 and 2 (between 6 and 15 choices)
- select the 3rd row which begins with the 2nd column's first two digits (again, between 6 and 15 choices)
and so on

After the 2nd row and for every row and column thereafter, do a quick check to ensure that too many tiles of one particular number have not been used (e.g. more than 5 3's means early rejection).

Running on a Pentium dual core (not core 2 duo) at 3GHz.

It would be possible to more sophisticated early rejection, but I couldn't be bothered!

EDIT: just as a matter of interest, version 1 of my program assumed that each row and column would contain one each of 1,2,3,4,5. This yielded 4288 (IIRC) solutions and took one minute to run.

EDIT2: I notice that I seemed to do a lot fewer tests than TW, but that's because I did a quick check before doing a full check of the grid, like so:

        // calculate, do NOT cycle the final row
        s = Box[4][0] = 15 - Box[3][0] - Box[2][0] - Box[1][0] - Box[0][0];
        if (s < 1 || s > 5) continue;
        s = Box[4][1] = 15 - Box[3][1] - Box[2][1] - Box[1][1] - Box[0][1];
        if (s < 1 || s > 5) continue;
        s = Box[4][2] = 15 - Box[3][2] - Box[2][2] - Box[1][2] - Box[0][2];
        if (s < 1 || s > 5) continue;
        s = Box[4][3] = 15 - Box[3][3] - Box[2][3] - Box[1][3] - Box[0][3];
        if (s < 1 || s > 5) continue;
        s = Box[4][4] = 15 - Box[3][4] - Box[2][4] - Box[1][4] - Box[0][4];
        if (s < 1 || s > 5) continue;
        boxsolution(Box); // test full grid

Excellent work! I guess that’s the puzzle solved.

Further puzzles/questions/amusements for those that can be arsed:

1. The minimum number of tiles needed to fully describe a solution. I gave an example earlier using only 13 tiles, which I believe leads directly to only one solution. I could check that out for certain if sufficiently motivated. Can anyone beat 13? Is that number true of any solution?
   
   
2. How many distinct board positions are there, including those that don’t sum to 15 on R, C & D’s? This can be found mathematically. I guess it is 25 factorial divided by some fairly large number comprised of factorials, which again I could probably work out if sufficiently motivated.
   
   
3. Find the most symmetrical or pleasing solution. I’ve already posted a few of these. Perhaps these are in the eye of the beholder.
   
   
4. The significance of the prime factorisation, if any, mention by Owlhoot.
   For 836,864 this is: 2 (^8), 7, 467

[Platypus]

How many distinct board positions are there, including those that don’t sum to 15 on R, C & D’s? This can be found mathematically. I guess it is 25 factorial divided by some fairly large number comprised of factorials, which again I could probably work out if sufficiently motivated.

I'm sure it's 25! / 5! / 5! / 5! / 5! / 5! = 6.2336E14

[Platypus]

Excellent work! I guess that’s the puzzle solved.

Now I shall write to the manufacturer pointing out that the one solution they provided is just 1 of 836,864 and that perhaps they should improve their solution sheet should mention that there are other solutions

But I won't go as far as to suggest that print these other solutions on the sheet

[TimberWolf]

I'm sure it's 25! / 5! / 5! / 5! / 5! / 5! = 6.2336E14

That seems about right. About 1 in three quarters of a billion chance of a random position being a solution then (6.23*10^14 / 836864).