FHTW Berlin Fachbereich 4 Internationale Medieninformatik Info2: Informatik II Sommersemester 2006

This is one of the standard exercises that all computer science students have to solve at least once in their lifetimes! If you have never played chess, find someone who does or find a book and look up how a Queen moves and threatens in chess. Find out what a chess board looks like. Define a matrix (two-dimensional array) of integers in Java. Write a method to put a -1 in every cell of the matrix. You do have a working matrix class, don't you? That would make this really trivial! Given two cells in a matrix, (r1, c1) and (r2, c2). How can you determine if       1. the cells are in the same row?       2. the cells are in the same column?       3. the cells are in the same ascending diagonal?       4. the cells are in the same descending diagonal? Implement the recursive solution to the Towers of Hanoi so that you can see how recursion works. Use the debugger at the start of class to investigate how the recursion works!

Lab exercises

1. Our goal is to write a program to determine if eight queens can be placed on an 8 x 8 chess board without them threatening each other! Start by deciding how to represent a chess board with a data structure. Don't worry about the colors of the board yet. Write a Chessboard class! What methods will you need?
2. Write a method for determining if the current board state contains a queen that is threatening another one. What is the complexity of your method in terms of N, the number of rows on the board? If your algorithm is worse than linear, you might want to look for something better.
3. We speak of "backtracking" when we go back to a previous state and try a different branch. Use some coins on a paper chess board to figure out what to do when you reach a state in which one queen is threatened by another. There are iterative, recursive, and random solutions to this problem. Try and implement a recursive solution!
4. Now implement a search routine that looks for a state in which the queens don't threaten each other. If there is a solution, print it to System.out. If there is more than one solution, print them as well. What is the complexity of your algorithm? Does your program work for 10 queens on a 10 x 10 board? 13 on a 13 x 13 board?
5. (For the bored) Design a Chessboard GUI with a queen figure. Output the result of the program using your Chessboard GUI.
6. (For the really bored) Animate the search by showing the positions as they are tested, illuminating the threats. How long does it take to show such an attempt? How long will the program need for the exhaustive search?
7. (If you are already finished with all of this and have time on your hands) How many knights can be put on an 8 x 8 board without threatening each other?
8. (For the mathematically curious) For which N is it possible to put N queens on an N x N board? Example: 2 queens cannot be placed on a 2 x 2 board, 3 cannot be placed on a 3 x 3 board. But 4 queens can be placed on a  4 x 4 board, for example at B1, D2, A3, C4. Can you prove this?