Bitmasking for N-Queen Backtracking

#1

Hi, i really enjoyed the informative webinar for optimizing backtracking algo.
while the final bitmasking code looks elegant and concise i am left with a few pressing doubts:

  1. If we are starting with all masks as 0, where exactlty in the code are we assigning the first queen. i got the entire mask and bit logic but i cannot figure out where the first queen is assigned and how.

  2. where is the backtracking line?? The unplacing of the queen and retracting of our steps?? the example demonstrated took no backtrack steps… so that is another issue i cannot figure out…

Thanks for your help!

#2

@ilovetocode
The crux of this question is the concept that the difference of all points(i, j) in a left diagonal remain constant and the sum of points(i, j) in a right diagonal remains constant. The step where you u set the left, top and right bitsets to 1 is the step where a queen has been placed and when we again set the left, right and top bitsets to zero is the backtracking step.

Please mark the query as resolved in case I was able to resolve your doubt.

#3

Hi Kshitij!
Thanks for your quick reply, however, you are explaining the bitset approach, my query is regarding the bitMASK* approach. The one where we use the rowMask and the DONE global variable.
in the bitmaksing approach, the recursive call is clear, the entire construction of the mask id clear, i just dont see the backtracking or the assignment steps clearly like its shown in the bitsetting approach (like you said, setting to 1 and setting back to 0 steps).
Thanks Again for your help!