[itachi-san]

Consider an empty 4x4 grid. You have to place a different 2 digit number in each square.

Here's the catch: they have to add up to the same number on the horizontal axis and the vertical axis and on the 2 diagonal segments that make an X across the grid.

Here's the bigger catch: flip the grid upside-down and the horizontals, verticals and diagonals all still have to add up to the same number.

[Guest]

I think it needs too hard work to get it. Although I've given up already, I want to ask two points:

You should restrict the question as "the numbers may not be all the same", because if you give, for example, 33 to all numbers, it will work.

Second; I couldn't understand, how the sums will change when you flip the grid upside- down. If you flip it left to right, the numbers will change: 12 --> 21.

But flipping upside-down?? Do you mean 6-->9, 1-->1, 2-->5 ????

[Guest]

Just put 11 in every squrare

[Guest]

I think it needs too hard work to get it. Although I've given up already, I want to ask two points:

You should restrict the question as "the numbers may not be all the same", because if you give, for example, 33 to all numbers, it will work.

Second; I couldn't understand, how the sums will change when you flip the grid upside- down. If you flip it left to right, the numbers will change: 12 --> 21.

But flipping upside-down?? Do you mean 6-->9, 1-->1, 2-->5 ????

umm 0 and 8 ??

[Guest]

Just put 11 in every squrare

I'm with you on that, the OP never said they had to be different numbers

[Guest]

I think the OP meant 89 -> 68. It is a tough one but solvable. Will do it tomorrow

[Guest]

Just put 11 in every squrare

a 2 digit number but different one in each square. That makes it a magic square. and 60 upside-down = 09.

[itachi-san]

yeah, I never implied this to be an easy out question. I'll amend the OP. putting 11 in each square gets you .01 kudos

[itachi-san]

I think it needs too hard work to get it. Although I've given up already, I want to ask two points:

You should restrict the question as "the numbers may not be all the same", because if you give, for example, 33 to all numbers, it will work.

Second; I couldn't understand, how the sums will change when you flip the grid upside- down. If you flip it left to right, the numbers will change: 12 --> 21.

But flipping upside-down?? Do you mean 6-->9, 1-->1, 2-->5 ????

you've gotten the 'magical' part of it

[EventHorizon]

So....what are all the single digit numbers that remain valid when flipped?

0 -> 0

1 -> 1

2 -> 2 (ugly when rotationally flipped...unless using 7 segment numbers (digital clock-like))

5 -> 5 (In an earlier post they had 2->5...which would just be flipped vertically)

6 -> 9

8 -> 8

9 -> 6

Are 2 and 5 even included in the answer? Just thought I would check...since they are a bit ugly compared to the rest.

One more question......does the value the row/columns sum to when not flipped equal the value the rows/columns sum to when flipped? I didn't think it would be, but thought I'd ask anyway since the wording wasn't completely clear.

Or would those questions give too much away?

[itachi-san]

So....what are all the single digit numbers that remain valid when flipped?

0 -> 0

1 -> 1

2 -> 2 (ugly when rotationally flipped...unless using 7 segment numbers (digital clock-like))

5 -> 5 (In an earlier post they had 2->5...which would just be flipped vertically)

6 -> 9

8 -> 8

9 -> 6

Are 2 and 5 even included in the answer? Just thought I would check...since they are a bit ugly compared to the rest.

One more question......does the value the row/columns sum to when not flipped equal the value the rows/columns sum to when flipped? I didn't think it would be, but thought I'd ask anyway since the wording wasn't completely clear.

Or would those questions give too much away?

2 -> 2 would be ugly and therefore doesn't fit. Digital clocks aside, go with BD's standard font.

yes actually. when flipped they all equal the same number as before the grid was flipped

[EventHorizon]

yes actually. when flipped they all equal the same number as before the grid was flipped

2 -> 2 would be ugly and therefore doesn't fit. Digital clocks aside, go with BD's standard font.

So....it turns out that there are quite a few grids that fit the conditions. I'll post a list (after looking through it to remove duplicates) and my code for anyone that's interested.

Here are a couple that my code has spit out as of yet (each with different sums!).

00 11 68 89

88 69 10 01

19 08 81 60

61 80 09 18

sum=168

00 11 88 96

98 86 10 01

16 08 91 80

81 90 06 18

sum=195

00 19 61 96

91 66 10 09

16 01 99 60

69 90 06 11

sum=176

00 69 86 98

96 88 60 09

68 06 99 80

89 90 08 66

sum=253

[EventHorizon]

It also turns out that if your answer to question 2 was different.....there would still be a large number of solutions.

Here are a few solutions (I have both programs running right now...)

00 11 66 89

86 69 10 01

19 06 81 60

61 80 09 16

sum1 = 166 sum2 = 178

00 11 66 98

96 68 10 01

18 06 91 60

61 90 08 16

sum1 = 175 sum2 = 196

00 16 68 89

69 88 06 10

86 60 19 08

18 09 80 66

sum1 = 173 sum2 = 248

00 16 68 99

69 98 06 10

96 60 19 08

18 09 90 66

sum1 = 183 sum2 = 246

00 16 88 99

98 89 10 06

19 08 96 80

86 90 09 18

sum1 = 203 sum2 = 245

00 18 61 86

81 66 10 08

16 01 88 60

68 80 06 11

sum1 = 165 sum2 = 198

[itachi-san]

So....it turns out that there are quite a few grids that fit the conditions. I'll post a list (after looking through it to remove duplicates) and my code for anyone that's interested.

Here are a couple that my code has spit out as of yet (each with different sums!).

00 11 68 89

88 69 10 01

19 08 81 60

61 80 09 18

sum=168

00 11 88 96

98 86 10 01

16 08 91 80

81 90 06 18

sum=195

00 19 61 96

91 66 10 09

16 01 99 60

69 90 06 11

sum=176

00 69 86 98

96 88 60 09

68 06 99 80

89 90 08 66

sum=253

Nicely done! When I posted this, I was certain you'd be the one to first solve it. I said to myself: "This one's for EventHorizon"

Edit: However... these aren't 2 digit numbers I congratulated too early

[EventHorizon]

Nicely done! When I posted this, I was certain you'd be the one to first solve it. I said to myself: "This one's for EventHorizon"

Edit: However... these aren't 2 digit numbers I congratulated too early

Fine.....here's one (simple modification from the one with a sum of 253)

11 69 86 98

96 88 61 19

68 16 99 81

89 91 18 66

sum = 264

I basically just replaced 0's with 1's

Hmm....now I wonder if there is more than 1 (excluding simple modifications like switch rows 2 and 4 and columns 2 and 4, etc). Stupid leading 0's.....

Edited November 20, 2008 by EventHorizon

[itachi-san]

Fine.....here's one (simple modification from the one with a sum of 253)

11 69 86 98

96 88 61 19

68 16 99 81

89 91 18 66

sum = 264

I basically just replaced 0's with 1's

hehe, that's the one. I was surprised to see those multiple answers at first. well done

[EventHorizon]

hehe, that's the one. I was surprised to see those multiple answers at first. well done

It turns out this problem was simpler (as well as more interesting) than I initially made it out to be... I do tend to jump to coding too quick...

There are 5 numbers that can be turned upside-down and remain numbers.

They are 0,1,6,8, and 9. You don't like leading zeros so remove the 0 (but even if you did let leading zeros slide (or if leading zeros are fine after being flipped then 0 is just not allowed for the ten's digit), you just need to choose 4 of the 5 numbers for the 10's digits and 4 of the 5 for the one's digits.....and if they are not the same set then the sums will be different when flipped).

That leaves four digits to combine pairwise into 16 different numbers. Coincidentally....there are exactly 16 possibilities..... 4 that start with 1, 4 that start with 6, etc.

Now you need all the rows, columns, and diagonals to sum to the same number. Do this by making sure there is 1 of each of the 4 digits in both the ten's digit and one's digit in each row, column, and diagonal. Treat the one's and ten's place separate. Choose one of the two grids below for the ten's digit, and one for the one's digit (notice that one is just the other transposed). Replace the a in the ten's grid with one of the digits, etc. Do the same for the grid one's digit grid....but not necessarily the same substitutions for the ten's as the one's.

a b c d

c d a b

d c b a

b a d c

a c d b

b d c a

c a b d

d b a c

Since each row/column/diagonal has one of each digit in both the ten's and one's place, their sums must be the same. This method allows all possible grids of two digit numbers that satisfy the puzzle.

Coincidentally....I won't be posting code...unless someone asks to see it. The theoretical analysis was more interesting than slightly optimized backtracking.

[Guest]

I design a program that generate the solutions of the problem and count them. And i found that there is a huge number of solutions even if the numbers are differents.

My question is: is there an efficient software that can count every solution of the problem in a short time(let say a day) run in a PC(4GHz)?. Its to say:Can be

design a software with such efficience? Or computationally speaking, is this problem computable for regular PCs?

If so, please reply the answer with a yes and the algorithm.

[Guest]

1st row: 21,38,17,22

2nd row:32,24,23,19

3rd row:18,26,25,29

4th row:27,10,33,28

[EventHorizon]

I design a program that generate the solutions of the problem and count them. And i found that there is a huge number of solutions even if the numbers are differents.

My question is: is there an efficient software that can count every solution of the problem in a short time(let say a day) run in a PC(4GHz)?. Its to say:Can be

design a software with such efficience? Or computationally speaking, is this problem computable for regular PCs?

If so, please reply the answer with a yes and the algorithm.

There is only 1 solution when you look at the restrictions that have been put on the problem. This is because of the various constraints put on it by Itachi-san.

First, you can only use 0,1,6,8,9 (He said 2's and 5's look ugly upside down, so you cannot use them), and no leading zeros (arguably not two digit numbers).

What algorithm did you use? Did you optimize it (this is essentially cutting down the search space intelligently ("pruning the search tree"))?

Even with 2's and 5's and allowing leading 0's and different sums for right-side up and flipped (he said they were the same in one post), I'm sure my code would run in a day (especially if I add in a couple more optimizations that I didn't want to code up....yeah...I'm lazy). I simply used optimized backtracking. I'll post my updated code a little later along with an explanation of the optimizations (I'm rather busy today (yea for procrastination! :-/ )).

One problem with "counting all solutions" is that there are many that are not necessarily unique. For instance, you can easily get another grid that works by transposing or rotating the grid or swapping given rows and columns (i.e., rows 2 and 4 get swapped, then columns 2 and 4 get swapped = another solution). Would these all count as unique? if not, you can optimize your code further. If so, you could just compute them as if they are not unique, and then run the results through another piece of code that outputs all permutations that produce valid results

So, the answer is yes, and the algorithm is optimized backtracking (though most any applicable algorithm will work when optimized...I just like backtracking since the memory use is small compared to other algorithms). As I said earlier....I'll explain this further later (As for now, I have a paper to finish).

[EventHorizon]

1st row: 21,38,17,22

2nd row:32,24,23,19

3rd row:18,26,25,29

4th row:27,10,33,28

What number is 7 upside-down (looks like an L to me)? What number is 4 upside-down (looks like an h in some fonts)? What number is 3 upside-down (looks like an E)? None of those remain numbers when upside-down. I don't think you got the "magic" part of the puzzle.

[EventHorizon]

I design a program that generate the solutions of the problem and count them. And i found that there is a huge number of solutions even if the numbers are differents.

My question is: is there an efficient software that can count every solution of the problem in a short time(let say a day) run in a PC(4GHz)?. Its to say:Can be

design a software with such efficience? Or computationally speaking, is this problem computable for regular PCs?

If so, please reply the answer with a yes and the algorithm.

Here's my code that ran in under an hour and a half (5015 seconds)...

//

#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
#include <time.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
time_t start,end;
time (&start);
cout << asctime(localtime(&start)) << endl << endl;

#define size 4
#define num 5
int up[num] = {0,1,6,8,9};
int down[num] = {0,1,9,8,6};//what the numbers are when they are upside-down

int grid[size*size*2];

int rows[11][size] = {{0,1,2,3},
{4,5,6,7},
{8,9,10,11},
{3,6,9,12},
{0,4,8,12},
{1,5,9,13},
{2,6,10,14},
{3,7,11,15},
{0,5,10,15},
{12,13,14,15},
{999,999,999,999}};//I could have automatically determined these....but it was simpler just to type them in. Note that you need to change these if you change the size of the grid...and sort them

int one=0,two=0;//row/column/diagonal sum rightside up and upside down

int zerosmaller = 1;//used to help prune the search tree

//initialize it
int index = 0;
grid[0] = -1;


while(index != -1)
{
grid[index]++;

if (grid[index]==num){index--; continue;}
else
{
index++;
if (index != size*size*2) grid[index] = -1;

if (index%2==0)
{
//check that value is unique
int bad = 0;
for(int i = 0; i < index-2; i+=2)
{
if ((grid[i] == grid[index-2]) && (grid[i+1] == grid[index-1]))
{
bad = 1;
index--;
break;
}
}
if (bad) continue;//if not unique, try the next value

if (index==4) zerosmaller = (grid[0]*10+grid[1] < grid[2]*10+grid[3]);

//"prune the search tree"
if (zerosmaller)
{
//check that the smallest value is in place 0 or 1 (top-left, or one to the right -- removes many equivalent matrices)
if ((index>=6) && (grid[0]*10+grid[1] > grid[index-2]*10+grid[index-1]))
bad = 1;
//Ensures that the value in place 1 is less than the value in place 2
else if ((index==6) && (grid[2]*10+grid[3] > grid[4]*10+grid[5]))
bad = 1;
//Ensure that 1<4 if 0 is smallest
else if ((index==10) && (grid[2]*10+grid[3] > grid[8]*10+grid[9]))
bad = 1;
//ensure that 1<8 if 0 is smallest
else if ((index==18) && (grid[2]*10+grid[3] > grid[16]*10+grid[17]))
bad = 1;
}
else
{
//check that the smallest value is in place 0 or 1 (top-left, or one to the right -- removes many equivalent matrices)
if ((index>=6) && (grid[2]*10+grid[3] > grid[index-2]*10+grid[index-1]))
bad = 1;
//Ensure that 0<3 if 1 is smallest
if ((index==8) && (grid[0]*10+grid[1] > grid[6]*10+grid[7]))
bad = 1;
//Ensures that the value in 0 is less than the value in 5
else if ((index==12) && (grid[0]*10+grid[1] > grid[10]*10+grid[11]))
bad = 1;
//ensure that 0<9 if 1 is smallest
else if ((index==20) && (grid[0]*10+grid[1] > grid[18]*10+grid[19]))
bad = 1;
}

if (bad)
{
index--;
continue;
}

//check if any of the sum constraints are violated
int con = 0;//the constraints are the sums of the rows, columns, and diagonals
while (rows[con][size-1] < (index/2)-1) con++;
while (rows[con][size-1] == (index/2)-1)
{
//check constraint
int testone = 0, testtwo = 0;

for(int i = 0; i < size; i++)
{
testone += up[grid[2*rows[con][i]]]*10;
testone += up[grid[2*rows[con][i]+1]];
testtwo += down[grid[2*rows[con][i]]];
testtwo += down[grid[2*rows[con][i]+1]]*10;
}

if (index == 2*size)//set one and two -- the sums of rows reg and upside-down
{
one = testone;
two = testtwo;
if ((one < 24) || (two < 24))//this is hardcoded for the problem given.....it's the average of the smallest and 16th smallest numbers multiplied by 4...so...the smallest possible sum of a row
{
bad = 1;
index--;
break;
}
}

if ((one != testone) || (two != testtwo)) // add || (testone != testtwo) to force the sum when upside-down to be equal to the sum when right-side up
{
bad = 1;
index--;
break;
}
con++;
}
if (bad) continue;


if (index == size*size*2)
{
//print off grid
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
cout << up[grid[2*(i*size+j)]] << up[grid[2*(i*size+j)+1]] << " ";
}
cout << endl;
}
cout << "sum1 = " << one << "\tsum2 = " << two << endl << endl;
index--;
}
}
}
}
time (&end);
cout << endl << asctime(localtime(&end)) << endl;
cout << "This program took " << difftime(end,start) << " seconds to run." << endl;
return 0;
}

// magicgrid.cpp : Defines the entry point for the console application.

So...what this code is doing is setting values in the grid one-by-one, and backtracks when it realizes that no solution can result (or a duplicate one).

The grids that it deems duplicates are those that can be found by flipping and rotating, as well as exchanging rows and columns (explained in the next paragraph). I found that there are rows and columns that when switched will change which numbers are added together. This leaves a number of matrices that look the same (same set of numbers). If you want these to be removed, then you could use the method I gave in a previous post (the one with the abcd matrices), but this only works with magic squares in this specific subset of magic squares (two digit numbers that work when flipped).

Row/column switches that don't change which sets of numbers are added together are swapping 1 and 4 (swap rows 1 and 4 then columns 1 and 4), 2 and 3, or both 1 with 2 and 3 with 4 (obviously there are more, but using these form a basis (eg, you can reach the other with these)). This leaves numbers on the diagonal that were on the diagonal, etc. This means that my statement about swapping rows and columns 2 and 4 wouldn't always work.

This code makes sure that the smallest value is either in the top left corner or in the place just to the right of the top left corner (can be moved there by rotations,mirroring,swapping row/column). It then prunes further by requiring the larger of those two values to be the smallest of a given set of numbers that could be put in that position using the swapping above.

I could have optimized this further by changing the order the cells are filled to move the checks (sums,duplicates,etc) earlier, but instead wanted the code to be somewhat understandable.

Any questions?