Re: N-queens solution

Firstly i would like to clarify that I have not read Dinesh's solution yet. Too lazy to read and C++ is not the easiest language.

I got thinking of the problem and may have a solution. I think its different cause I did not feel the need for a duplicate() or the need to set many attack conditions. Maybe the soln's might be same. And it's almost 3:30 AM so I'll just present an algo, which if different, I'll try coding later.

My basic principle is that each queen on the chess board will occupy only one row. There are 8 queens, q0, q1,.. q7 where qn will be placed in the n th row.

The methods are

[ ] getSafePositions()........//returns all safe column positions for a queen in a row
setAttackBelow()..............//set all positions below current position as unsafe
setAttackDiagonalLeft()...//set all positions diagonally left of current position as unsafe
setAttackDiagonalRight()..//set all positions diagonally right of current position as unsafe

.[ ] q0.getSafePositions()
.if [ ] == null, {reset board & continue};
.for each in [ ]
....q0.setAttack()
....[ ] q1.getSafePositions()
....for each in [ ]
.... ..
.... ..
...// and iterate for each lower row.
...// finally
.......[ ]q7.getSafePositions()
...........if [ ] != null
.............else {we have a soln}


Here q0 is the queen placed anywhere in the first row, q1 in the second row and so on. if q7 is also placed on the board, then thats a solution.

Now the other attack combinations ( up of the current queen row ) are not required as the next queen just cannot be placed there. So those above positions can be neglected for setAttack and also for getSafePositions()

So is my solution different or did I make a fool out of myself not reading Dinesh's code??

I suggest Hrishi and Mohn also try some solutions. Should we try more problems like these? We'll get a million from sites like topcoder.com.