FHTW Berlin
Fachbereich 4
Internationale Medieninformatik
PROG2: Programmierung II
Sommersemester 2003
Exercise 5 : Eight Queens
Finger exercises
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?
Lab exercises
Our goal is to write a program to determine if 8 queens can be placed on
an 8 x 8 chess board without 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 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.
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.
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?
(For the bored) Design a Chessboard GUI with a queen figure. Output the
result of the program using your Chessboard GUI.
(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?
(If you are already finished with all of this and have time on your hands)
How many knights can be put on an 8x8 board without threatening each other?
(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?
Letzte Änderung: [an error occurred while processing this directive]