matrix_aux_for_circuit = [
[None, None, 'd', None, 'c'],
[None, "start", None, 200, 'b'],
[None, 'f', 'e', None, None],
]
starting_point_box = (1, 1) #En este caso seria la celda de fila 1 y columna 1
circuit_list = []
el punto de inicio es el de la casilla indicada con la tupla starting_point_box = (1, 1)
,
coloca en circuit_list = [] las coordenadas de este primer punto, en este caso circuit_list = [(1, 1)]
sobre ese punto intentar empezar con un movimiento horizontal (es decir sobre esa misma fila) hacia la izquierda
hasta encontrarse con un casillero que contenga un elemento que no sea None
Si sobre esa fila hacia la izquierda no encuentra ningún casillero cuyo contenido no es None,
entonces debe intentar buscar un casillero cuyo contenido no sea None hacia la derecha, y si lo encuentra guardar las coordenadas de la celda en donde lo encuentra
Si sobre esa fila hacia la izquierda encuentra algún casillero cuyo contenido no es None,
entonces guarda las coordenadas de esta celda en en circuit_list = [] , en este caso circuit_list = [(1, 1), (1, 4)]
Si ni hacia la izquierda y ni hacia la derecha de esa fila, hubiese encontrado alguna celda que tuviese un elemento que no sea None entonces imprimir "no puede formarse un circuito"
En este caso, si encontró hacia la izquierda en la casilla de coordenadas (1, 4),
y ahora como el anterior movimiento era horizontal, entonces el siguiente tendrá que ser vertical (se van alternando)
por lo que prueba primero hacia arriba, y en este caso encuentra que la celda (0, 4) tiene un elemento que no es None,
por lo que debería guardar las coordenadas en circuit_list = [(1, 1), (1, 4), (0, 4)]
pero si no hubiese encontrado ninguna celda que tenga un elemento que no sea None hacia arriba entonces tendría que haber probado buscar si hacia abajo en esa misma columna hay alguna casilla que no tenga un elemento que no sea None y guardar sus coordenadas
Si ni hacia la arriba y ni hacia la abajo de esa columna, hubiese encontrado alguna celda que tuviese un elemento que no sea None entonces imprimir "no puede formarse un circuito"
En este caso, si encontró hacia arriba en la casilla de coordenadas (0, 4),
y ahora como el anterior movimiento era vertical, entonces el siguiente tendrá que ser horizontal (se van alternando)
por lo que prueba primero hacia la izquierda de (0, 4) , pero en este caso a su izquierda no hay ningún casillero que no tenga None,
por lo que probara hacia la derecha de (0, 4) y de este modo encontraría que la casilla de coordenadas (0, 2) la cual tiene un elemento diferente de None,
por lo que guarda sus coordendas en circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2)]
En este caso, si encontro hacia la derecha en la casilla de coordenadas (0, 2),
y ahora como el anterior movimiento era horizontal, entonces el siguiente tendrá que ser vertical (se van alternando)
por lo que prueba primero hacia arriba de (0, 2) , pero en este caso hacia arriba no hay ningún casillero que no tenga None,
por lo que probara hacia abajo de (0, 2) y de este modo encontraría que la casilla de coordenadas (2, 2) la cual tiene un elemento diferente de None,
por lo que guarda sus coordenadas en circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2), (2, 2)]
En este caso, si encontró hacia abajo en la casilla de coordenadas (2, 2),
y ahora como el anterior movimiento era vertical, entonces el siguiente tendrá que ser horizontal (se van alternando)
por lo que prueba primero hacia la izquierda de (2, 2) , pero en este caso hacia su izquierda no hay ningún casillero que no tenga None,
por lo que probara hacia la derecha de (2, 2) y de este modo encontraría que la casilla de coordenadas (2, 1) la cual tiene un elemento diferente de None,
por lo que guarda sus coordenadas en circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2), (2, 2), (2, 1)]
Y como el movimiento anterior era horizontal este movimiento sera vertical,
entonces probara ir hacia arriba de (2, 1) y como logro llegar al punto de inicio (1, 1) entonces debe terminar el circuito e imprimir las coordenadas de cada una de las casillas que conforman los vértices del circuito
circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2), (2, 2), (2, 1), (1, 1)]
Si no hubiese encontrado a un casillero que no sea None hacia arriba tendría que haber probado buscarlo hacia abajo
Para solucionar este problema, puedes seguir los siguientes pasos:
- Comience en el punto de partida especificado.
- Explora horizontal y verticalmente desde cada punto para encontrar el siguiente vértice no visitado (No puede ir 2 veces seguidas en desplazamiento horizontal o 2 veces en desplazamiento vertical, pero debe alternarse).
- Añade este vértice a la lista de vértices del circuito y continúa explorando desde este nuevo vértice.
- Repite el proceso hasta que hayas encontrado al menos tres vértices adicionales y hayas regresado al punto de partida.
El tipo de algoritmo que podría resolver este problema es un algoritmo de búsqueda en grafo con restricciones específicas. Este algoritmo exploraría el espacio de posibles movimientos dentro de la matriz, asegurándose de alternar entre movimientos horizontales y verticales, y evitando visitar una celda más de una vez, excepto el punto de partida.
En este caso, una posible salida u output correcto es circuit_list = [(1, 1), (1, 4), (0, 4), (0, 2), (2, 2), (2, 1), ( 1, 1)]
, tenga en cuenta que los circuitos nunca pueden tomar el mismo cuadrado como vértice dos veces excepto el cuadrado inicial.
Este es mi código pero se traba a la mitad del trazado del circuito, quedando así [(1, 1), (2, 1), (2, 2)]
:
matrix_aux_for_circuit = [
[None, None, 'd', None, 'c'],
[None, "start", None, 200, 'b'],
[None, 'f', 'e', None, None],
]
starting_point_box = (1, 1)
circuit_list = []
def find_next_vertex(matrix, current_position, last_move):
row, col = current_position
moves = [(0, 1), (0, -1), (1, 0), (-1, 0)] # Right, Left, Down, Up
if last_move == 'horizontal':
moves = moves[2:] # Exclude vertical moves
elif last_move == 'vertical':
moves = moves[:2] # Exclude horizontal moves
for move in moves:
new_row, new_col = row + move[0], col + move[1]
if 0 <= new_row < len(matrix) and 0 <= new_col < len(matrix[0]):
if matrix[new_row][new_col] is not None:
return (new_row, new_col), move
return None, None
def traverse_circuit(matrix, start_position):
current_position = start_position
last_move = None
circuit_list.append(start_position)
while True:
next_position, move = find_next_vertex(matrix, current_position, last_move)
if next_position is None:
print("No se puede formar un circuito")
return None
circuit_list.append(next_position)
last_move = 'vertical' if move[0] != 0 else 'horizontal'
current_position = next_position
if next_position == start_position and len(circuit_list) >= 4:
break
return circuit_list
traverse_circuit(matrix_aux_for_circuit, starting_point_box)
print(circuit_list)