$ mkdir ~/cs170/labs/lab24 $ cd ~/cs170/labs/lab24
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.
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.
. 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.>>> 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
Submit to inquire, under the link for Pop Quiz #2.
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
, and how it operates.Many people consider the
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 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?
Your job is to write a program
that
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
.START ON PAPER! Try
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.
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.
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.
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.