User:Tholden/11-1100/Homework Part 1 - Revision history

Tholden: /* 2x2x2 Rubik's cube */

2011-10-10T18:43:31Z

2x2x2 Rubik's cube

← Older revision		Revision as of 14:43, 10 October 2011
Line 183:		Line 183:
	Using the supplied files, the code can be executed as follows:		Using the supplied files, the code can be executed as follows:

			>> SimpleCube2
	>> tic; [table,tabLogic] = NonComGaussElim(myPerms); toc		>> tic; [table,tabLogic] = NonComGaussElim(myPerms); toc
	Elapsed time is 4.016460 seconds.		Elapsed time is 4.016460 seconds.

Tholden: /* Megaminx */

2011-10-10T18:30:41Z

Megaminx

← Older revision		Revision as of 14:30, 10 October 2011
Line 212:		Line 212:
	*<math> g_{12} =(122\ 126\ 132\ 130\ 123)(125\ 129\ 131\ 127\ 124)(67\ 78\ 89\ 100\ 111)(70\ 81\ 92\ 103\ 114)(71\ 82\ 93\ 104\ 115)</math>		*<math> g_{12} =(122\ 126\ 132\ 130\ 123)(125\ 129\ 131\ 127\ 124)(67\ 78\ 89\ 100\ 111)(70\ 81\ 92\ 103\ 114)(71\ 82\ 93\ 104\ 115)</math>

	As of writing this article, the algorithm has yet to converge. However, there are partial results that we can state. In particular, on four generators, the size of the group is the order of <math> 1.9 \times 10^{57} </math>.		As of writing this article, the algorithm has yet to converge. However, there are partial results that we can state. In particular, on four generators, the size of the group is the order of <math> 1.9 \times 10^{57} </math>. This was done using the code
			>>Dodecahedron2
			>>subPerms = myPerms(1:4);
			>> tic; [table,tabLogic] = NonComGaussElim(subPerms); toc
			Elapsed time is 1153.4619 seconds

Tholden: /* Megaminx */

2011-10-10T18:28:52Z

Megaminx

← Older revision		Revision as of 14:28, 10 October 2011
Line 192:		Line 192:

	==Megaminx==		==Megaminx==

			[[Image:Megaminx.jpg\|thumb\|right\|alt=The Megaminx permutation puzzle in a solved state. \|The Megaminx Permutation Puzzle.]]

			The Megaminx is an advanced but conceptually related cousin of the Rubik's cube. However, the polyhedron on which this puzzle is situated is not a cube, but is instead a dodecahedron. Consequently, this puzzle has twelve (12) faces and each face has a star configuration. The star configuration imparts eleven (11) stickers per face, meaning that this puzzle forms a subgroup of <math> S_{132} </math> which has order <math> 132! </math>.

			The sticker numbering for the Dodecahedron has been done by rendering a [http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/MegaminxNumbering.gif three-dimensional image of the dodecahedron.] With this numbering convention, the generators of the Megaminx group are given by

			*<math> g_1 =(1\ 5\ 11\ 9\ 2)(4\ 8\ 10\ 6\ 3)(20\ 64\ 53\ 42\ 31)(21\ 65\ 54\ 43\ 32)(22\ 66\ 55\ 44\ 35)</math>
			*<math> g_2 =(12\ 16\ 22\ 20\ 13)(15\ 19\ 21\ 17\ 14)(\ 1\ 33\ 86\ 68\ 57)(3\ 30\ 87\ 72\ 61)(2\ 27\ 88\ 75\ 64)</math>
			*<math> g_3 =(23\ 27\ 33\ 31\ 24)(26\ 30\ 32\ 28\ 25)(2\ 44\ 97\ 79\ 13)(6\ 41\ 98\ 83\ 17)(9\ 38\ 99\ 86\ 20)</math>
			*<math> g_4 =(34\ 38\ 44\ 42\ 35)(37\ 41\ 43\ 39\ 36)(9\ 55\ 108\ 90\ 24 )(10\ 52\ 109\ 94\ 28)(11\ 49\ 110\ 97\ 31)</math>
			*<math> g_5 =(45\ 49\ 55\ 53\ 46)(48\ 52\ 54\ 50\ 47)(5\ 60\ 121\ 108\ 42)(8\ 63\ 120\ 105\ 39)(11\ 66\ 119\ 101\ 35)</math>
			*<math> g_6 =(56\ 60\ 66\ 64\ 57)(59\ 63\ 65\ 61\ 58)(1\ 16\ 77\ 119\ 53)(4\ 19\ 76\ 116\ 50)(5\ 22\ 75\ 112\ 46)</math>
			*<math> g_7 =(67\ 71\ 77\ 75\ 68)(70\ 74\ 76\ 72\ 69)(12\ 82\ 130\ 112\ 57)(15\ 85\ 127\ 113\ 58)(16\ 88\ 123\ 111\ 56)</math>
			*<math> g_8 =(78\ 82\ 88\ 86\ 79)(81\ 85\ 87\ 83\ 80)(13\ 23\ 93\ 123\ 68)(14\ 26\ 96\ 124\ 69)(12\ 27\ 99\ 122\ 67)</math>
			*<math> g_9 =(89\ 93\ 99\ 97\ 90)(92\ 96\ 98\ 94\ 91)(24\ 34\ 104\ 122\ 79)(25\ 37\ 107\ 125\ 80)(23\ 38\ 110\ 126\ 78)</math>
			*<math> g_{10} =(100\ 104\ 110\ 108\ 101)(103\ 107\ 109\ 105\ 102)(35\ 45\ 115\ 126\ 90)(36\ 48\ 118\ 129\ 91)(34\ 49\ 121\ 132\ 89)</math>
			*<math> g_{11} =(111\ 115\ 121\ 119\ 112)(114\ 118\ 120\ 116\ 113)(46\ 56\ 71\ 132\ 101)(47\ 59\ 74\ 131\ 102)(45\ 60\ 77\ 130\ 100)</math>
			*<math> g_{12} =(122\ 126\ 132\ 130\ 123)(125\ 129\ 131\ 127\ 124)(67\ 78\ 89\ 100\ 111)(70\ 81\ 92\ 103\ 114)(71\ 82\ 93\ 104\ 115)</math>

			As of writing this article, the algorithm has yet to converge. However, there are partial results that we can state. In particular, on four generators, the size of the group is the order of <math> 1.9 \times 10^{57} </math>.

Tholden: /* 2x2x2 Rubik's cube */

2011-10-10T17:47:41Z

2x2x2 Rubik's cube

@@ Line 180: / Line 180: @@
 * <math> g_5 = (17\ 18\ 20\ 19) (22\ 16\ 12\ 3)(24\ 15\ 10\ 4) </math>
 * <math> g_6 = (21\ 23\ 24\ 22)(14\ 20\ 4\ 6)(16\ 18\ 2\ 8) </math>
 ==Megaminx==

Tholden: /* $2 \times 2 \times 2$ Rubik's cube */

2011-10-10T17:42:48Z

<math> 2 \times 2 \times 2 </math> Rubik's cube

← Older revision		Revision as of 13:42, 10 October 2011
Line 165:		Line 165:


	==~~<math>~~ ~~2 \times 2 \times 2 </math>~~ Rubik's cube==		== 2x2x2 Rubik's cube==

	[[Image:2x2x2CubeSmall.jpg\|thumb\|right\|alt=A picture of the 2x2x2 Rubik's cube.\|The 2x2x2 Rubik's cube.]]		[[Image:2x2x2CubeSmall.jpg\|thumb\|right\|alt=A picture of the 2x2x2 Rubik's cube.\|The 2x2x2 Rubik's cube.]]

Tholden: /* $2 \times 2 \times 2$ Rubik's cube */

2011-10-10T17:42:23Z

<math> 2 \times 2 \times 2 </math> Rubik's cube

← Older revision		Revision as of 13:42, 10 October 2011
Line 166:		Line 166:

	==<math> 2 \times 2 \times 2 </math> Rubik's cube==		==<math> 2 \times 2 \times 2 </math> Rubik's cube==

			[[Image:2x2x2CubeSmall.jpg\|thumb\|right\|alt=A picture of the 2x2x2 Rubik's cube.\|The 2x2x2 Rubik's cube.]]

			The <math> 2 \times 2 \times 2 </math> Rubik's cube is a simplified version of the classical Rubik's cube. Indeed, while this simplified Rubik's cube still has six faces, each face only has four stickers. This greatly simplifies the process of analyzing the subgroup generated by this problem. We note that there are a total of <math> 24 </math> stickers on this cube, so that the generators a subgroup of <math> S_{24} </math> which has order <math> 24! </math>.

			To determine our sticker numbering, we have rendered a [http://individual.utoronto.ca/tholden/CourseNotes/AlgebraWikiCode/RotatingCube.gif three-dimensional image of the cube], the source code for which can be found on my [[User:Tholden/11-1100/File Repository\|file repository]].

			Using the numbering scheme given in the rendered image of the cube, our generators can be given in cycle notation as
			* <math> g_1 = (1\ 3\ 4\ 2) (22\ 6\ 9\ 17) (21\ 5\ 10\ 18) </math>
			* <math> g_2 = (5\ 6\ 8\ 7) (21\ 14\ 11\ 1) (23\ 13\ 9\ 2) </math>
			* <math> g_3 = (9\ 11\ 12\ 10) (3\ 5\ 13\ 19) ( 1\ 7\ 15\ 17) </math>
			* <math> g_4 = (13\ 15\ 16\ 14) (24\ 8\ 11\ 19) (23\ 7\ 12\ 20) </math>
			* <math> g_5 = (17\ 18\ 20\ 19) (22\ 16\ 12\ 3)(24\ 15\ 10\ 4) </math>
			* <math> g_6 = (21\ 23\ 24\ 22)(14\ 20\ 4\ 6)(16\ 18\ 2\ 8) </math>

	==Megaminx==		==Megaminx==

Tholden at 16:27, 10 October 2011

2011-10-10T16:27:25Z

Show changes

Tholden at 15:56, 10 October 2011

2011-10-10T15:56:00Z

New page

This page showcases my work done in implementing the Non-Commutative Gaussian Elimination algorithm with direct application to solving a permutation puzzle. I would like it to be known that I had originally chosen the Megaminx puzzle and am still in the process of solving it. The algorithm is currently running on a Sun x4600 computational server using Matlab 2010b including eight Opteron 8212 processors with 32 GB of memory. However, the algorithm is not conducive to parallelization and so has yet to converge. As a test-case, I have solved the <math> 2 \times 2 \times 2 </math> Rubik's cube, which I will also present here. In the event that the algorithm has not converged, I will submit the <math> 2 \times 2 \times 2 </math> Rubik's cube for marking.

==Theoretical Review of the Algorithm==

The purpose of Non-Commutative Gaussian Elimination (NCGE) is to find the elements and order of a subgroup generated by a finite set of generators. The algorithm proceeds as follows:

Let <math>G = \langle g_1,\ldots, g_\alpha \rangle</math>. Define the pivot of <math>\sigma \in S_n</math> to be the minimal <math>k \in \mathbb N</math> such that <math>\sigma(k) \neq k</math>. We prepare a table which is mostly empty

[[Image:NCGETable1.jpg|thumb|right|alt=The table initialization for Non-Commutative Gaussian Elimination.|A mostly empty table for Gaussian Elimination]]

Feed <math>g_1, \ldots, g_n</math> in order. To feed a non-identity <math>\sigma</math>, find its pivotal position <math>i</math> and let <math>j = \sigma(i)</math>.
\begin{enumerate}
\item
If box <math>(i,j)</math> is empty, put <math>\sigma</math> in this box.
\item
If box <math>(i,j)</math> is not-empty, feed <math>\sigma' = \sigma_{i,j}^{-1} \sigma</math> into the table.
\end{enumerate}

==Matlab Implementation ==

==<math> 2 \times 2 \times 2 </math> Rubik's cube==

==Megaminx==

User:Tholden/11-1100/Homework Part 1 - Revision history

Tholden: /* 2x2x2 Rubik's cube */

Tholden: /* Megaminx */

Tholden: /* Megaminx */

Tholden: /* 2x2x2 Rubik's cube */

Tholden: /* 2 \times 2 \times 2 Rubik's cube */

Tholden: /* 2 \times 2 \times 2 Rubik's cube */

Tholden at 16:27, 10 October 2011

Tholden at 15:56, 10 October 2011

Tholden: /* $2 \times 2 \times 2$ Rubik's cube */

Tholden: /* $2 \times 2 \times 2$ Rubik's cube */