The general situation was that I had to use two different variables to hold cube information for the search. One was supposed to be fixed (the cube configuration being solved) and one was supposed to be part of the search (perform some moves and then compare the result to the database of known solved positions). However, every time I tried to change the position on the second cube, the first one would change.
My solution to this problem was to rewrite the code for making the copy of the cube. I didn't use the deepcopy program from the link. Instead, I just created a function that would return the values of the cube and used that to copy. But even then, I had some problems. Here's the original attempt:
def copyCube( master ):
return master
newCube = copyCube( oldCube )
This didn't work. When I made changes to newCube, it still impacted the old one. So I had to create an intermediate variable that held just the values and did not actually create a reference to the original.
def copyCube( master ):
tempCube = resetCube()
for i in range(6):
for ii in range(9):
tempCube[i][ii] = master[i][ii]
return tempCube
newCube = copyCube( oldCube )
I'll have to think about fine-tuning this to see how efficient I can get it. Right now, the program is completely functional. It even has a save feature for cube positions so that they can be loaded instead of needing to type them in. There's definitely space to grow in that direction for flexibility. I also added a randomizer.
On the Raspberry Pi, I get about 15,000 checked positions per second. There's a chance of improving that by multithreading, but that's another task for another day. I first want to make the base code as efficient as possible. I made a couple other changes that might support that, which includes organizing the library in order of move length so that I can check from the middle after I've already verified that the position wasn't already closer to the beginning. I haven't implemented this, but that will give me a few percent improvement. I also need to do some timing checks to see if I can't make other parts of the algorithm more efficient. But at least for now, I've got the minimum I've needed to get a program that can search for solution algorithms. It's slow, but it works.
import pickle
import time
import random
'''
Terminology:
A "command" is one basic twist of the cube.
A "move" is some move around a single axis of the cube.
A "sequence" is an ordered collection of unflattened moves.
'''
# Global Variables
'''
sqColor[face, position] -- The current state of the cube
Faces Positions
0 0 1 2
1 2 3 4 3 4 5
5 6 7 8
0 = Blue, 1 = Red, 2 = Yellow, 3 = Orange, 4 = White, 5 = Green, 6 = Gray
Solved position:
0 0 0
0 0 0
0 0 0
1 1 1 2 2 2 3 3 3 4 4 4
1 1 1 2 2 2 3 3 3 4 4 4
1 1 1 2 2 2 3 3 3 4 4 4
5 5 5
5 5 5
5 5 5
'''
sqColor = [ [ i for ii in range(9) ] for i in range(6) ]
'''
Axis moves -- xAxis = FB / yAxis = LR / zAxis = UD
'''
xAxis = [["F"], ["F2"], ["F'"], ["B"], ["B2"], ["B'"],
["F", "B"], ["F", "B2"], ["F", "B'"],
["F2", "B"], ["F2", "B2"], ["F2", "B'"],
["F'", "B"], ["F'", "B2"], ["F'", "B'"] ]
yAxis = [["L"], ["L2"], ["L'"], ["R"], ["R2"], ["R'"],
["L", "R"], ["L", "R2"], ["L", "R'"],
["L2", "R"], ["L2", "R2"], ["L2", "R'"],
["L'", "R"], ["L'", "R2"], ["L'", "R'"] ]
zAxis = [["U"], ["U2"], ["U'"], ["D"], ["D2"], ["D'"],
["U", "D"], ["U", "D2"], ["U", "D'"],
["U2", "D"], ["U2", "D2"], ["U2", "D'"],
["U'", "D"], ["U'", "D2"], ["U'", "D'"] ]
def resetCube():
return [ [ i for ii in range(9) ] for i in range(6) ]
def copyCube( master ):
tempCube = resetCube()
for i in range(6):
for ii in range(9):
tempCube[i][ii] = master[i][ii]
return tempCube
'''
premute -- perform some move on the cube
'''
def permute(comm):
if comm == "U":
swap4([0,0], [0,2], [0,8], [0,6])
swap4([0,1], [0,5], [0,7], [0,3])
swap4([4,0], [3,0], [2,0], [1,0])
swap4([4,1], [3,1], [2,1], [1,1])
swap4([4,2], [3,2], [2,2], [1,2])
elif comm == "U2":
swap2([0,0], [0,8])
swap2([0,2], [0,6])
swap2([0,1], [0,7])
swap2([0,3], [0,5])
swap2([1,0], [3,0])
swap2([1,1], [3,1])
swap2([1,2], [3,2])
swap2([2,0], [4,0])
swap2([2,1], [4,1])
swap2([2,2], [4,2])
elif comm == "U'":
swap4([0,0], [0,6], [0,8], [0,2])
swap4([0,1], [0,3], [0,7], [0,5])
swap4([1,0], [2,0], [3,0], [4,0])
swap4([1,1], [2,1], [3,1], [4,1])
swap4([1,2], [2,2], [3,2], [4,2])
elif comm == "L":
swap4([1,0], [1,2], [1,8], [1,6])
swap4([1,1], [1,5], [1,7], [1,3])
swap4([0,0], [2,0], [5,0], [4,8])
swap4([0,3], [2,3], [5,3], [4,5])
swap4([0,6], [2,6], [5,6], [4,2])
elif comm == "L2":
swap2([1,0], [1,8])
swap2([1,2], [1,6])
swap2([1,1], [1,7])
swap2([1,3], [1,5])
swap2([2,0], [4,8])
swap2([2,3], [4,5])
swap2([2,6], [4,2])
swap2([0,0], [5,0])
swap2([0,3], [5,3])
swap2([0,6], [5,6])
elif comm == "L'":
swap4([1,0], [1,6], [1,8], [1,2])
swap4([1,1], [1,3], [1,7], [1,5])
swap4([5,0], [2,0], [0,0], [4,8])
swap4([5,3], [2,3], [0,3], [4,5])
swap4([5,6], [2,6], [0,6], [4,2])
elif comm == "F":
swap4([2,0], [2,2], [2,8], [2,6])
swap4([2,1], [2,5], [2,7], [2,3])
swap4([0,6], [3,0], [5,2], [1,8])
swap4([0,7], [3,3], [5,1], [1,5])
swap4([0,8], [3,6], [5,0], [1,2])
elif comm == "F2":
swap2([2,0], [2,8])
swap2([2,2], [2,6])
swap2([2,1], [2,7])
swap2([2,3], [2,5])
swap2([0,6], [5,2])
swap2([0,7], [5,1])
swap2([0,8], [5,0])
swap2([1,8], [3,0])
swap2([1,5], [3,3])
swap2([1,2], [3,6])
elif comm == "F'":
swap4([2,0], [2,6], [2,8], [2,2])
swap4([2,1], [2,3], [2,7], [2,5])
swap4([0,6], [1,8], [5,2], [3,0])
swap4([0,7], [1,5], [5,1], [3,3])
swap4([0,8], [1,2], [5,0], [3,6])
elif comm == "R":
swap4([3,0], [3,2], [3,8], [3,6])
swap4([3,1], [3,5], [3,7], [3,3])
swap4([0,8], [4,0], [5,8], [2,8])
swap4([0,5], [4,3], [5,5], [2,5])
swap4([0,2], [4,6], [5,2], [2,2])
elif comm == "R2":
swap2([3,0], [3,8])
swap2([3,2], [3,6])
swap2([3,1], [3,7])
swap2([3,3], [3,5])
swap2([2,2], [4,6])
swap2([2,5], [4,3])
swap2([2,8], [4,0])
swap2([0,8], [5,8])
swap2([0,5], [5,5])
swap2([0,2], [5,2])
elif comm == "R'":
swap4([3,0], [3,6], [3,8], [3,2])
swap4([3,1], [3,3], [3,7], [3,5])
swap4([0,8], [2,8], [5,8], [4,0])
swap4([0,5], [2,5], [5,5], [4,3])
swap4([0,2], [2,2], [5,2], [4,6])
elif comm == "B":
swap4([4,0], [4,2], [4,8], [4,6])
swap4([4,1], [4,5], [4,7], [4,3])
swap4([0,2], [1,0], [5,6], [3,8])
swap4([0,1], [1,3], [5,7], [3,5])
swap4([0,0], [1,6], [5,8], [3,2])
elif comm == "B2":
swap2([4,0], [4,8])
swap2([4,2], [4,6])
swap2([4,1], [4,7])
swap2([4,3], [4,5])
swap2([0,2], [5,6])
swap2([0,1], [5,7])
swap2([0,0], [5,8])
swap2([1,0], [3,8])
swap2([1,3], [3,5])
swap2([1,6], [3,2])
elif comm == "B'":
swap4([4,0], [4,6], [4,8], [4,2])
swap4([4,1], [4,3], [4,7], [4,5])
swap4([0,2], [3,8], [5,6], [1,0])
swap4([0,1], [3,5], [5,7], [1,3])
swap4([0,0], [3,2], [5,8], [1,6])
elif comm == "D":
swap4([5,0], [5,2], [5,8], [5,6])
swap4([5,1], [5,5], [5,7], [5,3])
swap4([1,6], [2,6], [3,6], [4,6])
swap4([1,7], [2,7], [3,7], [4,7])
swap4([1,8], [2,8], [3,8], [4,8])
elif comm == "D2":
swap2([5,0], [5,8])
swap2([5,2], [5,6])
swap2([5,1], [5,7])
swap2([5,3], [5,5])
swap2([1,6], [3,6])
swap2([1,7], [3,7])
swap2([1,8], [3,8])
swap2([2,6], [4,6])
swap2([2,7], [4,7])
swap2([2,8], [4,8])
elif comm == "D'":
swap4([5,0], [5,6], [5,8], [5,2])
swap4([5,1], [5,3], [5,7], [5,5])
swap4([1,6], [4,6], [3,6], [2,6])
swap4([1,7], [4,7], [3,7], [2,7])
swap4([1,8], [4,8], [3,8], [2,8])
def swap4(p0, p1, p2, p3):
temp = sqColor[p0[0]][p0[1]]
sqColor[p0[0]][p0[1]] = sqColor[p3[0]][p3[1]]
sqColor[p3[0]][p3[1]] = sqColor[p2[0]][p2[1]]
sqColor[p2[0]][p2[1]] = sqColor[p1[0]][p1[1]]
sqColor[p1[0]][p1[1]] = temp
def swap2(p0, p1):
temp = sqColor[p0[0]][p0[1]]
sqColor[p0[0]][p0[1]] = sqColor[p1[0]][p1[1]]
sqColor[p1[0]][p1[1]] = temp
'''
Apply a sequence - The sequence is not flattened
'''
def applySeq(seq):
commList = flatten(seq)
for comm in commList:
permute(comm)
def flatten(seq):
return [ item for sublist in seq for item in sublist ]
'''
Compare cube: test vs target
returns 1 if matching, 0 if not
ignores color 6 (gray)
'''
def compCube( test, target ):
for i in range(6):
for ii in [0, 1, 2, 3, 5, 6, 7, 8]:
if test[i][ii] < 6:
if test[i][ii] != target[i][ii]:
return 0
return 1
def dbCompCube( test, cubePosList ):
for i in range( len(cubePosList) ):
if i % 10000 == 0:
print(i, 'of', len(cubePosList))
if compCube( test, cubePosList[i] ) == 1:
return i
return -1
'''
Find the next sequence
Generates the "next" sequence when listed pseudo-lexicographically
A
AA
AAA
AAB
AAC
AB
ABA
ABB
ABC
Except that the letters are moves taken from the lists xAxis, yAxis, and zAxis
The search will also not pick two moves from the same axis back-to-back
Need maxLen > 1
'''
def nextSeq(seq, seqLen):
if len(seq) == 0:
seq = [ xAxis[0] ]
else:
done = 0
goBack = 0
while done == 0:
lastMove = seq[-1]
if len(seq) < seqLen and goBack == 0:
if lastMove in xAxis:
seq.append( yAxis[0] )
else:
seq.append( xAxis[0] )
done = 1
elif lastMove in xAxis:
if xAxis.index( lastMove) < len( xAxis ) - 1:
seq[-1] = xAxis[ xAxis.index( lastMove) + 1]
else:
if len( seq ) > 1:
if seq[-2] in yAxis:
seq[-1] = zAxis[0]
else:
seq[-1] = yAxis[0]
else:
seq = [ yAxis[0] ]
done = 1
elif lastMove in yAxis:
if yAxis.index( lastMove) < len( yAxis ) - 1:
seq[-1] = yAxis[ yAxis.index( lastMove) + 1]
done = 1
else:
if len( seq ) > 1:
if seq[-2] in xAxis:
seq[-1] = zAxis[0]
done = 1
else:
seq = seq[:-1]
goBack = 1
else:
seq = [ zAxis[0] ]
done = 1
elif lastMove in zAxis:
if zAxis.index( lastMove) < len( zAxis ) - 1:
seq[-1] = zAxis[ zAxis.index( lastMove) + 1]
done = 1
else:
seq = seq[:-1]
goBack = 1
if seq == [ ] and goBack == 1:
done = 1
return seq
'''
Invert move list -- this is for building solution sequences for positions
'''
def invertMoves( flatSeq ):
inverted = []
for i in range(len(flatSeq)):
j = i+1
if flatSeq[-j] == "F":
inverted.append("F'")
elif flatSeq[-j] == "F'":
inverted.append("F")
elif flatSeq[-j] == "B":
inverted.append("B'")
elif flatSeq[-j] == "B'":
inverted.append("B")
elif flatSeq[-j] == "R":
inverted.append("R'")
elif flatSeq[-j] == "R'":
inverted.append("R")
elif flatSeq[-j] == "L":
inverted.append("L'")
elif flatSeq[-j] == "L'":
inverted.append("L")
elif flatSeq[-j] == "U":
inverted.append("U'")
elif flatSeq[-j] == "U'":
inverted.append("U")
elif flatSeq[-j] == "D":
inverted.append("D'")
elif flatSeq[-j] == "D'":
inverted.append("D")
else:
inverted.append( flatSeq[-j] )
return inverted
'''
Display cube
'''
def dispCube(cube):
print()
print(" ", cube[0][0], cube[0][1], cube[0][2])
print(" ", cube[0][3], cube[0][4], cube[0][5])
print(" ", cube[0][6], cube[0][7], cube[0][8])
print()
print(cube[1][0], cube[1][1], cube[1][2], " ",
cube[2][0], cube[2][1], cube[2][2], " ",
cube[3][0], cube[3][1], cube[3][2], " ",
cube[4][0], cube[4][1], cube[4][2] )
print(cube[1][3], cube[1][4], cube[1][5], " ",
cube[2][3], cube[2][4], cube[2][5], " ",
cube[3][3], cube[3][4], cube[3][5], " ",
cube[4][3], cube[4][4], cube[4][5] )
print(cube[1][6], cube[1][7], cube[1][8], " ",
cube[2][6], cube[2][7], cube[2][8], " ",
cube[3][6], cube[3][7], cube[3][8], " ",
cube[4][6], cube[4][7], cube[4][8] )
print()
print(" ", cube[5][0], cube[5][1], cube[5][2])
print(" ", cube[5][3], cube[5][4], cube[5][5])
print(" ", cube[5][6], cube[5][7], cube[5][8])
print()
def dispGuide():
print(''' Faces Positions Colors: 0 = Blue, 1 = Red, 2 = Yellow
0 0 1 2 3 = Orange, 4 = White, 5 = Green
1 2 3 4 3 4 5 6 = Gray (ignore)
5 6 7 8
''')
def go():
exec(open("./SpeedCubeV2.py").read())
# BEGIN MAIN PROGRAM!
menu = " "
sqColor = resetCube()
testCube = resetCube()
while menu != '9':
print('''
(1) Create library pickle
(2) Load library pickle
(3) Set Cube
(4) Solve Cube
(7) Load Cube
(8) Save Cube
(9) Quit
''')
menu = input('Select Menu Option: ')
if menu == '1':
maxLen = input('Select Maximum Length: ')
if maxLen.isdigit():
curSeq = []
seqList = [ curSeq ]
cubePosList = [ sqColor ]
bookmark = [ 0 ]
maxLen = int(maxLen)
for i in range(maxLen):
bookmark.append( len( seqList) )
seqLen = i+1
done = 0
while done == 0:
if len(seqList) % 1000 == 0:
print(len(seqList), curSeq)
curSeq = nextSeq( curSeq, seqLen )
sqColor = resetCube()
if len( curSeq ) == seqLen:
applySeq( curSeq )
cubePosList.append( sqColor )
seqList.append( invertMoves( flatten( curSeq ) ) )
elif curSeq == []:
done = 1
pickle_out = open("seqList.pickle",'wb')
pickle.dump(seqList, pickle_out)
pickle_out.close()
pickle_out = open("cubePosList.pickle",'wb')
pickle.dump(cubePosList, pickle_out)
pickle_out.close()
pickle_out = open("bookmark.pickle",'wb')
pickle.dump(bookmark, pickle_out)
pickle_out.close()
elif menu == '2':
pickle_in = open("seqList.pickle",'rb')
seqList = pickle.load(pickle_in)
pickle_in.close()
pickle_in = open("cubePosList.pickle",'rb')
cubePosList = pickle.load(pickle_in)
pickle_in.close()
pickle_in = open("bookmark.pickle",'rb')
bookmark = pickle.load(pickle_in)
pickle_in.close()
elif menu == '3':
done = 0
while done == 0:
dispCube(sqColor)
dispGuide()
face = input("Select face (0-5), F for full entry, R to randomize, S to save, Q to quit: ")
if face == 'Q':
done = 1
elif face == 'S':
testCube = copyCube(sqColor)
done = 1
elif face == 'F':
sqColor = [ ['X' for i in range(9)] for ii in range(6)]
for i in range(6):
for ii in range(9):
complete = 0
while complete == 0:
dispCube(sqColor)
dispGuide()
color = input("Location "
+ str(i) + ", " + str(ii) + ": ")
if color in ['0', '1', '2', '3', '4', '5', '6']:
sqColor[i][ii] = int(color)
complete = 1
elif face == 'R':
randSeq = []
for i in range(20):
randAxis = random.randint(0,2)
if randAxis == 0:
randMove = random.randint(0,len(xAxis)-1)
randSeq.append( xAxis[randMove] )
elif randAxis == 1:
randMove = random.randint(0,len(yAxis)-1)
randSeq.append( yAxis[randMove] )
else:
randMove = random.randint(0,len(zAxis)-1)
randSeq.append( zAxis[randMove] )
applySeq( randSeq )
elif face in ['0', '1', '2', '3', '4', '5']:
face = int(face)
position = input("Select position (0-8): ")
if position in ['0', '1', '2', '3', '4', '5', '6', '7', '8']:
position = int(position)
color = input("Select color (0-6, 6 = ignore): ")
if color in ['0', '1', '2', '3', '4', '5', '6']:
sqColor[face][position] = int(color)
elif menu == '4':
print("Begin search in database")
dispCube( testCube )
solIndex = dbCompCube( testCube, cubePosList )
if solIndex > -1:
print("Solution index:", solIndex)
print("Solution:", seqList[solIndex])
else:
print("Position not found in database.")
for searchDepth in range(1,15):
print("Searching at depth", searchDepth)
testSeq = [ ]
done = 0
count = 1
while done == 0:
testSeq = nextSeq(testSeq, searchDepth)
if len( testSeq ) > 0:
print("Count:", count)
print("Trying", testSeq)
sqColor = copyCube( testCube )
applySeq( testSeq )
dispCube( sqColor )
count = count + 1
solIndex = dbCompCube( sqColor, cubePosList )
if solIndex > -1:
print("Search sequence:", testSeq)
print("Solution index:", solIndex)
print("Solution:", seqList[solIndex])
done = 1
else:
done = 1
if solIndex > -1:
break
elif menu == '7':
pickle_in = open("testCube.pickle",'rb')
testCube = pickle.load(pickle_in)
pickle_in.close()
elif menu == '8':
pickle_out = open("testCube.pickle",'wb')
pickle.dump(testCube, pickle_out)
pickle_out.close()
