Exercise 4 Deadline: 5 o'clock, Friday the 28th of January, 2000 (i.e. end of week 1, semester 2 (to avoid clash with 52.234)) The Nqueens problem ------------------- This is a classic problem in computer science. The problem is to place N non-attacking queens on an N by N chessboard. That is, given a chess board that has N rows and N columns we must place N queens on the chess board such that no two queens exist on the same row, same column, or same diagonal. Below we have the first solution for the 10-queens problem. An "O" represents a queen. As you see, no queen is on the same row, same column, or same diagonal. --------------------------------------- | O | | | | | | | | | | --------------------------------------- | | | O | | | | | | | | --------------------------------------- | | | | | | O | | | | | --------------------------------------- | | | | | | | | O | | | --------------------------------------- | | | | | | | | | | O | --------------------------------------- | | | | | O | | | | | | --------------------------------------- | | | | | | | | | O | | --------------------------------------- | | O | | | | | | | | | --------------------------------------- | | | | O | | | | | | | --------------------------------------- | | | | | | | O | | | | --------------------------------------- The solution above can also be represented as follows [(0,0)(1,2)(2,5)(3,7)(4,9)(5,4)(6,8)(7,1)(8,3)(9,6)] This means that the first row, row zero, has a queen on column zero, row 1 has a queen on column 2, and so on. Just to show that there is nothing "funny" below we have the solution for the 6 queens. ----------------------- | | O | | | | | ----------------------- | | | | O | | | ----------------------- | | | | | | O | ----------------------- | O | | | | | | ----------------------- | | | O | | | | ----------------------- | | | | | O | | ----------------------- [(0,1)(1,3)(2,5)(3,0)(4,2)(5,4)] What you have to do ------------------- 1. Make a directory for this exercise 2. Copy all the files given here into your directory 3. Modify Nqueens.java such that method solve() produces a solution to the n-queens problem (or show that none exists) The method solve() - delivers true if there is a solution false otherwise. - if there is a solution solve() places N queens on the 2 dimensional array board. Therefore if in the solution a queen is placed on row i, column j, board[i][j] will be true (false otherwise) 4. NOTE: there is no solution for n=2 or n=3. 5. Marking information will be given nearer the deadline 6. NOTE: you can see n-queens solutions, for 0