rubiks.py (3987B)
1 import numpy as np 2 from operator import attrgetter 3 4 # Rubik's Cube 5 # Cubies: Individual cubes stored in 2D array ('R' = Red, 'G' = Green, 'B' = Blue) 6 # Weight: f = g + h value calculated via heuristic() and cost in solve() 7 # Move: Description of move performed (e.g. "Row 0 Left") 8 # Parent: Cube from which this cube is derived 9 class Rubiks: 10 def __init__(self, cubies, weight, move, parent): 11 self.cubies = cubies 12 self.weight = weight 13 self.move = move 14 self.parent = parent 15 16 # Print cubies as move performed to get there 17 def __str__(self): 18 return '\n'.join(['|'.join([str(cubies) for cubies in row]) for row in 19 self.cubies]) + '\nMove: ' + (self.move) 20 21 # Move Rubik's Cube by "rolling" row left or right OR column up and down 22 # E.g. R G B rolled left would be G B R 23 # and 24 # R G 25 # G rolled up would be B 26 # B R 27 def move(cubies, pos, dir): 28 29 # Duplicate cubies so that other cubes won't be altered 30 cubies = cubies.copy() 31 32 if dir == 'Left': 33 cubies[pos,:] = np.roll(cubies[pos,:], 2) 34 elif dir == 'Right': 35 cubies[pos,:] = np.roll(cubies[pos,:], -2) 36 elif dir == 'Up': 37 cubies[:,pos] = np.roll(cubies[:,pos], 2) 38 elif dir == 'Down': 39 cubies[:,pos] = np.roll(cubies[:,pos], -2) 40 41 return cubies 42 43 # Calculate h value (number of cubies out of place, i.e. Hamming distance) 44 # cost g calculated in solve() 45 def heuristic(cubies, goal): 46 h = 0 47 # If cubie not in right place add 1 to h 48 for i,j in np.ndindex(goal.shape): 49 if (cubies[i, j] != goal[i, j]): 50 h += 1 51 return h; 52 53 # Helper function to *efficiently* find move in opened/closed set 54 def find(list, key): 55 for item in list: 56 if np.array_equal(item.cubies, key.cubies): return 1 57 return 0 58 59 # A* search algorithm 60 def solve(rubiks, goal): 61 # Possible moves 62 dirs = ['Left', 'Right', 'Up', 'Down'] 63 # The A* search algorithm open priority queue 64 open = [] 65 # Start state automatically placed in closed 66 closed = [rubiks] 67 68 node = rubiks 69 70 cost = 0 71 72 # Heuristic of zero means goal state reached 73 while heuristic(node.cubies, goal) > 0: 74 cost += 1 75 76 # Generate all successors for node 77 # I.e. For row/column zero, one, or two you can move up, down, left, right 78 for dir in dirs: 79 for pos in range(np.shape(node.cubies)[0]): 80 cubies = move(node.cubies, pos, dir) 81 adjacent = Rubiks(cubies, heuristic(cubies, goal) + cost, ('Column ' 82 if dir == 'Up' or dir == 'Down' else 'Row ') + str(pos) + ' ' + dir, 83 node) 84 85 # Skip if in open or closed with lower weight 86 if find(open, adjacent) or find(closed, adjacent): 87 continue 88 89 # Else add to open 90 open.append(adjacent) 91 92 # Sort open by minimum weight 93 # Node has least weight and is popped off from open set 94 open.sort(key=lambda move: move.weight) 95 node = open.pop(0) 96 97 # If node's parent is in closed remove nodes following it, reset cost, 98 # and check open for stragglers 99 for i, c in enumerate(closed): 100 if c == node.parent: 101 closed = closed[:i + 1] 102 cost = i + 1 103 for o in open: 104 if o.parent not in closed: 105 open.pop(0) 106 107 # Add node to closed set after examining it 108 closed.append(node) 109 110 # Print moves needed to get to goal state 111 for c in closed: 112 print(c) 113 114 def main(): 115 116 # We want to get this to goal 117 start = np.array([['R', 'G', 'G'], 118 ['G', 'B', 'R'], 119 ['B', 'R', 'B']]) 120 121 122 # Here is what solved 2D Rubik's Cube looks like 123 goal = np.array([['R', 'R', 'R'], 124 ['G', 'G', 'G'], 125 ['B', 'B', 'B']]) 126 127 # Default cube will have these attributes: 128 # Cubies: start 129 # Heuristic: See heuristic() above 130 # No parent, it is the first one 131 # No move either, just call it Begin 132 rubiks = Rubiks(start, heuristic(start, goal), 'Begin', None) 133 134 # Solve the cube! 135 solve(rubiks, goal) 136 137 if __name__ == "__main__": 138 main()