There are 18 moves that are hard-coded into the program (3 moves per face * 6 faces). The most straight-forward search method (test each one, then test all two consecutive moves, then test all three consecutive moves) grows exponentially. To search a 4 move depth would require 18^4, which is just over 100,000 attempts. But many of these moves would be duplicates. For example, the pattern UU would have been searched at depth 1 by U2. There are also a lot of "dumb" moves like UU', which accomplishes nothing.
So my first idea is that I'm not going to search using the 18 standard moves, but instead I'm going to think of each move as being rotation around a particular pole. If you imagine the z-axis going up the U and D faces and consider all of the distinct moves that use only those faces, there are a total of 15 different things that can be done: U, U2, U', DU, DU2, DU', D2U, D2U2, D2U', D'U, D'U2, D'U', D, D2, D'. If the next move is along one of the other two axes, it will be impossible for me to have a move that's undone. I also know that if I do something along the z-axis twice in a row, I'm going to get something redundant. So my search tree will have 45*30*30*... total algorithms to check. But I'm guaranteed not to have anything too silly in the search.
One other issue that I'm concerned about is the time it will take to search. The way this is set up, I'm searching for exactly one arrangement (the solved position). It is possible for me to decrease the search time by expanding the space of winning arrangements. Instead of looking for the solved position, I could search for any position that is within one move of being solved. In other words, teach the program to recognize the almost-solved positions as well as the solved positions. Then if it's only one move away, it doesn't need to finish searching the entire tree at that depth before finding the solution. If I do this for all 3-deep positions from being solved, I go from one winning position to 45*30*30 = 40,500 winning positions.
In order to do this, I need to basically start from a solved cube and then apply all 3-deep moves to it. Since I'll be searching cases where certain pieces might not matter, I'll probably need to include the 1-deep and 2-deep moves in the list. But I'll work on that some other day. Here's the code as it stands.
import pygame
# Global Variables
sGap = 5
bGap = 10
boxSize = 30
def posCalc(bS, sG, bG):
return bS*boxSize + sG*sGap + bG*bGap
# Define drawing data
sqPos = [ [ [posCalc(3,3,1), posCalc(0,1,0)],
[posCalc(4,4,1), posCalc(0,1,0)],
[posCalc(5,5,1), posCalc(0,1,0)],
[posCalc(3,3,1), posCalc(1,2,0)],
[posCalc(4,4,1), posCalc(1,2,0)],
[posCalc(5,5,1), posCalc(1,2,0)],
[posCalc(3,3,1), posCalc(2,3,0)],
[posCalc(4,4,1), posCalc(2,3,0)],
[posCalc(5,5,1), posCalc(2,3,0)] ],
[ [posCalc(0,1,0), posCalc(3,3,1)],
[posCalc(1,2,0), posCalc(3,3,1)],
[posCalc(2,3,0), posCalc(3,3,1)],
[posCalc(0,1,0), posCalc(4,4,1)],
[posCalc(1,2,0), posCalc(4,4,1)],
[posCalc(2,3,0), posCalc(4,4,1)],
[posCalc(0,1,0), posCalc(5,5,1)],
[posCalc(1,2,0), posCalc(5,5,1)],
[posCalc(2,3,0), posCalc(5,5,1)] ],
[ [posCalc(3,3,1), posCalc(3,3,1)],
[posCalc(4,4,1), posCalc(3,3,1)],
[posCalc(5,5,1), posCalc(3,3,1)],
[posCalc(3,3,1), posCalc(4,4,1)],
[posCalc(4,4,1), posCalc(4,4,1)],
[posCalc(5,5,1), posCalc(4,4,1)],
[posCalc(3,3,1), posCalc(5,5,1)],
[posCalc(4,4,1), posCalc(5,5,1)],
[posCalc(5,5,1), posCalc(5,5,1)] ],
[ [posCalc(6,5,2), posCalc(3,3,1)],
[posCalc(7,6,2), posCalc(3,3,1)],
[posCalc(8,7,2), posCalc(3,3,1)],
[posCalc(6,5,2), posCalc(4,4,1)],
[posCalc(7,6,2), posCalc(4,4,1)],
[posCalc(8,7,2), posCalc(4,4,1)],
[posCalc(6,5,2), posCalc(5,5,1)],
[posCalc(7,6,2), posCalc(5,5,1)],
[posCalc(8,7,2), posCalc(5,5,1)] ],
[ [posCalc(9,7,3), posCalc(3,3,1)],
[posCalc(10,8,3), posCalc(3,3,1)],
[posCalc(11,9,3), posCalc(3,3,1)],
[posCalc(9,7,3), posCalc(4,4,1)],
[posCalc(10,8,3), posCalc(4,4,1)],
[posCalc(11,9,3), posCalc(4,4,1)],
[posCalc(9,7,3), posCalc(5,5,1)],
[posCalc(10,8,3), posCalc(5,5,1)],
[posCalc(11,9,3), posCalc(5,5,1)] ],
[ [posCalc(3,3,1), posCalc(6,5,2)],
[posCalc(4,4,1), posCalc(6,5,2)],
[posCalc(5,5,1), posCalc(6,5,2)],
[posCalc(3,3,1), posCalc(7,6,2)],
[posCalc(4,4,1), posCalc(7,6,2)],
[posCalc(5,5,1), posCalc(7,6,2)],
[posCalc(3,3,1), posCalc(8,7,2)],
[posCalc(4,4,1), posCalc(8,7,2)],
[posCalc(5,5,1), posCalc(8,7,2)] ]
]
sqColor = [ [ i for ii in range(9) ] for i in range(6) ]
drawColor = [ pygame.Color(0,0,255),
pygame.Color(255,0,0),
pygame.Color(255,255,0),
pygame.Color(255,100,0),
pygame.Color(255,255,255),
pygame.Color(0,255,0),
pygame.Color(100,100,100) ]
# Initialize
pygame.init()
window1Width = posCalc(12,10,3)
window1Height = posCalc(9,8,2)
window1 = pygame.display.set_mode((window1Width,window1Height))
# Functions
def menu():
menuSelect = 0
while menuSelect == 0:
print('''
Main Menu:
(1) Free Play
(2) Set up Cube
(8) Reset Cube
(9) Quit
''')
comm = input('Select Menu Option: ')
if comm in ['1', '2', '8', '9']:
menuSelect = 1
return int(comm)
def drawIt1(window, sqPos, sqColor, drawColor):
for i in range(6):
for ii in range(9):
pygame.draw.rect(window,
drawColor[sqColor[i][ii]],
( sqPos[i][ii][0], sqPos[i][ii][1], boxSize, boxSize ),
0)
pygame.display.update()
return
def playCube(sqColor):
commands = ["U", "U2", "U'",
"L", "L2", "L'",
"F", "F2", "F'",
"R", "R2", "R'",
"B", "B2", "B'",
"D", "D2", "D'"]
commList = "U, U2, U', L, L2, L', F, F2, F', R, R2, R', B, B2, B', D, D2, D'"
comm = ""
while comm != "Q":
print("Execute which command?")
print(commList)
comm = input('Select a move or Q to quit: ' )
if comm in commands:
sqColor = permute(comm, sqColor)
drawIt1(window1, sqPos, sqColor, drawColor)
def permute(comm, sqColor):
if comm == "U":
swap4(sqColor, [0,0], [0,2], [0,8], [0,6])
swap4(sqColor, [0,1], [0,5], [0,7], [0,3])
swap4(sqColor, [4,0], [3,0], [2,0], [1,0])
swap4(sqColor, [4,1], [3,1], [2,1], [1,1])
swap4(sqColor, [4,2], [3,2], [2,2], [1,2])
elif comm == "U2":
swap2(sqColor, [0,0], [0,8])
swap2(sqColor, [0,2], [0,6])
swap2(sqColor, [0,1], [0,7])
swap2(sqColor, [0,3], [0,5])
swap2(sqColor, [1,0], [3,0])
swap2(sqColor, [1,1], [3,1])
swap2(sqColor, [1,2], [3,2])
swap2(sqColor, [2,0], [4,0])
swap2(sqColor, [2,1], [4,1])
swap2(sqColor, [2,2], [4,2])
elif comm == "U'":
swap4(sqColor, [0,0], [0,6], [0,8], [0,2])
swap4(sqColor, [0,1], [0,3], [0,7], [0,5])
swap4(sqColor, [1,0], [2,0], [3,0], [4,0])
swap4(sqColor, [1,1], [2,1], [3,1], [4,1])
swap4(sqColor, [1,2], [2,2], [3,2], [4,2])
elif comm == "L":
swap4(sqColor, [1,0], [1,2], [1,8], [1,6])
swap4(sqColor, [1,1], [1,5], [1,7], [1,3])
swap4(sqColor, [0,0], [2,0], [5,0], [4,8])
swap4(sqColor, [0,3], [2,3], [5,3], [4,5])
swap4(sqColor, [0,6], [2,6], [5,6], [4,2])
elif comm == "L2":
swap2(sqColor, [1,0], [1,8])
swap2(sqColor, [1,2], [1,6])
swap2(sqColor, [1,1], [1,7])
swap2(sqColor, [1,3], [1,5])
swap2(sqColor, [2,0], [4,8])
swap2(sqColor, [2,3], [4,5])
swap2(sqColor, [2,6], [4,2])
swap2(sqColor, [0,0], [5,0])
swap2(sqColor, [0,3], [5,3])
swap2(sqColor, [0,6], [5,6])
elif comm == "L'":
swap4(sqColor, [1,0], [1,6], [1,8], [1,2])
swap4(sqColor, [1,1], [1,3], [1,7], [1,5])
swap4(sqColor, [5,0], [2,0], [0,0], [4,8])
swap4(sqColor, [5,3], [2,3], [0,3], [4,5])
swap4(sqColor, [5,6], [2,6], [0,6], [4,2])
elif comm == "F":
swap4(sqColor, [2,0], [2,2], [2,8], [2,6])
swap4(sqColor, [2,1], [2,5], [2,7], [2,3])
swap4(sqColor, [0,6], [3,0], [5,2], [1,8])
swap4(sqColor, [0,7], [3,3], [5,1], [1,5])
swap4(sqColor, [0,8], [3,6], [5,0], [1,2])
elif comm == "F2":
swap2(sqColor, [2,0], [2,8])
swap2(sqColor, [2,2], [2,6])
swap2(sqColor, [2,1], [2,7])
swap2(sqColor, [2,3], [2,5])
swap2(sqColor, [0,6], [5,2])
swap2(sqColor, [0,7], [5,1])
swap2(sqColor, [0,8], [5,0])
swap2(sqColor, [1,8], [3,0])
swap2(sqColor, [1,5], [3,3])
swap2(sqColor, [1,2], [3,6])
elif comm == "F'":
swap4(sqColor, [2,0], [2,6], [2,8], [2,2])
swap4(sqColor, [2,1], [2,3], [2,7], [2,5])
swap4(sqColor, [0,6], [1,8], [5,2], [3,0])
swap4(sqColor, [0,7], [1,5], [5,1], [3,3])
swap4(sqColor, [0,8], [1,2], [5,0], [3,6])
elif comm == "R":
swap4(sqColor, [3,0], [3,2], [3,8], [3,6])
swap4(sqColor, [3,1], [3,5], [3,7], [3,3])
swap4(sqColor, [0,8], [4,0], [5,8], [2,8])
swap4(sqColor, [0,5], [4,3], [5,5], [2,5])
swap4(sqColor, [0,2], [4,6], [5,2], [2,2])
elif comm == "R2":
swap2(sqColor, [3,0], [3,8])
swap2(sqColor, [3,2], [3,6])
swap2(sqColor, [3,1], [3,7])
swap2(sqColor, [3,3], [3,5])
swap2(sqColor, [2,2], [4,6])
swap2(sqColor, [2,5], [4,3])
swap2(sqColor, [2,8], [4,0])
swap2(sqColor, [0,8], [5,8])
swap2(sqColor, [0,5], [5,5])
swap2(sqColor, [0,2], [5,2])
elif comm == "R'":
swap4(sqColor, [3,0], [3,6], [3,8], [3,2])
swap4(sqColor, [3,1], [3,3], [3,7], [3,5])
swap4(sqColor, [0,8], [2,8], [5,8], [4,0])
swap4(sqColor, [0,5], [2,5], [5,5], [4,3])
swap4(sqColor, [0,2], [2,2], [5,2], [4,6])
elif comm == "B":
swap4(sqColor, [4,0], [4,2], [4,8], [4,6])
swap4(sqColor, [4,1], [4,5], [4,7], [4,3])
swap4(sqColor, [0,2], [1,0], [5,6], [3,8])
swap4(sqColor, [0,1], [1,3], [5,7], [3,5])
swap4(sqColor, [0,0], [1,6], [5,8], [3,2])
elif comm == "B2":
swap2(sqColor, [4,0], [4,8])
swap2(sqColor, [4,2], [4,6])
swap2(sqColor, [4,1], [4,7])
swap2(sqColor, [4,3], [4,5])
swap2(sqColor, [0,2], [5,6])
swap2(sqColor, [0,1], [5,7])
swap2(sqColor, [0,0], [5,8])
swap2(sqColor, [1,0], [3,8])
swap2(sqColor, [1,3], [3,5])
swap2(sqColor, [1,6], [3,2])
elif comm == "B'":
swap4(sqColor, [4,0], [4,6], [4,8], [4,2])
swap4(sqColor, [4,1], [4,3], [4,7], [4,5])
swap4(sqColor, [0,2], [3,8], [5,6], [1,0])
swap4(sqColor, [0,1], [3,5], [5,7], [1,3])
swap4(sqColor, [0,0], [3,2], [5,8], [1,6])
elif comm == "D":
swap4(sqColor, [5,0], [5,2], [5,8], [5,6])
swap4(sqColor, [5,1], [5,5], [5,7], [5,3])
swap4(sqColor, [1,6], [2,6], [3,6], [4,6])
swap4(sqColor, [1,7], [2,7], [3,7], [4,7])
swap4(sqColor, [1,8], [2,8], [3,8], [4,8])
elif comm == "D2":
swap2(sqColor, [5,0], [5,8])
swap2(sqColor, [5,2], [5,6])
swap2(sqColor, [5,1], [5,7])
swap2(sqColor, [5,3], [5,5])
swap2(sqColor, [1,6], [3,6])
swap2(sqColor, [1,7], [3,7])
swap2(sqColor, [1,8], [3,8])
swap2(sqColor, [2,6], [4,6])
swap2(sqColor, [2,7], [4,7])
swap2(sqColor, [2,8], [4,8])
elif comm == "D'":
swap4(sqColor, [5,0], [5,6], [5,8], [5,2])
swap4(sqColor, [5,1], [5,3], [5,7], [5,5])
swap4(sqColor, [1,6], [4,6], [3,6], [2,6])
swap4(sqColor, [1,7], [4,7], [3,7], [2,7])
swap4(sqColor, [1,8], [4,8], [3,8], [2,8])
return sqColor
def swap4(sqColor, 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
return sqColor
def swap2(sqColor, p0, p1):
temp = sqColor[p0[0]][p0[1]]
sqColor[p0[0]][p0[1]] = sqColor[p1[0]][p1[1]]
sqColor[p1[0]][p1[1]] = temp
return sqColor
def setCube(sqColor):
done = 0
print('''
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
Use Face = -1 to quit
''')
face = input('Enter a face to change: ')
if face in ['0', '1', '2', '3', '4', '5']:
pos = input('Enter a position to chance: ')
if pos in ['0', '1', '2', '3', '4', '5', '6', '7', '8']:
color = input('Enter the color: ')
if color in ['0', '1', '2', '3', '4', '5', '6']:
face = int(face)
pos = int(pos)
color = int(color)
sqColor[face][pos] = color
elif face == '-1':
done = 1
return done, sqColor
### Main program
comm = 0
while comm != 9:
comm = menu()
print(comm)
if comm == 1:
print('Free Play!!!')
drawIt1(window1, sqPos, sqColor, drawColor)
playCube(sqColor)
elif comm == 2:
finished = 0
while finished == 0:
drawIt1(window1, sqPos, sqColor, drawColor)
finished, sqColor = setCube(sqColor)
elif comm == 8:
sqColor = [ [ i for ii in range(9) ] for i in range(6) ]
elif comm == 9:
quit()
No comments:
Post a Comment