[Python] Implementation of A* Solver for a 4x4x4 Pyraminx puzzle [closed]

I have to make a solver for this gui I made for a pyraminx puzzle but cant seem to get it right. I have tried many different things. When I make one move and hit solve it doesnt work but when I use the same move 2 times in a row and then hit solve it will rotate that row and solve it but make one more move. Ill prove the code so that you all can run it yourself.

import pygame
import sys
import math
import pygame_gui
import random
import copy
import heapq
import functools

# Initialize Pygame
pygame.init()

# Set up the display
WIDTH, HEIGHT = 1000, 800
screen = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption("4x4x4 Pyraminx Puzzle")

# Colors
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 0, 255)
YELLOW = (255, 255, 0)

# Color mapping
COLOR_MAP = {
'R': RED,
'G': GREEN,
'B': BLUE,
'Y': YELLOW
}

class Pyraminx:
def __init__(self):
self.reset()


def reset(self):
self.faces = [
['R'] * 16,
['G'] * 16,
['B'] * 16,
['Y'] * 16
]

def RGB(self, face, layer):
affected_faces = {
0: (1, 2), # Front affects Left and Right
}

# Define the indices for each diagonal column
RGB_indices = [
[0, 4, 7, 9, 10, 13, 15], # First row (7 triangles)
[1, 5, 8, 11, 14], # Second row (5 triangles)
[2, 6, 12], # Third row (3 triangles)
[3] # Fourth row (1 triangle)
]
row_pieces = [self.faces[face] for i in RGB_indices[layer]]
row_pieces = row_pieces[-1:] + row_pieces[:-1]
# Rotate clockwise
for i, idx in enumerate(RGB_indices[layer]):
self.faces[face][idx] = row_pieces
# Rotate the affected faces

for affected_face in affected_faces[face]:
# Rotate the row
for idx in RGB_indices[layer]:
self.faces[affected_face][idx], self.faces[face][idx] = self.faces[face][idx], self.faces[affected_face][idx]

def RGY(self, face, layer):
affected_faces = {
0: (1, 3), # Front affects Left and bottom
}

# Define the indices for each diagonal column
RGY_indices = [
[3, 6, 8, 9, 12, 14, 15], # First row (7 triangles)
[2, 5, 7, 11, 13], # Second row (5 triangles)
[1, 4, 10], # Third row (3 triangles)
[0] # Fourth row (1 triangle)
]
row_pieces = [self.faces[face] for i in RGY_indices[layer]]
row_pieces = row_pieces[-1:] + row_pieces[:-1]
# Rotate clockwise
for i, idx in enumerate(RGY_indices[layer]):
self.faces[face][idx] = row_pieces
# Rotate the affected faces

for affected_face in affected_faces[face]:
# Rotate the row
for idx in RGY_indices[layer]:
self.faces[affected_face][idx], self.faces[face][idx] = self.faces[face][idx], self.faces[affected_face][idx]

def RYB(self, face, layer):
affected_faces = {
0: (2, 3), # Front affects Right and Bottom
}

# Define the indices for each diagonal column
RYB_indices = [
[0, 1, 2, 3, 10, 11, 12], # First row (7 triangles)
[4, 5, 6, 13, 14], # Second row (5 triangles)
[7, 8, 15], # Third row (3 triangles)
[9] # Fourth row (1 triangle)
]
row_pieces = [self.faces[face] for i in RYB_indices[layer]]
row_pieces = row_pieces[-1:] + row_pieces[:-1]
# Rotate clockwise
for i, idx in enumerate(RYB_indices[layer]):
self.faces[face][idx] = row_pieces
# Rotate the affected faces

for affected_face in affected_faces[face]:
# Rotate the row
for idx in RYB_indices[layer]:
self.faces[affected_face][idx], self.faces[face][idx] = self.faces[face][idx], self.faces[affected_face][idx]

def GYB(self, face, layer):
affected_faces = {
3: (1, 2), # Bottom affects Left and Right
}

# Define the indices for each diagonal column
GYB_indices = [
[0, 4, 7, 9, 10, 13, 15], # First row (7 triangles)
[1, 5, 8, 11, 14], # Second row (5 triangles)
[2, 6, 12], # Third row (3 triangles)
[3] # Fourth row (4 triangles)
]

row_pieces = [self.faces[face] for i in GYB_indices[layer]]
row_pieces = row_pieces[-1:] + row_pieces[:-1] # Rotate clockwise

# Rotate the current face
for i, idx in enumerate(GYB_indices[layer]):
self.faces[face][idx] = row_pieces

# Define the mapping between bottom face indices and affected face indices
index_mapping = {
1: {3:9, 2: 7, 6: 8, 12:15, 1:4 , 5:5 , 8:6 , 11:13 , 14:14, 0:0, 4:1, 7:2, 9:3, 10:10, 13:11, 15:12}, # Left face
2: {3:0, 2:1, 6:4, 12:10, 1:2 , 5:5 , 8:7 , 11:11 , 14:13, 0:3, 4:6, 7:8, 9:9, 10:12, 13:14, 15:15 } # Right face
}

# Rotate the affected faces
for affected_face in affected_faces[face]:
for bottom_idx in GYB_indices[layer]:
if bottom_idx in index_mapping[affected_face]:
affected_idx = index_mapping[affected_face][bottom_idx]
self.faces[affected_face][affected_idx], self.faces[face][bottom_idx] = \
self.faces[face][bottom_idx], self.faces[affected_face][affected_idx]


def randomize(self, num_moves):
self.solution_state = copy.deepcopy(self.faces)
self.optimal_move_count = num_moves

valid_moves = [
(self.RGB, 0, 4),
(self.RGY, 0, 4),
(self.RYB, 0, 4),
(self.GYB, 3, 4)
]

for _ in range(num_moves):
move_func, face, max_layer = random.choice(valid_moves)
layer = random.randint(0, max_layer - 1)
move_func(face, layer)

def heuristic(self):
total_misplaced = 0
for face in self.faces:
color = face[0]
misplaced = sum(1 for piece in face if piece != color)
total_misplaced += misplaced
return total_misplaced // 4


def make_move(self, move_func, face, index):
move_func(face, index)

def state_difference(self, state1, state2):
return sum(sum(1 for a, b in zip(face1, face2) if a != b) for face1, face2 in zip(state1, state2))

def get_state(self):
return tuple(tuple(face) for face in self.faces)

def set_state(self, state):
self.faces = [list(face) for face in state]

def solve_astar(self):
solver = AStarSolver(self)
solution = solver.solve()
if solution:
return solution
return None

def apply_move(self, move):
move_func, face, layer = move
move_func(face, layer)


def draw_triangle(surface, color, points):
pygame.draw.polygon(surface, color, points)
pygame.draw.polygon(surface, BLACK, points, 1)

def draw_pyraminx(screen, pyraminx):
center_x, center_y = WIDTH // 2, HEIGHT // 2 + 50
size = 250

labels = ["Front", "Left", "Right", "Bottom"]
font = pygame.font.Font(None, 36)

positions = [
(center_x, center_y - size * 1), # Top
(center_x - size * 1, center_y + size * -1), # Left
(center_x + size * 1, center_y + size * -1), # Right
(center_x, center_y + size * 0.1) # Bottom
]

for face_index, face in enumerate(pyraminx.faces):
x, y = positions[face_index]

small_size = size // 4
h = small_size * math.sqrt(3) / 2

triangle_data = [
# Original triangles (pointing down)
(0, 0, False), (1, 0, False), (2, 0, False), (3, 0, False),
(0, 1, False), (1, 1, False), (2, 1, False),
(0, 2, False), (1, 2, False),
(0, 3, False),
# Additional triangles (pointing up)
(0, 0.5, True), (1, 0.5, True), (2, 0.5, True),
(0, 1.5, True), (1, 1.5, True),
(0, 2.5, True)
]

for idx, (i, j, is_up) in enumerate(triangle_data):
small_x = x + (j - (3 - i) / 2) * small_size
small_y = y + i * h

if is_up:
small_points = [
(small_x, small_y),
(small_x - small_size / 2, small_y + h),
(small_x + small_size / 2, small_y + h)
]
else:
small_points = [
(small_x, small_y + h),
(small_x - small_size / 2, small_y),
(small_x + small_size / 2, small_y)
]

color = COLOR_MAP.get(face[idx], WHITE)
draw_triangle(screen, color, small_points)

# Add labels
label = font.render(labels[face_index], True, BLACK)
label_x = x - label.get_width() // 2
label_y = y + size * 0.85
screen.blit(label, (label_x, label_y))


#A* Algorithm class
class AStarSolver:
def __init__(self, pyraminx):
self.pyraminx = pyraminx

def heuristic(self, state):
misplaced = 0
for face in state:
color = face[0]
misplaced += sum(1 for piece in face if piece != color)
return misplaced // 4

def get_possible_moves(self):
return [
(self.pyraminx.RGB, 0, layer) for layer in range(4)
] + [
(self.pyraminx.RGY, 0, layer) for layer in range(4)
] + [
(self.pyraminx.RYB, 0, layer) for layer in range(4)
] + [
(self.pyraminx.GYB, 3, layer) for layer in range(4)
]

def apply_move(self, state, move):
move_func, face, layer = move
new_state = [list(face) for face in state]
self.pyraminx.set_state(new_state)
move_func(face, layer)
return self.pyraminx.get_state()

@functools.total_ordering
class HeapEntry:
def __init__(self, f, g, path, state):
self.f = f
self.g = g
self.path = path
self.state = state

def __eq__(self, other):
return self.f == other.f

def __lt__(self, other):
return self.f < other.f

def solve(self):
initial_state = self.pyraminx.get_state()
goal_state = tuple(tuple(color * 16) for color in 'RGBY')

initial_h = self.heuristic(initial_state)
open_set = [self.HeapEntry(initial_h, 0, [], initial_state)]
closed_set = set()

while open_set:
current = heapq.heappop(open_set)
f, g, path, current_state = current.f, current.g, current.path, current.state

if current_state == goal_state:
return path

if current_state in closed_set:
continue

closed_set.add(current_state)

for move in self.get_possible_moves():
next_state = self.apply_move(current_state, move)

if next_state not in closed_set:
new_g = g + 1
new_h = self.heuristic(next_state)
new_f = new_g + new_h
new_path = path + [move]
heapq.heappush(open_set, self.HeapEntry(new_f, new_g, new_path, next_state))

return None # No solution found


# Create Pyraminx instance
pyraminx = Pyraminx()

# Initialize pygame_gui
manager = pygame_gui.UIManager((WIDTH, HEIGHT))

# Create reset button
reset_button = pygame_gui.elements.UIButton(
relative_rect=pygame.Rect((10, 10), (100, 50)),
text='Reset',
manager=manager
)

# Create text box
text_box = pygame_gui.elements.UITextBox(
html_text="",
relative_rect=pygame.Rect((10, 70), (WIDTH - 20, 90)),
manager=manager
)

randomize_input = pygame_gui.elements.UITextEntryLine(
relative_rect=pygame.Rect((120, 10), (100, 50)),
manager=manager
)

# Create randomize button
randomize_button = pygame_gui.elements.UIButton(
relative_rect=pygame.Rect((230, 10), (100, 50)),
text='Randomize',
manager=manager
)

move_counter_label = pygame_gui.elements.UILabel(
relative_rect=pygame.Rect((10, 140), (300, 50)),
text="Estimated moves to solve: 0",
manager=manager
)

solve_button = pygame_gui.elements.UIButton(
relative_rect=pygame.Rect((340, 10), (100, 50)),
text='Solve',
manager=manager
)

# Main game loop
def main():
clock = pygame.time.Clock()
solution = Nonesolution_index = 0

# Add your custom text here
# In the main function, update the custom_text variable:

custom_text = (
"4x4x4 Pyraminx Puzzle; Use the labeled keys to rotate:<br>"
"&nbsp;&nbsp;&nbsp;&nbsp;- (1-4 RBG, Q-R RGY, A-F RYB, Z-V GYB)<br>"
"&nbsp;&nbsp;&nbsp;&nbsp;Enter a number and click 'Randomize' to shuffle"
)

text_box.html_text = custom_text
text_box.rebuild()


while True:
time_delta = clock.tick(60)/1000.0

for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
elif event.type == pygame.KEYDOWN:
# Row rotations
if event.key == pygame.K_1:
pyraminx.make_move(pyraminx.RGB, 0, 0)
elif event.key == pygame.K_2:
pyraminx.make_move(pyraminx.RGB, 0, 1)
elif event.key == pygame.K_3:
pyraminx.make_move(pyraminx.RGB, 0, 2)
elif event.key == pygame.K_4:
pyraminx.make_move(pyraminx.RGB, 0, 3)
elif event.key == pygame.K_q:
pyraminx.make_move(pyraminx.RGY, 0, 0)
elif event.key == pygame.K_w:
pyraminx.make_move(pyraminx.RGY, 0, 1)
elif event.key == pygame.K_e:
pyraminx.make_move(pyraminx.RGY, 0, 2)
elif event.key == pygame.K_r:
pyraminx.make_move(pyraminx.RGY, 0, 3)
elif event.key == pygame.K_a:
pyraminx.make_move(pyraminx.RYB, 0, 0)
elif event.key == pygame.K_s:
pyraminx.make_move(pyraminx.RYB, 0, 1)
elif event.key == pygame.K_d:
pyraminx.make_move(pyraminx.RYB, 0, 2)
elif event.key == pygame.K_f:
pyraminx.make_move(pyraminx.RYB, 0, 3)
elif event.key == pygame.K_z:
pyraminx.make_move(pyraminx.GYB, 3, 0)
elif event.key == pygame.K_x:
pyraminx.make_move(pyraminx.GYB, 3, 1)
elif event.key == pygame.K_c:
pyraminx.make_move(pyraminx.GYB, 3, 2)
elif event.key == pygame.K_v:
pyraminx.make_move(pyraminx.GYB, 3, 3)


if event.type == pygame.USEREVENT:
if event.user_type == pygame_gui.UI_BUTTON_PRESSED:
if event.ui_element == reset_button:
pyraminx.reset()
solution = None
elif event.ui_element == randomize_button:
try:
num_moves = int(randomize_input.get_text())
pyraminx.randomize(num_moves)
solution = None
except ValueError:
print("Please enter a valid number of moves")
elif event.ui_element == solve_button:
solution = pyraminx.solve_astar()
solution_index = 0
if solution:
print(f"Solution found with {len(solution)} moves")
else:
print("No solution found")

manager.process_events(event)

manager.update(time_delta)

# Apply solution moves gradually
if solution and solution_index < len(solution):
pyraminx.apply_move(solution[solution_index])
solution_index += 1

# Update the move counter using the heuristic function
estimated_moves = pyraminx.heuristic()
move_counter_label.set_text(f"Estimated moves to solve: {estimated_moves}")

screen.fill(WHITE)
draw_pyraminx(screen, pyraminx)
manager.draw_ui(screen)
pygame.display.flip()


if __name__ == "__main__":
main()`


I had trouble with the reading of the new states and added a class HeapEntry within the class AStarSolver and then it read the new states properly. After that I modified apply_move to apply a move to a new state instead of the current state and I thought my heuristic function was wrong so I fixed that but still no luck.

I would like the user to be able to click solve after making move or randomizing the puzzle and the algorithm solves the puzzle.

Continue reading...