interesting magic square

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

monicao
Posts: 5
Joined: Thu Oct 11, 2007 6:39 pm UTC

interesting magic square

Postby monicao » Thu Oct 11, 2007 7:24 pm UTC

Hy, I'm new here... I have to create a 6x6 magic square (sum of rows, colums, diagonals is the same). I have to use 1-once, 2-twice, 3-three times, 4-four times, 5 for five times and so on ... and 8 for eight times. I've tried many, many classic methods, but nothing worked... Any ideas, please? Thankyou!

P.S. I know this magic square is 34 sum.

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

Re: interesting magic square

Postby EricH » Fri Oct 12, 2007 3:17 am UTC

I'm not sure how to define an algorithm, but a solution can be achieved by brute force (I'm sad to say, over an hour's brute force...)

Also, introduce yourself on the intro thread, please. It's no fun to be mistaken for a spambot...

[EDIT]: Why do you have to make such a magic square? Is this a homework problem? Solution removed, for the moment; if it's homework, you need the method, not the answer.

-----------------
I am not obsessive.
I am NOT obsessive.
I am not obsessive.
I am not obsessive.
I am not obsessive.
I am not obsessive!

monicao
Posts: 5
Joined: Thu Oct 11, 2007 6:39 pm UTC

Re: interesting magic square

Postby monicao » Fri Oct 12, 2007 3:58 am UTC

Yes, Eric, I need a method, not the answer. And it's not a homework, it's ... a fun problem! Just for my brain.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: interesting magic square

Postby jestingrabbit » Fri Oct 12, 2007 4:26 am UTC

The first method I could think of involved finding all the ways to make a row, and then banging rows together in some way. Don't know how effective a method that could be.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

Re: interesting magic square

Postby EricH » Fri Oct 12, 2007 2:15 pm UTC

Actually, rabbit, that was my second idea; I didn't find it effective, just because there were...a large number of ways to combine numbers. My first attempt was, like monicao, trying an old algorithm. My third was to try for four 3x3 magic squares, but the pool of numbers was uncomfortably large. Fourth idea, I took the whole pool of numbers, 122333444455555666666777777788888888, and looked for the five in sequence that add up to 34; that is, 556666. I put those down one diagonal, and then spread out 8's and 7's next to them, hoping that the sums would be getting close, and I could drop in smaller numbers to finish them up. That didn't work out real well, either, because I'd neglected the other diagonal. Fifth try, I laid out the first diagonal the same way, and then laid out the second diagonal, with leftover numbers, then tried again to squeeze in what was left. Couldn't find places for all the 8s. Then I altered the first diagonal for symmetry, 656656, put in the rest of the numbers, and I had two diagonals that added properly, some rows or columns, but not all. After that, I started swapping numbers around to make sums come out right, and kept at it for about thirty minutes. Not recommended. The only tool I used was a spreadsheet to do the sums automatically.

My solution

Spoiler:
6 8 4 7 5 4
7 5 7 2 5 8
8 8 6 7 3 2
4 1 7 6 8 8
3 5 7 8 5 6
6 7 3 4 8 6

You can see that I left that first diagonal intact, but not much else survived. I started, for instance, with the 8s arranged like this:
6 x x 8 x x
x 5 8 x x x
x 8 6 x x 8
8 x x 6 8 x
x x x 8 5 x
x x 8 x x 6
and you can see that only three of them remained in their original positions.


So, no trace of elegance to my method. What I did note, mathematically, is that this is the only reasonable size magic square you can make this way, because 36 is the only number that's both square and triangular. Well, 1, but that's rather like binary Sudoku. The next chance doesn't come until 1225--a 35x35 magic square, filled with one 1, two 2s, and so on up to forty-nine 49s, where all the lines add up to 595. Unwieldy, to say the least. Anyone who finds the 6x6 square too easy, is welcome to the bonus problem.... I'm not that obsessive.
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: interesting magic square

Postby jestingrabbit » Fri Oct 12, 2007 3:55 pm UTC

Fair enough eric, but I'm not totally convinced that it can't be made workable. The trick is that once you've got five rows, you've got the sixth (though it mightn't be consistent with the other five), and you can further reduce computation by going for pairs of rows that don't contain too many of one number, then triples that don't either, and then bang triples and pairs together until you get lucky. There might be other ways to reduce the search space that I'm not seeing too. That's definitely how I'd try to get all the possible squares anyway.

This might be computationally bad, but its what I did to solve the 36 officers problem one time, and it worked for that. There are a lot more "clashes" that can happen in that problem though, and you can choose the first row and a diagonal there too, so it might not be applicable at all *shrug*.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
EdgarJPublius
Official Propagandi.... Nifty Poster Guy
Posts: 3715
Joined: Tue Oct 09, 2007 4:56 am UTC
Location: where the wind takes me

Re: interesting magic square

Postby EdgarJPublius » Fri Oct 12, 2007 5:44 pm UTC

With this sort of puzzle (this one specifically almost) I'd start of with the largest numbers since 8*4 is so close to (but larger than) the 'magic sum' you don't really want too many of them sitting too close to each other and you can make logical assumptions about their final position in the puzzle (I.E. place the 8s such that no four are on the same line (obviously) and such that as few are on the same line as two others as possible) in which case filling in the other positions becomes fairly easy as you work your way down. You don't need to concern yourself with arranging a line right away as you will usually find that eventually a previous line will screw you up, building the puzzle in logical pieces like using the eights first makes later steps easier instead of harder.
Roosevelt wrote:
I wrote:Does Space Teddy Roosevelt wrestle Space Bears and fight the Space Spanish-American War with his band of Space-volunteers the Space Rough Riders?

Yes.

-still unaware of the origin and meaning of his own user-title

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

Re: interesting magic square

Postby EricH » Fri Oct 12, 2007 5:59 pm UTC

jestingrabbit wrote:Fair enough eric, but I'm not totally convinced that it can't be made workable.


Oh, I wouldn't claim it couldn't work; when it comes to generating an algorithm, it certainly seems to approach the answer more quickly than my method; it's just that, doing it mostly in my head, the computation was more than I wanted to tackle. If I hadn't stumbled on a solution, I'd have been more inclined to work with sets of possible rows.
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.

bittyx
Posts: 194
Joined: Tue Sep 25, 2007 9:10 pm UTC
Location: Belgrade, Serbia

Re: interesting magic square

Postby bittyx » Fri Oct 12, 2007 7:21 pm UTC

I've got another solution:

Spoiler:
8 6 8 4 2 6
3 8 2 6 8 7
5 8 6 3 8 4
5 3 6 7 5 8
6 4 5 7 4 8
7 5 7 7 7 1


Like EricH, all I used was an Excel spreadsheet to sum for me.
I actually started doing it on paper and, after a bit of common sense struck me, turned to my computer. Obviously, I started with the diagonals, with a random combination, mostly composed of 8s. I put the leftover 8s in places that seemed to "lack" big numbers. I filled in the grid row by row, making sure all of the sums were as close as possible to 34.

When I completed the grid, I checked for differences in sums; for example, if two columns were 32 and 36, I would find 2 numbers in the same row of each column that had a difference of 2, giving advantage to pairs that don't change diagonals. This way, the sums in each row would remain the same, while the column sums reached the right number. I did this for a while, and in the end only one diagonal had a wrong sum, which was easy to fix using the same logic.

It took me less than 20 mins, so I guess it wouldn't be that hard to do a computer program that solves it.

I also have the feeling that there are many, many solutions to this problem.

I would do the following:
1) Find two random combinations for the diagonals that equal 34.
2) Find combinations, row by row, that equal 34.
3) Now, all rows and the diagonals would be proper, so we would fix all the columns.
4) If there is no way to fix a column without altering a row or a diagonal, we fix it the best way possible.
5) After all the columns are complete, we start fixing the rows in the same manner.
6) After the rows are fixed, we do the diagonals.
7) If the process is not done, we repeat it from step 4.

I'm pretty sure that, after a while, a program like this would come up with a solution (well, either that, or it would make circular changes and never end), but I don't have the time to try actually coding it right now. I might try it in a few days, though.

P.S. If anyone thinks I should spoil my post, please say; I noticed that there's not a lot of spoiling in this topic, so I avoided it.

User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Re: interesting magic square

Postby Mouffles » Sat Oct 13, 2007 11:45 am UTC

I wrote a backtracking algorithm in c++ to find them. These are the first few magic squares it spat out:
Spoiler:
127888
265678
778345
873754
856663
875446

127888
265678
778354
873745
856663
875446

127888
265678
778354
873754
855664
876436

127888
265678
867346
884743
856573
775546

127888
265678
867355
873844
867463
775546

127888
265678
867355
874744
855673
786436

127888
265678
867355
884734
855673
776446

127888
265678
867355
884743
856474
775636

127888
265678
867355
884743
856663
775447
The first two rows are the same for all of these, which suggests there will be a huge number of possible squares. At the moment my program is too slow to find all of them, but I'm sure it could be improved.

EDIT: I let it run and it took about half an hour to get to 10,000 magic squares. And these all started with 127888.

EDIT2: I came back a few hours later and it was in the hundreds of thousands. Based on how far it had got, I'd guess that there are around 4 million or so magic squares just with 127888 as the first row.
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

crp
Posts: 118
Joined: Tue Oct 16, 2007 1:17 am UTC

Re: interesting magic square

Postby crp » Tue Oct 16, 2007 1:18 am UTC

i'll take this one on, I'm king of magic squares lol

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: interesting magic square

Postby Cosmologicon » Tue Oct 16, 2007 7:36 am UTC

How many ways can a regular 6x6 magic square be permuted (rotations, reflections, permutations of rows and columns that leave the diagonals intact)? It seems to me that permutations of rows/columns is the only operation you need, and I count 384.

For this puzzle, not every solution will have this many, because you can get some symmetries. I think, anyway.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests