Badeamug at 04:25, 12 October 2010

2010-10-12T04:25:41Z

New page

== Pyraminx Analysis Using Matlab ==
=== By: Peter Badea ===

This article will attempt to guide the reader through an analysis of the number of possible permutations of a Pyraminx puzzle (see [http://en.wikipedia.org/wiki/Pyraminx Pyraminx]):

[[Image:10-1100-Peter-pyraminx.jpg]]
----
Please Note: It has come to my attention that Mr. Charles Tsang has also posted an analysis of the Pyraminx problem. This is an unfortunate coincidence that was only observed after the problem had been solved. A quick glance at the very different program code (and even program used) will surely lead any reader to this conclusion. His solution can be found [http://katlas.math.toronto.edu/drorbn/index.php?title=10-1100/Assignment_1_Part_1_by_Charles here].

----
As can be seen above, this puzzle is similar to that of the Rubik's cube except for the differing shape (that of a tetrahedron as opposed to a cube). Each side is an equilateral triangle composed of 9 smaller equilateral triangles all joined in the fashion shown below:

[[Image:10-1100-Peter-pyramix_map.jpg]]

The labeling shown above is important to understand the meaning of each permutation expressed in standard notation. To apply the the Schreier–Sims algorithm to this problem, a set of generators must first be found. These can be expressed as the 8 rotations (about each of 4 vertices) that involve rotating either only the vertex piece (4 trivial rotations) or 2 (of the total 3) rows of pieces.

A recursive function for feeding each permutation into the table T is then constructed in Matlab:

function Tnew = feed(s,T)

j2 = 0;
Tnew = T;

%find pivot point
for i2 = 1:36
if s(i2) ~= i2
j2 = s(i2);
break
end
end

if j2 ~= 0 %s is not identity permutation
if T(1,i2,j2) == 0 %empty box
Tnew(:,i2,j2) = s;
else %T(1,i2,j2) ~= 0; non-empty box
for k2 = 1:36 %define t inverse, where t is the permutation currently in the box
tInv(k2) = find(T(:,i2,j2) == k2);
end

for k2 = 1:36 %define t inverse * s
tInvs(k2) = tInv(s(k2));
end

%feed t inverse * s
Tnew = feed(tInvs,T);
end

end

Using this function, the Schreier–Sims algorithm is then implemented in Matlab in the following way:

clear
clc

T = zeros(36,36,36);

%initialize T
for i = 1:36
T(:,i,i) = ones(36,1);
end

Tnew = T;

%generators
s1 = 1:36;
s1([1,26,36]) = [26,36,1];

s2 = 1:36;
s2([5,10,11]) = [10,11,5];

s3 = 1:36;
s3([9,15,16]) = [15,16,9];

s4 = 1:36;
s4([30,31,32]) = [31,32,30];

s5 = 1:36;
s5([2,3,4,17,25,27,28,34,35]) = [28,27,17,34,2,35,25,4,3];

s6 = 1:36;
s6([2,6,7,12,13,17,18,19,20]) = [13,12,20,18,19,7,6,2,17];

s7 = 1:36;
s7([4,7,8,13,14,22,23,24,25]) = [13,22,14,23,24,25,4,8,7];

s8 = 1:36;
s8([19,20,21,22,23,28,29,33,34]) = [22,23,33,34,28,20,21,29,19];

%feed generators into Tnew
Tnew = feed(s1,Tnew);
Tnew = feed(s2,Tnew);
Tnew = feed(s3,Tnew);
Tnew = feed(s4,Tnew);
Tnew = feed(s5,Tnew);
Tnew = feed(s6,Tnew);
Tnew = feed(s7,Tnew);
Tnew = feed(s8,Tnew);

while length(find(Tnew ~= T)) ~= 0 %while table is still changing
T = Tnew;
for i = 1:35
for j = i+1:36
for k = 1:35
for l = k+1:36
if T(1,i,j) ~= 0 & T(1,k,l) ~= 0
Tnew = feed(T(T(:,k,l),i,j),Tnew);
end
end
end
end
end
end

ord = 1;

for i = 1:36
ord = ord * length(find(T(1,i,:)));
end

disp(['Order = ',num2str(ord)])

for i = 1:36
for j = 1:36
if T(1,i,j) ~= 0
plot(i,j,'+')
hold on
axis equal
end
end
end

The above code yields the following result:
Order = 75582720

Graphing the values where the table T is non-zero yields the following graph:
[[Image:10-1100-Peter-pyramix_matrix.jpg]]

If we then change the code slightly to disallow turning of the 4 vertex pieces (the trivial rotations), we get a different result:
Order = 933120

This is a more accurate description of the difficulty that solving such a puzzle would entail due to the fact that the 4 vertex pieces may always be turned at the very end, and no particular strategy needs to be employed in placing them.

10-1100/Assignment 1 Part 1 by Peter - Revision history

Badeamug at 04:25, 12 October 2010