Created
December 18, 2011 22:41
-
-
Save lebed2045/1494705 to your computer and use it in GitHub Desktop.
Rubik's cube NxNxN
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'''by lebedkin Alex | |
system of coordinate: | |
0X - left to right > | |
0Y - bottom to top ^ | |
0Z - front to rear . | |
''' | |
import pprint | |
from collections import deque | |
from time import clock, time | |
#size of Rubik's cube NxNxN | |
N = 2 | |
#3d array correspond to faces of Rubic's cube in the assembled state | |
cube3D = [[[0 for x in range(N+2)] for y in range(N+2)] for z in range(N+2)] | |
#each face contain NxN little colored squars | |
#tatal count of such squars are: | |
countOfSqrs = 0 | |
#list of easy turns of cube | |
generators = list() | |
xTurns = list() | |
yTurns = list() | |
zTurns = list() | |
nameOfTurn ={} | |
def faceDoesntContainFixedSqrs(cube3D,x1,y1,z1, x2,y2,z2): | |
for x in xrange(x1,x2+1): | |
for y in xrange(y1,y2+1): | |
for z in xrange(z1,z2+1): | |
if cube3D[x][y][z] == -1: | |
return False | |
return True | |
def faceZIsAbleToRorate(cube3D,Z): | |
return faceDoesntContainFixedSqrs(cube3D,0,0,Z, N+1,N+1,Z) | |
def generateAndReturnCubesItem( cube3D, x, y, z ): | |
global countOfSqrs | |
if cube3D[x][y][z] == 0: | |
countOfSqrs += 1 | |
cube3D[x][y][z] = countOfSqrs | |
return cube3D[x][y][z] | |
def numberedAllFaces(cube3D): | |
#top face | |
y = N+1 | |
for z in range(N,0,-1): | |
for x in range(1,N+1): | |
generateAndReturnCubesItem(cube3D,x,y,z) | |
#left face | |
x = 0 | |
for y in range(N,0,-1): | |
for z in range(N,0,-1): | |
generateAndReturnCubesItem(cube3D,x,y,z) | |
#front face | |
z = 0 | |
for y in range(N,0,-1): | |
for x in range(1,N+1): | |
generateAndReturnCubesItem(cube3D,x,y,z) | |
#right face | |
x = N+1 | |
for y in range(N,0,-1): | |
for z in range(1,N+1): | |
generateAndReturnCubesItem(cube3D,x,y,z) | |
#rear face | |
z = N+1 | |
for y in range(N,0,-1): | |
for x in range(N,0,-1): | |
generateAndReturnCubesItem(cube3D,x,y,z) | |
#bottom face | |
y = 0 | |
for z in range(1,N+1): | |
for x in range(1,N+1): | |
generateAndReturnCubesItem(cube3D,x,y,z) | |
def printNetOfCube(A): | |
#top face | |
print " "+(' ' * N)+" +"+('---' * N)+"-+"+(' ' * N)+" "+(' ' * N)+" " | |
y = N+1 | |
for z in range(N,0,-1): | |
print " "+(' ' * N)+" |", | |
for x in range(1,N+1): | |
print "%2d"%(A[x][y][z]), | |
print "|" | |
print "+"+('---' * N)+"-+"+('---' * N)+"-+"+('---' * N)+"-+"+('---' * N)+"-+" | |
for y in xrange(N,0,-1): | |
#left face | |
print "|", | |
for i in xrange(N): | |
print "%2d"%(A[1-1][y][N-i]), | |
#front face | |
print "|", | |
for i in xrange(N): | |
print "%2d"%(A[1+i][y][1-1]), | |
#right face | |
print "|", | |
for i in xrange(N): | |
print "%2d"%(A[N+1][y][1+i]), | |
#rear face | |
print "|", | |
for i in xrange(N): | |
print "%2d"%(A[N-i][y][N+1]), | |
print "|" | |
print "+"+('---' * N)+"-+"+('---' * N)+"-+"+('---' * N)+"-+"+('---' * N)+"-+" | |
#bottom face | |
y = 0 | |
for z in range(1,N+1): | |
print " "+(' ' * N)+" |", | |
for x in range(1,N+1): | |
print "%2d"%(A[x][y][z]), | |
print "|" | |
print " "+(' ' * N)+" +"+('---' * N)+"-+"+(' ' * N)+" "+(' ' * N)+" " | |
def printNetOfCubeCorrespondingPermutation(permutationGroupElement): | |
#sage.groups.perm_gps.permgroup_element.PermutationGroupElement | |
p = Permutation(permutationGroupElement) | |
global cube3D | |
tmp = [[[0 for x in range(N+2)] for y in range(N+2)] for z in range(N+2)] | |
#renumbered all faces of cube | |
for x in xrange(N+2): | |
for y in xrange(N+2): | |
for z in xrange(N+2): | |
if cube3D[x][y][z] == -1: | |
tmp[x][y][z] = -1 | |
elif cube3D[x][y][z] == 0: | |
tmp[x][y][z] = 0 | |
else: | |
tmp[x][y][z] = p[cube3D[x][y][z]-1] | |
printNetOfCube(tmp) | |
# generator of contrclockwise rotate in the plane Z == const | |
def makeGeneratorOfZFace(A,Z): | |
result = "" | |
#rotate in Z == const plane | |
for i in xrange(1,N+1): | |
result += "(%d,%d,%d,%d)" % ( A[i][N+1][Z], A[N+1][N-i+1][Z], A[N-i+1][1-1][Z], A[1-1][i][Z] ) | |
#if current face insn't inner face | |
if Z == 1 or Z == N: | |
if Z == 1: | |
Z = 0 | |
if Z == N: | |
Z = N+1 | |
''' | |
M - size of square | |
for example: | |
face = | |
+--------------+ | |
| 1 2 3 | | |
| 4 9 5 | | |
| 6 7 8 | | |
+--------------+ | |
M = 3, square = | |
+--------------+ | |
| 1 2 3 | | |
| 4 . 5 | | |
| 6 7 8 | | |
+--------------+ | |
M = 1, square = | |
+--------------+ | |
| . . . | | |
| . 9 . | | |
| . . . | | |
+--------------+ | |
''' | |
for M in range(N,0,-2): | |
dXY = (N - M) / 2 | |
for i in range(1,M): | |
result += "(%d,%d,%d,%d)" % (A[i+dXY][N-dXY][Z], A[N-dXY][N-i+1-dXY][Z], A[N-i+1-dXY][1+dXY][Z], A[1+dXY][i+dXY][Z] ) | |
return result | |
def turnCubeLeft(cube3D): | |
tmp = [[[0 for x in range(N+2)] for y in range(N+2)] for z in range(N+2)] | |
for x in xrange(0,N+2): | |
for y in xrange(0,N+2): | |
for z in xrange(0,N+2): | |
tmp[x][y][z] = cube3D[N+2 - z - 1][y][x] | |
return tmp | |
def turnCubeForward(cube3D): | |
tmp = [[[0 for x in range(N+2)] for y in range(N+2)] for z in range(N+2)] | |
for x in xrange(0,N+2): | |
for y in xrange(0,N+2): | |
for z in xrange(0,N+2): | |
tmp[x][y][z] = cube3D[x][z][N+2 - y - 1] | |
return tmp | |
def makeGenerators(): | |
global countOfSqrs | |
global cube3D | |
Sn = SymmetricGroup(countOfSqrs) | |
#generate | |
tempCube = cube3D | |
for z in range(1,N+1): | |
if faceZIsAbleToRorate(tempCube,z): | |
generators.append( makeGeneratorOfZFace(tempCube,z) ) | |
zTurns.append( Sn(generators[-1]) ) | |
tempCube = turnCubeLeft(tempCube) | |
for z in range(1,N+1): | |
if faceZIsAbleToRorate(tempCube,z): | |
generators.append( makeGeneratorOfZFace(tempCube,z) ) | |
xTurns.append( Sn(generators[-1]) ) | |
tempCube = turnCubeForward(tempCube) | |
for z in range(1,N+1): | |
if faceZIsAbleToRorate(tempCube,z): | |
generators.append( makeGeneratorOfZFace(tempCube,z) ) | |
yTurns.append( Sn(generators[-1]) ) | |
#name | |
counter = 0 | |
for xTurn in xTurns: | |
counter += 1 | |
nameOfTurn[xTurn] = "X%d"%counter | |
counter = 0 | |
for yTurn in yTurns: | |
counter += 1 | |
nameOfTurn[yTurn] = "Y%d"%counter | |
counter = 0 | |
for zTurn in zTurns: | |
counter += 1 | |
nameOfTurn[zTurn] = "Z%d"%counter | |
def farthestVertex(start): | |
resDistance = 0 | |
resVertex = start | |
counter = 0 | |
fivePercentCounterBarrier = 3674160 // 100 | |
d = deque() | |
d.append( start ) | |
distance = {start:0} | |
while (d): | |
current = d.popleft() | |
currentDistance = distance[current] | |
if currentDistance > resDistance: | |
resDistance = currentDistance | |
resVertex = current | |
for turn in xTurns+yTurns+zTurns: | |
#90 degree turn | |
tmp = current * turn | |
if( not tmp in distance ): | |
distance[tmp] = currentDistance + 1 | |
d.append( tmp ) | |
counter += 1 | |
#180 degree turn | |
tmp = tmp*turn | |
if( not tmp in distance ): | |
distance[tmp] = currentDistance + 1 | |
d.append( tmp ) | |
counter += 1 | |
#270 degree turn | |
tmp = tmp*turn | |
if( not tmp in distance ): | |
distance[tmp] = currentDistance + 1 | |
d.append( tmp ) | |
counter +=1 | |
#show current progress | |
if counter % fivePercentCounterBarrier < 3: | |
sys.stdout.write("\rBFS %d%% completed" % (counter // fivePercentCounterBarrier)) | |
sys.stdout.flush() | |
counter += 3 | |
print "." | |
return resVertex, resDistance | |
def diameterOfGraphOfGroup(): | |
Sn = SymmetricGroup(countOfSqrs) | |
#the identity permutation correspond the initial state of the Rubic's cube | |
E = Sn.identity() | |
V,d = farthestVertex(E) | |
return farthestVertex(V)[1] #return only distance | |
def godsNumberOfCube(): | |
Sn = SymmetricGroup(countOfSqrs) | |
return farthestVertex(Sn.identity())[1] #return only distance | |
def solveCubic( state, maxIterations = 0 ): | |
result = "" | |
start = state | |
finish = SymmetricGroup(countOfSqrs).identity() | |
d = deque() | |
d.append( start ) | |
d.append( finish ) | |
INF = 1000000 | |
distance = {} | |
distance[start] = 0 | |
distance[finish] = INF*2 | |
lastTurn = {} | |
lastTurn[start] = list(),0 | |
lastTurn[finish] = list(),0 | |
#start_time = time.clock() | |
counter = 0 | |
#Meet in the Middle | |
while (d): | |
current = d.popleft() | |
currentDistance = distance[current] | |
for turn in xTurns+yTurns+zTurns: | |
tmp = current | |
for pow in xrange(1,4): | |
tmp = tmp * turn | |
if( not tmp in distance ): | |
distance[tmp] = currentDistance + 1 | |
lastTurn[tmp] = turn,pow | |
d.append( tmp ) | |
counter += 1 | |
elif abs(distance[tmp] - currentDistance) > INF: | |
#wow! We've found edge between two components | |
fromFinish = current | |
fromStart = tmp | |
if distance[tmp] >= INF: | |
fromFinish = tmp | |
fromStart = current | |
#make path from start to fromStart | |
tmp = fromStart | |
while lastTurn[tmp][1] > 0: | |
tmpTurn,tmpPow = lastTurn[tmp] | |
result = "(" + nameOfTurn[tmpTurn]+"^" + "%d"%(tmpPow) + ")" + result | |
tmp = tmp * tmpTurn**(-tmpPow) | |
#make path from fromStart to fromFinish | |
tmp = fromStart | |
for tmpPow in xrange(1,4): | |
tmp = tmp * turn | |
if fromFinish == tmp: | |
result += "(" + nameOfTurn[turn] + "^" + "%d"%(tmpPow) + ")" | |
from time import clock, time | |
#make path from fromFinish to Finish | |
tmp = fromFinish | |
while lastTurn[tmp][1] > 0: | |
tmpTurn,tmpPow = lastTurn[tmp] | |
result = "(" + nameOfTurn[tmpTurn]+"^" + "%d"%(-tmpPow) + ")" + result | |
tmp = tmp * tmpTurn**(-tmpPow) | |
return result | |
if counter > maxIterations: | |
break | |
#if time.clock() - time_start > dtime: | |
# return "too diffcult to solve for %dsec " % dtime | |
return "Couldn't solve" | |
def main(): | |
for x in xrange(0,N+2): | |
for y in xrange(0,N+2): | |
for z in xrange(0,N+2): | |
cube3D[x][y][z] = 0 | |
if N % 2 == 0: | |
#fix the corner of cube | |
cube3D[0][1][1] = cube3D[1][0][1] = cube3D[1][1][0] = -1 | |
else: | |
#fix centers of the faces | |
cube3D[0][(N+1)//2][(N+1)//2] = -1 | |
cube3D[N+1][(N+1)//2][(N+1)//2] = -1 | |
cube3D[(N+1)//2][0][(N+1)//2] = -1 | |
cube3D[(N+1)//2][N+1][(N+1)//2] = -1 | |
cube3D[(N+1)//2][(N+1)//2][0] = -1 | |
cube3D[(N+1)//2][(N+1)//2][N+1] = -1 | |
numberedAllFaces(cube3D) | |
printNetOfCube(cube3D) | |
genetators = makeGenerators() | |
pp = pprint.PrettyPrinter(width = 70, depth=6, indent=4) | |
print "Generators of Group =" | |
pp.pprint(generators) | |
cubeGroup = PermutationGroup(generators) | |
print "Cube.order() = ", factor( cubeGroup.order() ), " = ", cubeGroup.order() | |
randomCube = cubeGroup.random_element() | |
print "random item = ", randomCube | |
printNetOfCubeCorrespondingPermutation(randomCube) | |
''' | |
E = SymmetricGroup(countOfSqrs).identity() | |
randomCube = E*xTurns[0]*xTurns[1]*yTurns[0]*yTurns[1]*zTurns[0] | |
print "cube X0 * X1 * Y0 * Y1 * Z0:" | |
printNetOfCubeCorrespondingPermutation(randomCube) | |
''' | |
orbits = cubeGroup.orbits() | |
print "orbits = ", orbits | |
#try to solve for 1 minute | |
solve = solveCubic(state = randomCube, maxIterations = 1000000) | |
print solve | |
if( N == 2 ): | |
diameter = diameterOfGraphOfGroup() | |
print "Diameter = ", diameter | |
godsNumber = godsNumberOfCube() | |
print "God's number = ", godsNumber | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment