|
|
Before you do anything, please read the entire assignment carefully. It contains many suggestions which can save you a lot of struggle later on.
You should print out hard copy of your code and any example outputs, and either turn them in at lecture or in the TA's mailbox at Sudikoff by class time on Wed. Nov. 4, 2009. Late assignments will be strongly penalized, so please start early.
For this assignment, you are to work alone. You may not share code with anyone else, nor may you look at anyone else's code.
For CS 8 programming assignments, such as this one, you must turn in a hard copy listing of any procedures you wrote yourself, or modified from the example code provided with the assignment. You must also turn in example output for each section of the problem set, as applicable.
You should not turn in printouts of any code we provided you which you did not make any changes to, and please be sure to label everything carefully, so that the graders will know what they are looking at.
You must also e-mail an electronic version of your code to cs8hw@cs.dartmouth.edu with the subject "CS 8 Problem Set 4", by no later than 2:00 am on the date it is due. Please organize your code in one or more plain text files and attach them as enclosures to your message. Do not include your code directly in the body of the e-mail message! If you are sending more than one file, please make sure the files have descriptive names, and that you include comments that will let the graders know what they are looking at.
Code submitted electronically must be sent as plain text, in one or more files with the filename extension ".hs" or ".lhs" (e.g., mycode.hs). Do not send your programs as Word documents, RTF, or other "formatted" types of files.
For each part of any assignment, we require output which demonstrates that your code correctly solves the problem it is supposed to solve. If you turn in code with no output, you may receive only partial credit, or no credit, for that part of the assignment.
Some problems will give specific test cases you need to provide output for. However, even if specific test cases are not provided, and even if it is not listed under "What to Turn In" for a particular problem, you must provide some sample output that shows how your code behaves on typical inputs.
If you are unable to get your code working, please turn in whatever you do have, so that we can determine if you should receive partial credit. Please do not include output which suggests your code works if it doesn't -- however, if your code works for some of the test cases, and not for others, you should turn in whatever output you are able to generate, even if it is incorrect. You will get credit for the "Testing" part of the score, even if the tests indicate that the program is incorrect.
Output is not required to be submitted electronically, although you are welcome to do so if you wish. If you do choose to submit output electronically, put your output samples in a separate file from your code submissions. Output may be submitted in any reasonable file format, though plain text is easiest to read.
Backtracking is a method of solving a problem like Sudoku, where a number of distinct choices must be made, and earlier choices make later choices infeasible. Instead of trying all possible patterns and eliminating those that don't work, at each step all possible choices are made for the given step, and for each choice the rest of the puzzle is solved recursively. The important point is that if a given choice is not feasible (because it somehow conflicts with earlier choices), that choice should be pruned. The word comes from agriculture. The process of building all possible solutions forms a tree, where at each step there are as many branches as there are choices. Eliminating a choice eliminates not only that choice, but the entire subtree rooted at that choice. Thus early pruning lops off large subtrees of branches and leaves. Effort spent pruning usually (but not always) pays off in the end, because of the exponential growth in number of solutions considered each time a choice is made.
A famous problem that is amenible to fairly easy backtracking solutions is the 8-Queens problem. It asks you to place 8 queens on a chessboard so that no two can capture one another; that is, no two are on the same row, column, or diagonal. For a fuller explanation of this problem (with pictures) see http://en.wikipedia.org/wiki/Eight_queens_puzzle. Note - this web site has code (though not in Haskell) and links to other sites with code. Please solve this problem without looking at code from the web or any other source. I chose a fairly easy backtracking problem because you will be spending the beginning of the week preparing for your midterm, but it is one from which you can learn a lot about backtracking.
You are to solve the n-Queens problem, where n is a parameter to the solver. The
goal is to place n Queens on an n x n chessboard so no two lie on in the same
row, column, or diagonal. To do this you should write a backtracking program.
A solution to the problem should be a list, where each position represents a
column and each value represents a row. Thus the list [2,4,6,8,3,1,7,5]
represents the first solution shown on the Wikipedia page linked above. Your
program should return a list of all possible solutions. For example, when n = 6,
your program should return:
[[2,4,6,1,3,5],[3,6,2,5,1,4],[4,1,5,2,6,3],[5,3,1,6,4,2]]
You should construct the lists column by column, either left to right or right to left. One way of doing this is to pass to the call to place the kth queen a list of all valid ways to place the first k-1 queens. For each of these try all values from 1 to n for the kth queen and eliminate those that are invalid, getting a list of all valid placements of k queens. When there are no more queens to be placed your list of partial placements is a list of complete placements, so it is the solution.
Note that the four solutions to the 6-queen problem are not really
different: [[2,4,6,1,3,5],[3,6,2,5,1,4],[4,1,5,2,6,3],[5,3,1,6,4,2]]
The first and fourth are mirror images of each other left to right, as are
the second and the third. (Note that the lists are reverses of one another.)
In this part you are to take the output from part 1 and create a list of
solutions, no two of which are symmetrical. By symmetrical I mean that they
are reflections of one another along either a vertical line, a horizontal line,
or a diagonal line (either diagonal), or they are rotations of one another
by 90, 180, or 270 degrees.
Detecting reflections vertically or horizontally are easy. Detecting diagonal reflections are a bit harder. Detecting rotations is hardest. For detecting diagonals and rotations it may be easiest to convert your list of column values to a list of (row, column) pairs.
In the Sudoku program we saw in class the author mentioned the possibility of finding an entry of the Choices Matrix with a minimum number of possible choices (greater than 1) and expanding that first. The theory is that a smaller branching factor will lead to a smaller tree, and that longer lists are likely to have been pruned to much shorter lists before you finally decide to expand them. Implement this strategy and report on how it affects run time for the harder puzzles. (The easier ones are fast no matter what.)
Turn in your code for the n-Queens problem. Show test runs for all solutions and for all unique solutions for n = 3, 4, 5, 6, 7, and 8. Compute the lengths of the lists of all solutions and all unique solutions for n = 10 and 11.
If you do the extra credit, turn in the modified Sudoku code and a report on how it affected run time.
The rubric for grading can be found here.
Home Page |
Announcements |
Course Info |
Materials |
Software |
Department of Computer Science, Dartmouth College, Hanover, New Hampshire, USA
Last modified: 12-August-2009