0 votes

Count all the conflicts in a given n-Queen state.  It is easy to do in O(n2) time.  Give an O(n) time algorithm to count all conflicts.

in Informed Search by AlgoMeister (1.6k points)

1 Answer

+2 votes
 
Best answer
We can count line by line to determine how many queens in a line.

For example, we take the horizontal direction as row by row from top to bottom.

In each row, we count how many queens in this row and get the number of conflicts= ((number of queens-1)+1)*(number of queens-1)/2.

There are almost n line in each direction and there is 4 direction.

So cost=4*n=O(n).
by Active (300 points)
selected by
Take one row for example. If the length of the row is n, then you have to check each position in the row to confirm if there is a queen? Isn't it still be O(n)?
Then for each row, column and diagonal, doesn't it still cost O(n^2)?
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, so if there is no queen and we do nothing. Only when we meet the queen position we take sum. So, for each direction we only take n sum function, even though we refresh sum to 0 at the start of each line.
for (int i = 0; i < size; i++)
            row[col[i]]++;
for (int i = 0; i <size; i++)
            if(col[i]<=i)
                diagonal[0][i-col[i]]++;
            else
                diagonal[0][size+col[i]-i]++;
for (int i = 0; i < size; i++)
        diagonal[1][col[i]+i]++;

Related questions

0 votes
3 answers
0 votes
6 answers
+3 votes
1 answer
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...