This can be solved using using backtracking algorithm . It is almost same like sudoku solving . Every row in NxN matrix should be filled with queen and it should satisfy the following condition .One Queen should not interfere another queen in the matrix .
Code: (in C)
In the above code checkColumn checks the column to find whether the column already has a queen or not and checkDiagonal is used to check the diagonal elements and it is not implemented here.
Please let me know if u have any questions ..
5 comments:
Not quite sure about line that is resetting the value back to 0 - why is that necessary?
Thats how the backtracking works . When you put a queen in a place and if its not suitable you change its position . To change its position i am setting it to 0.
Thanks for the response.
Sorry, I may be missing something very obvious, but I am failing to understand how you determine if its "not suitable"??
Consider 4x4 matrix . when you start filling it
step 1
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
step 2
1 0 0 0
0 0 1 0
0 0 0 0
0 0 0 0
Now you cant fill it in 3rd row (you cannot place a queen in third row) .so you need to backtrack and change the second row .
step 3
1 0 0 0
0 0 0 1
0 0 0 0
0 0 0 0
That's why i am resetting the value to 0 to use the next position .This continues until you get an answer
e.g
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
http://www.slideshare.net/Tech_MX/8-queens-problem-using-back-tracking
it is clearly explained here . see the 11th slide for graphical representation
Post a Comment