代写CS206、代做C/C++编程、代写C/C++语言、代做N chess queens

日期：2018-11-20 09:11

CS206 Project 1

Assign 2018-11-07    Due 2018-11-26

N queen problem

Problem description: The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. The queen on chessboard can attack any square in any of the eight directions (left, right, up, down, and the four diagonals).

For example, following is a solution for the 4 Queen problem.

0  0  1  0

1  0  0  0

0  0  0  1

0  1  0  0

Solution algorithm:

1.Initialize a blank chessboard as N*N matrix. The matrix must be allocated dynamically .

2.Write a function to solve the N queen problem.

3.Write a function to judge whether all N queens are safe on the chessboard. If all N queens are safe, then return true or 1. Otherwise, return false or 0;

4.Print the solutions.

Submit:

1.Files to submit: CS206_studentID_name(CN).h and CS206_studentID_name(CN).cpp

2.The following class definition is included in your header file. You should complete the methods of the class in the .cpp file.

1.class NQueens{

2.private:

3. int **chessboard;

4.int N;

5.public:

6. NQueens(int n);

7 int check_chessboard(int **board,const int n);

8. void print_chessboard();

9.// int isSafe(int row, int col);

10. void solve_NQ(int row,int col);

11.};

3.The description of the class NQueens as followed:

a)The member variable“chessboard” denotes an N*N matrix as a chessboard.

b)The “chessboard” should be dynamically allocated in the constructor method “NQueens(int n)”.

c)The method “solve_NQ(int row, int col)” is to solve the N Queen problem starting from the position (row, col). We always suppose the starting position is (0,0). The solution(s) should be outputted.

d)The method “int check_chessboard(int **board, const int n)” is used to check all the queens on the n*n board are safe. If they are all safe, return 1. Otherwise, return 0. You must use the stack for this method.

e)The method “print_chessboard()” is to print the chessboard (N*N matirx).

If necessary, you can add any variable or methods into the class.

4.Score

a)The constructor method can dynamically generate an N*N chessboard (matrix).  The values of all cells are 0 initially. (10%)

CAUTION: If the matrix is a static 2-D array, the score will be marked 0 !

b)The method “print_chessboard()” is to print the chessboard correctly.(10%)

c)The method “solve_NQ(int row, int col)” can get all the solutions about N queen problem correctly.(40%)

d)Given a chessboard, “int check_chessboard(int **board,const int n)” can check whether it is a solution of the n-queen problem or not.(40%)

5.Submit by email:

a)Email subject : CS206_studentID_studentName(CN).

b)Send email to TA after attaching your .h and .cpp files.

c)TA’s (Li Chun) email address: 2351583604@qq.com

6.Due date: 2018-11-26

a)No acceptance after 5 days.

b)10% penalty per day up to 5 days.

7.The following file can be used to test your code.

#include <iostream>

#include “yourheadfile.h”

1.int main(){

2.//construct 2 chessbords, a is 4*4, b is 8*8

3. NQueens a(4);

4.NQueens b(8);

5.

6 //print a,b chessboard. Now, they are blank.

7. //Each cell must be 0

8. cout << "a chessboard is:"<<endl;

9.a.print_chessboard();

10. cout<< "b chessboard is :"<<endl;

11. b.print_chessboard();

12.

13. // output the solutions of 4*4, 8*8

14. cout << "4 queens solutions are:" <<endl;

15. a.solve_NQ(0,0);

16. cout << "8 queens solutions are:" << endl;

17. b.solve_NQ(0,0);

18

19. // given a board on which all queens are placed

20. int first[4][4] = {{0,0,1,0},{1,0,0,0},{0,0,0,1},{0,1,0,0}};

21. int second[4][4] = {{0,0,0,0},{1,0,0,0},{0,0,0,1},{0,1,0,0}};

22. int **ft = new int* [4];

23. int **se = new int* [4];

24. for (int i=0; i<4; i++) {

25. ft[i] = new int [4];

26. se[i] = new int [4];

27.

28. }

29.

30. for (int i=0; i<4; i++) {

31.for (int j=0; j<4; j++) {

32. ft[i][j] = first[i][j];

33.se[i][j] = second[i][j];

34. }

35. }

36.

37.// check whether it is a solution of N queen problem

38. // if it is return 1, otherwise 0

39.cout << endl;

40. cout << "first board is a solution:\t";

41. cout << a.check_chessboard(ft,4) <<endl;

42. cout << "second board is a solution:\t";

43. cout << a.check_chessboard(se,4) <<endl;

44.

45.

46.return 0;

47.}