$ mkdir ~/cs170/labs/lab26 $ cd ~/cs170/labs/lab26
Today, we go over the coding activities from Test #2. These were the problems that a lot of people listed as unfair. I hear your complaints, and obviously I feel like these questions were fair. So as we go over these problems today, let's have a discussion about why the questions were unfair in your eyes.
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 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?
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.
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.
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.
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
lab26 directory. To create a tar
file, execute the following commands:
cd ~/cs170/labs tar czvf lab26.tgz lab26/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
26. Make sure you include a header
listing the authors of the file.