5 by 5 grid puzzle
OwlHoot
On a forum I frequent someone described n interesting puzzles, which
to everyone's surprise turns out to have literally hundreds of
thousands of solutions despite the apparent tightness of the
conditions.
However, two of the numbers posted so far differ. So I'd like to find
a reference to this problem, or a keyword to search on. ("magic
squares" finds nothing that I can see.)
Anyway, the problem is to find ways to fit the integers 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5 into a 5-
by-5 array, one per element of course (as there are 25 integers to
choose from), such that every row, every column, and both main
diagonals, sum to 15.
Any ideas?
Cheers
John Ramsden
P.S. The numbers posted were 836,864 and 162688.
Martin Chlond
Search "Latin squares".
Martin
"OwlHoot" <raven...@googlemail.com> wrote in message
news:d9cb393b-e551-45a7...@v12g2000vbx.googlegroups.com...
Ted Schuerzinger
13452
52134
34521
21345
45213
Plus rotation, reflection, and switching between the numbers 1-5. (I
wouldn't be surprised if there's another different configuration.) Is
the puzzle to figure out how many ways the conditions can be filled?
--
Ted S.
fedya at hughes dot net
Now blogging at http://justacineast.blogspot.com
OwlHoot
>
> [..]
>
> Is the puzzle to figure out how many ways the conditions can be filled?
Yes, and the number of ways is literally in the hundreds of thousands!
So I'm not interested in particular solutions one can find by
inspection
but in whether the total number of possibilities is 836864 or 162688.
I'm fairly sure the first figure is correct, but there's a possibility
it is the second.
I tried searches on "Latin Squares" and "Magic Squares", and several
such terms, but found nothing on this specific problem or anything
obviously related.
Cheers
John R Ramsden
Frederick Williams
>
> On Dec 30, 3:48 pm, Ted Schuerzinger <fe...@hughes.spam> wrote:
> >
> > [..]
> >
> > Is the puzzle to figure out how many ways the conditions can be filled?
>
> Yes, and the number of ways is literally in the hundreds of thousands!
>
> So I'm not interested in particular solutions one can find by
> inspection
> but in whether the total number of possibilities is 836864 or 162688.
>
> I'm fairly sure the first figure is correct, but there's a possibility
> it is the second.
Dear Professor Hoot (or may I call you Owl?),
According to this:
http://en.wikipedia.org/wiki/Small_Latin_squares_and_quasigroups#Order_5
there are 161,280 _if_ the things that you describe are Latin squares.
> I tried searches on "Latin Squares" and "Magic Squares", and several
> such terms, but found nothing on this specific problem or anything
> obviously related.
--
"The Academy is too large and too vulgar. Whenever I have gone
there, there have been either so many people that I have not been
able to see the pictures, which was dreadful, or so many pictures
that I have not been able to see the people, which was worse."
Bart Goddard
d4e098...@v12g2000vbx.googlegroups.com:
> Anyway, the problem is to find ways to fit the integers 1, 1, 1, 1, 1,
> 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5 into a 5-
> by-5 array, one per element of course (as there are 25 integers to
> choose from), such that every row, every column, and both main
> diagonals, sum to 15.
> P.S. The numbers posted were 836,864 and 162688.
Sloane gives 161280 as the number of latin squares of
order 5:
Maybe try searching under 'quasigroup'. Also the
term 'latin square with constant diagonal.'
--
Cheerfully resisting change since 1959.
OwlHoot
> OwlHoot <ravensd...@googlemail.com> wrote in news:d9cb393b-e551-45a7-a52a-
> d4e09812d...@v12g2000vbx.googlegroups.com:
>
> > Anyway, the problem is to find ways to fit the integers 1, 1, 1, 1, 1,
> > 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5 into a 5-
> > by-5 array, one per element of course (as there are 25 integers to
> > choose from), such that every row, every column, and both main
> > diagonals, sum to 15.
> > P.S. The numbers posted were 836,864 and 162688.
>
> Sloane gives 161280 as the number of latin squares of
> order 5:
>
> http://oeis.org/A002860
>
> Maybe try searching under 'quasigroup'. Also the
> term 'latin square with constant diagonal.'
>
> --
> Cheerfully resisting change since 1959.
Hmm, the snag is none of the rows and columns need be
ordered in this puzzle. So it can't be a reduced Latin
square.
Also, contrary to what one might initially assume,
not every row, column, and main diagonal need contain
a whole set 1, 2, 3, 4, 5. You can throw them in any
old how, as long as all the sums I mentioned come out
right, for example:
5 4 3 2 1
4 2 1 3 5
2 1 5 4 3
3 5 2 1 4
1 3 4 5 2
Here the right diagonal contains two 5s, which may be
seen as a "flaw" but satisfies the conditions of the
puzzle as stated.
One can also of course group solutions into equivalence
classes of (in general) 8, obtained by four rotations,
a flip, and four more rotations.
Also, each solution (a_ij) has a "dual" solution (6 - a_ij)
To start with, I assumed there would be a couple of dozen
solutions at most. But, as I say, there are in fact almost
a million! (or at least over 100000, if you believe that
figure of 162688.
Anyway, thanks for the replies so far, and keep them coming.
Someone must have heard of this variant of Latin squares.
Cheers
John Ramsden
OwlHoot
>
> [..]
Here's an even more lopsided example:
11355
14433
55221
52242
33414
> Cheers
>
> John Ramsden
James Dow Allen
> Anyway, the problem is to find ways to fit the integers 1, 1, 1, 1, 1,
> 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5 into a 5-
> by-5 array, one per element of course (as there are 25 integers to
> choose from), such that every row, every column, and both main
> diagonals, sum to 15.
>
I counted the solutions and got exactly 836,864.
That divided by 8 would be a lower bound of solutions
unique after rotation and reflection. I *think* my
counting demonstrated an upper bound for that
smaller than 162688, so that number may be something else.
James Dow Allen
OwlHoot
How did you count them? There are 381 distinct unordered
sequences (allowing repetitions of course) from among
1,2,3,4,5 that sum to 15.
So a brute force scan needs trying 381^4 combinations
of rows (where the column sums determine the 5th row).
But then you have the diagonals to check too, and
that all 25 numbers have been used, which makes the
whole thing quite slow just from the vast number of
possibilities that need checking.
Or did you think of some crafty combinatoric trick
to deduce that total using factorials or something?
That would be really interesting, but if you don't
mind my saying so highly unlikely.
I think this is a very intractable problem from that
standpoint, because the sums impose an "artificial"
constraint which seems at odds with basic position
counting and suchlike.
I came up with the idea of flipping an array about
its centre row and adding the result to itself,
then repeating this with the result's centre
column, and finally a third stage with a main
diagonal.
This gives a very symmetric array of the form:
2 a11 a12 2 a13 a12 2 a11
a12 2 a22 2 a23 2 a22 a12
2 a13 2 a23 8 a33 2 a23 2 a13
a12 2 a22 2 a23 s a22 a12
2 a11 a12 2 a13 a12 2 a11
in which there are at most 5 distinct integers, and
only a few possibilities. One can then work backward
from this, reversing the flips and merges. But the
details are quite intricate. (It's about ten times
faster than a brute search of the original though.)
Cheers
John Ramsden
Tim Little
> So a brute force scan needs trying 381^4 combinations of rows (where
> the column sums determine the 5th row).
That's easily within the capabilities of modern computers to run
through in less time than it takes to write the program.
> But then you have the diagonals to check too, and that all 25
> numbers have been used, which makes the whole thing quite slow just
> from the vast number of possibilities that need checking.
As soon as the first test fails, you can skip all other tests for that
arrangement. With careful choice of test ordering, most arrangements
can be discarded with one test.
More clever algorithms may be of use in larger versions of such a
puzzle.
- Tim
James Dow Allen
> On Dec 30, 6:53 pm, James Dow Allen <jdallen2...@yahoo.com> wrote:
> > I counted the solutions and got exactly 836,864.
>
I really did enumerate them completely, writing each solution
to a file and doing a "wc -l" at the end to count them.
(I'd intended to do a "sort | uniq -d" afterwords to
confirm the software didn't print the same solution twice,
but forgot to. Anyway, if there were such a bug it would
probably have caused the program to loop forever. :-)
As Tim Little points out, computers are ridiculously fast
these days. The only "trick" in my *very brutish* program was
that after filling the grid lexicographically to
X X X X X
X X X X X
X 3 . . .
1 4 . . .
2 5 . . .
I switched to vertical filling (that is, 1,2,3,4,5 came next)
in order to get to the {if (sum != 15) reject; } tests sooner.
(I didn't check how much speed-up this gave.) Of course I
kept track of each digit's counts and ceased trying those which
had met their quotas.
James