Comparison Between the Backtracking algorithm and the Greedy Algorithm to solve

Question

Comparison Between the Backtracking algorithm and the Greedy Algorithm to solve the n-Queens Problem IMPORTANT NOTE You can consult books in the library to learn more about the backtracking and the greedy algorithms. There are many books and other resources available. You should implement the backtracking algorithm to solve the problem and show for which value for n you can get a solution. Record also the time. You should then implement the greedy algorithm and give also the value for n (the number of queens) and the time. Programming I'd prefer not to place restrictions on the programming language. Most languages should have access to a decent sorting library, but be sure to look into this before you commit to an approach.

Explanation / Answer

Backtracking Algorithm:

As per Backtracking Algorithm place queens one by one in different columns, starts from the leftmost column. Suppose When we place a queen in a column, then check for clashes with already placed. If we find a row for which there is no clash,mark this row and column as part of the solution. If we do not then we backtrack and return false.

Algorithem
1) Initially start in the leftmost column
2) If all queens are placed
return true
3) Visit all rows in the current column. Do following for every visited row.
a) If the queen can be placed safely in this row then mark this as part of the solution and recursively check if placing queen here leads to a solution.
b) If placing queen in [row, column] leads to a solution then return
true.
c) If placing queen doesn't lead to a solution then umark this [row,
column] and go to step (a) to visit other rows.
3) If all rows have been visited and nothing worked, return false to
backtracking.

Greedy search algorithm:

The main theme behind Greedy search algorithm is to find a solution by placing the queens in the best possible spots. That means it may also place the queens on non-valid locations. The main theme is Queens need to be initialized before moved and ensured that each line has just one. By Adjusting the starting positions may be done randomly. This may slows down the execution but ensures that a solution will be found.

Algorithm steps:

1. Initialize queens starting positions. We may place the queens randomly but no more than one queen may occupie a line because if there are no remaining rows / columns to stop causes to Failure to find a solution.
2. Save the attacked positions of the queens
3.For each queen from the first line to the last line do steps 4 to 6:
4. Find the appropriate spot in the line.
5.Then After Move the queen in that spot.
6. Save the attacked positions.
7. After that Check if there are remaining attacks.Suppose if there are not the algorithm has found a solution
8.Then increase a counter by one. If the counter is greater than a predifined value go to step 1.
9.Go to step 3

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.