From Don.Woods@eng.sun.com Mon Dec 20 19:21:46 1993 Return-Path: Received: from Sun.COM by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10335; Mon, 20 Dec 93 19:21:46 EST Received: from Eng.Sun.COM (zigzag.Eng.Sun.COM) by Sun.COM (4.1/SMI-4.1) id AA04625; Mon, 20 Dec 93 16:21:45 PST Received: from colossal.Eng.Sun.COM by Eng.Sun.COM (4.1/SMI-4.1) id AA17679; Mon, 20 Dec 93 16:20:26 PST Received: by colossal.Eng.Sun.COM (5.0/SMI-SVR4) id AA10356; Mon, 20 Dec 93 16:21:50 PST Date: Mon, 20 Dec 93 16:21:50 PST From: Don.Woods@eng.sun.com (Don Woods) Message-Id: <9312210021.AA10356@colossal.Eng.Sun.COM> To: cube-lovers@ai.mit.edu Subject: Re: Search order of Tangle Cc: jandr@xirion.nl X-Sun-Charset: US-ASCII Content-Length: 1571 > I saw the discussion of Dale and Don about the search order > (fillpattern) for rubiks tangle come by, and wondered why they both > missed an even better search order (the best?): > > Don: Dale: Jan: Equivalent to: > 1 3 5 7 9 1 2 6 10 15 1 2 5 10 17 17 16 15 14 13 > 2 4 6 8 10 3 4 7 11 16 3 4 6 11 18 18 5 4 3 12 > 11 12 13 14 15 5 8 12 17 20 7 8 9 12 19 19 6 1 2 11 > 16 17 18 19 20 9 13 18 21 23 13 14 15 16 20 20 7 8 9 10 > 21 22 23 24 25 14 19 22 24 25 21 22 23 24 25 21 22 23 24 25 I missed it on the 5x5 because my program was fast enough that I didn't look further. When I modified my program to try the 10x10 last week, I did come up with the ordering Jan suggests. It shaved about 1/3 the running time off my 5x5 search, but it actually doesn't seem to make that big a difference in the 10x10. It turns out the 10x10 search isn't quite as bad as I thought, because the tree does get trimmed rather early. When a piece is constrained on two edges, there are on average only 2/3 choices for that piece. I've got my program chugging along, and so far it has eliminated 4 of the 96 choices for piece (w/ orientation) for the upper left corner. There are 4896 choices for the first 4 points in the search order, and it's going through one choice per 25 minutes on average, so it'll finish in a mere 3 months, if I have the patience for it. (I may try to dig up some otherwise idle workstations to leave running over the holiday break.) -- Don.