{"id":91,"date":"2011-03-01T19:09:01","date_gmt":"2011-03-02T00:09:01","guid":{"rendered":"http:\/\/puzzlezapper.com\/blog\/2011\/03\/a-semimagic-magic-45-omino\/"},"modified":"2011-03-01T18:54:25","modified_gmt":"2011-03-01T23:54:25","slug":"a-semimagic-magic-45-omino","status":"publish","type":"post","link":"https:\/\/puzzlezapper.com\/blog\/2011\/03\/a-semimagic-magic-45-omino\/","title":{"rendered":"A Semimagic Magic 45-omino"},"content":{"rendered":"

Bryce Herdt has found a solution<\/a> to problem #21<\/b>:<\/p>\n

<\/div>\n

The shape of the darker region is “magic” because the number of cells in each 3\u00d73 block corresponds to a number in a magic square, while the number of cells in each row, column, and main diagonal is 5. The sum of the numbers in each row and column is 115. <\/p>\n

There’s still room for improvement here: note that the diagonals do not add up to the magic sum. (A mostly magic square with this property is called semimagic<\/i>.) <\/p>\n

Problem #21.1<\/b> Find a magic magic 45-omino, as above, but with diagonals adding to the magic sum.<\/p>\n

It’s interesting that this solution was found by manually tweaking the output of a program that I wrote to solve the problem. I was never able to get the program to find an actual solution, so I had it give up after a certain number of trials and output the best near solution. There may well be a large number of solutions, but the search space is enormous. <\/p>\n

It’s pretty simple to get fairly close by picking a random permutation of numbers and repeatedly swapping them around to get sums closer to the magic sum. But getting from this local minimum to a real solution is the hard part. The problem would seem to call for something like simulated annealing, and indeed I found a reference to a magic square finder algorithm<\/a> using something similar. (It should be noted that if all you want is a magic square of a given size, there are deterministic methods that will get you one very quickly.) I added a hack to my code to make it do a crude version of this, but it doesn’t seem to have helped much. (The near solution that Herdt fixed up was made with the old version of the code.) <\/p>\n

Feel free to look at my solver code<\/a> (in Python). I do wonder if there is some way it can be fixed up to be better at getting from near solutions to real solutions. <\/p>\n","protected":false},"excerpt":{"rendered":"

Bryce Herdt has found a solution to problem #21: The shape of the darker region is “magic” because the number of cells in each 3\u00d73 block corresponds to a number in a magic square, while the number of cells in each row, column, and main diagonal is 5. The sum of the numbers in each … Continue reading A Semimagic Magic 45-omino<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[44,49,11,48,50],"class_list":["post-91","post","type-post","status-publish","format-standard","hentry","category-recreational-mathematics","tag-magic-45-ominoes","tag-magic-squares","tag-polyominoes","tag-python","tag-solved-problems"],"_links":{"self":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/91","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/comments?post=91"}],"version-history":[{"count":1,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/91\/revisions"}],"predecessor-version":[{"id":92,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/91\/revisions\/92"}],"wp:attachment":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/media?parent=91"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/categories?post=91"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/tags?post=91"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}