tag:blogger.com,1999:blog-5195188167565410449.post5408584066017567741..comments2014-03-09T17:09:45.698+00:00Comments on Haskell for Maths: How to count the number of positions of Rubik's cubeDavidAhttp://www.blogger.com/profile/16359932006803389458noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-5195188167565410449.post-11058459450945369682009-08-15T18:24:31.756+01:002009-08-15T18:24:31.756+01:00Jeremy,
Yes, you could work out the moves. Roughl...Jeremy,<br /><br />Yes, you could work out the moves. Roughly, it would go like this:<br />1. The Schreier-Sims algorithm, which is implemented in the library, but not yet explained in the blog, enables us to obtain what I've called a "tranversal generating set" for the Rubik's cube group.<br />2. Given a TGS, we can express any group element as a product of elements of the TGS.<br />3. So the only additional thing we need is to be able to express the elements of the TGS as products of the original generating set {f,b,l,r,u,d}.<br />To do this, we need a modified version of the Schreier-Sims algorithm which takes (String,Permutation a) pairs, so that it can track (in the String part), how it arrived at the TGS from the original generators.<br /><br />So we might give it a Rubik cube position, and get told that this is "flffudrllbfrudlrf", for example. I don't currently have code to do this, but it's on my todo list, so watch this space.<br />(However, I know from the literature that the solutions you find this way tend to be quite long - longer than the optimal solutions - so this may not be a practical way to solve the cube.)DavidAhttp://www.blogger.com/profile/16359932006803389458noreply@blogger.comtag:blogger.com,1999:blog-5195188167565410449.post-34369632887707208132009-08-10T11:18:51.328+01:002009-08-10T11:18:51.328+01:00So can you work out the moves that swap a pair of ...So can you work out the moves that swap a pair of corners or a pair of edges? This is pretty cool!Jeremy Gibbonshttp://www.blogger.com/profile/03945885134870183516noreply@blogger.com