Welcome to our community

Be a part of something great, join today!

Puzzle with digits

  • Thread starter
  • Moderator
  • #1

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,702
I came across this little teaser on Another Forum.
Can anyone figure out this problem ? I have tried many ways and can find no solution.
Put the following numbers into the grid so that no single digit appears more than once in any row, column, or main diagonal.
10,12,13,21,34,38,40,47,50,53,57,64,65,78,89,98
The 'grid' is 4 rows of 4 boxes each, stacked on top of each other.
-------------
[ ][ ][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]
I found a solution, more or less by trial and error. I don't know if there is a more systematic way to tackle it.

Notice that some digits occur more often than others. It might help to place the numbers containing them them in the grid first.
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
Clarification: does "main diagonal" mean upper left to lower right only? Or does it also include upper right to lower left?
 
  • Thread starter
  • Moderator
  • #3

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,702
Clarification: does "main diagonal" mean upper left to lower right only? Or does it also include upper right to lower left?
I think that in this case both diagonals are meant.
 

Sudharaka

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
Hi everyone, :)

Suppose we have four numbers which share one digit in common. Then the only way to arrange those four numbers with one number at the first row-first column position is,

x
x
x
x

Now suppose we are given another four numbers which have a digit in common that we have to place in the table such that one number among those four numbers should be second row, second column position. Then,

xy
y
x
x
y
y
x

Similarly given a third quadruplet of numbers......

x
y
z
z
y
x
x
z
y
y
z
x

And the final four numbers......

x
m
y
z
z
y
m
x
m
x
z
y
y
z
x
m

In our problem the situation is similar. We can arrange the given numbers into four groups:

Numbers with the digit 1 in common: 10,12,13,21 (x-group)

Numbers with the digit 4 in common: 34,40,47,64 (y-group)

Numbers with the digit 5 in common: 50,53,57,65 (z-group)

Numbers with the digit 8 in common: 38,78,89,98 (m-group)

Now let us begin the arrangement.

10
12
13
21

Now we move to the second group. Note that the number 34 which is in the second set, can only be placed in the following position,

1034
12
13
21

Similarly the number 40 is forced to place as follows,



1034
12
1340
21

Now consider the number 50 in the third group. The only position it can take is,

1034
12
1340
5021

Then for the number 53 the only option is,

1034
5312
1340
5021

As usual 38 has only one place to go,

1034
5312
1340
502138

The remaining numbers are,

Numbers with the digit 4 in common: 47,64 (y-group)

Numbers with the digit 5 in common: 57,65 (z-group)

Numbers with the digit 8 in common: 78,89,98 (m-group)

So we have two possible y-values that can fill the second row-second column box. If we use 47 we get two tables;

10893457
53479812
78136540
64502138

and,

10983457
53478912
78136540
64502138

If we use 64 to fill the second row-second column box we have another two possibilities,

10783465
53649812
89135740
47502138

and,

10783465
53648912
98135740
47502138

The whole thing would change if I had used a different element than 10 in the first box. There are \(4!\) possible arrangements for the initial table where only the x-group elements are listed, so I feel that this problem has quite a number of solutions. :)

Kind Regards,
Sudharaka.
 
  • Thread starter
  • Moderator
  • #5

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,702
My solution was
98105364
47562138
13894057
50347812
 

Sudharaka

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
My solution was
98
105364
47562138
13894057
50347812
Thank you for the solution. You have taken the corner element from the x-group (with reference to my previous post) as 12. By swapping 98 and 89 we can get another table. Also 21 and 12 can be interchanged. :)
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
Currently working on a brute-force computer search. To do that, you have to be able efficiently to compute all 16! permutations of 16 numbers. I've finally got the Plain Change algorithm working to the point where I estimate it would take ~80 hours of typical laptop computing time to generate the permutations. Naturally, for each permutation, I have to fit the numbers into the matrix in that order, and test the matrix. If good, print it out and increment a counter. If bad, discard. I'll let you know how things progress. It would be interesting to know exactly how many solutions there are, and what they look like.

[EDIT]: This is a highly parallelizable problem, in theory. If I can figure out how to divide the problem up into several pieces, depending on the number of cores I have, I'll let you know.
 
Last edited:

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
So I have code that works on a 3 x 3 matrix. I had to cheat a little with some 3-digit numbers to make sure I got some valid combos. My set of numbers was {12,13,14,56,57,58,103,114,129}. The code is here:

View attachment newsquare.txt

I had to change the extension from .c to .txt. It's C code. In Debian Linux's X Terminal, I ran

gcc -g3 -Wall -Wextra -c newsquare.c
gcc -o newsquare newsquare.o
./newsquare > ThreeDResults.txt

So the output, consisting of all the valid matrix combinations and the number of combinations, redirected to the ThreeDResults.txt file, which I attach here for you.

View attachment ThreeDResults.txt

There are exactly 48 solutions to this problem, according to my code. This problem is very reminiscent of the 8 queens problem, the first fun problem I solved on computer (I used FORTRAN to solve it, way back in the day).

Now to step up to the original problem is, as I said before, going to take a significant amount of computing time. I plan to start the computation next Monday and hopefully it will finish by Sunday.

One very fun aspect of this problem was the permutation generator code. I got the algorithm from Donald Knuth's The Art of Computer Programming, one of the preprints available online. While the algorithm does work, and it's pretty efficient, his pseudocode could use some serious improvement, vis-a-vis variable names! Maybe Donald Knuth could read Code Complete, and get a few tips on variable names.

Cheers.
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
So I ran my code over the last weekend, but was unable to finish running, because business must go on. So far, it found 62 solutions. I'll post a couple of them now. Unfortunately, I didn't set up piping, so these results are only in my bash shell.

$$\begin{bmatrix}
64 &10 &78 &53\\
57 &38 &12 &40\\
13 &47 &50 &98\\
89 &65 &34 &21
\end{bmatrix}$$

and

$$\begin{bmatrix}
47 &10 &65 &38\\
89 &53 &12 &40\\
13 &64 &98 &57\\
50 &78 &34 &21
\end{bmatrix}$$
 
  • Thread starter
  • Moderator
  • #10

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,702
So I ran my code over the last weekend, but was unable to finish running, because business must go on. So far, it found 62 solutions. I'll post a couple of them now. Unfortunately, I didn't set up piping, so these results are only in my bash shell.

$$\begin{bmatrix}
64 &10 &78 &53\\
57 &38 &12 &40\\
13 &47 &50 &98\\
89 &65 &34 &21
\end{bmatrix}$$

and

$$\begin{bmatrix}
47 &10 &65 &38\\
89 &53 &12 &40\\
13 &64 &98 &57\\
50 &78 &34 &21
\end{bmatrix}$$
Notice that if you have one solution, then you can generate others by rotations and reflections of the matrix. In fact, the group $D_8$ of symmetries of the square acts on the set of solutions. So starting from one solution you get a total of 8 solutions that way. In addition, in any solution you can interchange 12 and 21, and also 89 and 98. Finally, you can interchange rows 1 and 2, rows 3 and 4, columns 1 and 2, and columns 3 and 4, to get another solution.

Thus one solution generates a family of $8\times 2\times 2\times2 = 64$ essentially equivalent solutions. Thus the total number of solutions should be a multiple of 64, and that multiple will tell you how many essentially different solutions there are. There must be at least three distinct families, because the solutions given by me, Sudharaka and Ackbach are essentially different: in Achbach's examples all ten digits occur somewhere on one of the two diagonals, in Sudharaka's examples there are no 2s on a diagonal, and in my example there are no 3s or 7s on a diagonal. Therefore there must be at least $3\times64=192$ solutions (and I would not be surprised if there were many more).
 
Last edited:

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
Notice that if you have one solution, then you can generate others by rotations and reflections of the matrix. In fact, the group $D_8$ of symmetries of the square acts on the set of solutions. So starting from one solution you get a total of 8 solutions that way. In addition, in any solution you can interchange 12 and 21, and also 89 and 98.

Finally, there are some other permutations that act on the set of solutions. Given a solution, you can interchange rows 1 and 2, rows 3 and 4, columns 1 and 2, and columns 3 and 4, to get another solution. Similarly, you can interchange rows and columns 1 and 3, and rows and columns 2 and 4, to get another solution. (You could also interchange rows and columns 1 and 4, and rows and columns 2 and 3, but that would be equivalent to 180 degree rotation of the whole matrix, so would not give you anything new.)

Thus one solution generates a family of $8\times 2\times 2\times3 = 96$ essentially equivalent solutions. Thus the total number of solutions should be a multiple of 96, and that multiple will tell you how many essentially different solutions there are. There must be at least three distinct families, because the solutions given by me, Sudharaka and Ackbach are essentially different: in Achbach's examples all ten digits occur somewhere on one of the two diagonals, in Sudharaka's examples there are no 2s on a diagonal, and in my example there are no 3s or 7s on a diagonal. Therefore there must be at least $3\times96=288$ solutions (and I would not be surprised if there were many more).
Too bad I'm not smart enough to figure out how to incorporate these ideas into my code to save running time! Ah, well. Incidentally, I'll probably have to wait until Christmas break to run the code again, unless I try a different computer altogether.