November 2003 - mathfun@mailman.xmission.com

[math-fun] Magic torus of maximum magicity
by asimovd＠aol.com 14 Nov '03

14 Nov '03

Rich announces: << Congratulations to Christian Boyer and Walter Trump, who have found a magic cube of size 5! >> That's really cool! (I hadn't even knownrealized this question was unsolved.) I can't help wondering about whether there is such a thing as a "magic torus" T with maximum magicity. Meaning: Viewing T as the group (Z_k)^n, consider all "affine lines" of the form L = { v + j*w | v,w are in T, and 0 <= j < k } such that card(L) = k. QUESTION: For which (k,n) does there exist an assignment of 1,2,...,k^n to the points of (Z_k)^n such that *every* affine line has the same sum? Or less generally, what is known about this question? --Dan

1 0

[math-fun] magic cube, size 5
by Richard Schroeppel 14 Nov '03

14 Nov '03

Congratulations to Christian Boyer and Walter Trump, who have found a magic cube of size 5! They sent me a .gif picture of the cube. I've transcribed it below. K=315. I spot checked a couple of rows but haven't done a full check of all 109 lines. [109 = (7^3-5^3)/2.] There is some amount of symmetry, opposite cells adding to 126, but it's irregular. Sometimes the symmetry is reflection through a center plane rather than through the center cell. Hopefully we'll hear more about the technique for finding the cube soon. I think this leaves size 6 as the only magic cube size of undetermined existence. Gardner's columns c. 1974 had a magic cube of size 7, and I think 8+ had already been done. Size 7 is a straightforward generalization of the stepping method for the magic 3^2 and 5^2. I proved there's no magic 4^3 (published in MGs column), and the nonex. of 3^3 was already well known. Curiously, the magic 6^2 is harder to construct than squares of size 4,5,7,8. 4K+2 seems to be a hard size. I have some simple results on magic 6^3 properties: various groups of cells must have the expected average value. (Make a semihemidemi-magic 3^3 by folding the 6^3 along the three center planes, adding the cells. Various rows & agonals must have the average value, and algebra gives a little bit more.) The nonexistence of magic 5^4 follows from each 5^3 having the same required center value. There should be enough line types to prove that a magic 7^4 must have center 1201, but I haven't done the algebra. I've tried to show the impossibility of the magic 6^4 but have only partial results, which don't lean either way. This magic 5 cube supports my conjecture that existence of a magic object (of size >1) is equivalent to the corresponding tictactoe game being a draw. (Since 4^3 TTT is a long battle for the win, 5^3 seems certain to be a draw.) Let the analysis begin! Rich rcs(a)cs.arizona.edu ----- Walter Trump & Christian Boyer Magic 5^3 (<= Nov 14, 2003) 25 16 80 104 90 115 98 4 1 97 42 111 85 2 75 66 72 27 102 48 67 18 119 106 5 91 77 71 6 70 52 64 117 69 13 30 118 21 123 23 26 39 92 44 114 116 17 14 73 95 47 61 45 76 86 107 43 38 33 94 89 68 63 58 37 32 93 88 83 19 40 50 81 65 79 31 53 112 109 10 12 82 34 87 100 103 3 105 8 96 113 57 9 62 74 56 120 55 49 35 121 108 7 20 59 29 28 122 125 11 51 15 41 124 84 78 54 99 24 60 36 110 46 22 101 ----- From: "Christian Boyer" <cboyer(a)club-internet.fr> To: <rcs(a)CS.Arizona.EDU> Cc: "Walter Trump" <TrumpNbg(a)aol.com> Subject: "The center of an order 5 magic cube must be 63" Date: Fri, 14 Nov 2003 18:05:49 +0100 Dear Richard, You will probably be happy by these news. As reported by Martin Gardner, and as reported at http://www.inwap.com/pdp10/hbaker/hakmem/number.html#item50, you have proved in 1972 that a perfect magic cube of order 5, if it exits, has a central value = 63. But nobody had found such a cube. We, my German friend Walter Trump and me, have computed this week the first perfect cube of order 5. 109 ways to sum 315. Of course, as you proved, its central value is 63: look at the attached file! Best regards. Christian Boyer. www.multimagie.com/indexengl.htm

2 1

[math-fun] 15 puzzle - one of rich's nits
by Chris Landauer 14 Nov '03

14 Nov '03

hihi, all - rich's first nit about the set of reachable positions: indeed each move is a transposition in S16, but it is easy to see that the only way for the blank space to get back to its original position requires an even number of them, so all of those permutations are even, and my previous note was about a proof (i think) that all even permutations are possible, if the outline is thick enough (as the square is) then the set of all positions is A15 in S16 fixing 16 with the added transpositions making a transitive group on all 16 positions, with overall size therefore (15!/2) x 16, though it is not A16 (as rich said) the key to the proof that you can get all of A15 is to show that in any 2x2 subsquare, with any one of the four unit squares fixed, you can get the 3-cycle for the other three unit squares (almost): pick a 2x2 subsquare, and one of the unit squares in it that is not a corner of the entire square - then it is easy to move the blank spot to a position adjacent to the fixed unit square in that 2x2 subsquare without disturbing any of the unit squares in it - move the fixed one out into the blank spot, cycle the other three unit squares, move the fixed one back, and reverse the moves to get the blank spot back to position 16 this is a lot of 3-cycles, i think easily enough of them to generate all of A15 (i do remember having a real argument for that, but i can't remember what it was) more later, cal

1 0

[math-fun] 15 puzzle - a few nits
by Richard Schroeppel 13 Nov '03

13 Nov '03

A few minor nits on the 15 puzzle. I've always seen the puzzle discussed as "half the arrangements are reachable", and simply assumed it was the even permutations of the sliding pieces that were reachable. I was trying to write down a mapping from the (nonnegative) integers < 16!/2 to the reachable positions and ran into trouble. The mapping to even permutations of [1,16] is easy enough, but a tiny problem appears. [I'm calling the blank space 16 here.] If the blank is in the last position (lower right corner, assuming standard reading order for the cells), then the piece to the left can be moved into the blank cell. This is a swap, which switches an even permutation to an odd one and vice versa. The truth appears to be that indeed, exactly half the positions are reachable, but the description is more complicated. Suppose we color the puzzle cell positions with a checkerboard of black and white squares. The a position is achievable iff it's an even permutation and the blank is at a black square, or if it's an odd permutation and the blank is at a white square. Still 50%, but the mapping rule for the integers will need a little fixup. --- Second nit. The "max solution is 80" paper doesn't tell us the graph diameter, but only that all nodes are within distance 80 of the starting position. (Along with giving 2 of the furthest- from-start positions.) I think we can say that the diameter is at most 82, since a position with the blank in a central or edge position can be morphed into the initial position in one or two moves (plus a relabeling of the tiles). Redoing the search with an initial position where the blank is on the edge and getting a final answer of 79 would prove diameter 80. --- The group of positions for Rubik's is much bigger than 16! But solving individual positions in the rigorous minimum number of moves is feasible now, and has been for a while, since you can work from both Start and Goal towards the middle, and there are only around 10^10 middle positions. If we were lucky, a similar situation might apply to the 15 puzzle, with only about sqrt(16!/2) ~= 3 million positions being reachable in 40 moves. I have no idea if this is true. --- 10^13 positions can be represented as a bit table (reachable in <=K steps, or maybe exactly K steps). That's only 1.25 TB. A lot of storage, but 100GB disks are cheaply available. --- Wechsler's solution algorithm (his note 4, with three lists) can be simplified slightly for the 15 puzzle, since each move changes the color of the "blank square". The reachable positions can be subdivided exactly into two equinumerous classses, those with the blank on a black square (which are reachable in an even number of moves), and those with the blank on a white square (which are an odd distance from Start). When discarding positions reachable from the Current List, only the Previous and Next Lists need be examined; they are of opposite color to the Current List. A good encoding of positions can give considerable locality for the 1-neighbor operator, so the implied sorting step for uniquing the 1-neighbors of the Current List is tractable. --- During the 15-puzzle craze (1880?) there were published problems with prizes and best-found solutions. I wonder if anyone has compared these answers to "truth". Rich rcs(a)cs.arizona.edu

1 0

[math-fun] The 15-Puzzle
by Guy Haworth 12 Nov '03

12 Nov '03

"Chips Challenging Champions" by Schaeffer & Herik, has an article "Disjoint pattern database heuristics" by R.E. Korf and A. Felner, pp. 13-26. This is based on the Culberson/Schaeffer ideas of Computer Intelligence, v14.3 (1998) p 318-334. The Iterative-Deepening-A* algorithm is seen as necessary for the 15-puzzle. IDA* with the Manhatten Distance Function was the first algorithm to find optimal solutions to random instances of the 15-Puzzle. An average of 400m nodes are generated per problem instance in the search, requiring almost 5 hours of DEC 2060 time (as in 1984). Further ideas beyond IDA*/Manhatten are required for the 15- & 24-Puzzle. Their ideas reduce number of nodes by over 10,000 and running time by a factor of over 2,000. They averaged 2 days' computation (average) in solving 50 instances of the 24-Problem. With only the Manhatten_Distance concept, solving time would be 50,000 years per problem. Guy

1 0

[math-fun] 15 puzzle solved?
by N. J. A. Sloane 11 Nov '03

11 Nov '03

Patric.Ostergard(a)hut.fi writes as follows: a(4)=80. This has been shown in A. Br\"ungger, A. Marzetta, K. Fukuda & J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), 45--63. NJAS

2 1

[math-fun] 15-Puzzle
by Guy Haworth 11 Nov '03

11 Nov '03

I'm sure there's a chapter on the 15-puzzle etc in "Chips Challenging Champions" by Schaeffer and Herik (2002), but regret I can't lay hands on my copy at the moment. http://www.cs.ualberta.ca/~joe/Abstracts/15puzzle.html This paper by Culberson and Schaeffer (1996) is available on the web, refers to A*-searching, and says that they reduced the computational effort 1000-fold with their method. g

1 0

[math-fun] 15-puzzle
by Chris Landauer 10 Nov '03

10 Nov '03

hihi, all - i think i proved something once long ago that might help i was thinking about the set of possible configurations in the 15-puzzle, and in some generalizations of it to other ``outlines'' (i.e., shapes other than a large surrounding square) - the specific problem was to recognize starting points that could not reach the expected solution pattern i argued successfully (to myself at least), that in any arrangement of unit squares that was connected by paths of width at least 2 (that is, if a 2x2 square can be moved around inside the outline), then any even permutation of the original unit squares is possible that leaves the initial empty square in the same place (the fact that all and only even permutations are possible was given as the solution of the reachability problem for the square outline, and has apparently been known for some time) - i don't think my argument depended on the outline being simply connected, just ``thick enough'' to have the 2x2 squares fit everywhere (i.e., no narrow necks) this connects the problem to a generator word counting problem in a known (though large, of course) group with a determinable set of generators (i think it was 3-cycles on any 3 unit squares in any 2x2 square, but i don't exactly remember how or if i dealt with the cosets, that is, the different locations of the empty square - i know i did not consider the word lengths at all) there is also a question of what constitutes a move - whether one move is sliding just one of the unit squares into the adjacent empty square, or if an entire row or column (or part of one) can slide as a single move (i prefer the former choice, but i've seen others that prefer the latter, since it is more like how we actually make the moves in the game) more later, cal

1 0

Re: Subject: [math-fun] 15-puzzle
by Dan Hoey 10 Nov '03

10 Nov '03

NJAS wrote: > I'm surprised that the 4x4 case hasn't been solved - can anyone help? The fifteen puzzle is quite a bit harder than the Rubik's cube kind of puzzle, because it's not a group. The set of moves from a given position depend on where the blank is. Also, there is only two-fold symmetry to the puzzle, except in the variant where the home position of the blank is the center. There is also a variant in which sliding a row of tiles counts as a single move. I wrote a simple program to find the results for the eight-puzzle in all these variants (fancy search techniques are unnecessary for this size of problem). The answers I get are: Move Blank Maximum Number of maximal-distance positions and slide home distance (position of blank in those positions) tile corner 31 2 (adjacent edge) tile edge 31 2 (adjacent corner) tile center 30 148 (88 corner, 60 center) row corner 24 1 (center) row edge 24 2 (diagonally adjacent edge) row center 24 4 (corner) By the way, 16!/2 milliseconds is "only" about 331.5 years, and I'd guess the time taken to examine a position is probably more like a few dozen microseconds than a millisecond. But it's still cpu-years. Dan

4 5

[math-fun] Jigsaw puzzle
by Jon Perry 10 Nov '03

10 Nov '03

Can anyone enlighten me as to the software used to design the layout for a diecut jigsaw puzzle? Or at least, how would you go about programming it? Simple designs would be easy, but with more complex pattern, the possibility for impossible pieces increases. How would the program achieve something like; http://www.oldpuzzles.com/ Plus an interesting article; http://www.oldpuzzles.com/styles/styles.htm The closest I could find is; http://www.drescherpuzzle.com/process.html but it's like they don't want to tell us something. Or is the diecut made by hand? Jon Perry perry(a)globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com

1 0