- mathfun@mailman.xmission.com - mailman.xmission.com

[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

Re: [math-fun] 15-puzzle
by MCKAY＠vax2.concordia.ca 09 Nov '03

09 Nov '03

Your number of configurations i misleading since there ios plenty of symmetry. I expect someone from Donald Michie's Dept. of machine Intelligence working in the 60's will have done the computation in Edinburgh. John McKay From: IN%"math-fun(a)mailman.xmission.com" "math-fun" 9-NOV-2003 21:37:37.48 To: IN%"math-fun(a)mailman.xmission.com" "math-fun" CC: Subj: RE: [math-fun] 15-puzzle Return-path: <math-fun-bounces(a)mailman.xmission.com> Received: from clyde.concordia.ca (clyde.Concordia.CA [132.205.1.1]) by vax2.concordia.ca (PMDF V6.2 #30759) with ESMTP id <01L2UCJ5B1GA000YT5(a)vax2.concordia.ca> for mckay(a)vax2.concordia.ca (ORCPT mckay(a)vax2.concordia.ca) Sun, 09 Nov 2003 21:37:36 -0400 (EDT) Received: from mailman.xmission.com (mailman.xmission.com [198.60.22.29]) by clyde.concordia.ca (8.12.10/8.12.10) with ESMTP id hAA2bQk9172924 for <mckay(a)vax2.concordia.ca>; Sun, 09 Nov 2003 21:37:26 -0500 (EST) Received: from localhost ([127.0.0.1] helo=mailman.xmission.com) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1AJ1vY-0001V5-03; Sun, 09 Nov 2003 19:37:16 -0700 Received: from place.org ([65.163.18.18] helo=zachs.place.org ident=postfix) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1AJ1vW-0001Uy-00 for <math-fun(a)mailman.xmission.com>; Sun, 09 Nov 2003 19:37:14 -0700 Received: from ACW.alum.mit.edu (pool-129-44-175-237.bos.east.verizon.net [129.44.175.237]) by zachs.place.org (Postfix) with ESMTP id E61A8180EC for <math-fun(a)mailman.xmission.com>; Sun, 09 Nov 2003 20:36:57 -0600 (CST) Date: Sun, 09 Nov 2003 21:28:51 -0500 From: "Allan C. Wechsler" <acw(a)alum.mit.edu> Subject: Re: [math-fun] 15-puzzle In-reply-to: <200311100120.UAA84181(a)fry.research.att.com> Sender: math-fun-bounces(a)mailman.xmission.com X-Sender: acw(a)place.org To: math-fun <math-fun(a)mailman.xmission.com> Errors-to: math-fun-bounces(a)mailman.xmission.com Reply-to: math-fun <math-fun(a)mailman.xmission.com> Message-id: <5.1.0.14.0.20031109212244.023f4d90(a)place.org> MIME-version: 1.0 X-Mailer: QUALCOMM Windows Eudora Version 5.1 Content-type: text/plain; format=flowed; charset=us-ascii Precedence: list X-BeenThere: math-fun(a)mailman.xmission.com X-Mailman-Version: 2.1.1 X-Scanned-By: MIMEDefang 2.35 List-Post: <mailto:math-fun@mailman.xmission.com> List-Subscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=subscribe> List-Unsubscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=unsubscribe> List-Archive: <http://mailman.xmission.com/cgi-bin/mailman/private/math-fun> List-Help: <mailto:math-fun-request@mailman.xmission.com?subject=help> List-Id: math-fun <math-fun.mailman.xmission.com> Original-recipient: rfc822;mckay(a)vax2.concordia.ca >I'm surprised that the 4x4 case hasn't been solved - can anyone help? >NJAS Why is this surprising? There are more than 2e13 configurations. If we could search a thousand configurations per second, considering each of them would take almost a millennium. So, someone will have to do some non-trivial theory in order to get a better handle on the diameter of the 15-puzzle. I believe the diameter of Rubik's Cube is also not known, in any of the popular metrics. -A _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

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

09 Nov '03

Jud McCranie sent in this sequence to the OEIS: %I A087725 %S A087725 0,6,31 %N A087725 Maximum number of moves required for the n X n generalization of the Fifteen Puzzle. %C A087725 a(4) >= 66, a(5) >= 114. a(3) is from Reinefeld, using the method of Korf. The lower bounds on a(4) and a(5) are from Korf and Korf & Taylor, and are unlikely to be tight. %D A087725 Richard E. Korf, Depth-First Iterative-Deeping: An Optimal Admissible Tree Search, Artificial Intelligence, 27(1), 97-110, 1985. %D A087725 Richard E. Korf and Larry A Taylor, Finding Optimal Solutions to the Twenty-Four Puzzle, Proceedings of the 11th National Conference on Artificial Intelligence, 756-761, 1993. %H A087725 Richard E. Korf, <a href="http://citeseer.nj.nec.com/cache/papers/cs/4003/http:zSzzSzwww.cs.ucla.eduz…">Home Page</a> %H A087725 Alexander Reinefeld, Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*, International Joint Conference on Artificial Intelligence, pp. 248-253, 1993. <a href="http://www.ams.org/notices/200004/fea-hales.pdf">Reinefe H A087725 Alexander Reinefeld, <a href="http://www.ams.org/notices/200004/fea-hales.pdf">Home Page</a> %H A087725 Eric Weisstein, <a href="http://mathworld.wolfram.com/15Puzzle.html">15 Puzzle in MathWorld</a> %e A087725 All solvable configurations of the Eight Puzzle on a 3x3 matrix can be solved in 31 moves or fewer, and some configurations require 31 moves, so a(3)=31. %Y A087725 Cf. A046164. %Y A087725 Adjacent sequences: A087722 A087723 A087724 this_sequence A087726 A087727 A087728 %K A087725 hard,nonn,bref,nice %O A087725 0,2 %A A087725 Jud McCranie (j.mccranie(AT)adelphia.net) Sep 30 2003 I'm surprised that the 4x4 case hasn't been solved - can anyone help? NJAS

2 1

[math-fun] Prentice Hall strikes again
by R. William Gosper 08 Nov '03

08 Nov '03

My tutoree is now in 8th grade, and, miraculously, didn't carry home another Prentice Hall "science" book. But he just got a smearox of three pages which smell familiar. Remember "The weak force is the key to the power of the Sun."? "Because of the air within it, a huge ocean liner can float on the surface of the ocean."? The ridiculous eclipse drawing that showed both limbs of Sun, moon, and Earth lying on just two straight lines? Now they're "doing" biology. Not, as Einstein prescribed, as simply as possible. Way simpler than that. Summary: the brighter and more curious the student, the more discouraged and confused this crap will leave him. Anyone getting an A on this material is a parrot who has been misled to believe s/he has learned something. I'll indent their text. P 88. 4-2 Respiration: Using the Energy in Food Green plants (autotrophs) I'm glad they cleared that up. I thought they meant photoautotrophs. make their own food. Animals (heterotrophs) eat green plants or other animals that eat green plants. Let's see, so fish eat mosquito larvae and mosquitos eat green plants. Carnivores have an agreement not to eat each other. You have learned that energy is stored in the bonds that link together atoms in foods, such as glucose. That comma makes the sentence wrong. You can think of the energy stored in food as a savings account. You eat food to add to your energy savings account. Huh?? You eat food to add to the energy stored in food? P89 During aerobic respiration, food enters the mitochondria. Burgers, fries, Ding-Dongs with taco sauce, oysters with Cool Whip, ... The food is broken down when it combines with oxygen. During this process, water and carbon dioxide are produced as waste products. Yeah, that water stuff is pretty useless. A worse greenhouse gas than CO2. But respiration produces BOTH! We must save the Earth by banning respiration. And club soda. Maybe if we could consume enough anti-oxidants ... The energy released from food during respiration is not always used right away by the cell. Often, it is stored in a chemical compound called ATP. But sometimes the cell just needs a hit of warm club soda? Basically, ATP is a chemical substance that can be used to store energy. How does a chemical store energy without becoming some other chemical? When a cell needs energy, it breaks down the ATP and uses the energy released. Is this like breaking down food? Although respiration occurs in a series of complex steps, the overall process can be written down as a word equation and as a chemical equation, as follows: Glucose + Oxygen --> Carbon Dioxide + Water + ATP (energy) or C6H12O6 + 6O2 --> 6CO2 + 6H2O + ATP Gee, I thought the P in ATP had something to due with phosphorus. But there's no phosphorous on the left side. Wow, cells can make phosphorus out of glucose. Nuclear transmutation! Notice anything familiar about the equation for respiration? You are quite right if you said it is the opposite of the equation for photosynthesis. Yeah except there's no chlorophyll in respiration and you didn't mention ATP in photosynthesis. Maybe that's what you mean by "opposite". p90 So how do anaerobic organisms get their energy? The answer is that anaerobic organisms undergo a different type of respiration, appropriately called anaerobic respiration. I'm sure glad you told me it was appropriately. Scientists use the term fermentation when they speak of anaerobic respiration. Do they mean the same thing, or does one occur during the other, or is one an example of the other, or are they just wishing they had a beer? Carbon dioxide is also the source of bubbles in alcoholic beverages such as beer and wine. But not soda? Hey, my dad's Chianti doesn't bubble. Must be some new kind of emissions control. 4-2 Section Review 2. Why are the mitochondria appropriately called the powerhouses of the cell? Beats the hell out of me, but I'm sure glad you told me it was appropriately.

19 40

[math-fun] moRe: powers of PseudoAntisymmetric (-1,0,1)- Matrices
by wouter meeussen 08 Nov '03

08 Nov '03

rehash of thread 15/08/2003, with some news. OEIS?Anum=A072148 Sequence: 2,14,92,796,7672 Definitions: pseudoAntisymmetric : T(i,j)= -T(j,i) for j<i , so T = diagonal+Antisymmetric. (my definition, forgive..) powerlength: minimal p>0 so that T^p = Identity Consider the (-1,0,1)-matrices T with properties : Det[T] not zero (invertible), all powers T^k are also invertible (-1,0,1) matrices. Properties: powerlength of T divides 12, Det[t] is 1 or -1, T is pseudoAntisymmetric, the powers T^k need not be all pseudoAntisymmetric: for 4x4 matrices, all those with 8 non-zero elements have powerlength 4, and their powers 2 and 3 are not pseudoAntisymmetric; for the 5x5 matrices, all those with 9 non-zero elements have powerlength 4, and their powers 2 and 3 are not pseudoAntisymmetric; all those with 10 non-zero elements have powerlength 12, and their powers 2,3,6,7,10 and 11 are not pseudoAntisymmetric; There is a system in this madness, but this margin is too small... W. (I owe Marc LeBrun <mlb(a)fxpt.com> for help, partial insight & lots inspiration, thanx Marc) I put the 796 4-by4 and the 7672 5-by-5 on http://users.pandora.be/Wouter.Meeussen/pseudoAntisymmMatrixPowers_4.txt http://users.pandora.be/Wouter.Meeussen/pseudoAntisymmMatrixPowers_5.txt

1 0