N-Queens Problem The aim of this problem is to place N queens on a chessboard of...

Transcribed Image Text:

N-Queens Problem The aim of this problem is to place N queens on a chessboard of size NxN in an order where no queen may attack another. A queen can attack other queens either diagonally, or in same row or column (See Figure-1). Q1 Figure 1: Example of 8-queens Q7 Q6 Q4 Q2 Q5 Q3 80 Q8 Suggested formulation (optional): State: Arrangement of all the N queens one per column. This can be done using a vector of size N) Initial state: All queens are listed in the first row. Actions: Select a queen that is under attack and move it to another location where it is safe/safer from others. Each action costs 1 unit. Goal State: Arrangement of all the N queens one per column with no queen attacking any other queen. Program description: You need to write a program to implement and solve the N-queens problem. Input: N (integer) Strategy (BFS, IDS, or A*) Process: Solve the N-queens problem using each of the given strategies. Output: For each strategy, your program is expected to produce the following items) 1- Total number of steps to reach a solution (solution cost) 2- Total number of nodes generated before reaching a solution (search cost) 3- Maximum size of the frienge 4- Bonus point: Visulaization (Simulation of the solutions, queens movments throughout the solution path) N-Queens Problem The aim of this problem is to place N queens on a chessboard of size NxN in an order where no queen may attack another. A queen can attack other queens either diagonally, or in same row or column (See Figure-1). Q1 Figure 1: Example of 8-queens Q7 Q6 Q4 Q2 Q5 Q3 80 Q8 Suggested formulation (optional): State: Arrangement of all the N queens one per column. This can be done using a vector of size N) Initial state: All queens are listed in the first row. Actions: Select a queen that is under attack and move it to another location where it is safe/safer from others. Each action costs 1 unit. Goal State: Arrangement of all the N queens one per column with no queen attacking any other queen. Program description: You need to write a program to implement and solve the N-queens problem. Input: N (integer) Strategy (BFS, IDS, or A*) Process: Solve the N-queens problem using each of the given strategies. Output: For each strategy, your program is expected to produce the following items) 1- Total number of steps to reach a solution (solution cost) 2- Total number of nodes generated before reaching a solution (search cost) 3- Maximum size of the frienge 4- Bonus point: Visulaization (Simulation of the solutions, queens movments throughout the solution path)