< Back

Lecture 24 - Backtracking


As usual, create a directory to hold today's activities:

$ mkdir ~/cs170/labs/lab24 
$ cd ~/cs170/labs/lab24 

Pop Quiz!

The following problem is to be solved individually, on your computer. You may look at any old files you desire for this activity, but you may not consult any other webpages. You have 15 minutes to complete this quiz.


Missing Letters

Write a function called missing_letters(a_string), which takes a string as a parameter. Your function should return (in alphabetical order), the letters that are missing from the passed string. You can assume all of the letters are lower case in the string. There are also spaces in the string.

For this program, you should start by creating a list that contains the letters a through z. You must follow this algorithm. Alternate solutions will not be graded. Use a for loop to iterate over the letters in the string parameter. Every time you see a letter in the string, remove it from the list. Then, at the end, write a for loop to merge the letters from the list into a string.


Examples

>>> print("Missing Letters:",
          missing_letters("the quick brown fox jumps over the lazy dog"))
Missing Letters:
>>> print("Missing Letters:",
          missing_letters("the quick brown fox jumped over the lazy dog"))
Missing Letters: s

Submission

Submit to inquire, under the link for Pop Quiz #2.



Backtracking and Sudoku

Today is the day that we will begin looking at the relationship between stacks and recursion. The big relationship between them is through the class of algorithms known as backtracking. Backtracking can be thought of as a directed brute-force approach, but through the backtracking mechanism you ultimately don't end up performing a full brute-force approach. Let's take a look at how we could use recursion to perform the maze solution, and how it operates.


Lab Activity 1
Eight Queens

Many people consider the Queen in a game of chess to be the most powerful piece to own. This may be largely because of the mobility the queen piece affords. If you are unfamiliar with chess, the Queen is the only piece that can move in the four cardinal directions, as well as the four diagonals. And the Queen can move as far as she wants in any of these directions.

This mobility of the queen sparked one of the more interesting logic puzzles related to chess: On an \(8 \times 8\) sized chess board, is there a way to place 8 queens on the board such that none of the queens can "take" one another?

Details

Your job is to write a program that recursively tries to place 8 queens on an \(8 \times 8\) chess board, such that none of the queens can take one another. To accomplish this, you will write a backtracking algorithm similar to the maze traversal program covered in class.

Key things to note are that once you have placed a queen on a given column of the board, you cannot place another queen in that column. As such, you only need to try placing queens somewhere in each of the columns of the board.

For this program, you will be representing the board as an \(8 \times 8\) 2-d list. A \(0\) will represent an empty location on the board, while the string \(Q\) will represent a location which holds a Queen.

START ON PAPER! Try mechanically placing queens on the chess board on paper. Can you trace through and find a solution manually? If you can find the solution manually, you should be able to write an algorithm that will mimic what you did on paper.

Hint

  • First, it will be prudent to write a function called check_board(chess_board, row, col), which takes the current state of the chess_board and returns \(True\) only if none of the queens on the board can take the position specified by row and column. Otherwise, this function should return False.

    The most difficult part of this function is the diagonal check. Keep in mind that you do not need to check AHEAD of the current column. Since you are filling columns from left to right, you only need to check the diagonals BEHIND the column you are trying to be set.

    You need a loop to compute the diagonals. You can use a for loop if you can figure out the size of the diagonal. If not, just use a while loop. In the diagonals, you need to change the row and column indices at the same rate. To get the "upper" diagonal, you will subtract the same amount from row and column. For the "lower" diagonal, you will add to row, and subtract from column.

  • Write a recursive function called place_queen(chess_board, column), which should try to place a queen in the specified column of the chess board. Do you think this function needs to return anything?

  • Your base case for the recursion should simply be that you have successfully placed all of the queens on the board. And in this case you want to print the state of the board.

 

Challenge

The full, formal definition of the logic puzzle described above asks if it is possible to place \(N\) queens on an \(N \times N\) chessboard. If you write your program well enough, this should be a simple change to make. Try out a few different chess board sizes. Can you determine what sizes of boards have solutions? Write up your findings in comments of your file.



Submission

When you have finished, create a tar file of your lab24 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab24.tgz lab24/

To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 24. Make sure you include a header listing the authors of the file.