8 queens problem Solve the 8 queens problem by gluing k rand

8 queens problem

Solve the 8 queens problem by gluing k random queens to the board and placing the other 8-k queens using backtracking. What value for k gives the best result (on avereage)? How does the running time compare to the traditional backtracking algorithm?

Solution

}

Running time : If we donot use backtracking, we have seen solu­tion matrix, at every row we have only one entry as 1 and rest of the entries are 0. Solu­tion matrix takes O(N²) space. We can reduce it to O(N). We will solve it by tak­ing one dimen­sional array and con­sider solution[1] = 2 as “Queen at 1st row is placed at 2nd column.

result[i]=j means queen at i-th row is placed at j-th column.

Check if Queens placed at (x1, y1) and (x2,y2) are safe