Simulador del Knight's Tour

Bienvenido al simulador del Knight's Tour, un recorrido en el que el caballo de ajedrez debe visitar cada casilla de un tablero exactamente una vez. Este problema, conocido desde hace siglos, ha fascinado a matemáticos y entusiastas del ajedrez debido a su dificultad y a las estrategias únicas necesarias para resolverlo.

Usa este simulador para visualizar cómo se mueve el caballo a través del tablero, experimenta con diferentes tamaños de tablero y observa las rutas predefinidas.

Algoritmo utilizado

      from grafo import Grafo

      def knight_tour(n):
          grafo = Grafo()
          rellenar_grafo(grafo, n)
      
          return camino_hamiltoniano(grafo)
      
      def rellenar_grafo(grafo: Grafo, n):
          # Crear tablero
          for i in range(n):
              for j in range(n):
                  grafo.agregar_vertice((i, j))
      
          # Aristas
          for v in grafo.obtener_vertices():
              fil = v[0]
              col = v[1]
                  
              # movimientos arriba y abajo
              if fil >= 2: #puede subir largo
                  if col > 0: #puede izq corto
                      if not grafo.estan_unidos(v, (fil-2, col-1)):
                          grafo.agregar_arista(v, (fil-2, col-1))
                  if col < n-1: #puede der corto
                      if not grafo.estan_unidos(v, (fil-2, col+1)):
                          grafo.agregar_arista(v, (fil-2, col+1))
      
              if fil < n-2: #puede bajar largo
                  if col > 0: #puede izq corto
                      if not grafo.estan_unidos(v, (fil+2, col-1)):
                          grafo.agregar_arista(v, (fil+2, col-1))
                  if col < n-1: #puede der corto
                      if not grafo.estan_unidos(v, (fil+2, col+1)):
                          grafo.agregar_arista(v, (fil+2, col+1))
      
              # movimientos izq y der
              if col > 2: #puede izq largo
                  if fil < n-1: #puede abajo corto
                      if not grafo.estan_unidos(v, (fil+1, col-2)):
                          grafo.agregar_arista(v, (fil+1, col-2))
                  if fil > 0: #puede arriba corto
                      if not grafo.estan_unidos(v, (fil-1, col-2)):
                          grafo.agregar_arista(v, (fil-1, col-2))
              
              if col < n-2: #puede der largo
                  if fil < n-1: #puede abajo corto
                      if not grafo.estan_unidos(v, (fil+1, col+2)):
                          grafo.agregar_arista(v, (fil+1, col+2))
                  if fil > 0: #puede arriba corto
                      if not grafo.estan_unidos(v, (fil-1, col+2)):
                          grafo.agregar_arista(v, (fil-1, col+2))
          
      
      def camino_hamiltoniano(grafo: Grafo):
          visitados = set()
          camino = []
      
          for v in grafo.obtener_vertices():
              if v not in visitados:
                  if camino_hamiltoniano_dfs(grafo, v, visitados, camino):
                      return camino
                  
          return camino
      
      def camino_hamiltoniano_dfs(grafo: Grafo, v, visitados: set, camino: list):
          visitados.add(v)
          camino.append(v)
      
          if len(grafo.obtener_vertices()) == len(camino):
              return True
      
          for w in grafo.adyacentes(v):
              if w not in visitados:
                  if camino_hamiltoniano_dfs(grafo, w, visitados, camino):
                      return True
          camino.pop()
          visitados.remove(v)
          return False