Algorithm to find a random Hamiltonian path in a g

Question

I'm looking for an efficient algorithm that is able to find an as random as possible Hamiltonian path in a bidirectional N*M grid.

Does anyone know where I can find, or how to go about constructing such an algorithm?

---

I've already found an efficient approach (see image below). The end result here is a Hamiltonian cycle. Removing a random edge will make it a Hamiltonian path. This algorithm is efficient, but does not provide enough randomness. This approach will always have the begin and end point of the path right next to each other, while I'd like to have those in random locations. Space-filling curve http://img593.imageshack.us/img593/8060/sfc.png Image taken from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type=pdf

Answer 1

Enough randomness is very general, You should have some benchmarks, most famous algorithm for eucleadian TSP has 3/2 approximation (Christofides algorithm), which uses MST (like algorithm you mentioned which is 2-approximate), and as you can see in wiki best PTAS found currently has running time depending to (n log n)^f(c,2) for c > 0 (in 2 dimentional space like your sample) with approximation of (1+1/c), and best approximation for TSP with constant factor is 3/2 - 1/500 algorithm (recently found), but all of them using logical ways, there are some random usages but it doesn't cause to leave all things to random selections. if you just want using random you can use Random Walk, It's more random but see Markove Chain for better performance and randomness.

Answer 2

You can start with the approach you mentioned to find a Hamiltonian path. To further randomize the solution you can start rotating edges as mentioned on the wiki. Doing this more often will make the solution more random. Rotating a random edge N*M times keeps the algorithm in the efficient realm, while making the found Hamiltonian path more random.

Answer 3

First of all, the algorithm displayed on your image from the pdf file is not a solution to the Hamilton path problem but a solution to a maze generation as the final path has several branches.

To find algorithms for a maze generation, see: https://en.wikipedia.org/wiki/Maze_generation_algorithm

Now here is a simple algorithm to generate a Hamiltonian path on a N*M 2D grid:

1) Let a N*M grid be (for instance, 4*5):

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

2) Let's start from the East/North corner and let's create a simple zigzag to the West and to the East:

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

Now we have a Hamiltonian path.

3) Let's search two glued edges which one front of the other. They are the beginning and the end of a loop:

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

4) Ensure that there is at least one edge inside the loop that is glued to an edge outside the loop, otherwise, go to step 3:

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

5) Shortcut the loop:

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

6) Reattach the loop by the two other glued edges:

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

7) If the Hamiltonian path is not randomized enough, go to step 3.

Only the start and the end will not move. To randomize the end or the start, you can replace the initial zigzag by another algorithm:

1. Choose one of the four corners
2. Search all the non-visited neighbors
3. If there is no neighbor, the map is filled, otherwise go to step 4
4. Only keep the neighbors that have a void or a visited cell on one side, left or right (in other words, the neighbors that walk along the border of the non-visited area)
5. Choose one of those neighbors, visit it and go to step 2

The result may look like that:

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

With this algorithm, the start remains on a corner but the end can be anywhere. To randomize the start AND the end, you can apply an algorithm that you can iterate as many times as you want either on the start or on the end. Let's take the start:

1) Locate the start:

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

2) Locate a neighbor that is not directly connected to the start (you will always find one in a 2D grid):

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

3) Find from where you arrive to it from the start (respectively from the end):

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

4) Cut this link and create a link between this point and the start:

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

The start has moved two cells. The start and the end are as on a checkerboard and they only can move on a case with the same color.

Now your path is completely randomized.

Here is the whole algorithm in Python. You can run it here: http://www.compileonline.com/execute_python3_online.php

The result is stored in an array (self.gameGrid) that is logged twice (with arrows and with nodes and lines). The first two glued edges are called a permutation and the second ones are called an intersection.

#!/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()

Answer 4

This paper describes a method:

Oberdorf, R.; Ferguson, A.; Jacobsen, J.L.; Kondev, J. - Secondary Structures in Long Compact Polymers (arXiv.org)

The method roughly consists of the following: start with a zig-zag pattern (a non-random Hamiltonian path on the grid) and repeatedly apply a transformation (called "backbite") to the path. A backbite consists of adding an edge from one of the endpoints A to an adjacent vertex B other than the one A is connected to (thus creating a loop), and then remove the edge that starts in B that is not the one just added and that causes a loop (there will always be only one causing a loop other than the one just added).

The authors add some conditions to obtain rough uniformity (including an estimation on how many times to apply the backbite move). Details in the paper.

The authors also prove empirically that the probability of their method generating adjacent endpoints approximately matches the theoretical probability in uniform random Hamiltonian paths.

There is an implementation of the algorithm in JavaScript here: Hamiltonian Path Generator