Solve the Digit Puzzle: 4x4 Grid w/ 15 Numbers

[Opalg]

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.

Spoiler

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

 

[Ackbach]

Clarification: does "main diagonal" mean upper left to lower right only? Or does it also include upper right to lower left?

 

[Opalg]

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]

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,

x		y
	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,

10		34
			12
	13
		21

Similarly the number 40 is forced to place as follows,

10		34
			12
	13		40
		21

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

10		34
			12
	13		40
	50	21

Then for the number 53 the only option is,

10		34
53			12
	13		40
	50	21

As usual 38 has only one place to go,

10		34
53			12
	13		40
	50	21	38

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;

10	89	34	57
53	47	98	12
78	13	65	40
64	50	21	38

and,

10	98	34	57
53	47	89	12
78	13	65	40
64	50	21	38

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

10	78	34	65
53	64	98	12
89	13	57	40
47	50	21	38

and,

10	78	34	65
53	64	89	12
98	13	57	40
47	50	21	38

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.

 

[Opalg]

My solution was

98	10	53	64
47	56	21	38
13	89	40	57
50	34	78	12

 

[Sudharaka]

My solution was

98	10	53	64
47	56	21	38
13	89	40	57
50	34	78	12

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]

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.

 

[Ackbach]

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 487

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 488

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]

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}$$

 

[Opalg]

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

 

[Ackbach]

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.