An NP-complete problem is a fascinating kind of problem because till now no one has discovered the polynomial-time algorithm to solve it and also no one has proved that no polynomial-time algorithm can exist for any NP-complete problem. It is an open research problem since it was first posed in 1971 to prove P#NP. The NxN Queens problem can be summarized as follows: putting N chess queens on an N×N chessboard such that none of them is able to attack any other queen using the standard chess queen's moves (row-column- diagonal). Thus, a solution requires that no two queens share the same row, column, or diagonal. Solutions exist only for N = 1 or N > 4. Use the given function below to test whether a queen is attacked by another or not. You are not allowed to use any other code to check if a queen is safe. Implement a backtracking solution for the algorithm in Java that finds all possible solutions for N queens and measure the execution time it takes for N=4 to 12 and compare them according to the time and the number of solutions. Discuss whether the timing results correspond to any time complexity model. You should implement a recursive method, public static void solve(int k), that takes only 1 integer k (pass the value 0 which is the first row of the board). The base condition of the recursive method is when k==N. When a queen is positioned in a row and it is safe then you call the method with the next column (k+1). Also use a static counter for the number of solutions. The output should be similar to the following and time should be in milliseconds (adherence to the output is required and penalty is incurred if different output is given). Store all times and the number of solutions for all values of N in a table and use in your justification in the discussion. Solution 1: 1 3/0 2 //These are the position of N safe Queens (don't print this comment) Solution 2: 2 0 3 1 * Q * Elapsed Time = 0.443447 ms private static int count=1; private static int N = 4; private static int position []=new int [N]; // to store the positions of the safe queens public static boolean is_Queen_Safe (int queen, int row) { for (int i=0; i
An NP-complete problem is a fascinating kind of problem because till now no one has discovered the polynomial-time algorithm to solve it and also no one has proved that no polynomial-time algorithm can exist for any NP-complete problem. It is an open research problem since it was first posed in 1971 to prove P#NP. The NxN Queens problem can be summarized as follows: putting N chess queens on an N×N chessboard such that none of them is able to attack any other queen using the standard chess queen's moves (row-column- diagonal). Thus, a solution requires that no two queens share the same row, column, or diagonal. Solutions exist only for N = 1 or N > 4. Use the given function below to test whether a queen is attacked by another or not. You are not allowed to use any other code to check if a queen is safe. Implement a backtracking solution for the algorithm in Java that finds all possible solutions for N queens and measure the execution time it takes for N=4 to 12 and compare them according to the time and the number of solutions. Discuss whether the timing results correspond to any time complexity model. You should implement a recursive method, public static void solve(int k), that takes only 1 integer k (pass the value 0 which is the first row of the board). The base condition of the recursive method is when k==N. When a queen is positioned in a row and it is safe then you call the method with the next column (k+1). Also use a static counter for the number of solutions. The output should be similar to the following and time should be in milliseconds (adherence to the output is required and penalty is incurred if different output is given). Store all times and the number of solutions for all values of N in a table and use in your justification in the discussion. Solution 1: 1 3/0 2 //These are the position of N safe Queens (don't print this comment) Solution 2: 2 0 3 1 * Q * Elapsed Time = 0.443447 ms private static int count=1; private static int N = 4; private static int position []=new int [N]; // to store the positions of the safe queens public static boolean is_Queen_Safe (int queen, int row) { for (int i=0; i
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
![An NP-complete problem is a fascinating kind of problem because till now no one has discovered the
polynomial-time algorithm to solve it and also no one has proved that no polynomial-time algorithm can exist
for any NP-complete problem. It is an open research problem since it was first posed in 1971 to prove P#NP.
The NxN Queens problem can be summarized as follows: putting N chess queens on an N×N chessboard such
that none of them is able to attack any other queen using the standard chess queen's moves (row-column-
diagonal). Thus, a solution requires that no two queens share the same row, column, or diagonal. Solutions exist
only for N = 1 or N 2 4. Use the given function below to test whether a queen is attacked by another or not. You
are not allowed to use any other code to check if a queen is safe.
Implement a backtracking solution for the algorithm in Java that finds all possible solutions for N queens and
measure the execution time it takes for N=4 to 12 and compare them according to the time and the number of
solutions. Discuss whether the timing results correspond to any time complexity model. You should
implement a recursive method, public static void solve(int k), that takes only 1 integer k (pass the value 0
which is the first row of the board). The base condition of the recursive method is when k==N. When a queen is
positioned in a row and it is safe then you call the method with the next column (k+1). Also use a static counter
for the number of solutions.
The output should be similar to the following and time should be in milliseconds (adherence to the output is
required and penalty is ineurred if different output is given). Store all times and the number of solutions for all
values of N in a table and use in your justification in the discussion.
Solution 1: 1 3/0 2 //These are the position of N safe Queens (don't print this comment)
* Q
Q **
* * O *
Solution 2: 2 0 3 1
Elapsed Time = 0.443447 ms
private static int count=1;
private static int N = 4;
private static int position[]=new int [N]; // to store the positions of the safe queens
public static boolean is_Queen_Safe (int queen, int row) {
for (int i=0; i<queen; i++){ // Check all queens before this one
int other row = position[i]; // Get another queen's in current row
if (other row == row || // Check if same row
other row == row - (queen - i) || // Same diagonal
other row == row
return false;
(queen - i))
// Same diagonal
return true;
public static void solve (int k) {//part of the recursive solve method use without any change
if (k == N) { // Base condition - We placed N-1 queens (0 included), problem solved!
// Solution found print it
} else {
for (int i = 0; i < N; i++) { // generate ALL combinations
you only need to add the printing code here
if (is Queen Safe (k, i)){ // check if we can put queen (the k-th one) in a row
position [k] = i; // store queen position into array
solve (k + 1); // place next queen](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fd44fa7f7-aa0f-4d28-9368-561deeaf6767%2Fd93cf034-ac35-4a9c-8e31-1c429db505b9%2Fgby0wpk_processed.jpeg&w=3840&q=75)
Transcribed Image Text:An NP-complete problem is a fascinating kind of problem because till now no one has discovered the
polynomial-time algorithm to solve it and also no one has proved that no polynomial-time algorithm can exist
for any NP-complete problem. It is an open research problem since it was first posed in 1971 to prove P#NP.
The NxN Queens problem can be summarized as follows: putting N chess queens on an N×N chessboard such
that none of them is able to attack any other queen using the standard chess queen's moves (row-column-
diagonal). Thus, a solution requires that no two queens share the same row, column, or diagonal. Solutions exist
only for N = 1 or N 2 4. Use the given function below to test whether a queen is attacked by another or not. You
are not allowed to use any other code to check if a queen is safe.
Implement a backtracking solution for the algorithm in Java that finds all possible solutions for N queens and
measure the execution time it takes for N=4 to 12 and compare them according to the time and the number of
solutions. Discuss whether the timing results correspond to any time complexity model. You should
implement a recursive method, public static void solve(int k), that takes only 1 integer k (pass the value 0
which is the first row of the board). The base condition of the recursive method is when k==N. When a queen is
positioned in a row and it is safe then you call the method with the next column (k+1). Also use a static counter
for the number of solutions.
The output should be similar to the following and time should be in milliseconds (adherence to the output is
required and penalty is ineurred if different output is given). Store all times and the number of solutions for all
values of N in a table and use in your justification in the discussion.
Solution 1: 1 3/0 2 //These are the position of N safe Queens (don't print this comment)
* Q
Q **
* * O *
Solution 2: 2 0 3 1
Elapsed Time = 0.443447 ms
private static int count=1;
private static int N = 4;
private static int position[]=new int [N]; // to store the positions of the safe queens
public static boolean is_Queen_Safe (int queen, int row) {
for (int i=0; i<queen; i++){ // Check all queens before this one
int other row = position[i]; // Get another queen's in current row
if (other row == row || // Check if same row
other row == row - (queen - i) || // Same diagonal
other row == row
return false;
(queen - i))
// Same diagonal
return true;
public static void solve (int k) {//part of the recursive solve method use without any change
if (k == N) { // Base condition - We placed N-1 queens (0 included), problem solved!
// Solution found print it
} else {
for (int i = 0; i < N; i++) { // generate ALL combinations
you only need to add the printing code here
if (is Queen Safe (k, i)){ // check if we can put queen (the k-th one) in a row
position [k] = i; // store queen position into array
solve (k + 1); // place next queen
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 3 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY