# Self Avoiding Walks

This week, I’m going to talk about space filling self-avoiding walks.

Imagine you had a chess board, and you started on one square. If you were allowed to only move one square at a time, horizontally or vertically (but not diagonally) to a previously un-visited square, is it possible to find a tour that visits all the squares on the board?

Is it always possible? Does it depend on where you start? How does this change with the size of the grid?

Here is an example for an *8x8* grid (starting from where a bishop would start a game).

## Try it out

**Reset**button). Click on the grid to extend the path, and use

**Undo**to, recursively, remove the last step if you back yourself into a corner.

## Hamiltonian Paths

## 1x1

## 2x2

## 3x3

*Greek Key Tours*(presumably in reference to the popular tiling pattern?).

__there is no solution__. Why is this? Well, the checkerboard pattern gives us a strong clue. If we shade the board alternating black and white we can see that a move from a square changes the

*parity*of the color. If we were on a black square, a move will change us to a white square, and vice-versa. Because of the odd sized grid, there are an odd number of squares in total (in the example here, there is one more white square than black squares).

## 4x4

##### Here are the 52 solutions starting at a corner space:

##### Here are the 25 solutions starting at one of the edge locations:

##### Here are the 36 solutions possible from one of the four center locations:

## 5x5

## 6x6

## 7x7 and beyond …

Grid | Number of Greek Key Tour Solutions |
---|---|

1 | 1 |

2 | 2 |

3 | 8 |

4 | 52 |

5 | 824 |

6 | 22,144 |

7 | 1,510,446 |

8 | 180,160,012 |

9 | 54,986,690,944 |

10 | 29,805,993,260,994 |

11 | 41,433,610,713,353,366 |

12 | 103,271,401,574,007,978,038 |

13 | 660,340,630,211,753,942,588,170 |

14 | 7,618,229,614,763,015,717,175,450,784 |

15 | 225,419,381,425,094,248,494,363,948,728,158 |

## Space Filing Curves

## Generating Hamiltonian Paths

*backbite*algorithm.

##### Algorithm

- Select either of the two end points on the current graph.
- Select, at random, one of the neighbor vertices of this end point that is not the one connected to the current point. (If the chosen vertex happens to be the opposite endpoint, add an edge to it and remove the edge that it was connected to originally).
- This creates a loop, and the selected node now has a valency of three. (One link is the edge just created. One will lead to the opposite end of the graph, and the third loops back to itself).
- The one that loops back to itself should be removed. This is the
*backbite*.

## Example

One of these candidates is selected at random and added to to the graph. This is shown in red. The addition of this new edge creates a loop in the graph.

Adding this link also creates a node with a valency of three. The newly created link remains, and we need to determine which of the other two links to break. This is done by propagating along each of the other two links. One of the these paths will take us to the other end-node of the graph, and the other will loop back on itself.

One path goes to the other end, the other loops back.

The link that forms the loop is deleted.

This is the *backbite*.