Warm up: The recursion
1) implement the function calculating the factorial (two version of functions recursive and iterative, see the lecture)
2) implement the function calculating Fibonacci sequence (again, two versions: recursive and iterative)
The main exercise: The backtracking
Implement: Eight queens puzzle
Write the program which will find all possible configurations (and count them) of the queens on chess board (8x8).
The output should be:
Configuration: 1
| |
A |
B |
C |
D |
E |
F |
G |
H |
| 1 |
X |
|
|
|
|
|
|
|
| 2 |
|
|
X |
|
|
|
|
|
| 3 |
|
|
|
|
X |
|
|
|
| 4 |
|
|
|
|
|
|
|
|
| 5 |
|
|
|
|
|
|
|
|
| 6 |
|
|
|
|
|
|
|
|
| 7 |
|
|
|
|
|
|
|
|
| 8 |
|
|
|
|
|
|
|
|
Configuration: 2
...
Total number of possible configurations: ??
3) Repeat/homework
On an 8×8 board one can place 32 knights, or 14 bishops, 16 kings or 8 rooks.
Using the same strategy write the program which will answer the question: "In how many ways can 8 rooks be placed on an 8×8 chessboard so that neither of them attacks the other?"