Homework 11
Document last modified: 

Do either assignment or both for extra credit.

Maze Assignment

Give a working backtracking algorithm in your favorite language to find and display any path through a maze given a maze representation of your choice and a starting point. There are plenty of maze solutions readily available but your algorithm should be patterned after examples from the notes discussed in class as follows:

Generic Backtracking Algorithm

Backtrack( X[1..i] )
--  pre: X[1..i] specifies first i components of a solution
--  post: Solution X[1..i]
--           Si+1 is solution i+1

  1. if X[1..i] is a solution then print X[1..i]

  2. else

  3.    for each x ∈ Si+1 do

  4.       if x is consistent with X[1..i] and valid option for problem constraints then

  5.            X[i+1] ← x

  6.            Backtrack( X[1..i+1] )

The following is one way to represent a maze where D is a door and W is a wall and each room has only 4 sides. Note that there can be 2 doors between the same rooms, so you can enter in one door and exit out the other.

        int D=-1, W=-2;

        int maze[][][] = {
                                    { {W,W,D,W},{D,W,D,D},{D,W,D,D},{D,W,W,D} },
                                    { {W,W,D,W},{D,D,W,D},{W,D,W,D},{W,D,W,D} },
                                    { {W,W,W,W},{W,D,D,D},{D,D,W,W},{W,D,W,W} },
                                    { {D,W,D,W},{D,D,W,W},{W,W,W,W},{W,W,W,W} }
                                };

Suppose the maze you’re given has rooms arranged in a 4x4 square. In Java, indices from 0..3x0..3 would be inside the maze. Note the correspondence of the maze to room indices: the leftmost room is at maze[0][0], the upper-right room at maze[0][3], other indices such as -1 or 4 would be outside the maze.

The goal is to exit the maze, considering the maze row/column of a room, anytime either the row/column < 0 or > 3 the maze has been exited.

The key for orientation of room sides is:
  1  
0   2
  3  

 

 An exit door in one room must have an entrance door in the next room. For example, Room(0,0) and Room(0,1) are:
  W  
W   D
  W  
  W  
D   W
  W  

where Room(0,0) is the maze[0][0] entry {W,W,D,W} as:
0 1 2 3
W W D W

The Maze above is then:

       0          1         2         3  
 

0

 

 

1

 

 

2

 

 

3
  W  
W 0 D
  W  
  W  
D 1 D
  D  
  W  
D 2 D
  D  
  W  
D   W
  D  
  W  
W   D
  W  
  D  
D   W
  D  
  D  
W 3 W
  D  
  D  
W   W
  D  
  W  
W   W
  W  
  D  
W 5 D
  D  
  D  
D 4 W
  W  
  D  
W   W
  W  
  W  
D 7 D
  W  
  D  
D 6 W
  W  
  W  
W   W
  W  
  W  
W   W
  W  

Yellow is the path taken.

Blue is backtracking from a dead-end.

 The maze array can be marked with numbers where doors are passed through to indicate the path. Below, WW0W 0W1D indicates the Room(0,0) was exited through door 0 and the next Room(0,1) was entered through door 0.

One path through the above maze array, starting by being dropped into Room(0,0) and marking the order doors entered and exited by 0, 1, 2, etc. is:

WW0W 0W1D 1W22 2WW3
WW6W 65W6 W2W3 W3W4
WWWW W647 43WW W4WW
9W8W 87WW WWWW WWWW

The rightmost column (blue) in the maze reflects the backtracking from the dead-end in Room(2,3), bold print above.

Or as rooms in the path from start to finish:

0 0,0
1 0,1
2 0,2
3 1,2
4 2,2
5 2,1
6 3,1
7 3,0

Backing out of a dead-end path, such as Room(0,3) to Room(1,3) to Room(2,3), are not included in the path.

Turn in

  1. Cover sheet with your name, C455, date, and Homework 11.
  2. Listing of the algorithm. You're welcome to use another maze representation.
  3. Results for the maze above; print out any one path through the maze.
  4. Zip and upload algorithm and any related files necessary to execute along with instructions.

 

Circuit-Satisfiability Assignment

The text discusses circuit satisfiability, an important topic in NP-completeness.

The basic idea is to simulate a circuit, outputting the assignments to input variables where the circuit output is true. The text Figure 34.8 is equivalent to:

((¬x3∧ x1∧ x2)∨¬x3)∧ ((x1∨x2)∨¬x3)∧ (¬x3∧ x1∧ x2)

Both are satisfied by the assignment x1=true, x2=true, x3=false

The brute force approach would make all possible Boolean assignments to input variables, outputting the assignments where the output were true. The following would do the trick:

for x1 ∈ {false, true} do

for x2 ∈ {false, true} do

for x3 ∈ {false, true} do

if ((¬x3∧ x1∧ x2)∨¬x3)∧ ((x1∨x2)∨¬x3)∧ (¬x3∧ x1∧ x2) then print x1, x2, x3

However, backtracking can often reduce the complexity which in above algorithm is Θ(2n).

  Assignment

1) Implement a backtracking algorithm to print all assignments satisfying the expression:

(w∨¬x∨¬z)∧ (¬x∨y)∧ (¬y∨¬z)∧ (¬w∨¬x∨y∨z)∧ (¬v∨¬w∨¬x∨y∨z)∧ (v∨w)∧ (¬v∨w∨z)

Not is ¬   Or is ∨   And is ∧

Follow backtracking examples from the notes discussed in class as follows:

Generic Backtracking Algorithm

Backtrack( X[1..i] )
--  pre: X[1..i] specifies first i components of a solution
--  post: Solution X[1..i]
--           Si+1 is solution i+1

  1. if X[1..i] is a solution then print X[1..i]

  2. else

  3.    for each x ∈ Si+1 do

  4.       if x is consistent with X[1..i] and valid option for problem constraints then

  5.            X[i+1] ← x

  6.            print(X[1..i] -> X[1..i+1]);

  7.            Backtrack( X[1..i+1] )

2) Draw the recursion tree similar to below.

To assist in drawing the recursion tree, Line 6 prints the partial solution at each step. For example, assuming X[1..i] assignments of {true, false} and X[1..i+1] assignments of {true,false,true}, Line 6 would print:

{true, false} -> {true,false,true}

Using 0=false and 1=true, the tree explored for ((¬x3∧ x1∧ x2)∨¬x3) ∧ ((x1∨x2)∨¬x3) ∧ (¬x3∧¬x2) is below.

When the circuit is determined to be not satisfiable (e.g. cannot be true), the algorithm backtracks. For example, the 000 represents exploring (¬x3∧¬x2) where x1 is not a factor but x2=0 and x3=0 is required. There are two complete solutions listed below. No partial solutions are displayed and backtracked over that do not lead to a complete solution because none exist, for example, x1=0 is part of a complete solution and is displayed while x1=0 and x2=1 is not part of a solution so is not displayed.

Note: To draw many of the recursion trees presented in class, I use a graphics program named dot or Graphviz, which is freely available. The program, backtracking in this case, while generating the recursion tree, prints the corresponding space as graphics commands to a file from which dot generates the graphics.

The dot drawing file for the above recursion tree is:

digraph g {
  rank=source;
  compound=true;
  size="12,4";
  n [shape=none label="" fontsize=48 ];
  n -> n0 [weight=12 label="x1=0" color=red fontsize=48 ];
  n0 [shape=none label="0" fontsize=48 ];
  n0 -> n01 [weight=12 label="x2=1" color=red fontsize=48 ];
  n01 [shape=none label="01" fontsize=48 ];
  n -> n1 [weight=12 label="x1=1" color=red fontsize=48 ];
  n1 [shape=none label="1" fontsize=48 ];
  n1 -> n11 [weight=12 label="x2=1" color=red fontsize=48 ];
  n11 [shape=none label="11" fontsize=48 ];
  n11 -> n110 [weight=12 label="x3=0" color=red fontsize=48 ];
  n110 [shape=none label="110" fontsize=48 ];
}

This beats drawing the tree by hand and is a good debugging tool, allowing you to quickly visualize the recursion generated.

Turn in

  1. Cover sheet with your name, C455, date, and Homework 11.
  2. Listing of the algorithm.
  3. All variable assignments satisfying the expression:

    (w∨¬x∨¬z)∧ (¬x∨y)∧ (¬y∨¬z)∧ (¬w∨¬x∨y∨z)∧ (¬v∨¬w∨¬x∨y∨z)∧ (v∨w)∧ (¬v∨w∨z)

     

  4. The tree explored by the algorithm showing partial solutions.
  5. Zip and upload algorithm and any related files necessary to execute along with instructions.