Question

In: Computer Science

In this case study, your task is to study different search algorithms to solve the N-Queens...

In this case study, your task is to study different search algorithms to solve the N-Queens Problem which has been presented in class. We will focus on the incremental formulation in which we add a queen to any square in the leftmost empty column that is not attacked by any other queen.

Question: Using Hill Climbing (HC) algorithms, how many steps are needed to find the solution for the 12-Queens Problem? What is it? Draw on an 12x12 table. Show your steps.

Solutions

Expert Solution

The N Queen is a problem of placing N chess queens on NxN chessboard such that no 2 queens attack each other.

Algorithm :

1. Start with a random state/ configuration of the board.

2. Scan through all possible neighbours of current state and jump to the highest neighbour with highest objective value. If there's none, exit.

3. Repeat step 2 until reaching a state which is strictly higher than all neighbours. Go to step 4.

4. State is either local or global optimum.

5. Output the state and return.

Following the above algorithm, For N=12,

Output ( the 12x12 table) :

000000000010

000000010000

000010000000

010000000000

000100000000

000000100000

000000000100

000000000001

100000000000

001000000000

000001000000

000000001000

As can be seen, the 12 queens have been placed in a way such that no 2 queens are attacking each other. So, the output is correct.

Thus, it will take 12 steps to solve the 12-queens problem.

venereology answered 4 months ago
Next > < Previous

Related Solutions

In this case study, your task is to study different search algorithms to solve the N-Queens...
In this case study, your task is to study different search algorithms to solve the N-Queens Problem which has been presented in class. We will focus on the incremental formulation in which we add a queen to any square in the leftmost empty column that is not attacked by any other queen. We will compare the following algorithms: 1- Breadth-first Seatch (BFS) 2- Depth-first Search (DFS) 3- Simulated Annealing (SA) 4- Hill Climbing (HC) Question is:. Using any of the...
In this case study, your task is to study different search algorithms to solve the N-Queens...
In this case study, your task is to study different search algorithms to solve the N-Queens Problem which has been presented in class. We will focus on the incremental formulation in which we add a queen to any square in the leftmost empty column that is not attacked by any other queen. Question: Using Depth-first Search (DFS) algorithms, how many steps are needed to find the solution for the 8-Queens Problem? What is it? Draw on an 8x8 table. Show...
In this case study, your task is to study different search algorithms to solve the N-Queens...
In this case study, your task is to study different search algorithms to solve the N-Queens Problem which has been presented in class. We will focus on the incremental formulation in which we add a queen to any square in the leftmost empty column that is not attacked by any other queen. Question: Does Simulated Annealing (SA) algorithms (with 10 iterations) solve the 14-Queens Problem? What about Simulated Annealing (SA) algorithms (with 50 iterations). Show your answer.
Introduction to Algorithms - Analysis of Algorithms Solve the following recurrence relation: T(n) = T(an) +...
Introduction to Algorithms - Analysis of Algorithms Solve the following recurrence relation: T(n) = T(an) + T((1 - a)n) + n
CASE STUDY:                                         &n
CASE STUDY:                                           “THE CARPENTER” Chris is a shy, anxious-looking, 31-year old carpenter who has been hospitalized after making suicide attempt by putting his head in a plastic bag. He asks to meet with the psychiatrist in a darkened room. He is wearing a baseball cap pulled down over his forehead and partially covering his eyes. Looking down at the floor, Chris says he has no friends, has just been fired from his job, and was recently rejected by his...
Using the case study below or your own health issue with goal and objective, your task...
Using the case study below or your own health issue with goal and objective, your task is to develop three outputs and one indicator for each output, considering the means of verification and assumptions for your indicators through completing the table below Goal: Decrease the complications of Hyperglycemia Objective: To maintain the blood glucose level within normal range Output Indicators (Measure to verify to what extent the goal is fulfilled – include targets and baseline data where possible) Means of...
Module 7 showed that one way of comparing different algorithms for accomplishing the same task is...
Module 7 showed that one way of comparing different algorithms for accomplishing the same task is complexity analysis. You will recall that in complexity analysis we express the time an algorithm takes to run as a function of the size of the input, and we used the big-Oh notation. For example, if an algorithm has a complexity of O(1), then it always runs in the same amount of time, no matter what the size of the input is; if it...
There are two algorithms that perform a particular task. Algorithm 1 has a complexity function: f(n)...
There are two algorithms that perform a particular task. Algorithm 1 has a complexity function: f(n) = 5n + 50. Algorithm 2 has a complexity function g(n) = n^2 + 10g . (Show your answer) a)Which algorithm is more efficient when n = 5? b) Which algorithm is more efficient when n = 20? c) what are complexity of f(n) and g(n)
Task: Read the case study below and answer the following questions. Case Study: The Reveton Ransomware...
Task: Read the case study below and answer the following questions. Case Study: The Reveton Ransomware Attacks In August 2012, the Internet Crime Complaint Center (IC3), a partnership between the FBI and the National White Collar Crime Center, was inundated with reports of a new type of cybercrime. Victims across the United States reported that while searching the Internet, their computers locked up, and they received the following message, purportedly from the FBI: “This operating system is locked due to...
What are the different algorithms we may use to solve the 0/1 Knapsack problem? Compare and...
What are the different algorithms we may use to solve the 0/1 Knapsack problem? Compare and contrast the different methods.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT