Алгоритм поиска случайного гамильтонова пути в сетке?

Прежде всего, алгоритм, отображаемый на вашем изображении из файла pdf, не является решением проблемы пути Гамильтона, а решением генерации лабиринта, поскольку конечный путь имеет несколько ветвей.

Чтобы найти алгоритмы для создания лабиринта, см .: https://en.wikipedia.org/wiki/Maze_generation_algorithm

O-O-O-O-O
| | | | |
O-O-O-O-O
| | | | |
O-O-O-O-O
| | | | |
O-O-O-O-O

O-O-O-O-O
|
O-O-O-O-O
        |
O-O-O-O-O
|        
O-O-O-O-O

O-O-O-O-O
|        
O-OXO-O-O
        |
O-OXO-O-O
|        
O-O-O-O-O

O-O-O-O-O
|        
O-OXO-O-O
        |
O-OXOxO-O
|        
O-O-OxO-O

O-O-O-O-O
|        
O-O O-O-O
  | |   |
O-O OxO-O
|        
O-O-OxO-O

O-O-O-O-O
|        
O-O O-O-O
  | |   |
O-O O O-O
|   | |  
O-O-O O-O

O-O-O-O-O
        |
O-O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

|
v
O-O-O-O-O
        |
O-O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

  O-O-O-O-O
          |
->O-O-O-O O
  |     | |
  O O-O O O
  |   | | |
  O-O-O O-O

O-O-O-O-O
        |
OXO-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

O-O-O-O-O
|       |
O O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

Вот весь алгоритм на Python. Вы можете запустить его здесь: http://www.compileonline.com/execute_python3_online.php

Результат сохраняется в массиве (self.gameGrid), который регистрируется дважды (со стрелками, узлами и линиями). Первые два склеенных ребра называются перестановкой, а вторые - пересечением.

#!/usr/local/bin/python3

import random

class CellRoom:

  def generateGame(self):
    ## Constants
    self.UNDEFINED = 0
    self.FROM_NOWHERE = 1
    self.FROM_NORTH = 2
    self.FROM_EAST = 3
    self.FROM_SOUTH = 4
    self.FROM_WEST = 5

    self.LEFT = 0
    self.RIGHT = 1

    self.GAME_WIDTH = random.randint(3, 20)
    self.GAME_HEIGHT = random.randint(3, 20)

    self.initGame()

    for i in range(100):
      self.permutate()

    ##self.logGameWithPath()
    ##self.logGameWithArrow()
    for i in range(50):
      self.start = self.moveExtremity(self.start)
    self.logGameWithPath()
    self.logGameWithArrow()
    self.verifyGame()

  ## Print the map of the game on the standard output.
  ## Do not show the orientation.
  def logGameWithPath(self):
    print ('game width: ' + str(self.GAME_WIDTH))
    print ('game height: ' + str(self.GAME_HEIGHT))
    print ('Start [x=' + str(self.start[1]) + ', y=' + str(self.start[0]) + ']')

    gameText = ''

    for i in range(len(self.gameGrid)):
      for j in range(len(self.gameGrid[i])):
        if (self.gameGrid[i][j] == self.FROM_NORTH) or ((i > 0) and (self.gameGrid[i - 1][j] == self.FROM_SOUTH)):
          gameText = gameText + ' |'
        else:
          gameText = gameText + '  '
      gameText = gameText + ' \n'
      for j in range(len(self.gameGrid[i])):
        if (self.gameGrid[i][j] == self.FROM_WEST) or ((j > 0) and (self.gameGrid[i][j - 1] == self.FROM_EAST)):
          gameText = gameText + '-O'
        else:
          gameText = gameText + ' O'
      gameText = gameText + ' \n'

    for j in range(len(self.gameGrid[i])):
      gameText = gameText + '  '
    gameText = gameText + ' \n'

    print (gameText)

  ## Print the map of the game on the standard output.
  ## It shows the orientation.
  def logGameWithArrow(self):
    gameText = ''

    for gameLine in self.gameGrid:
      for j in gameLine:
        if j == self.FROM_NOWHERE:
          gameText = gameText + 'X'
        elif j == self.FROM_NORTH:
          gameText = gameText + 'V'
        elif j == self.FROM_EAST:
          gameText = gameText + '('
        elif j == self.FROM_SOUTH:
          gameText = gameText + '^'
        elif j == self.FROM_WEST:
          gameText = gameText + ')'
      gameText = gameText + '\n'

    print (gameText)

  ## Generate a new map with an extremity (ex. start point) at another place.
  ## It receives and returns a valid map.
  def moveExtremity(self, extremity):
    ## Search the points.
    possibleNewOrigins = []
    if ((extremity[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[extremity[0] + 1][extremity[1]] != self.FROM_NORTH)):
      possibleNewOrigins.append(self.FROM_NORTH)
      besidePoint = [extremity[0] + 1, extremity[1]]
    elif ((extremity[1] > 0) and (self.gameGrid[extremity[0]][extremity[1] - 1] != self.FROM_EAST)):
      possibleNewOrigins.append(self.FROM_EAST)
      besidePoint = [extremity[0], extremity[1] - 1]
    elif ((extremity[0] > 0) and (self.gameGrid[extremity[0] - 1][extremity[1]] != self.FROM_SOUTH)):
      possibleNewOrigins.append(self.FROM_SOUTH)
      besidePoint = [extremity[0] - 1, extremity[1]]
    elif ((extremity[1] < self.GAME_WIDTH - 1) and (self.gameGrid[extremity[0]][extremity[1] + 1] != self.FROM_WEST)):
      possibleNewOrigins.append(self.FROM_WEST)
      besidePoint = [extremity[0], extremity[1] + 1]

    besidePointNewOrigin = possibleNewOrigins[random.randint(0, len(possibleNewOrigins) - 1)]

    if besidePointNewOrigin == self.FROM_NORTH:
      besidePoint = [extremity[0] + 1, extremity[1]]
    elif besidePointNewOrigin == self.FROM_EAST:
      besidePoint = [extremity[0], extremity[1] - 1]
    elif besidePointNewOrigin == self.FROM_SOUTH:
      besidePoint = [extremity[0] - 1, extremity[1]]
    elif besidePointNewOrigin == self.FROM_WEST:
      besidePoint = [extremity[0], extremity[1] + 1]

    ##print ('New start: [' + str(extremity[0]) + ', ' + str(extremity[1]) + ']')
    ##print ('besidePoint: [' + str(besidePoint[0]) + ', ' + str(besidePoint[1]) + ']')

    ## Search the new extremity
    if self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_NORTH:
      newExtremity = [besidePoint[0] - 1, besidePoint[1]]
    elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_EAST:
      newExtremity = [besidePoint[0], besidePoint[1] + 1]
    elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_SOUTH:
      newExtremity = [besidePoint[0] + 1, besidePoint[1]]
    elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_WEST:
      newExtremity = [besidePoint[0], besidePoint[1] - 1]

    ## Do the move.
    self.reversePath(extremity, newExtremity)

    self.gameGrid[besidePoint[0]][besidePoint[1]] = besidePointNewOrigin
    self.gameGrid[newExtremity[0]][newExtremity[1]] = self.FROM_NOWHERE
    ##print ('extremity: [' + str(newExtremity[0]) + ', ' + str(newExtremity[1]) + ']')

    return newExtremity

  ## Rewrite the path on the map as the end was the start and vice versa.
  ## The end becomes undefined.
  def reversePath(self, start, end):
    currentPoint = start
    ##print ('start: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
    ##print ('end: [' + str(end[0]) + ', ' + str(end[1]) + ']')
    while (currentPoint[0] != end[0]) or (currentPoint[1] != end[1]):
      ##print ('currentPoint: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
      ## We search the next point, not the point we just have reversed
      if (currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.FROM_NORTH) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_SOUTH):
        self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_SOUTH
        currentPoint[0] = currentPoint[0] + 1
      elif (currentPoint[1] > 0) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.FROM_EAST) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_WEST):
        self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_WEST
        currentPoint[1] = currentPoint[1] - 1
      elif (currentPoint[0] > 0) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.FROM_SOUTH) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_NORTH):
        self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_NORTH
        currentPoint[0] = currentPoint[0] - 1
      elif (currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.FROM_WEST) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_EAST):
        self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_EAST
        currentPoint[1] = currentPoint[1] + 1
    ##print ('reversePath: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
    self.gameGrid[currentPoint[0]][currentPoint[1]] = self.UNDEFINED

  ## Check that we go on every cell.
  def verifyGame(self):
    moveCount = 0
    currentPoint = [self.start[0], self.start[1]]

    isEnd = 0
    while (isEnd == 0):
      if (currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.FROM_NORTH):
        currentPoint[0] = currentPoint[0] + 1
      elif (currentPoint[1] > 0) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.FROM_EAST):
        currentPoint[1] = currentPoint[1] - 1
      elif (currentPoint[0] > 0) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.FROM_SOUTH):
        currentPoint[0] = currentPoint[0] - 1
      elif (currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.FROM_WEST):
        currentPoint[1] = currentPoint[1] + 1
      else:
        isEnd = 1

      if isEnd == 0:
        moveCount = moveCount + 1

    ## The number of moves should equal to the size of the map minus one cell because we don't arrive on the start
    if moveCount == ((self.GAME_HEIGHT * self.GAME_WIDTH) - 1):
      print ('OK')
    else:
      print ('ko!!!')

  ## Fill the map with void data.
  def initGame(self):
    self.gameGrid = []
    for i in range(self.GAME_HEIGHT):
      gameLine = []
      for j in range(self.GAME_WIDTH):
        gameLine.append(self.UNDEFINED)

      self.gameGrid.append(gameLine)

    self.initComplexMap()

  ## Create a valid simple map.
  ## It uses a complex algorithm.
  def initComplexMap(self):
    startPoint = random.randint(0, 3)
    if startPoint == 0:
      self.start = [0, 0]
    elif startPoint == 1:
      self.start = [0, self.GAME_WIDTH - 1]
    elif startPoint == 2:
      self.start = [self.GAME_HEIGHT - 1, 0]
    elif startPoint == 3:
      self.start = [self.GAME_HEIGHT - 1, self.GAME_WIDTH - 1]

    self.gameGrid[self.start[0]][self.start[1]] = self.FROM_NOWHERE
    currentPoint = [self.start[0], self.start[1]]

    while ((0 < currentPoint[0]) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.UNDEFINED)) or ((currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.UNDEFINED)) or ((0 < currentPoint[1]) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.UNDEFINED)) or ((currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.UNDEFINED)):
      possibilities = []
      if ((0 < currentPoint[0]) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.UNDEFINED)) and (((0 == currentPoint[1]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[1] == self.GAME_WIDTH - 1) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] + 1] != self.UNDEFINED))):
        possibilities.append([currentPoint[0] - 1, currentPoint[1], self.FROM_SOUTH])

      if ((currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.UNDEFINED)) and (((0 == currentPoint[1]) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[1] == self.GAME_WIDTH - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] + 1] != self.UNDEFINED))):
        possibilities.append([currentPoint[0] + 1, currentPoint[1], self.FROM_NORTH])

      if ((0 < currentPoint[1]) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.UNDEFINED)) and (((0 == currentPoint[0]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[0] == self.GAME_HEIGHT - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] - 1] != self.UNDEFINED))):
        possibilities.append([currentPoint[0], currentPoint[1] - 1, self.FROM_EAST])

      if ((currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.UNDEFINED)) and (((0 == currentPoint[0]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] + 1] != self.UNDEFINED)) or ((currentPoint[0] == self.GAME_HEIGHT - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] + 1] != self.UNDEFINED))):
        possibilities.append([currentPoint[0], currentPoint[1] + 1, self.FROM_WEST])

      possibility = possibilities.pop(random.randint(0, len(possibilities) - 1))
      currentPoint = [possibility[0], possibility[1]]
      self.gameGrid[possibility[0]][possibility[1]] = possibility[2]

  ## Create a valid simple map.
  ## It uses a basic algorithm.
  def initSimpleMap(self):
    direction = self.RIGHT

    if random.randint(0, 1) == 0:
      for i in range(self.GAME_HEIGHT):
        if direction == self.RIGHT:
          self.gameGrid[i][0] = self.FROM_NORTH
          for j in range(1, self.GAME_WIDTH):
            self.gameGrid[i][j] = self.FROM_WEST
          direction = self.LEFT
        else:
          for j in range(self.GAME_WIDTH - 1):
            self.gameGrid[i][j] = self.FROM_EAST
          self.gameGrid[i][self.GAME_WIDTH - 1] = self.FROM_NORTH
          direction = self.RIGHT

        self.gameGrid.append(gameLine)

      self.gameGrid[0][0] = self.FROM_NOWHERE
    else:
      for j in range(self.GAME_WIDTH):
        if direction == self.RIGHT:
          self.gameGrid[0][j] = self.FROM_WEST
          for i in range(1, self.GAME_HEIGHT):
            self.gameGrid[i][j] = self.FROM_NORTH
          direction = self.LEFT
        else:
          for i in range(self.GAME_HEIGHT - 1):
            self.gameGrid[i][j] = self.FROM_SOUTH
          self.gameGrid[self.GAME_HEIGHT - 1][j] = self.FROM_WEST
          direction = self.RIGHT

      self.gameGrid[0][0] = self.FROM_NOWHERE

  ## Search all the possible permutations.
  ## It doesn't affect the map.
  def listPermutation(self):
    self.permutableZones = []
    for i in range(self.GAME_HEIGHT - 1):
      for j in range(self.GAME_WIDTH - 1):
        if (self.gameGrid[i + 1][j] == self.FROM_NORTH) and (self.gameGrid[i][j + 1] == self.FROM_SOUTH):
          self.permutableZones.append([[i + 1, j], [i, j + 1]])
        elif (self.gameGrid[i][j] == self.FROM_SOUTH) and (self.gameGrid[i + 1][j + 1] == self.FROM_NORTH):
          self.permutableZones.append([[i, j], [i + 1, j + 1]])
        elif (self.gameGrid[i][j] == self.FROM_EAST) and (self.gameGrid[i + 1][j + 1] == self.FROM_WEST):
          self.permutableZones.append([[i, j], [i + 1, j + 1]])
        elif (self.gameGrid[i][j + 1] == self.FROM_WEST) and (self.gameGrid[i + 1][j] == self.FROM_EAST):
          self.permutableZones.append([[i, j + 1], [i + 1, j]])

  ## Permutate the connection of path.
  ## It receives and returns a valid map.
  def permutate(self):
    self.listPermutation()

    if len(self.permutableZones) > 0:
      permutation = self.permutableZones.pop(random.randint(0, len(self.permutableZones) - 1))
      start = permutation[0]
      end = permutation[1]
      ##print ('Entry of the loop: (' + str(start[0]) + ', ' + str(start[1]) + ')')
      ##print ('Exit of the loop: (' + str(end[0]) + ', ' + str(end[1]) + ')')
      if self.isLoop(end, start):
        self.findPermutation(start, end)
      else:
        end = permutation[0]
        start = permutation[1]
        ## Assertion
        if not self.isLoop(end, start):
          print ('Wrong!')
        self.findPermutation(start, end)

  ## It doesn't affect the map.
  def isInLoop(self, searchedPoint):
    found = False
    for point in self.currentLoop:
      if (searchedPoint[0] == point[0]) and (searchedPoint[1] == point[1]):
        found = True

    return found

  ## It doesn't affect the map.
  def isLoop(self, originalPoint, destination):
    self.currentLoop = []

    point = []
    point.append(originalPoint[0])
    point.append(originalPoint[1])
    self.currentLoop.append([originalPoint[0], originalPoint[1]])
    while ((point[0] != destination[0]) or (point[1] != destination[1])) and (self.gameGrid[point[0]][point[1]] != self.FROM_NOWHERE):
      ##print ('Loop point: (' + str(point[0]) + ', ' + str(point[1]) + ')')
      newY = point[0]
      newX = point[1]
      if self.gameGrid[point[0]][point[1]] == self.FROM_SOUTH:
        newY = point[0] + 1
      elif self.gameGrid[point[0]][point[1]] == self.FROM_NORTH:
        newY = point[0] - 1
      elif self.gameGrid[point[0]][point[1]] == self.FROM_WEST:
        newX = point[1] - 1
      elif self.gameGrid[point[0]][point[1]] == self.FROM_EAST:
        newX = point[1] + 1
      point[0] = newY
      point[1] = newX
      self.currentLoop.append([newY, newX])

    return ((point[0] == destination[0]) and (point[1] == destination[1]))

  ## Permutate the connections of path.
  ## It receives and returns a valid map.
  def findPermutation(self, start, end):
    self.findIntersections()
    if len(self.intersections) > 0:
      self.modifyIntersection(start, end)

  ## Permutate the connections of path.
  ## It doesn't affect the map.
  def findIntersections(self):
    self.intersections = []
    for i in range(1, len(self.currentLoop) - 1):
      point = self.currentLoop[i]
      if self.gameGrid[point[0]][point[1]] == self.FROM_NORTH:
        if (0 < point[1]) and (self.gameGrid[point[0] - 1][point[1] - 1] == self.FROM_SOUTH) and not self.isInLoop([point[0] - 1, point[1] - 1]):
          self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] - 1]])
        elif (point[1] < self.GAME_WIDTH - 1) and (self.gameGrid[point[0] - 1][point[1] + 1] == self.FROM_SOUTH) and not self.isInLoop([point[0] - 1, point[1] + 1]):
          self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] + 1]])

      elif self.gameGrid[point[0]][point[1]] == self.FROM_SOUTH:
        if (0 < point[1]) and (self.gameGrid[point[0] + 1][point[1] - 1] == self.FROM_NORTH) and not self.isInLoop([point[0] + 1, point[1] - 1]):
          self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] - 1]])
        elif (point[1] < self.GAME_WIDTH - 1) and (self.gameGrid[point[0] + 1][point[1] + 1] == self.FROM_NORTH) and not self.isInLoop([point[0] + 1, point[1] + 1]):
          self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] + 1]])

      elif self.gameGrid[point[0]][point[1]] == self.FROM_WEST:
        if (0 < point[0]) and (self.gameGrid[point[0] - 1][point[1] - 1] == self.FROM_EAST) and not self.isInLoop([point[0] - 1, point[1] - 1]):
          self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] - 1]])
        elif (point[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[point[0] + 1][point[1] - 1] == self.FROM_EAST) and not self.isInLoop([point[0] + 1, point[1] - 1]):
          self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] - 1]])

      elif self.gameGrid[point[0]][point[1]] == self.FROM_EAST:
        if (0 < point[0]) and (self.gameGrid[point[0] - 1][point[1] + 1] == self.FROM_WEST) and not self.isInLoop([point[0] - 1, point[1] + 1]):
          self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] + 1]])
        elif (point[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[point[0] + 1][point[1] + 1] == self.FROM_WEST) and not self.isInLoop([point[0] + 1, point[1] + 1]):
          self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] + 1]])

  ## Permutate the connections of path.
  ## It receives and returns a valid map.
  def modifyIntersection(self, start, end):
    ##self.logGameWithPath()
    ##self.printGameOld()
    intersection = self.intersections[random.randint(0, len(self.intersections) - 1)]
    ## Disconnect the loop
    self.modifyPath([start, end])
    ## Reconnect the loop
    self.modifyPath(intersection)

  ## Change the connections on the map.
  def modifyPath(self, intersection):
    ##print ('modifyPath: (' + str(intersection[0][0]) + ', ' + str(intersection[0][1]) + ') with (' + str(intersection[1][0]) + ', ' + str(intersection[1][1]) + ')')
    firstPoint = self.gameGrid[intersection[0][0]][intersection[0][1]]
    secondPoint = self.gameGrid[intersection[1][0]][intersection[1][1]]

    if (self.gameGrid[intersection[0][0]][intersection[0][1]] == self.FROM_NORTH) or (self.gameGrid[intersection[0][0]][intersection[0][1]] == self.FROM_SOUTH):
      if (intersection[0][1] < intersection[1][1]):
        firstPoint = self.FROM_EAST
        secondPoint = self.FROM_WEST
      else:
        firstPoint = self.FROM_WEST
        secondPoint = self.FROM_EAST
    if (self.gameGrid[intersection[0][0]][intersection[0][1]] == self.FROM_EAST) or (self.gameGrid[intersection[0][0]][intersection[0][1]] == self.FROM_WEST):
      if (intersection[0][0] < intersection[1][0]):
        firstPoint = self.FROM_SOUTH
        secondPoint = self.FROM_NORTH
      else:
        firstPoint = self.FROM_NORTH
        secondPoint = self.FROM_SOUTH

    self.gameGrid[intersection[0][0]][intersection[0][1]] = firstPoint
    self.gameGrid[intersection[1][0]][intersection[1][1]] = secondPoint

cellRoom = CellRoom()
cellRoom.generateGame()

В этой статье описывается метод:

Обердорф, Р .; Фергюсон, А .; Jacobsen, J.L .; Кондев, Дж. - Вторичные структуры в длинных компактных полимерах (arXiv.org)

Примерно метод состоит из следующего: начните с зигзагообразного узора (неслучайный гамильтонов путь на сетке) и многократно примените к нему преобразование (называемое «заклиниванием»). Обратный прикус состоит из добавления ребра от одной из конечных точек A к соседней вершине B, отличной от той, с которой соединен A (таким образом, создавая петлю), а затем удаления ребра, которое начинается в B, которое не является только что добавленным, и который вызывает цикл (всегда будет только один вызывающий цикл, отличный от только что добавленного).

Авторы добавляют некоторые условия для получения приблизительной однородности (в том числе оценку того, сколько раз применять ход обратного прикуса). Подробности в газете.

Авторы также эмпирически доказывают, что вероятность того, что их метод генерирует смежные конечные точки, приблизительно соответствует теоретической вероятности в однородных случайных гамильтоновых путях.

Здесь есть реализация алгоритма на JavaScript: Гамильтониан пути

Достаточная случайность является очень общей, у вас должны быть некоторые тесты, самый известный алгоритм для евклеадического TSP имеет приближение 3/2 (Christofides алгоритм), который использует MST (например, алгоритм, который вы упомянули, который является 2-приближенным), и, как вы можете видеть в wiki лучшие PTAS, найденные в настоящее время, имеют время работы в зависимости от (n log n) ^ f (c, 2) для c> 0 (в двухмерном пространстве, как в вашем примере) с приближением (1 + 1 / c), а наилучшим приближением для TSP с постоянным коэффициентом является 3/2 - 1/500 алгоритм (недавно найдено), но все они используют логические способы, есть некоторые случайные использования, но это не заставляет оставлять все на случайный выбор. если вы просто хотите использовать случайный выбор, вы можете использовать Случайное блуждание, это более случайное, но видите Цепь Маркова для повышения производительности и случайности.

Вы можете начать с упомянутого вами подхода, чтобы найти гамильтонов путь. Чтобы еще больше рандомизировать решение, вы можете начать вращать края, как указано в вики. Если вы будете делать это чаще, решение будет более случайным. Поворот случайного ребра N * M раз сохраняет алгоритм в эффективной области, делая найденный гамильтонов путь более случайным.