search

jainaman224 / Algo_Ds_Notes

A comprehensive resource for learning and implementing algorithms and data structures. This repository includes detailed notes, complexity analysis, and code examples in C++, Java, Python, and more. Ideal for students, professionals, and those preparing for coding interviews.
GNU General Public License v3.0
2.24k stars 2.09k forks source link

Backtracking using Bitmasking #1597

Open shreyasrivastava936 opened 4 years ago

shreyasrivastava936 commented 4 years ago

I would like to contribute to this problem for GSSoC'20.

RiaJha02 commented 4 years ago

Hello, I would like to try this!

RiaJha02 commented 4 years ago

The N-Queen problem can be solved using backtracking and bit masking, this is an optimised approach than the normal backtracking approach. In this case, we don’t need to write a function which works in linear time for finding the correct placing of the queen in each case basically the safe place, instead we use bitsets which work in O(1) time. For rows and columns a simple array can be maintained for checking while for the diagonals, the difference between the indices will be taken into consideration for checking a safe place.

raghav-dalmia commented 4 years ago

@shreyasrivastava936 you have 2 active issues. So, I am assigning it to @RiaJha02.

RiaJha02 commented 4 years ago

@raghav-dalmia please review my Pull Request Done with the listed changes :+1: