CSE 102 – Tutorial 4 – Backtracking

General instructions

After you are finished with the tutorial, please upload your submission to Moodle by completing “Tutorial 4 assignment” before the indicated deadline.

Warmup: maze escape!

In this exercise you are navigating through a square grid maze, such as the one below:

Your goal is to go from the upper left corner of the maze to the lower right corner without entering a gray cell. For example, this maze has two possible solutions:

         

We will represent square grid mazes in Python by \(n \times n\) matrices with 1s and 0s indicating whether a cell is free or blocked respectively. For example, the \(6 \times 6\) maze above will be encoded like so:

example_maze = [ [1 , 0 , 0 , 1 , 0 , 0] ,
                 [1 , 1 , 1 , 1 , 1 , 0] ,
                 [0 , 0 , 1 , 0 , 1 , 1] ,
                 [1 , 1 , 1 , 1 , 1 , 0] ,
                 [1 , 0 , 0 , 1 , 0 , 0] ,
                 [1 , 0 , 1 , 1 , 1 , 1] ]

We will represent paths through the maze as lists of (row, column) pairs, where rows are numbered from top to bottom and columns from left to right using 0-indexing. For example, the two paths above will be encoded as follows:

red_path = [(0,0), (1,0), (1,1), (1,2), (1,3), (1,4), (2,4), (3,4), (3,3), (4,3), (5,3), (5,4), (5,5)]
purple_path = [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3), (4,3), (5,3), (5,4), (5,5)]

In general, we say that a list of coordinates \(p = [(r_1,c_1),\dots,(r_n,c_n)]\) constitutes a path in a maze \(M\) just in case it satisfies four conditions:

1. (\(p\) is contiguous:) \((r_{i+1} = r_i \wedge c_{i+1} = c_i \pm 1) \vee (r_{i+1} = r_i\pm 1 \wedge c_{i+1} = c_i)\) for all \(1 \le i < n\);
2. (\(p\) stays within the maze:) \(0 \le r_i < n\) and \(0 \le c_i < n\) for all \(1 \le i \le n\);
3. (\(p\) only visits free cells:) \(M[r_i][c_i] = 1\) for all \(1 \le i \le n\);
4. (\(p\) doesn’t cross itself:) \((r_i,c_i) \ne (r_j,c_j)\) for all \(i \ne j\).

To qualify as a solution to a maze of dimension \(n\), a path must satisfy two additional conditions:

5. (start in the upper left corner:) \((r_1,c_1) = (0,0)\);
6. (end in the lower right corner:) \((r_n,c_n) = (n-1,n-1)\);

Our aim is to solve mazes using backtracking, for which it’s important to have a notion of “partial” solution. In this case, we can simply drop condition (6). In other words, we consider paths that start at the upper left corner \((0,0)\) and end somewhere inside the maze, at some white cell \((r,c)\). This leads to a simple recursive algorithm that attempts to solve a maze starting from any partial solution \(p\):

• try extending the current path by adding a cell \((r\pm 1,c)\) or \((r,c \pm 1)\) (assuming it doesn’t violate conditions 2-4), to form an extended path \(p'\);
• recursively look for a solution extending \(p'\);
• if you found a solution extending any of the \(p'\), then it is a solution extending \(p\);
• otherwise, you have to backtrack and try a different partial solution \(p\).

Your first task is to write this recursive backtracking function.

Now that you’ve written this backtracking solver that starts from an arbitrary partial solution, it is then an easy task to apply it to solve any (solvable) maze.

Cyclic dice

A sequence of dice \(A_1, A_2, \dots, A_n\) is said to be cyclic if \(A_1\) rolls higher than \(A_2\) more than half the time, \(A_2\) rolls higher than \(A_3\) more than half the time, and so on up to \(A_n\), which rolls higher than \(A_1\) more than half the time. This is a special case of non-transitive dice and tends to go against most people’s ideas about probability, making them convenient for tricks or bets.

An example of a cyclic sequence of 6-sided dice, due to Bradley Efron, is the following:

A: 4, 4, 4, 4, 0, 0
B: 3, 3, 3, 3, 3, 3
C: 6, 6, 2, 2, 2, 2
D: 5, 5, 5, 1, 1, 1

which leads to \(\Pr(A>B) = \Pr(B>C) = \Pr(C>D) = \Pr(D>A) = \frac{2}{3}\)

Representing the dice sequence

One can prove that it is equivalent to consider all sides of all dice different or to allow some repetitions. For simplicity we will therefore use always different sides, starting at \(0\). We will represent the sequence of dice as a single list of length \(n \cdot s\) of distinct numbers between 0 and \(n\cdot s-1\), where \(n\) is the number of dice and \(s\) the number of sides. Hence each permutation of list(range(n*s)) represents a list of dice.

For example, the three 3-sided dice [[0, 4, 8], [2, 3, 7], [1, 5, 6]] (which are a cyclic dice sequence with each die beating the next one with probability \(5/9\)) are represented by the list [0, 4, 8, 2, 3, 7, 1, 5, 6]. One can slice such a list back into individual dice as follows:

def slice_dice(n, s, dice):
    return [dice[i * s:i * s + s] for i in range(n)]

That is, we have slice_dice(3, 3, [0, 4, 8, 2, 3, 7, 1, 5, 6]) = [[0, 4, 8], [2, 3, 7], [1, 5, 6]].

Partial solutions for backtracking

Our goal is to build a list of \(s\)-sided cyclic dice of length \(n\). To do this through backtracking, we must once again come-up with a notion of partial solution. Here, we will consider a sequence of length \(k\) of integers smaller than \(n\cdot s\), where moreover:

• all the elements of the sequence should be different;
• inside each subsequence corresponding to an individual die, the elements should be strictly increasing; and
• each complete pair of successive dice \((A, B)\) contained in the sequence should have \(\Pr(A > B) > \frac{1}{2}\).

Generating all solutions

In contrast to the maze escape problem where it was sufficient to find a single path through the maze, now we want to generate all solutions to the cyclic dice problem. This can be done very conveniently in Python using generators, where we yield as soon as we’ve found a solution, and backtrack when the user calls the generator again to ask for another solution.

However, we only want to generate all solutions up to symmetry. In order to suppress the symmetry that (for example) if \((A, B, C)\) is a cyclic sequence of dice, \((B, C, A)\) is also such a sequence, we will enforce that our single list starts with \(0\). In other words we enforce that \(A\) is lexicographically the smallest die.

Optimization (optional)

If one intends to bet using such dice, it is useful to have the largest chance to beat whatever die your opponent will choose. Hence we will consider the score of a cyclic sequence as the minimum of the \(n\) winning probabilities between one die and the next in the cyclic order.

To optimize the score we will use a branch and bound procedure around our backtracking search. The idea is to iteratively search for one solution, but with a new constraint each time: that this solution is better than the best we have found so far.

Long live the queens (optional)

The famous “\(n\) queens problem” asks whether \(n\) chess queens can be placed on an \(n \times n\) chessboard so that no two queens are attacking each other.

In this part of the tutorial we will be considering two variations of the \(n\) queens problems, one where the chessboard is replaced by a honeycomb and the chess queens are replaced by queen bees, and the other where the chess queens are grouped in two opposing teams.

The \(n\) queen bees problem

To illustrate the first problem, consider the following rendering (in ASCII art) of a \(4 \times 4\) honeycomb on which 4 queen bees have been placed, in such a way that no two bees are on the same (vertical or diagonal) row:

            __
         __/  \__
      __/@@\__/  \__
   __/  \__/  \__/  \__
__/  \__/  \__/  \__/@@\__      # a valid arrangement of 4 queen bees
  \__/@@\__/@@\__/  \__/        # on a 4x4 honeycomb
     \__/  \__/  \__/
        \__/  \__/
           \__/

The following is an invalid arrangement of queen bees, since two bees are on the same (positively-sloped) diagonal row:

            __
         __/  \__
      __/@@\__/  \__
   __/  \__/  \__/@@\__
__/  \__/  \__/  \__/  \__      # an invalid arrangement of 4 queen bees
  \__/@@\__/@@\__/  \__/        # on a 4x4 honeycomb
     \__/  \__/  \__/
        \__/  \__/
           \__/

The general problem is to place \(n\) queen bees on an \(n \times n\) honeycomb, in such a way that no two bees are on the same row. Actually, it is not hard to come up with a rather boring solution for any \(n\):

            __
         __/  \__
      __/  \__/  \__
   __/  \__/  \__/  \__
__/@@\__/@@\__/@@\__/@@\__      # a boring arrangement of 4 queen bees
  \__/  \__/  \__/  \__/        # on a 4x4 honeycomb
     \__/  \__/  \__/
        \__/  \__/
           \__/

However, we are interested in finding all solutions.

In order to solve the \(n\) queen bees problem using backtracking, we will use the following notion of partial solution: for some \(k \le n\), place \(k\) bees on each of the first \(k\) negative(ly sloped) diagonal rows of the \(n \times n\) honeycomb, in such a way that no two bees are on the same vertical or positive diagonal row. The condition is trivially satisfied when \(k=0\), and when \(k = n\) it gives a full solution to the \(n\) queen bees problem.

As an example, here is a partial solution for the case \(n = 4\) with \(k=3\):

            __
         __/  \__
      __/@@\__/  \__
   __/  \__/  \__/  \__
__/  \__/  \__/  \__/  \__      # a valid arrangement of 3 queen bees
  \__/@@\__/@@\__/  \__/        # on the first 3 negative diagonal rows
     \__/  \__/  \__/           # of a 4x4 honeycomb
        \__/  \__/
           \__/

In this case, we see that there is a unique way to extend the partial solution to a valid arrangement of 4 queen bees, corresponding to the first arrangement given above.

Representing the honeycomb

A partially-filled honeycomb such as the above can be represented in Python as a list of \(k\) numbers between \(0\) and \(n-1\), where each number gives the positive offset of the corresponding bee along its negative diagonal. For instance, the example above is represented by the list [1,2,0]. For your convenience, we have provided the following utility function for printing out partially-filled honeycombs (this is a bit involved, since we have to convert between positions on the line and “bee coordinates”):

def comb_print(n, comb):
    def occupied(i,j):
        return i<len(comb) and comb[i] == j

    print(' '*3*n + '__')
    for line in range(n):
        print(' '*(n-line-1)*3 + '__/', end='')
        for cell in range(line+1):
            i = n-1-line+cell
            j = cell
            s = '@@' if occupied(i,j) else '  '
            print(s + '\\__' + ('/' if cell<line else ''), end='')
        print()
    for line in range(n,2*n):
        print(' '*(line-n)*3 + '  \\__/', end='')
        for cell in range(2*n-1-line):
            i = cell
            j = cell+line-n+1
            s = '@@' if occupied(i,j) else '  '
            print(s + '\\__/', end='')
        print()
    print()

Implementation

Peaceable queens

The second variation of the \(n\) queens problem is known as peaceable queens, as described in this Numberphile video. Briefly, the goal is to place two opposing camps of \(m\) black queens and \(m\) white queens on an \(n \times n\) chessboard, in such a way that no two queens of opposing camps are attacking each other. Moreover, we want \(m\) to be as large as possible.

For example, the following is one possible “peaceable” arrangement of two teams of \(5\) queens on a \(6 \times 6\) chessboard:

+-------------+
| B . B . . . |
| . . . . W W |
| . . B . . . |
| B B . . . . |
| . . . W . W |
| . . . . W . |
+-------------+

It turns out that this is the best possible, in the sense that there is no peaceable arrangement of two teams of size \(6\) on a \(6 \times 6\) board.

Representing the board, and ordering moves for backtracking

Once again, to setup a backtracking problem it is always important to identify a notion of partial solution. In this case, to a first approximation, we can simply consider a peaceable arrangement of \(k\) queens from each team, for some \(k \le m\), represented in Python as a pair of lists black and white containing the (row,col) coordinates of the black queens and the white queens. We will use the following function for printing out such partial board assignments:

def board_print(n, black, white):
    def square(i,j):
        if (i,j) in black:
            return 'B'
        elif (i,j) in white:
            return 'W'
        return '.'

    print('+' + '-' * (2*n+1) + '+')
    for i in range(n):
        print('|', end = '')
        for j in range(n):
            print(' ' + square(i,j), end = '')
        print(' |')
    print('+' + '-' * (2*n+1) + '+')

For example, calling board_print(6, [(0,0),(0,2)], [(1,4),(1,5)]) prints out the following board:

+-------------+
| B . B . . . |
| . . . . W W |
| . . . . . . |
| . . . . . . |
| . . . . . . |
| . . . . . . |
+-------------+

However, we still have to be a bit more careful before setting up the problem for backtracking, in order to avoid exploring redundant possibilities. For example, although the partial solution above could have been reached by placing the first pair of black and white queens at squares (0,0) and (1,4)

+-------------+
| B . . . . . |
| . . . . W . |
| . . . . . . |
| . . . . . . |
| . . . . . . |
| . . . . . . |
+-------------+

and the second pair at squares (0,2) and (1,5), at least naively, it could have just as easily been reached by placing the first pair at (0,2) and (1,5)

+-------------+
| . . B . . . |
| . . . . . W |
| . . . . . . |
| . . . . . . |
| . . . . . . |
| . . . . . . |
+-------------+

and the second pair at (0,0) and (1,4), or the first pair at (0,2) and (1,4) and the second pair at (0,0) and (1,5), etc. This artificially increases the size of the search space, since there is no point in considering these different paths to the same position.

The way we remedy this is by placing an ordering on the squares of the board, and enforcing the rule that once a team has placed a queen on a square, that team can no longer place a queen on an “earlier” square. For instance, we could take the lexicographic order on (row,col) coordinates, which would mean that the first move in the example above could only have been placing the black and white queens at squares (0,0) and (1,4). The ordering one uses can actually make a difference for the efficiency of backtracking search, and a heuristic is to prioritize moves that cut down the search space as much as possible in the beginning. For our purposes, though, we just care that some ordering exists, since it is what enables us to avoid going down different paths towards the same destination.

Implementation

Gambling queens

Note that there are no automated tests for this sequence of optional exercises, it is up to you to ensure that your code is correct!

In class, we saw how to solve the \(n\)-queens problem using backtracking. It is also possible to take a randomized approach:

This is a “Las Vegas algorithm”, in the sense that it always returns a correct solution, although it may get unlucky and require many iterations to find one.

One nice feature of backtracking is that it allows us to exhaustively enumerate all solutions. On the other hand, depending on our available computing power the full backtracking tree might be too large to exhaust. The Las Vegas algorithm described above can be adapted to quickly obtain a Monte Carlo estimate of the size of the full backtracking tree, which we can use to decide whether it is worth performing a full enumeration.

The idea is to keep track of the number of choices \(c_1,\dots,c_k\) we had at each iteration, from the initial choice (in this case, a choice of an arbitrary row for the first queen, so that \(c_1 = n\)) up until the point where either the search failed (with \(c_k = 0\)) or we found a complete solution (with \(k = n\) and \(c_n > 0\)). From each such trial, we infer an estimate of

\[ 1 + c_1 + c_1c_2 + \dots + c_1c_2\cdots c_n \]

for the number of nodes in the backtracking tree, and by performing repeated trials we can get a pretty good estimate for the actual number of nodes.